|
sept.-dic. 2.009
|
Lunes
|
Miércoles
|
|
(1)
21-23sept.
|
21sept.: Presentación del curso. ¿Qué es un
algoritmo eficiente?. Notación
Asintótica.
Complejidad
en Tiempo y espacio de un algoritmo.
|
23sept: El Concepto de Grafo. Concepto orientado,
no orientado. Conceptos independientes de si es orientado o no.
|
|
(2)
28-30sept
|
28sept: El concepto de grafos: Invariantes. Aplicaciones: Rutas mas
cortas. Coloración de un grafo (SUDOKU)
|
30sept: Conceptos en grafos: caminos,
cadenas, ciclos, circuitos, ciclos eulerianos.
|
|
(3)
5-7OCT
|
5 OCT: Algoritmo para determinar si
un grafo es Euleriano. |
7 OCT: Alcance.
Algoritmo de Roy-Warshal (técnica de
programación dinámica) |
|
(4)
12-14OCT
|
12 oct: FERIADO |
14oct: Clausura Transitiva. Conectividad,
Conectividad Fuerte. Un primer algoritmo para conectividad fuerte. Modelo General de etiquetamiento
para determinar caminos en grafos. |
|
(5)
19-21 OCT
|
19oct: Modelo General de etiquetamiento:
propiedades.
Búsqueda en
profundidad
(DFS).
|
21oct: DFS recursivo. DFS: visita de nodos, detección de arcos
del bosque, ida, vuelta, cruzados. Propiedades. BFS. Aplicación del
DFS:
determinación
de las componentes fuertemente conexas de un grafo dirigido.
|
|
(6)
26-28 OCT
|
26oct: cont....Aplicación del
DFS:
determinación
de las componentes fuertemente conexas de un grafo dirigido.
|
28oct: Primer Examen Parcial (material
cubierto hasta semana 5 completa) 50% |
|
(7)
2-4 NOV
|
2 NOV: Backtracking.
Búsqueda en
amplitud (BFS). |
4 NOV:
Modelo de algoritmo de
búsqueda
de caminos de costo mínimo.
|
|
8)
9-11 NOV
|
9 NOV: Algoritmo de Dijkstra.
Versión
especializada de Dijkstra |
11nov: Caminos de costo
mínimo con costos
negativos. Algoritmo de
Floyd (técnica de programación
dinámica).
Principio de Optimalidad. |
|
(9)
16-18 NOV
|
16nov: Grafos de precedencia. Niveles
y altura. Relaciones de orden.
Ordenamiento
Topológico. |
18nov: Caminos de costo
mínimo y máximo
en grafos de precedencia (Bellman). |
|
(10)
23-25 NOV
|
23nov:
Aplicación:
Planificación
de Proyectos. |
25nov: árboles
y ciclos |
|
(11)
30-2 DIC
|
30nov: propiedades Árboles
|
2 DIC: Algoritmos de Prim y Kruskal.
correctitud |
|
(12)
7-11 DIC
|
7 DIC:
Segundo Examen Parcial (material cubierto hasta la semana 11 completa)
50% . |
|
Notas:
- Las copias en
exámenes serán
sancionadas con el aplazamiento de
la materia y una amonestación en la
coordinación de la carrera que
puede llevar a la expulsión de la carrera.
|
