$[/\]$

Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

$[\/]$

CI-1303 Estructuras de Datos y Análisis de Algoritmos

I Semestre 1999

Profesora Sandra Kikut

REQUISITOS

CI-1201 Programación II	Horas:	4
CI-1104 Matemáticas Discretas I	Créditos:	4

OBJETIVO

Dado un problema a computarizar, el estudiante será capaz de identificar y seleccionar el objeto o modelo más adecuado para resolverlo y las operaciones que se deberán realizar sobre tal objeto. El estudiante será capaz de implementar el objeto mediante la escogencia de la estructura de datos apropiada, así como de implementar las operaciones mediante un algoritmo específico. Ambas implementaciones deberán hacerse tomando en cuenta criterios de eficiencia, tanto de espacio como de tiempo, para lo cual el estudiante deberá saber calcular el orden de duración de un algoritmo, así como estimar la cantidad de espacio que utiliza.

OBJETIVOS ESPECIFICOS

Estudiar los modelos matemáticos básicos, sus diversas representaciones y sus operaciones.
Estudiar las principales estructuras de datos para la organización eficiente de información.
Estudiar los principales algoritmos para ordenamiento, búsqueda, manejo de grafos, etc.
Estudiar las técnicas fundamentales para la resolución de problemas.
Estudiar un modelo para medir la complejidad "espacio-tiempo" de un algoritmo.

CONTENIDOS

Primera parte: (material del primer examen parcial)

Cálculo del tiempo de ejecución y orden de duración un algoritmo.
Modelos: lista, pila, cola, correspondencia o función, árbol n-ario, conjunto, diccionario, cola de prioridad, relación 1:N y relación N:M, sus operaciones y representaciones.
Estructuras de datos: arreglos (circular y lineal), diversas listas enlazadas (por punteros o por cursores), lista de listas, multilista, árbol de búsqueda binaria, árboles balanceados, vector heap, etc.
Algoritmos para la implementación de las operaciones y aplicaciones de los modelos.

Segunda parte: (material del segundo examen parcial)

Modelo grafo (dirigido y no dirigido), sus operaciones y representaciones.
Estructuras de datos: matriz de adyacencia y lista de adyacencia.
Algoritmos para el manejo de grafos.
Técnicas para la resolución de problemas: búsqueda greedy, búsqueda exhaustiva (ramificación y acotamiento), local, etc.
Algoritmos de ordenamiento interno: burbuja, selección, inserción, quicksort, heapsort, mergesort, radixsort.

EVALUACION

Se realizarán 2 exámenes parciales, 2 o más proyectos programados, quices y tareas cortas. La nota final se calculará de la siguiente manera:

65% el promedio de los 2 exámenes parciales.
20% el promedio de los proyectos programados.
15% el promedio de quices y tareas cortas.

FECHAS IMPORTANTES

I examen parcial: miércoles 5 de mayo, 2:00 pm.
II examen parcial: miércoles 16 de junio, 2:00 pm.
Examen final: martes 29 de junio, 2:00 pm.

BIBLIOGRAFIA

El libro de texto es el de Aho, Hopcroft y Ullman. Los demás son obras de consulta.

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.
Baase Sara: "Computer Algorithms".
Horowitz, E.; Sahni, S.: "Fundamentals of Data Structures"; Computer Science Press; 1982.
Knuth, Donald: "The Art of Computer Programming, Vol. 1 Fundamental Algorithms"; Addison-Wesley; 1968.
Knuth, Donald: "The Art of Computer Programming, Vol. 3 Sorting and Searching"; Adisson-Wesley; 1971.
Kronsjo, Lydia: "Algorithms: Their complexity and efficiency".
Sedgewick, Robert: "Algorithms". Addison-Wesley, 1995

$[/\]$