La Materia

Objetivos
  • Que el alumno aprendan a analizar complejidad temporal de los programas.
  • Que el alumno aprenda los distintos esquemas algorítmicos adecuados a la resolución de diferentes tipos de problemas teniendo en cuenta la complejidad
  • Que el alumno pueda distinguir diferentes clases de problemas y técnicas de resolución.
Contenidos mínimos

Introducción a algoritmos. Eficiencia. Análisis asintótico de la eficiencia temporal en programas iterativos. Resolución de recurrencias. Análisis asintótico de la eficiencia temporal en funciones recursivas.

Técnicas de diseño de algoritmos. Caracterización del tipo de problema, esquema algorítmico, problemas representativos: Divide y conquista, Greedy, Programación dinámica y backtracking.

Algoritmos de ordenamiento. Algoritmos cuadráticos y NlogN.

Algoritmos sobre grafos. Algoritmos clásicos: recorrido en grafos, algoritmo de Dikjstra, Algoritmo de Floyd, algoritmo de Prim, algoritmo de Kruskal, componentes conectadas.

Problemas NP-hard. Problemas clásicos y algoritmos de aproximación: El problema del viajante, recubrimiento de vértices, coloreo de un grafo.

Bibliografía básica

Brassard, G.; Bratley, P. Prentice-Hall. Fundamentos de Algoritmia. 1997

Cormen, T.; Lieserson, C.; Rivest, R. “Introduction to Algorithms” Ed. The MIT Press. 2009.