|
sept.-dic. 2.011
|
Lunes
|
Miércoles
|
|
(1)
19-23sept.
|
19sept.:
- Introducción: análisis y síntesis de algoritmos.
- Cálculo tiempo de corrida en el peor caso. Ej:
ordenamiento por inserción.
- Cálculo del tiempo de corrida en el caso promedio.
Ej: ordenamiento por inserción.
- Orden polinómico versus exponencial.
- Notación O, W, Q . Recursos tiempo y espacio de un
programa. |
21sept:
- Análisis Amortizado. Método de contabilidad y
potencial.
- Correctitud de algoritmos. Correctitud de ciclos.
Correctitud de algoritmos recursivos. Ej: ordenamiento por inserción,
merge sort. |
|
(2)
26-30sept
|
26sept: Estructuras
de datos para representar conjuntos
dinámicos. Heap binario, Árboles binarios, Árboles AVL
|
28sept:
Heap binomial.
Análisis de los operadores implementados con las distintas estructuras
de datos.
- Algoritmos Greedy (Voraces). Esquema general.
Ej:
coloración de un grafo. Conjunto estable maximal. mochila
|
|
(3)
3-7OCT
|
3 OCT:
- Árbol mínimo cobertor. Estructuras de datos para
almacenar conjuntos de
conjuntos. Implementación usando la estructura de datos "disjoint set".
Complejidad peor caso. Correctitud. Concepto de matroide |
5OCT:
Fundamentos
teóricos sobre algoritmos Greedy:
Matroides. |
|
(4)
10-14OCT
|
10 oct: Divide&Conquer.
Esquema. Nos permite hacer
fórmulas de recurrencia: Conteo de tuplas (no. De n-tuplas 0-1-2 con un
número par de ceros), de conjuntos. Búsqueda binaria.
Multiplicación de enteros grandes. Quicksort. Complejidad caso promedio
del quicksort.
|
12oct: FERIADO
|
|
(5)
17-21 OCT
|
17oct:
Estadísticos de orden.
Aumento de árboles AVL para determinar est. de orden.
Entrega enunciado primer
examen: 35% |
19oct: Algoritmo D&C
para selección. Cálculo de la
mediana en un arreglo simple. Programación dinámica. Coeficiente
binomial. Principio de Optimalidad.
|
|
(6)
24-28 OCT
|
24oct: Programación
Dinámica: Devolver cambio. Problema de la mochila. Multiplicación
encadenada de matrices. Clausura
transitiva. Floyd. Caminos mínimos (o maximos) desde un vértice en
grafos sin circuitos.
Entrega por el estudiante
de la solución del examen.
|
26oct: Bellman
(bottom-up: sort topológico). Funciones con memoria. Inicialización
virtual.
Recorridos
en grafos: Modelo general de
etiquetamiento. DFS |
|
(7)
31oct-2 NOV
|
31 oct: Backtracking.
Ej:
permutaciones, mochila, N reinas. Suma de conjuntos. Estrategias de
poda.
|
2
NOV: Brach and Bound.
Ej: problema de asignación.
Problema de la mochila. Programación entera 0-1.
|
|
8)
7-11 NOV
|
7 NOV: Teoría de la
Complejidad Computacional. Clases de Complejidad. Algoritmos
Pseudo-polinomiales.
|
9nov: Problemas NP-Hard.
(capítulo 6 y sección 7.1 de J.
Hromkovic. Theoretical Computer Science). Reducción de problemas.
|
|
(9)
14-18 NOV
|
14nov: Algoritmos de Aproximación. (secciones
7.2, 7.3 de J.
Hromkovic. Theoretical Computer Science)
Entrega enunciado 2do.
examen: 35% |
16nov: Algoritmos de Aproximación. (secciones 7.2, 7.3 de J.
Hromkovic. Theoretical Computer Science)
|
|
(10)
21-25 NOV
|
21nov: Algoritmos Aleatorios.
Secciones 21., 2.2, 2.3 de J. Hromkovic. Design
and Analysis of Randomized Algorithms
Entrega por
el estudiante de la solución del examen.
|
23nov: Algoritmos Aleatorios. Sección 2.4
de J. Hromkovic. Design
and Analysis of Randomized Algorithms y cap. 10 de Brassard |
|
(11)
28-2 DIC
|
28nov: Exposiciones
|
30 nov: Exposiciones |
|
(12)
5-9 DIC
|
5dic: Exposiciones |
7 dic: Exposiciones
|