|
Semana |
Contenidos |
Evaluaciones |
| 17/1 al 21/1 (1) |
Presentación.
Programa, textos y evaluación. Unidad 1. Técnicas avanzadas de diseño y análisis. Tema 1. Métodos básicos de diseño: algoritmos incrementales, recursivos, divide-y-vencerás. |
Corrección de la prueba diagnóstico. Asignación del ejercicio 1. |
| 24/1 al 28/1 (2) | Backtracking y programación dinámica. Ejemplos. | -- |
| 31/1 al 4/2 (3) | Inducción matemática. Tema 2. Análisis amortizado: Método agregado, método del contador y método del potencial. | Corrección del ejercicio 1 (10%). |
| 7/2 al 11/2 (4) | No clases por suspensión de actividades docentes. Tema 3. Pruebas y correctitud de algoritmos. - - - C A R N A V A L - - - | Asignación del ejercicio 2. |
| 14/2 al 18/2 (5) | Unidad 2. Algoritmos para grafos. Tema 1. Fundamentos: Definiciones, especificación, representaciones, relaciones, dígrafos, dígrafos acíclicos. No clases por suspensión de actividades docentes. |
Prueba 1 sobre la unidad 1 (20%). |
| 21/2 al 25/2 | Búsqueda en amplitud, búsqueda en profundidad, ordenamiento topológico y conectividad. Tema 2. Análisis amortizado: Método agregado, método del contador y método del potencial. | Corrección del ejercicio 2 (10%). |
| 28/2 al 4/3 (6) | Tema 2. Árboles abarcadores mínimos: Algoritmo de Prim y algoritmo de Kruskal. Tema 3. Pruebas y correctitud de algoritmos. | -- |
| 7/3 al 11/3 (7) | Tema 3. Digrafos etiquetados: Caminos más cortos y relajación, algoritmo de Dijkstra, algoritmo de Bellman-Ford. Unidad 2. Algoritmos para grafos. Tema 1. Fundamentos: Definiciones, especificación, representaciones, relaciones, dígrafos, dígrafos acíclicos. | -- |
| 14/3 al 18/3 (8) | Restricciones y caminos más cortos (programación lineal), algoritmo de Floyd-Warshall y algoritmo de Johnson. Búsqueda en amplitud | -- |
| 21/3 al 25/3 (9) | S E M A N A - S A N T A | Asueto |
| 28/3 al 1/4 (10) | Tema 4. Flujo máximo: Redes de flujo y método de Ford-Fulkerson. Unidad 3. Algoritmos matemáticos. Tema 1. Matrices: Operaciones sobre matrices, Representaciones especiales de matrices, algoritmo de Strassen. Búsqueda en profundidad. | |
| 4/4 al 8/4 (11) | 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. Ordenamiento topológico y conectividad. | Prueba 2 sobre la unidad 2 (20%). |
| 11/4 al 15/4 (12) | Tema 2. Polinomios y Transformada rápida de Fourier: Representaciones de polinomios, Transformada discreta de Fourier y transformada rápida de Fourier. Tema 2. Árboles abarcadores mínimos: Algoritmo de Prim y algoritmo de Kruskal | |
| 18/4 al 22/4 (13) | Tema 3. Algoritmos de teoría de números: Nociones de teoría de números, máximo común divisor, aritmética modular, sistemas lineales de ecuaciones modulares, teorema de resto chino, potencias de un entero y algoritmo RSA de criptografía. Tema 3. Digrafos etiquetados: Caminos más cortos y relajación, algoritmo de Dijkstra, algoritmo de Bellman-Ford. | |
| 25/4 al 29/4 (14) | Unidad 4. Completitud NP. 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. 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. Restricciones y caminos más cortos (programación lineal), algoritmo de Floyd-Warshall y algoritmo de Johnson. | |
| 2/5 al 6/5 (15) | Unidad 5. Geometría computacional. Tema 1. Teoremas de galería de arte, teoría de triangulación, área de polígono, intersección de segmentos y algoritmos de triangulación. Tema 2. Partición de polígonos: Partición monótona, trapeciolización, partición en montañas monótonas, triangulación de tiempo lineal, partición convexa. Tema 4. Flujo máximo: Redes de flujo y método de Ford-Fulkerson. | |
| 9/5 al 13/5 (16) | Tema 3. Cerco convexo: Definiciones de convexidad y de cerco convexo, algoritmos cándidos para puntos extremos, cálculo de papel de regalo, cerco rápido, algoritmo de Graham, algoritmos divide-conquista, representaciones poliedrales, algoritmos aleatorizados y cerco n-dimensionales. Unidad 5. Geometría computacional. Tema 1. Teoremas de galería de arte. | |
| 16/5 al 20/5 (17) | Tema 4. Diagramas de Voronoi: Definiciones y propiedades básicas, triangulaciones de Delaunay, algoritmos y aplicaciones. Tema 5. Disposición de líneas: Definiciones, combinatorias de disposiciones, algoritmo incremental, 3 y n dimensiones, dualidad y diagramas de Voronoi de alto orden. Ejercicios de grafos. Segundo examen escrito. | |
| 23/5 al 27/5 (18) | Tema 6. Búsqueda e intersección: Intersección segmento-segmento, intersección segmento-triángulo, pertenencia de punto en polígono, pertenencia de punto en poliedro, intersección de polígonos convexos, intersección de segmentos e intersección de polígonos no convexos. Exposiciones: Jueves 26/5/05: G. Máquez (5.1, 5.6 y 5.9), J. Fuentes (6.6), J. Justo (7.4 y 7.5) y D. Moreno (7.6 y 7.8). Viernes 27/5/05: C. Arismendi (8.4 y 9.6), R. León (9.7), (Cap. 19) y (Cap. 22) | Entrega de exposiciones |
| 30/5 al 3/6 (19) | Jueves 2/6/05: R. Márquez (10.1-10.5), Z. Chacón (10.6), L. Molina (10.7) y A. Rangel (11.1-11.4). Viernes 3/6/05: M. A. Espinoza (11.6), M. Mazzarri (11.7-11.9), C. Ramírez (12.1-12.2) y M. Rincón (12.3) | Entrega de exposiciones |
| 6/6 al 10/6 (20) | Jueves 9/6/05: N. Grimaldos (12.4), A. Hernández (12.5 y 12.6) y J. Ussher (13.1 y 13.2). Viernes 10/6/05: L. Peña (13.3-13.5), J. Torres (RSA) y (Cap. 41 TRF) | Entrega de exposiciones |
| 13/6 al 17/6 (21) | teoría de triangulación, área de polígono, intersección de segmentos y algoritmos de triangulación. | Entrega de exposiciones |
| 20/6 al 24/6 (22) | Tema 2. Partición de polígonos: Partición monótona, trapeciolización, partición en montañas monótonas, triangulación de tiempo lineal, partición convexa | Prueba 3 sobre la unidad 5 (20%). |
Ejercicios: 20% y Exámenes: 90%
Regresar...
al programa.....