CI-2617 Algoritmos y Estructuras III

(antes CI-2613 + CI-2693)

Contenido del Curso Bibliografía Profesores Programación del Curso Evaluación Material de Apoyo NOTAS Y REVISION:  Fecha cambiada

Contenido del Curso:

• Conceptos básicos de Teoría de Grafos
• Conectividad
• Recorridos
• Caminos de Costo Mínimo. Modelo General de Etiquetamiento
  
• Arboles y Arborescencias
• Arbol Mínimo Cobertor
  

volver al principio

Bibliografía:

• Texto: "Grafos y Algoritmos". O. Meza y M. Ortega.  Editorial Equinoccio. 1993.
• 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. 2004):

• Teoría: Martes y jueves de 1:30 a 3:30.  Aula: ENE-118
  
• Prof. Maruja Ortega F..
• Oficina: MYS 215-B
• Horas de Consulta:  por fijar.
• Taller:
Bloque A. Secciones 1,2 :  Lunes de 9:30 a 12:30 .
• Seccion 1:  Prof. Victor Theoktisto
• Oficina: MYS 211-B
• Horas de Consulta:  por fijar.
• Sección 2:  Preparador
  
Bloque B.  Seccion 3 :   Lunes de 12:30 a 3:30
• Sección 3: Prof. Wilmer Pereira
  

volver al principio

Programación del Curso:

Teoría.

Semana	Martes	Jueves
1) sept 14-16	Conceptos Básicos	Representación de Grafos. Isomorfismos e Invariantes
2) sept 21-23	Conectividad: caminos y cadenas	Caminos Eulerianos y Hamiltonianos
3) sept 28-30	Alcance. Clausura Transitiva. Alg. para determinar Componentes fuertemente conexas.	Modelo General de Etiquetamiento
4) oct 5-7	DFS	DFS: aplicaciones
5) oct 12-14	FERIADO	Backtracking.  BFS
6) oct 19-21	Repaso, Ejercicios	Parcial 1 (30%)
7) oct 26-28	Modelo General de Etiquetamiento para Busqueda de Caminos de Costo Mínimo. Principio de Optimalidad.	Algoritmo de Dijkstra
8) nov 2-4	Algoritmo de Floyd.	Grafos de Precedencia. Ordenamiento Topológico
9) nov 9-11	Caminos de Costo mínimo y máximo en grafos de Precedencia: Algoritmo de Bellman	Aplicación: Planificación de Proyectos
10) nov 16-18	Arboles y Ciclos. Propiedades.	Arbol Mínimo Cobertor
11) nov 23-25	Algoritmos Prim/Kruskal	Repaso, Ejercicios
12) nov 30	Parcial 2 (35%)	.

Taller:

Se entregarán durante el curso 3 proyectos, los cuales serán discutidos en clase.
Para cada proyecto se calculan 2 semanas de trabajo, contando desde la fecha en que es entregado en clase hasta la fecha en que el mismo es evaluado.


Proyecto 1.   ( .doc   .pdf).  Entrega  y Evaluación.   Lunes 11 de Octubre.
Proyecto 2. (.doc )  Entrega y Evaluación.  Lunes 1 de Noviembre (Sem. 8)
Proyecto 3.  (.doc)   Entrega y Evaluación.  Lunes  29 de Noviembre (Sem 12)

Evaluación:

Teoría : 2 examenes parciales: 65%

Taller: 3 proyectos: 35%

Cada proyecto deberá ser entregado al profesor en la fecha abajo indicada, acompañado de un informe y un diskette con el código fuente y un ejecutable. Adicionalmente se llevará a cabo una evaluación en clase sobre el proyecto el mismo día de la entrega.

volver al principio

Material de Apoyo:

    Teoría :

• Problemario (cada capitulo de la versión digital del  libro incluye problemas al final)
• Conectividad. Definiciones (.doc)
  

    Taller:

• Reglas de Documentación de Programas:  postscript            MSword         idoclet.jar   idoclet.bat 
  

volver al principio

NOTAS Y REVISION: