Matemáticas
Undergraduate Programme. Academic Year 2024/2025.
GEOMETRÍA COMPUTACIONAL - 800620
Curso Académico 2024-25
Datos Generales
- Plan de estudios: 0803 - GRADO EN MATEMÁTICAS (2009-10)
- Carácter: Optativa
- ECTS: 6.0
SINOPSIS
COMPETENCIAS
Generales
CG1 - Comprender y utilizar el lenguaje matemático. Adquirir la capacidad para enunciar proposiciones en distintos campos de la
Matemática, para construir demostraciones y para transmitir los conocimientos matemáticos adquiridos.
CG3 - Asimilar la definición de un nuevo objeto matemático, en términos de otros ya conocidos, y ser capaz de utilizar este objeto
en diferentes contextos.
CG4 - Saber abstraer las propiedades estructurales (de objetos matemáticos, de la realidad observada, y de otros ámbitos)
distinguiéndolas de aquellas puramente ocasionales y poder comprobarlas con demostraciones o refutarlas con contraejemplos, así
como identificar errores en razonamientos incorrectos.
Matemática, para construir demostraciones y para transmitir los conocimientos matemáticos adquiridos.
CG3 - Asimilar la definición de un nuevo objeto matemático, en términos de otros ya conocidos, y ser capaz de utilizar este objeto
en diferentes contextos.
CG4 - Saber abstraer las propiedades estructurales (de objetos matemáticos, de la realidad observada, y de otros ámbitos)
distinguiéndolas de aquellas puramente ocasionales y poder comprobarlas con demostraciones o refutarlas con contraejemplos, así
como identificar errores en razonamientos incorrectos.
Transversales
CT4 - Poder transmitir información, ideas, problemas y soluciones a un público tanto especializado como no.
Específicas
CE5 - Desarrollar programas que resuelvan problemas matemáticos utilizando para cada caso el entorno computacional adecuado.
Otras
- Comprender los conceptos geométricos subyacentes a los algoritmos más comunes en Geometría computacional. (CG1, CG3)
- Implementar algunos algoritmos, decidiendo el más apropiado según su eficiencia y las posibles restricciones adicionales de cálculo o almacenamiento. (CG4,
CE5)
- Ser capaz de usar métodos geométricos para modificar los algoritmos, adaptándolos a problemas similares o hipótesis adicionales. (CG1, CG3, CE5)
- Implementar algunos algoritmos, decidiendo el más apropiado según su eficiencia y las posibles restricciones adicionales de cálculo o almacenamiento. (CG4,
CE5)
- Ser capaz de usar métodos geométricos para modificar los algoritmos, adaptándolos a problemas similares o hipótesis adicionales. (CG1, CG3, CE5)
ACTIVIDADES DOCENTES
Clases teóricas
Exposición del contenido teórico del curso.
Clases prácticas
Resolución de ejercicios relativos al contenido teórico.
Laboratorios
Implementación y verificación de algoritmos por parte de cada estudiante.
Presentaciones
Si el desarrollo del curso lo permite, presentación en el aula proyectos avanzados elaborados individualmente o en grupo.
Presenciales
6
Semestre
8
Breve descriptor:
Introducción a la geometría computacional. Se estudiarán problemas geométricos discretos desde el punto de vista computacional y su resolución algorítmica. Se pondrá énfasis en la implementación y estudio de la eficiencia de dichos algoritmos.
Requisitos
No hay requisitos previos, aunque es recomendable poseer nociones básicas de algoritmia.
Objetivos
Aprender algoritmos que permiten resolver problemas geométricos elementales, implementarlos y comprobar su funcionamiento. Discutir la eficiencia de los algoritmos desde un punto de vista teórico y práctico. Modelizar problemas discretos de carácter geométrico.
Contenido
Introducción a la geometría computacional. Repaso de algoritmos de ordenación y de complejidad de algoritmos.
Construcciones elementales en el plano. Intersección de familias de segmentos. Algoritmo de barrido (sweep line). Intersección de polígonos.
Cierres convexos. Envolvente convexa de una nube de puntos. Algoritmo incremental, Graham's scan.
Triangulaciones. Problema de la galería de arte. Triangulación de polígonos. Polígonos monótonos.
Diagramas de Voronoi. Algoritmos. Triangulación de Delaunay. Dualidad.
Localización de puntos. Árboles binarios y otras estructuras de datos adaptadas.
Espacios de configuraciones. Visibilidad con obstáculos poligonales. Caminos más cortos. Desplazamiento de objetos.
Evaluación
Un requisito imprescindible para superar la asignatura será la entrega de prácticas realizada individualmente y consistente en la implementación de algoritmos tratados en el curso. La valoración de las prácticas se podrá apoyar en el seguimiento de su confección a lo largo del curso.
Se realizará un examen final y si el desarrollo del curso lo permite se podrán elaborar y presentar proyectos avanzados de forma individual o en grupo y también se podrán pedir entregas de problemas.
El reparto de pesos en la calificación final dependerá de las actividades antes citadas. La nota de prácticas y del examen final no supondrán más del 50% de la nota final (cada una). La nota de las entregas de problemas y/o del proyecto, si ha lugar, no supondrá más del 25% de la nota final. La superación de la asignatura se supedita a la entrega de prácticas.
Se realizará un examen final y si el desarrollo del curso lo permite se podrán elaborar y presentar proyectos avanzados de forma individual o en grupo y también se podrán pedir entregas de problemas.
El reparto de pesos en la calificación final dependerá de las actividades antes citadas. La nota de prácticas y del examen final no supondrán más del 50% de la nota final (cada una). La nota de las entregas de problemas y/o del proyecto, si ha lugar, no supondrá más del 25% de la nota final. La superación de la asignatura se supedita a la entrega de prácticas.
Bibliografía
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.
- S. Devadoss, J. O'Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.
- J. O'Rourke. Computational geometry in C. Cambridge University Press, 2012.
- F. Preparata, M. Shamos. Computational Geometry. An introduction. Springer, 1985
- S. Devadoss, J. O'Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.
- J. O'Rourke. Computational geometry in C. Cambridge University Press, 2012.
- F. Preparata, M. Shamos. Computational Geometry. An introduction. Springer, 1985
Otra información relevante
No se tolerará el plagio. Se podrá requerir a cada estudiante la explicación pormenorizada del código incluido en sus prácticas. En caso de que las explicaciones sean insatisfactorias, sus prácticas se descartarán y no podrá superar la asignatura.
Estructura
| Módulos | Materias |
|---|---|
| CONTENIDOS AVANZADOS DE CIENCIAS DE LA COMPUTACIÓN | GEOMETRÍA COMPUTACIONAL |
Grupos
| Clases teóricas | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| Grupo único | 20/01/2025 - 09/05/2025 | MARTES 10:00 - 11:00 | S-106 | LUIS HERNANDEZ CORBATO |
| MIÉRCOLES 11:00 - 12:00 | S-106 | LUIS HERNANDEZ CORBATO | ||
| Clases prácticas | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| Grupo único | 20/01/2025 - 09/05/2025 | MARTES 11:00 - 12:00 | S-106 | LUIS HERNANDEZ CORBATO |
| Clases en aula de informática | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| AulaInf-1 (MT-InMt) | 20/01/2025 - 09/05/2025 | MIÉRCOLES 10:00 - 11:00 | INF4 Aula de Informática | LUIS HERNANDEZ CORBATO |
| AulaInf-2 (MT) | 20/01/2025 - 09/05/2025 | MIÉRCOLES 13:00 - 14:00 | INF4 Aula de Informática | LUIS HERNANDEZ CORBATO |