|
(2 sesiones/semana) |
Contenidos |
Evaluaciones |
| 14/3 al 18/3 (0) | Inducción. Presentación. Programa, textos y evaluación. | -- |
| 21/3 al 25/3 (1) | Unidad 1. Técnicas avanzadas de análisis y diseño.
Sesión 1. Tema 1. Análisis de algoritmos: Tipos abstractos de datos (TAD), notación TDSO, Sesión 2. notaciones estándares, funciones comunes, análisis probabilístico. |
Asignación del ejercicio 1. |
| 28/3 al 1/4 (2) | Sesión 3. análisis
amortizado: Método agregado, método del contador, método
del potencial y tablas dinámicas. Sesión 4. Tema 2. Técnicas de diseño: Introducción a las técnicas de diseño: algoritmos incrementales y recursivos |
Entrega del ejercicio 1. |
| 4/4 al 8/4 (3) | Sesión 5. Divide-y-vencerás, backtracking Sesión 6. Programación dinámica. Ejemplos. |
Corrección del ejercicio 1 (4%). Asignación del ejercicio 2. |
| 11/4 al 15/4 (4) | Sesión 7. Tema 3. Técnicas de pruebas y correctitud de algoritmos: Pruebas de corrección parcial, pruebas de parada | Asignación del ejercicio 2. |
| 18/4 al 22/4 | S E M A N A ----- S A N T A | Feriado Entrega del ejercicio 2. |
| 25/4 al 29/4 (5) | Sesión 8. pruebas de programas iterativos y recursivos, eliminación de la recursividad. | Corrección del ejercicio 2 (2%). Asignación del ejercicio 3. |
| 2/5 al 6/5 (6) | Unidad 2.
Estructuras de datos avanzadas. Sesión 9. Tema 1. Fundamentos: Estructuras lineales de datos: Pilas, colas y listas. Hashing perfecto. Colas por prioridad. Aumento de estructuras de datos y árboles de intervalos. Sesión 10. Montículos de Fibonacci: estructura y operaciones. Conjuntos disjuntos: operaciones, bosques y análisis de la unión por rango con caminos de compresión. |
Corrección del ejercicio 3 (2%). Asignación del ejercicio 4. |
| 9/5 al 13/5 (7) | Sesión 11. Tema 2. Árboles monocriterio:
Introducción. Árboles binarios de búsqueda y rojinegros. Sesión 12. Familia de árboles_B.(Marco Camejo) Htree. |
Corrección del ejercicio 4 (2%). Asignación del ejercicio 5. |
| 16/5 al 20/5 (8) | Sesión 13. Continuación tema 2. Árbol_B+ y
Htree Sesión 14. Tema 3. Árboles multicriterio: Introducción. Árbol k-d. Quadtree. Octree. Sesión 9: Estructuras lineales de datos, hashing, colas por prioridad, aumento de estructuras de datos y árboles de intervalos. |
Corrección del ejercicio 5 (3%). Asignación del ejercicio 6. Asignación del ejercicio 4. |
| 23/5 al 27/5 (9) | Sesión 15. Árbol_R. Unidad 3.
Algoritmos para grafos y algoritmos matemáticos. Sesión 16. Tema 1. Fundamentos: Definiciones, especificación, representaciones, relaciones, dígrafos, dígrafos acíclicos, búsqueda en amplitud, búsqueda en profundidad. |
Corrección del ejercicio 6 (3%). Asignación del ejercicio 7. Corrección del ejercicio 4. |
| 30/5 al 3/6 (10) | Sesión 17. Ordenamiento topológico y conectividad.
Árboles de expansión mínima: algoritmos de Kruskal y Prim. Sesión 18. Tema 2. Digrafos etiquetados: Caminos más cortos y relajación, algoritmo de Dijkstra, algoritmo de Bellman-Ford, restricciones y caminos más cortos. |
Corrección del ejercicio 7 (3%). Asignación del ejercicio 8. |
| 6/6 al 10/6 (11) | Sesión 19. Algoritmo de Floyd-Warshall y algoritmo de Johnson. Flujo máximo: Redes de flujo y método de Ford-Fulkerson. Sesión 20. Flujo máximo: Redes de flujo y método de Ford-Fulkerson. | Corrección del ejercicio 8 (3%). Asignación del ejercicio 9. |
| 13/6 al 17/6 (12) | Sesión 21. Tema 3. Matrices: Operaciones sobre matrices: Representaciones especiales de matrices, algoritmo
de Strassen, sistemas numéricos algebraicos y multiplicación de matrices. Sistemas lineales de ecuaciones,
inversión de matrices. Matrices simétricas positivas y aproximación de mínimos
cuadrados. Sesión 22. Tema 4. Algoritmos Probabilistas y Transformada Rápida de Fourier: Algoritmos probabilistas. |
Corrección del ejercicio 9 (3%). Asignación del ejercicio 10. |
| 20/6 al 24/6 (13) | Sesión 23. Transformada discreta de Fourier y transformada
rápida de Fourier. Sesión 24. Tema 5. Algoritmos de teoría de números: Nociones de teoría de números, máximo común divisor. |
Corrección del ejercicio 10 (4%). Asignación del ejercicio 11. |
| 27/6 al 1/7 (14) | Sesión 25. Aritmética modular, sistemas lineales de ecuaciones modulares,
teorema de resto chino, potencias de un entero y algoritmo RSA de criptografía. Unidad 4. Geometría Computacional. Sesión 26. Tema 1. Algoritmos sobre polígonos: Teoremas de galería de arte, Teoría de triangulación, área de polígono. |
Corrección del ejercicio 11 (4%). Asignación del ejercicio 12. |
| 4/7 al 8/7 (15) | Sesión 27. Intersección de segmentos y algoritmos de
triangulación. Tema 2. Partición de polígonos: Partición monótona,
trapeciolización. Sesión 28. Partición en montañas monótonas, triangulación de tiempo lineal, partición convexa. |
Corrección del ejercicio 12 (5%). Asignación del ejercicio 13. |
| 11/7 al 15/7 (16) | Unidad 5. Complejidad Computacional. Sesión 29. Tema 1. Problemas NP-completos: Clases P y NP, reducciones polinomiales, problemas NP, algunas pruebas de completitud NP, algoritmos no determinísticos y problemas NP duros. Sesión 30. Tema 2. Heurísticas y algoritmos de aproximación: Algoritmos heurísticos, coloreo de grafos, el problema del vendedor viajero, el problema del morral y aproximaciones a problemas NP duros. |
Corrección del ejercicio 13 (5%). Asignación del ejercicio 14. |
| 18/7 al 22/7 (17) | . | Corrección del ejercicio 14 (8%). Prueba escrita final sobre toda la materia (50%). |
al programa.....