Profesor | Jorge Urrutia Galicia | lu mi vi | 12 a 13 | P213 |
Profesor | Adriana Ramírez Vigueras | |||
Ayudante | Alma Rosario Arévalo Loyola | ma ju | 12 a 13 | P213 |
Introducción a la complejidad de los algoritmos, algunos ejemplos interesantes.
Ordenación y búsqueda, cotas inferiores, hepsort, mergesort, quicksort, etc.
Búsquedas binarias, árboles binarios. Mediana y k-selección.
Programación dinámica, multiplicación de matrices, subsucesión común mas larga, subsucesión creciente mas larga, triangulación de peso mínimo de polígonos convexos.
Algoritmos greedy.
Algoritmos para gráficas, la ruta mas corta, árboles generadores de peso mínimo, flujos en redes.
Breve introducción a los problemas NP-completos.
A lo largo del curso estudiaremos varios problemas recientes cuya solución fue basada en los algoritmos básicos que estudiaremos durante el curso. Por ejemplo, estudiaremos varios problemas de la Geometría Computacional, estructuras de datos dinámicas, problemas de clasificación de datos, problemas de rutas en redes ad-hoc e inalámbricas, etc.
Introduction to Algorithms.
Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford. The MIT Press. 2009
The Algorithm Design Manual
Skiena, Steven S. Springer Publishing Company, Incorporated. 2008
Exámenes: 70 %
Tareas: 30 %
Para acreditar el curso, los estudiantes tienen que promediar al menos 60 % en los exámenes.
Habrán dos exámenes, uno a mediados del semestre y uno al finalizar el mismo. Tendremos 5 o 6 tares durante el semestre. No hay extraordinarios largos, o exámenes de reposición. Las tareas se entregan a la hora de clase. UNA VEZ QUE COMIENCE A RECIBIR CALIFICACIONES EN TAREAS O EXAMENES NO SON ELEGIBLES A NP.