CURSO : Estructuras y Representacion de Datos
SIGLA : IIC2132
CRÉDITOS : 10
REQUISITOS : IIC1222 Programacion Avanzada
SEMESTRE : II
1. OBJETIVOS
Al finalizar el curso, el alumno conocera y manejara las estructuras de datos fundamentales
y sus algoritmos; y sera capaz de seleccionar y dise?ar estructuras de datos y algoritmos
apropiados para situaciones especificas considerando rapidez de acceso y procesamiento de
la informacion, utilizacion de memoria, complejidad de implementacion, etc.
2. CONTENIDO
- Fundamentos. Tipos, estructuras y tipos abstractos de datos. Dise?o y analisis de
algoritmos. Crecimiento de funciones, sumas y recurrencias.
- Estructuras simples. Colas, stacks, listas ligadas.
- Estructuras complejas. Colas de prioridades, tablas de dispersion, arboles binarios de
busqueda; conjuntos disjuntos.
- Ordenacion. Tecnicas simples; heapsort; quicksort; counting-sort y radix-sort.
- Grafos. Representaciones; algoritmos simples; arboles de cobertura de costo minimo;
caminos mas cortos; flujo maximo.
- Manejo de memoria. Representaciones; recoleccion de basura.
- Ordenacion y busqueda externas. Ordenacion por mezcla balanceada y polifasica.
Acceso secuencial indexado; dispersion extensible; arboles-B.
- Programacion dinamica y algoritmos codiciosos. Conceptos. Ejemplos: multiplicacion
de una cadena de matrices; caminos mas cortos entre todos los pares de nodos;
seleccion de actividades; codigos de Huffman. Versiones 0-1 y fraccional del problema
de la mochila.
3. BIBLIOGRAFIA
Minima:
CORMEN, Thomas H., LEISERSON, Charles and RIVERST, Ronald L.
Introduction to algorithms. Cambridge, MIT, 1990.
Complementaria:
MAIN, M. and SAVITCH, W. Data structures and others objects using C++.
Reading, Mass., Addison Wesley, 1997.
SEDGEWICK, Robert. Algorithms in C++. 3rd ed. Reading, Mass., Addison
Wesley, 1997. Parts: 1-4.
