CI-2613 Algoritmos y Estructuras III

(antes Teoría de CI-2617)

Contenido del Curso Bibliografía Profesores Programación del Curso Evaluación Material de Apoyo NOTAS

Contenido del Curso:

• Conceptos básicos de Teoría de Grafos
• Conectividad
• Recorridos en grafos. Modelo General de Etiquetamiento.
  
• Caminos de Costo Mínimo
• Arboles y Arborescencias
• Arbol 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 (Abril-Julio 2009):

• Teoría: Lunes y Miercoles (ENE 124):  de 1:30 a 3:30. 
  
• Prof. Maruja Ortega F.
• Oficina: MYS 122
• Horas de Consulta:  al finalizar la clase
  

volver al principio

Programación del Curso:

Teoría.

Semana	Lunes	Miercoles
1.  Abril.	20/4  Introducción	22/4  Conceptos Básicos. Representación de Grafos.
2.  Abril.	27/4  Isomorfismos e Invariantes. Conectividad: caminos y cadenas	29/4  Caminos Eulerianos y Hamiltonianos
3.  Mayo	4/5  Alcance. Algoritmo de Roy Warshall.  Clausura Transitiva.	6/5  Quiz  (15%)
4.  Mayo	11/5  Componentes Conexas y Fuertemente Conexas.	13/5   Modelo General de Etiquetamiento.     Alg. de Búsqueda en Profundidad (DFS)
5.  Mayo	18/5  DFS: Aplicaciones	20/5  Alg. de Búsqueda en Amplitud (BFS).  Aplicaciones
6.  Mayo	25/5 Extensión a Grafos No Orientados	27/5  Modelo General de Etiquetamiento para Busqueda de Caminos de Costo Mínimo. Principio de Optimalidad.
7.  Junio	1/6  Algoritmo de Dijkstra. Algoritmo de Floyd.	3/6  Parcial 1 (40%)
8.  Junio	8/6  Grafos de Precedencia. .Ordenamiento Topológico	10/6 Caminos de Costo mínimo y máximo en grafos de Precedencia: Algoritmo de Bellman
9. Junio	15/6 Planificación de Proyectos	17/6  Arboles y Ciclos. Propiedades.
10. Junio	22/6  Arborescencias. Propiedades	24/6  Arbol Mínimo Cobertor
11. Junio / Julio	29/6  Algoritmos Prim/Kruskal	1/7  Repaso.
12) Julio	6/7  Parcial 2 (45%)	.

Evaluación:

Teoría : 1 Quiz (15%) + 2 examenes parciales (40% + 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 : 

•  QUIZ  (15%)
• 1er. Parcial (40%)  Revisión: viernes 12/06/09 de 2 a 3 pm en MYS 122 (DII).
  
• 2do. Parcial y Definitivas.  Revisión:  Miercoles 08/07/2009, 2 a 3  pm en MYS 122 (DII).