Existe una gran variedad de situaciones en las que un informático se enfrenta a la necesidad de desarrollar algoritmos eficientes tanto en tiempo como en memoria. En prácticamente cualquier área de la Informática (sistemas operativos, bases de datos, telemática, inteligencia artificial, etc.) aparecen problemas que requieren un conocimiento profundo de técnicas de diseño y análisis de algoritmos, así como de las estructuras de datos apropiadas que éstos deben manejar.
En esta asignatura se profundizará en el estudio del análisis de algoritmos (eficiencia y complejidad, análisis probabilista, etc.), y en técnicas generales de diseño de algoritmos (por ejemplo, algoritmos voraces o programación dinámica, estrategias que permiten abordar grandes clases de problemas de una forma sistemática). Asimismo, también se estudiarán estructuras de datos como los árboles binarios o los montículos, y también estructuras de datos geométricas (que son más sofisticadas y están relacionadas con el campo de la geometría computacional).
Objetivos
- Afianzar conceptos relativos al análisis y diseño de algoritmos
- Reforzar conocimientos sobre estructuras de datos básicas
- Conocer las principales estructuras de datos geométricas
Temario
- Presentación de la asignatura
- Preliminares matemáticos
- Operaciones con matrices
- Eficiencia y complejidad
- Recurrencias
- Análisis probabilista
- Montículos
- Árboles binarios de búsqueda
- Programación dinámica
- Quadtrees-Octrees
- BSP Trees
- Bounding Volume Hierarchies
- Distance Fields
Bibliografía
-
"Introduction to Algorithms". Cormen, Leiserson, Rivest, y Stein. MIT, Press, 2a edición, 2001
-
"Geometric Data Structures for Computer Graphics". Langetepe y Zachmann. A K Peters Ltd., 2006
Profesor
-
Manuel Rubio (Ampliación del Edificio de Rectorado, Despacho 2026. Tel. 914888286). Tutorías: Jueves de 19:00-21:00, y por petición.
Enlaces
Normas Apuntes- Complejidad de Algoritmos
- Recurrencias
- Resumen: Estructuras de datos Geométricas
- Ejercicios resueltos de complejidad de algoritmos
Normas de evaluación
Convocatoria de enero
- Los alumnos organizados en grupos de unas 4 personas deberán preparar una presentación de una hora de un capítulo del libro Geometric Data Structures for Computer Graphics (Langetepe), además de una memoria sobre el material presentado de unas 20 páginas de extensión. Los grupos deben de estar formados durante el primer mes de clase. Para reservar un trabajo los alumnos deben escribir un email al profesor de la asignatura indicando los nombres de los alumnos que forman el grupo, y la estructura de datos que deseen estudiar. Se atenderán peticiones según el orden de llegada. El 50% de la nota final dependerá de esta actividad. Es obligatorio asistir a las sesiones de presentación de trabajos, que se celebrarán en las últimas clases del curso.
- El 50% restante corresponde a un examen sobre todo el contenido visto en la asignatura.
- La segunda convocatoria, para los alumnos suspensos o no presentados en la convocatoria de enero, consistirá en una práctica que podrá incluir aspectos sobre todo el contenido visto en la asignatura.
Asignación de trabajos Trabajos
- Quadtrees-Octrees. [17 de diciembre] (Fransisco Javier Astiz Saldaña, José Antonio Martín Caro Gómez de Aranda, Paulo Ricardo Miranda Ferreira)
- BSP Trees. [10 de diciembre] (No asignado todavía)
- Bounding Volume Hierarchies. [17 de diciembre] (Christian Lugo Ramirez, Juan Ramón Cañizares Gómez, Vinicius de Melo Jucá, Andrés García Ochoa Gonzñalez)
- Distance Fields. [10 de diciembre] (No asignado todavía)
NOTA: Es obligatorio asistir a las presentaciones de los trabajos. Los alumnos que no hayan formado un grupo a estas alturas corren serio riesgo de suspender la asignatura, ya que su presentación sería el próximo jueves 10 de diciembre, que vale el 50% de la nota total. En el caso de no encontrar compañeros de grupo, se aceptará un trabajo individual sobre alguna estructura de datos geométrica, sin necesidad de realizar una presentación oral. En esos casos especiales, será necesario hablar con el profesor de la asignatura previamente, quien determinará el alcance del trabajo y el peso en la nota final.
