$[/\]$

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

$[\/]$

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

II Semestre 1996

Profesor Adolfo Di Mare

REQUISITOS

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

OBJETIVO

Desarrollar en el estudiante habilidades para la construcción de programas eficientes aplicando tanto los algoritmos como las estructuras de datos adecuadas.

OBJETIVOS ESPECIFICOS

Dado un problema a computerizar, 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 las estructuras de datos apropiadas, así como de implementar las operaciones mediante un algoritmos o precedimiento específico. Ambas implementaciones deberán hacerse tomando en cuenta criterios de eficiencia, tanto de espacio como de tiempo, para lo quel el estudiante deberá saber calcualr el orden de duración de un algoritmo.

HABILIDADES COGNOSCITIVAS

Reconocer y usar los algoritmos de ordenamiento clásicos y las estructuras de datos principales.
Escoger el Tipo Abstracto de Datos adecuado para una aplicación específica.
Implementar ADTs usando la tecnología de Programación Orientada a los Objetos.
Calcular la eficiencia en espacio y tiempo de un algoritmo o una estructura de datos.
Afinar algoritmos para una aplicación específica.

CONTENIDOS

Relaciones de recurrencia         Parametrización de contenedores
  Solución                          Biblioteca STL de C++
  Aplicaciones                      Iteradores
  Complejidad computacional         Memoria dinámica

Listas                            Grafos
  Listas de punteros                Grafos dirigidos
  Listas de cursores                Algoritmos para grafos
  Multilistas
  Pila                            Expresiones regulares
  Cola                              Autómatas finitos


Arreglos                          Métodos de búsqueda
  Matrices                          BinSearch()
  Matriz de adyacencia              LinearSearch()
  Lista de adyacencia               KMPsearch()
                                    BMearch()
Arbol
  Representación                  Métodos de ordenamiento
  Arboles de búsqueda               BubbleSort()
  Arboles balanceados               SelectionSort()
                                    InsertionSort()
Montículo (Heap)
  Colas de prioridad                HeapSort()
                                    QuickSort()
Hashing                             MergeSort()
  Conjuntos
  Diccionarios                      RadixSort()
                                    BinSort()
Métodos de búsqueda                 ShellSort()

En todos los temas se incluye el análisis de tiempo de cada algoritmo y se estudia en términos de eficiencia las diferentes estructuras escogidas para la implantación de un TAD.

INDICE DE MATERIALES DEL CURSO

Tarea #1: ADT Matriz.pas con matriz rala auto-reconfigurable.
Operaciones: LU(), Traspuesta(), + - *, Inversa(), Determinante()
- En parejas.
Tarea #2: ADT Matriz.c++ con las mismas operaciones de .pas, pero usando sobrecarga de operadores.
- En parejas diferentes.
Tarea #3: Artículo comparando Tarea #1 vs Tarea #2.
- Individual, en Español. Versión en Papel y HTML.
Tarea #4: Comparación de System.Pos(), strlen(), KMPsearch(), BMsearch()
- En Parejas, en Inglés. Versión en Papel y HTML.

EVALUACION

Examen Parcial #1 15%      Tareas Programadas 35%

Examen Parcial #2 15%      Otros 10%

Examen Final 25%

BIBLIOGRAFIA

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "The Design and Analysis of Computer Algorithms"; Addisson Wesley Publishing Co.; 1974.
Di Mare, Adolfo: "Convenciones de Programación para Pascal, v2"; Reporte técnico ECCI-01-88; ECCI-UCR; 1988.
http://www.di-mare.com/adolfo/p/convpas.htm
Di Mare, Adolfo: "Tipografía de artículos en Internet", Revista Ingeniería, Facultad de Ingeniería, Universidad de Costa Rica, Volumen 6, Número 2, pp [5570], 1996.
http://www.di-mare.com/adolfo/p/typeset0.htm
Baase Sara: "Computer Algorithms".
Horowitz, E.; Sahni, S.: "Fundamentals of Computer Algorithms"; Computer Science Press; 1978.
Horowitz, E.; Sahni, S.: "Fundamentals of Data Structures"; Computer Science Press; 1982.
"GNU libg++"; Version 2.6: ftp://prep.ai.mit.edu/pub/gnu/libg++-2.6.tar.gz; [1,324,942 bytes].
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
Stepanov, Alexander; Lee, Meng: "The C++ Standard Template Library"; Generic Programming Project, Hewlett Packard Research Labs; 1995.
ftp://butler.hpl.hp.com/stl/stl.zip
Wirth, Niklaus: "Algoritmos y Estructua de Datos"; Prentice Hall Hispanoamericana; México 1982.

$[/\]$

Examen Parcial #1	15%	Tareas Programadas	35%
Examen Parcial #2	15%	Otros	10%
Examen Final	25%