Enero-Marzo 2008
|
Martes
|
Jueves
|
(1)
15 y
17 enero
|
Presentación
del curso.
Análisis y síntesis de algoritmos. Complejidad en
tiempo
de algoritmos: Complejidad exacta. Análisis PeorCaso y Caso promedio.
Ej: ordenamiento por inserción.
Notación O grande,
Omega, etc.
Algoritmos eficientes. Problemas que se pueden resolver
eficientemente.
entrega enunciado
proyecto 1 (15%)
|
Reducción de problemas.
Ejemplos: Cálculo de caminos mínimos en grafos sin circuitos a caminos
máximos. Caminos mínimos hasta cada vértice alcanzable desde uno dado
en caminos mínimos desde cada vértice que alcanza uno dado. Ejemplo:
agente viajero a circuito hamiltoniano
de costo mínimo. SUDOKU
general a SAT. etc.
|
(2)
22 y 24 ene
|
Máquinas de Turing
deterministas y no deterministas. Clase P y NP.
|
Problemas NP, problemas NP-completos, NP-hard. Ejemplos: SAT, 3-SAT,
Coloración, etc. Ejemplos de reducción para mostrar que están en
NP-completos (clique máxima) |
(3)
29 y 31 ene
|
Verificación
de la corrección de algoritmos. Corrección de ciclos. Ejemplo:
ordenamiento por inserción, |
Recorridos en grafos. Modelo general de etiquetamiento. DFS
propiedades, BFS propiedades. Aplicaciones: enumeración de conjuntos.
Backtracking. Ejemplos
|
(4)
5 y 7 feb
|
CARNAVAL |
trabajo en el proyecto
|
(5)
12 y 14 fe
|
Backtracking,
estrategias de poda más eficientes, ej: el problema de la suma.
entrega solución proyecto 1. Discusión de resultados por los equipos.
entrega enunciado proyecto
2 (10%).
|
Branch&bound.
Ejemplos. |
(6)
19 y 21 feb
|
Estrategia Greedy. Como heurística: cambio
moneda, coloración. Como algoritmo exacto: Kruskal, Problema
de la Mochila fraccionario (knapsack). Secuenciación |
entrega enunciado 1er. examen (35%)
Verificar correctitud de Kruskal. Estructura de
datos para representar particiones de conjuntos. Uso en Kruskal.
|
(7)
26 y 28 feb
|
Verificacion de que el
algoritmo greedy para secuenciación es exacto. Un poco de teoría:
Matroides.
|
entrega solución 1er. examen.
b-uniformidad. Solúción de recurrencias útiles en
algoritmos recursivos. Teorema maestro.
Ejemplos de análisis
en tiempo de algoritmos recursivos.
|
(8)
4 y 6 mar
|
Corrección
de algoritmos recursivos. Ejemplo: merge-sort. |
Divide-and-Conquer:
esquema general.
Quicksort (análisis promedio) Multiplicación de enteros grandes.
|
(9)
11 y 13 mar
|
entrega solución proyecto 2. Discusión cada
equipo.
entrega enunciado proyecto
3 (10%)
Discusión enunciado, estrategias para mejorar la solución (heurísticas,
estructuras de datos, etc.).
|
Estadísticos
de Orden. Aumento de estructuras de datos
para hallar estadísticos de orden. Divide-and-Conquer: Cálculo de la
mediana en tiempo lineal |
18 y 20 mar
|
SEMANA
|
SANTA
|
(10)
25 y
27 mar
|
Aplicación
en geometría computacional: dos puntos más cercanos
|
Prog.
Dinámica: En qué
consiste: Coeficiente binomial. Bellman.
|
(11)
1 y 3 abril
|
Prog.
Dinámica: Floyd-Warshall. Devolver
cambio.
entrega enunciado
2do. examen (30%)
|
Prog. Din. ejemplos: Knapsack,
evaluación de expresiones, multiplicación de n matrices. Funciones con
memoria. Inicialización
Virtual. |
(12)
8 y 10
abril
|
entrega
solución 2do. examen
entrega solucion proyecto
3. Discusión por equipo.
|
|
(*) B: Brassard, C:
Cormen, S: Sipser
|