El análisis y diseño de algoritmos juegan un papel central en el área de las ciencias de la computación. El saber aplicar los conceptos de complejidad y justificación, es uno de los retos más complicados en el diseño de algoritmos. Este curso ofrece profundizar y dar a conocer temas como ordenamientos, búsquedas, programación dinámica, estrategias voraces y algoritmos que involucran el uso de gráficas, con el fin de contar con un amplio bagaje para confrontar los problemas que un científico de la computación tiene en su vida profesional.
Introducción a la complejidad de los algoritmos, algunos ejemplos interesantes.
Ordenación y árboles binarios, búsqueda, cotas inferiores, heapsort, mergesort, quicksort, etc.
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 voraces. Códidos de Huffman.
Algoritmos para gráficas, la ruta mas corta, árboles generadores de peso mínimo, flujos en redes.
Algoritmos de ruteo.
Breve introducción a Geometría computacional
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
Las sesiones del curso serán los martes y jueves de 13:00 a 14:30 hrs. En caso de requerir ayudantías se programarán con anticipación con el ayudante.
Exámen: 70 %
Tareas : 30 %.
Para acreditar el curso, los estudiantes tienen que promediar al menos 60 % en examenes y tareas.
Tendremos 5 o 6 tareas durante el semestre, estas deben entregarse por correo en formato pdf, es importante mencionar que no se aceptan tareas con lápiz.
NO hay exámenes de reposición.
UNA VEZ QUE COMIENCE A RECIBIR CALIFICACIONES EN TAREAS o EXÁMENES NO SON ELEGIBLES A NP.