Este curso es una introducción al análisis matemático de algoritmos y a los fundamentos de la Teoría de Complejidad Computacional. Primero discutiremos como se mide la cantidad de recursos necesarios para resolver un problema algorítmico y luego nos concentraremos en dos extremos: por un lado problemas algorítmicos que admiten soluciones muy eficientes (algoritmos de divide and conquer y probabilísticos) y por otro lado problemas que creemos que no pueden resolverse de manera eficiente mediante ningún método, los problemas NP completos. Distinguir entre unos y otros es el objetivo principal de la teoría de complejidad computacional, y el problema abierto más importante de la teoría de la computación, conocido como P vs NP, que introduciremos como tema final del curso.

Textos: La referencia principal seran las notas clase a clase del instructor. Estas se basarán en los siguientes libros de referencia (altamente recomendados y complementarios entre si):

• [KT] Kleinberg Jon y Tardos Eva: Algorithms Design, Pearson Education (2006).
• [R2] Roughgarden Tim: Algorithms Illuminated Part 2: Graph Algorithms and Data Structures, Soundlikeyourself Publishing, LLC (2019).
• [R3] Roughgarden Tim: Algorithms Illuminated Part 3: Greedy Algorithms and Dynamic Programming, Soundlikeyourself Publishing, LLC (2019).
• [C] Cormen Thomas, Leiserson Charles, Rivest Ronald y Stein Clifford: Introduction to Algorithms, The MIT press (2003).

Metodología y Evaluación:

La mayor parte de lo que aprenderán en este curso será el resultado de su propio trabajo en dos aspectos de igual importancia: Reflexión posterior a cada clase sobre los resultados discutidos en ella y trabajo en los talleres Prácticos asignados clase a clase.

Los criterios de evaluación del curso son:

• El 50% de la nota será determinado por talleres prácticos a ser realizados en grupos de a lo más tres estudiantes (ver fechas de entrega de los prácticos abajo, marcados con la letra [P]). Todos los prácticos tienen una participación igual en el 50%.
• El 50% restante de la nota será determinado por dos exámenes parciales individuales (25% cada uno) a ser realizados en clase en las fechas marcadas abajo.
• La nota final se decidirá calculando el promedio ponderado de las notas como en los párrafos anteriores, redondeando al entero más cercano y convirtiéndolo a la escala oficial: S: 96-100 MB: 91-95, BMB: 83-90, B: 75-82, R: 41-74, D: 0-40.

Instructor:

• Mauricio Velasco (mauricio.velasco@ucu.edu.uy)