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 LABORATORIO (CI-2693) 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 (Sept-Dic 2008):

• Teoría: Lunes (AUL 014), Miercoles (ENE 118):  de 1:30 a 3:30. 
  
• Prof. Maruja Ortega F.
• Oficina: MYS 215-B
• Horas de Consulta: 
  
• Laboratorio: 
• Bloque A:
  
• Seccion 1: Prof. Hilmar Castro.
• Oficina:
  
• Bloque B:
• Sección 2:  Ing. Guillermo Palma
• Oficina:
  

volver al principio

Programación del Curso:

Teoría.

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

• La revision del 2do. parcial será el viernes 5/12 a las 9:30 en la sala de conferencias del Dpto. de Computación. Se explicarán los criterios de corrección y luego se entregará el examen para su revisión. Hasta las 11 am.

• Las notas se publicarán en la Cartelera del Dpto. de Computación a las 9:20 am del viernes 5/12.   Posiblemente se publiquen también en esta página.

•  QUIZ  (15%)
• 2do. Parcial y Definitivas