CI-2613 Algoritmos y Estructuras III

· Contenido del Curso

· Bibliografía

· Programación del Curso

· Evaluación
· Material de Apoyo

· NOTAS

INFORMACIÓN: Notas y revisión del 2do. parcial - Viernes 9/12 de 9 a 10:30 en MYS 122 (DII).

Contenido del Curso:

Conceptos básicos de Teoría de Grafos
Conectividad
Recorridos en grafos. Modelo General de Etiquetamiento.
Caminos de Costo Mínimo
Árboles y Arborescencias
Árbol Mínimo Cobertor.

volver al principio

Bibliografía:

Texto: "Grafos y Algoritmos". O. Meza y M. Ortega. 2da. Ed. Editorial Equinoccio. 2006
Libros de Consulta:

"Estructuras de Datos y Algoritmos". Aho, Hopcroft y Ullman. Editorial Addison Wesley.
"Algoritmos y Estructuras de Datos". N. Wirth. Editorial Prentice Hall.

volver al principio

Profesores:

Trimestre en curso (Sept-Dic 2011):

Teoría: Lunes (AUL 009) - Miercoles (MYS 111) de 9:30 a11:30.

Prof. Maruja Ortega F.

Oficina: MYS 122
Horas de Consulta:

volver al principio

Programación del Curso:

Teoría.

Semana	Lunes	Miercoles
1. Sept.	18/9 Introducción. Definición Grafo	21/9 Conceptos Básicos. Isomorfismos e Invariantes.
2. Sept.	26/9 Representación de Grafos. Conectividad: caminos y cadenas	28/9 Conectividad (cont.) Caminos y cadenas Eulerianos y Hamiltonianos
3. Oct.	3/10 Alcance. Algoritmo de Roy Warshall. Clausura Transitiva.	5/10 Componentes Conexas y Fuertemente Conexas.
4. Oct.	10/10 Quiz (15%)	12/10 Feriado
5. Oct.	17/10 Modelo General de Etiquetamiento. Alg. de Búsqueda en Profundidad (DFS)	19/10 DFS: Propiedades, Aplicaciones
6. Oct.	24/10 Alg. de Búsqueda en Amplitud (BFS). Aplicaciones Extensión a Grafos No Orientados	26/10 Modelo General de Etiquetamiento para Búsqueda de Caminos de Costo Mínimo. Principio de Optimalidad.
7. Oct./Nov.	31/10 Algoritmo de Dijkstra. Algoritmo de Floyd.	2/11 Parcial 1 (40%)
8. Nov.	7/11 Grafos de Precedencia. Ordenamiento Topológico	9/11 Caminos de Costo mínimo y máximo en grafos de Precedencia: Algoritmo de Bellman
9. Nov.	14/11 Planificación de Proyectos	16/11 Árboles y Ciclos. Propiedades.
10. Nov.	21/11 Arborescencias. Propiedades.	23/11 Árbol Mínimo Cobertor
11. Nov.	28/11 Algoritmos Prim/Kruskal	30/11 Repaso
12. Dic.	5/12 Parcial 2 (45%)	7/12

volver al principio

Evaluación:

Teoría : 1 Quiz (15%) + 2 exámenes parciales (40% + 45%)

Evaluación de Teoría
.	Fecha	Valor
Quiz	10/10	15%
Parcial 1	2/11	40%
Parcial 2	5/12	45%

volver al principio

Material de Apoyo:

Teoría :

Problemario (cada capitulo del libro incluye problemas al final)
Conectividad. Definiciones (.doc)

volver al principio

NOTAS :