Imprimir

Programa

CURSO			    : ESTRUCTURAS DE DATOS Y ALGORITMOS
TRADUCCION		    : DATA STRUCTURES AND ALGORITHMS
SIGLA		   	    : IIC2133
CREDITOS		    : 06 SCT-Chile / 10 UC
MODULOS			    : 03
TIPO DE ASIGNATURA	: CATEDRA
CALIFICACION		: ESTANDAR
DISCIPLINA		    : INGENIERIA


I. DESCRIPCION

El curso ense?a las estructuras de datos fundamentales y sus algoritmos, tanto en la memoria principal y disco duro, haciendo hincapie en el uso tipico, las ventajas y limitaciones de cada una. El curso tambien ense?a las principales tecnicas algoritmicas para resolver problemas de optimizacion discreta, colocando hincapie en el analisis cuantitativo de los algoritmos.


II. OBJETIVOS

1. Identificar y explicar las estructuras de datos fundamentales (listas ligadas, colas, heaps, tablas de hash, arboles de busqueda, bosques disjuntos), y los tipos de datos abstractos fundamentales (grafos, diccionarios, colas priorizadas, y conjuntos disjuntos).

2. Dise?ar, implementar y comparar estructuras de datos.

3. Explicar que es un algoritmo computacional.

4. Analizar un algoritmo para determinar su desempe?o en terminos de espacio y tiempo, correccion y completitud; en particular, analizar el desempe?o de diferentes algoritmos de ordenacion: ordenacion por mezclas, ordenacion basada en heaps y quicksort.

5. Aplicar tecnicas algoritmicas especificas --algoritmos codiciosos, dividir para conquistar, programacion dinamica-- para resolver problemas especificos.

6. Explicar los fundamentos de la teoria de grafos, y los siguientes algoritmos sobre grafos: busquedas en amplitud y en profundidad, arboles de cobertura de costo minimo, rutas de costo minimo.


III. CONTENIDOS

1. Introduccion. El papel de los algoritmos en la computacion y la importancia de las estructuras de datos en el dise?o de algoritmos eficientes.

2. Estructuras de datos. Estructuras de datos elementales; tablas de hash; arboles de busqueda binarios; arboles rojo-negros; arboles B; algoritmos para manejar estas estructuras: agregar, eliminar y tener acceso a objetos.

3. Algoritmos de ordenacion. Heapsort; Quicksort; analisis de desempe?o; ordenacion en tiempo lineal.

4. Tecnicas algoritmicas. Programacion dinamica; algoritmos codiciosos; estructuras de datos para conjuntos disjuntos.

5. Representacion y manejo de grafos. Representaciones matricial y por listas de adyacencias; algoritmos elementales: busquedas en amplitud y en profundidad, ordenacion topologica; arboles de cobertura minimos; rutas mas cortas.


IV. METODOLOGIA

- Clases expositivas.
- Ayudantias.


V. EVALUACION

- Pruebas.
- Proyectos.
- Tareas.


VI. BIBLIOGRAFIA

Minima:

Cormen, T., C. Leiserson y R. Riverst. Introduction to algorithms. Cambridge, MIT, 1990.

Complementaria:

Main, M. y W. Savitch. Data structures and others objects using C++. Reading, Mass.: Addison Wesley, 1997.

Sedgewick, Robert. Algorithms in C++. 3? Ed. Reading, Mass.: Addison Wesley, 1997. Parts 1-4.



PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
FACULTAD DE INGENIERIA / Julio 2015