CC30A: Programa del curso

Requisitos

Objetivos

Programa

• Métodos de programación
  • Nociones básicas de verificación de programas.
  • Invariantes.
  • Diagramas de estados.
  • Recursividad.
  • Co-rutinas.
  • Desarrollo de programas "top-down" y "bottom-up".
  • Encapsulamiento y tipos de datos abstractos (TDAs).
  
  
• Nociones de análisis de algoritmos
  • Cómo medir la eficiencia de los algoritmos: peor caso, caso promedio, costo amortizado.
  • Notación "O".
  • Técnicas para plantear y resolver ecuaciones de recurrencia.
  
  
• Técnicas básicas para la estructuración de datos
  • Arreglos, punteros, listas, árboles.
  
  
• TDAs básicos
  • Stacks (con aplicaciones a eliminación de recursividad), Colas.
  
  
• TDA "diccionario"
  • Definición, variantes.
  • Implementaciones en base a búsqueda secuencial.
  • Búsqueda binaria.
  • "Skip lists".
  • Árboles de búsqueda binaria.
  • Árboles óptimos.
  • Árboles balanceados: AVL, 2-3.
  • "B-trees".
  • "Splay trees".
  • Árboles digitales.
  • "Hashing".
  
  
• Métodos de ordenación
  • Cota inferior.
  • Métodos cuadráticos.
  • "Quicksort".
  • "Heapsort".
  • "Bucketsort".
  • Ordenamiento externo.
  
  
• Búsqueda en texto
  • Método de fuerza bruta.
  • Knuth-Morris-Pratt.
  • Boyer-Moore-Horspool.
  
  
• Algoritmos en grafos
  • Representación de grafos.
  • Recorridos.
  • Árboles de costo mínimo.
  • Distancias mínimas.
  
  
• Algoritmos probabilísticos

• Problemas NP-completos

Bibliografía

• R. Lafore, Data Structures & Algorithms in Java, Second Edition, SAMS,2001
• M. A. Weiss, "Data Structures & Problem Solving Using Java", Addison-Wesley, 1998.
• U. Manber, "Introduction to Algorithms: A Creative approach", Addison Wesley, 1989.
• T. Cormen, C. Leiserson y R. Rivest, "Introduction to Algorithms", The MIT Press, 1990.
• R. Sedgewick, "Algorithms in Java, Parts 1-4: Fundamental Data Structures, Sorting, Searching", Addison Wesley, 2003.
• R. Sedgewick, "Algorithms in Java, Part 5: Graphs", Addison Wesley, 2003.
• G. H. Gonnet y R. Baeza-Yates, "Handbook of Algorithms and Data Structures", Addison-Wesley, 1991.
• D. E. Knuth, "The Art of Computer Programing", Vol. 1, "Fundamental Algorithms", Third Edition, Addison-Wesley, 1997.
• D. E. Knuth, "The Art of Computer Programming", Vol. 3, "Sorting and Searching", Second Edition, Addison-Wesley, 1998.