Computación teórica

¿Por qué un programa que ordena un millón de datos tarda un segundo y otro, que hace lo mismo, tarda un día? ¿Cómo se demuestra que un algoritmo es correcto y no solo que «funciona en los ejemplos»? Este es un curso de nivel grado en ingeniería dedicado a diseñar y analizar algoritmos eficientes: aprenderás a medir su coste con recurrencias y el teorema maestro, a dominar las grandes técnicas de diseño —divide y vencerás, algoritmos voraces, programación dinámica y vuelta atrás—, a usar las estructuras de datos que las hacen rápidas (montículos y conjuntos disjuntos) y a resolver los problemas clásicos sobre grafos: recorridos, árboles de expansión mínima, caminos mínimos y flujo máximo. Cada algoritmo se acompaña de su demostración de corrección y de una medición empírica que confirma el análisis.

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

• Módulo 1 · Análisis de algoritmos y divide y vencerás — Tema 1 Análisis de algoritmos: coste, corrección y medición · Tema 2 Recurrencias y el teorema maestro · Tema 3 Divide y vencerás · Práctica 1 · Medir y predecir: divide y vencerás bajo la lupa
• Módulo 2 · Estructuras de datos, grafos y algoritmos voraces — Tema 4 Montículos, conjuntos disjuntos y análisis amortizado · Tema 5 Grafos: representación y recorridos · Tema 6 Algoritmos voraces y su corrección · Tema 7 Árboles de expansión mínima y caminos mínimos · Práctica 2 · Redes eficientes: árboles de expansión y caminos mínimos
• Módulo 3 · Programación dinámica — Tema 8 Programación dinámica · Práctica 3 · De la recurrencia a la tabla: programación dinámica aplicada
• Módulo 4 · Flujo en redes y búsqueda exhaustiva — Tema 9 Flujo máximo y emparejamientos · Tema 10 Vuelta atrás: búsqueda exhaustiva con podas · Práctica 4 · Asignar y explorar: flujo máximo frente a vuelta atrás

Cada tema trae un PDF propio con el esquema de cada técnica, algoritmos en pseudocódigo y en Python, demostraciones de corrección y de coste comentadas y ejemplos resueltos paso a paso; un notebook de entrenamiento con ejercicios autocorregibles, que entregas para que lo revise el tutor (su solución se abre 7 días después de tu entrega), y una autoevaluación que desbloquea lo siguiente. Las prácticas combinan implementación (ordenación y selección instrumentadas, montículos y union-find propios, Kruskal, Prim, Dijkstra y Bellman-Ford, tablas de programación dinámica con reconstrucción, Edmonds-Karp y vuelta atrás con podas), análisis formal (invariantes, recurrencias, argumentos de intercambio, subestructura óptima) y estudio experimental (tiempos y contadores en escala log-log frente a la predicción teórica).

Trabajarás en Python 3 con la biblioteca estándar, networkx para generar grafos y comprobar resultados y matplotlib para las gráficas, en local o en Google Colab. Dedicación estimada: 129 horas de temas y prácticas, más una hora de presentación (unas 10 horas semanales durante 13 semanas). Dirigido a estudiantes de ingeniería informática, matemáticas o titulaciones afines y a profesionales del software que quieran escribir código más rápido y razonar con rigor sobre él, también como preparación de entrevistas técnicas y programación competitiva. Requisitos: programación en Python (incluida la recursión), estructuras de datos básicas (listas, pilas, colas, árboles, tablas hash), matemática discreta (inducción, sumatorios, logaritmos) y nociones de grafos. Se complementa con el curso Teoría de la Complejidad Computacional, que estudia qué hacer cuando no existe un algoritmo eficiente.

¿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, que entregas para que lo revise el tutor (su solución se abre 7 días después de tu entrega), 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).