Algoritmos y Estructuras de datos

HRS./SEM.: 4

Objetivo: Estudiar métodos de diseño de algoritmos y de desarrollo de programas. Conocer los principales algoritmos y estructuras de datos, incluyendo el análisis informal de su desempeño.

  • Recursividad. Dividir para reinar, nociones de análisis de algoritmos, planteamiento y resolución de ecuaciones de recurrencia, programación dinámica, conceptos de orientación a objetos.
  • Estructuras de datos básicas. Arreglos, punteros, listas enlazadas, árboles.
  • Tipos de datos abstractos. Concepto de encapsulamiento, listas, pilas, colas.
  • Grafos. Representación y recorrido, árbol cobertor mínimo, distancia mínima.
  • Diccionario. Implementaciones simples, árboles de búsqueda binaria, árboles AVL, árboles 2-3, árboles B, árboles digitales, skip lists, hashing.
  • Ordenamiento. Cota inferior, quicksort, heapsort, bucketsort, mergesort, ordenamiento externo.
  • Búsqueda en texto. Método de fuerza bruta, Knuth & Morris & Pratt,, Boyer & Moore.
  • Algoritmos probabilísticos.

Bibliografía.
[1] M. A. Weiss, Data structures and problem solving using Java, Addison & Wesley, 1998.

[2] U. Manber, Introduction to algorithms: a creative approach, Addison & Wesley, 1989.

[3] T. Cormen, C. Leiserson y R. Rivest, Introduction to algorithms, MIT Press, 1990.

[4] D. Knuth, The art of computer programming, vol. 1 y 3, Addison & Wesley, 1998.