Curso libreTecnología y desarrollo de software
Análisis de algoritmos
El curso Análisis de algoritmos proporciona al estudiante herramientas para medir y comparar la eficiencia de algoritmos con notación asintótica, recurrencias y el teorema maestro, analizar algoritmos de ordenamiento y elegir estrategias como divide y vencerás, voraces y programación dinámica, para escribir software que escale.
A quién va dirigido
Estudiantes que programen con soltura en algún lenguaje y conozcan estructuras de datos básicas.
Objetivos
✓Comprender el modelo de costo, el conteo de operaciones y las notaciones O, Omega y Theta.
✓Analizar algoritmos recursivos con árboles de recursión y el teorema maestro.
✓Aplicar la medición experimental con timeit en Python a algoritmos de búsqueda y ordenamiento.
✓Diseñar soluciones con divide y vencerás, algoritmos voraces y programación dinámica.
✓Evaluar resultados experimentales frente a la complejidad teórica y los límites de P y NP.
Plan de estudios por sesión
1
Eficiencia: modelo de costo y conteo de operacionesNotaciones O, Omega y Theta; mejor, peor y caso promedio · Medición experimental con timeit en Python
2
Recursión: algoritmos recursivosÁrbol de recursión y teorema maestro · Búsqueda binaria
3
Ordenamiento: inserción y selecciónMerge sort y quicksort; límite inferior por comparación · Ordenamiento en tiempo lineal: counting sort
4
Presentación del ejercicio final: informe comparativo de tres ordenamientosDivide y vencerás, algoritmos voraces y programación dinámica · Mochila, subsecuencia común más larga y P y NP
Evaluación
Inicial30%Taller de conteo de operaciones y notación asintótica con mediciones en timeit.
Intermedio30%Resolución de recurrencias con árbol de recursión y teorema maestro aplicadas a búsqueda binaria.
Final40%Ejercicio final: informe que implemente tres ordenamientos en Python, mida tiempos y contraste con su complejidad.
Proyecto final
Informe comparativo que implemente tres algoritmos de ordenamiento en Python, mida sus tiempos con distintas entradas y contraste los resultados con su complejidad teórica.