La materia tiene por objetivo que l@s estudiantes :
- Incorporen la noción formal de orden de complejidad temporal y espacial de un algoritmo para el peor caso y el caso promedio.
- Elijan entre dos algoritmos en base a su propio cálculo de complejidad temporal y espacial en peor caso para los mismos.
- Pueden desarrollar algoritmos más eficientes que los triviales para distintos problemas, mediante el uso de las técnicas algorítmicas de Divide y Vencerás y Programación Dinámica.
- Encuentren un algoritmo a problemas de decisión, enumeración u optimización de cierta complejidad mediante el uso de Backtracking.
- Conozcan los algoritmos de Precondicionamiento Transformacion de Dominio y los problemas de propagación de errores en los algoritmos numéricos.
- Conozcan los problemas clásicos de grafos, sus soluciones algorítmicas más importantes y sus aplicaciones más relevantes.
- Conozcan los problemas clásicos sobre cadenas, sus soluciones algorítmicas más importantes y sus aplicaciones más relevantes, en particular aquellas de la bioinformática.
Modos de Cursada: Cuatrimestral Presencial
Horas Semanales: 6 horas
Demanda de tiempo en casa semanal: 6 horas
Sitio web:
Programa de la materia:
Contenidos Mínimos:
- Noción de algoritmo, ejemplos de algoritmos (criba de Eratóstenes, mcd, etc). Criterios de selección de un algoritmo.
- Notación O y W. Análisis teórico del tiempo de ejecución de un algoritmo Análisis practico del tiempo de ejecución de un algoritmo.
- Algoritmos Divide y Vencerás. Análisis de procedimientos recursivos.
- Algoritmos Basados en Programación Dinámica.
- Algoritmos Greedy.
- Algoritmos de Precondicionamiento y Transformación del Dominio.
- Algoritmos de programación matemática, heurísticas. Algoritmos numéricos y propagación de errores.
- Casos: algoritmo de Huffman, encriptación, compresión, búsqueda, actualización, ordenamiento, estructuras de datos y algoritmos, árboles estrella, matrices.
- Algoritmos sobre grafos (DFS, BFD, Prim, Kruskal, Dijkstra, Floyd, sort topológico, etc).
Algoritmos básicos sobre cadenas: matching, alineamiento, sufijos.