Estructuras de Datos y Algoritmos

Asignatura

Ficha Técnica
Modalidad Obligatoria
Área Especialización
U.C: 3
Código 2120360000220

Justificación

El Desarrollo de programas de aplicación en los ambientes tecnológicos, requiere que los elementos de software sean más seguros y eficientes a medida que el uso del computador invade áreas de mayor complejidad. Esto hace que los programadores requieran, cada vez más, conocimientos formales sobre diseño de datos, y el análisis de correctitud y eficiencia de algoritmos.

Objetivos del Curso

Al finalizar el curso, el estudiante estará en capacidad de:

  • Definir formalmente estructuras y tipos abstractos de datos y utilizar estas definiciones operacionalmente para el diseño de algoritmos y construcción de programas.
  • Determinar la eficiencia de los algoritmos de un programa, utilizando los parámetros adecuados para especificar la complejidad de dichos algoritmos.
  • Decidir la estructura de datos y los correspondientes algoritmos adecuados a las características ambientales y operacionales del programa que los utilizará.

Prerequisitos

Haber cursado la asignatura Técnicas de Programación.

Contenido Programático

Unidad 1: Introducción

  • Revisión matemática.
  • Recursión.
  • Elementos de Java.
  • Objetos.
  • Excepciones.
  • Entrada y salida.
  • Organización del código.

Unidad 2: Análisis de algoritmos

  • Base matemática.
  • Modelo de análisis.
  • Determinación del tiempo de ejecución.

Unidad 3: Listas

  • Tipos abstractos de datos (ADTs).
  • El ADT lista.
  • Implementación usando arreglos.
  • Listas encadenadas.
  • Aplicaciones.
  • Implementación mediante cursores.
  • El ADT pila (Stack).
  • Implementación de pilas.
  • Aplicaciones.
  • El ADT cola.
  • Implementación de colas.
  • Aplicaciones.

Unidad 4: Algoritmos de ordenamiento

  • Algoritmos simples: inserción, selección e intercambio.
  • Algoritmo de Shell.
  • Algoritmos HeapSort MergeSort.
  • Algoritmo QuickSort.
  • Algoritmos de ordenamiento externo.

Unidad 5: Árboles

  • Introducción.
  • Árboles Binarios.
  • El ADT árbol de búsqueda.
  • Árboles AVL.
  • Árboles B.

Unidad 6: Tablas de búsqueda por dispersión (hashing)

  • Funcionamiento.
  • Funciones de dispersión.
  • Colisiones: Búsqueda lineal, cuadratica y doble hashing.
  • Rehashing.

Unidad 7: Colas con prioridad (heaps)

  • Modelo.
  • Implementaciones simples.
  • Montículos (Heap) binarios.
  • Aplicaciones.
  • d-Heaps.
  • Colas binomiales.

Unidad 8: Conjuntos dispersos

  • Relaciones de equivalencia.
  • El problema de equivalencia dinámica.
  • Algoritmos de unión.
  • Una aplicación.

Unidad 9: Algoritmos para grafos

  • Definiciones.
  • Orden topológico.
  • Ruta mas corta.
  • Flujo en redes.
  • Árbol de mínima expansión.
  • Aplicaciones de búsqueda en profundidad.
  • Problemas NP-completos.

Unidad 10: Técnicas de diseño de algoritmos

  • Algoritmos avaros.
  • Dividir y conquistar.
  • Programación dinámica.
  • Algoritmos aleatorizados.
  • Algoritmos de ensayo y error.

Unidad 11: Analisis amortizado

  • Colas binomiales.
  • Skew Heaps.
  • Heaps de Fibonacci.
  • Arboles Splay.

Unidad 12: Estructuras de datos avanzadas

  • Árboles Top-Down Splay.
  • Árboles rojo-negro.
  • Listas de salto determinísticas.
  • Árboles AA.
  • Treaps.
  • Árboles k-d.
  • Pairing Heaps.

Metodología de la Enseñanza

Se realizarán exposiciones por parte del profesor discutiendo los puntos resaltante del tema en estudio. Los cursantes estudiarán, previamente a la clase, los temas indicados en el libro de texto. Las preguntas, opiniones y dudas que aparezcan durante el estudio del tema le serán participadas al profesor a través de mensajes de correo electrónico, antes de ser tratado el tema en clase. El profesor atenderá los mensajes recibidos y los contestara en el plazo no mayor de una semana.

Se proveerá los estudiantes con programas que muestran el funcionamiento de los algoritmos, así como los grupos de datos necesarios y los resultados correspondientes a su ejecución. Para reforzar el aprendizaje los estudiantes elaboraran trabajos prácticos de programación.

Intensidad Horaria

La intensidad horaria del curso es de una sesión semanal de tres horas para la teoría y trabajos prácticos en ambientes de computación del Instituto de Cálculo Aplicado, durante 16 semanas que equivalen a cuatro unidades crédito.

Bibliografía

  • Lafore, Robert, Data Structures y Algorithms in Java, Waite Group Press, 1998
  • Antón, Howard and Bernard Colman. Applied finite Mathematics, 3rd ed., Academic Press, Orlando, 1982.
  • Kuth, Donald E., "The art of computer Programming" , Vol 1 - Fundamental Algorithms, 3ra edición, Addison-Wesley, 1997
  • Kuth, Donald E., "The Art of Computer Programming" , Vol 3 - Sorting ans Searching, 2da edición, Addison-Wesley, 1998
  • Aho, Alfred, Hopcroft, John y Ullman, Jeffrey, "Data Structures and Algoritms", Addison-Wesley, 1983
  • Tenenbaum, Aaron y Augenstein, Moshe, "Data Structures Using Pascal", Prentice-Hall, 1997
  • Sedgewick, Robert, "Algorithms", 2da edición, Addison-Wesley, 1988
  • Wirth, Niklaus, "Algrithms+Data Structures=Programs", Prentice-Hall, 1976
  • Horowitz, Ellis y Sahni, Sartaj, "Fundamentals of Data Structures", W.H. Freeman y Co, 1983
  • Horowitz, E. Y Sahni, S.; Algoritms: Desingn and Análisis, Computer Science Press, Potomac, MD., 1977.