Información del curso

¿Por qué algunos problemas se resuelven en milisegundos y otros, en apariencia parecidos, no se resolverían ni con todos los ordenadores del mundo? ¿Hay problemas que ningún programa puede resolver? Este es un curso de nivel grado en ingeniería informática que responde a estas preguntas con rigor y con código: parte de los modelos de cómputo (autómatas finitos y máquinas de Turing), delimita lo computable, clasifica los problemas por su dificultad (P, NP, PSPACE, NP-completitud y reducciones) y termina con las técnicas para atacar problemas intratables: algoritmos exactos inteligentes, aproximación y aleatorización.

Qué incluye: 10 temas y 7 prácticas evaluables

• Módulo 1 · Modelos de cómputo y computabilidad — Tema 1 Lenguajes formales y autómatas finitos · Tema 2 Máquinas de Turing y la tesis de Church-Turing · Tema 3 Decidibilidad y límites de lo computable · Práctica 1 · Simuladores de autómatas y máquinas de Turing
• Módulo 2 · Clases de complejidad y reducciones — Tema 4 Coste de los algoritmos y problemas tratables · Práctica 2 · Caminos y circuitos: Euler, Hamilton y búsqueda de caminos · Tema 5 Clases de complejidad: P, NP, PSPACE y EXPTIME · Tema 6 Reducciones polinómicas y el teorema de Cook-Levin · Práctica 3 · Verificadores y reducciones polinómicas
• Módulo 3 · NP-completitud en la práctica — Tema 7 Un catálogo de problemas NP-completos · Práctica 4 · Reducciones en acción: coloreado, recubrimientos y SUBSET-SUM · Tema 8 Algoritmos exactos para problemas intratables · Práctica 5 · Resolver SAT: preprocesado, búsqueda y codificaciones · Práctica 6 · Árboles de búsqueda: recubrimientos, 3-SAT y N reinas
• Módulo 4 · Aproximación y aleatorización — Tema 9 Algoritmos de aproximación · Tema 10 Algoritmos aleatorizados y clases probabilistas · Práctica 7 · Aproximar y aleatorizar: un estudio experimental

Cada tema trae un PDF propio con definiciones, teoremas y demostraciones comentadas, un notebook de entrenamiento con ejercicios autocorregibles y su solución, y una autoevaluación que desbloquea lo siguiente. Las prácticas combinan código (simuladores de AFD, AFN y máquinas de Turing, circuitos eulerianos y hamiltonianos, búsqueda de caminos, verificadores, reducciones entre SAT, CLIQUE, recubrimiento de vértices, coloreado y SUBSET-SUM, árboles de búsqueda, un resolutor DPLL, las N reinas en SAT, algoritmos aproximados y aleatorizados) y razonamiento formal (diseño de máquinas, demostraciones de corrección y de coste).

Trabajarás en Python 3, casi siempre con la biblioteca estándar y con networkx y matplotlib para grafos y gráficos, en local o en Google Colab. Dedicación estimada: 158 horas de temas y prácticas, más una hora de presentación (unas 10 horas semanales durante 16 semanas). Se aprueba con un 7/10 de nota final y al menos un 7/10 en cada práctica. Dirigido a estudiantes de ingeniería informática y a profesionales del software que quieran entender los límites de la computación. Requisitos: programación en Python, estructuras de datos y algoritmos básicos (recorridos de grafos, recursión), y matemática discreta (lógica proposicional, conjuntos, inducción y nociones de grafos).