Este curso ofrece una introducción a los fundamentos teóricos de la computación, mediante el estudio formal de las capacidades y limitaciones de las máquinas computacionales.
El objetivo de este curso es que cada estudiante sea capaz de explicar los fundamentos teóricos de las máquinas computacionales, sus propiedades, capacidades y limitaciones, a partir de la formulación matemática de la teoría de la computación.
Durante este curso cada estudiante desarrollará habilidades para:
- Explicar la arquitectura y función de la Máquina de Turing, y las nociones de decidibilidad, reducibilidad, el Problema de la Parada y el Teorema de la Recursión.
- Describir y analizar la complejidad temporal y espacial de los problemas computacionales.
- Conocer y describir con ejemplos las distintas formas de hacer investigación en las Ciencias de la Computación: prototipado, prueba de teoremas y el método empírico.
| Objetivo específico | Eje temático | Desglose |
|---|---|---|
| 1 | La Máquina de Turing | Repaso de los conceptos y propiedades fundamentales de los autómatas de estado finito. Descripción formal de la máquina universal de Turing. Componentes y arquitectura: alfabeto, estados posibles, la cinta infinita, la unidad lectora-escritora, el conjunto de reglas. El ciclo de operación. |
| 1 | Teoría de la Computabilidad | Propiedades de los problemas y las máquinas. Decidibilidad y semidecidibilidad. Prueba por diagonalización. El Problema de la Parada. Reducibilidad. El problema de la incompletitud de Gödel. |
| 2 | Teoría de la Complejidad Computacional | Métricas temporales y espaciales. Clases de complejidad P, NP, L, NL, PSPACE, BPP, IP. Problemas completos. P vs NP. |
| 3 | Investigación en las Ciencias de la Computación | Prototipado, prueba de teoremas, el método empírico. |
[1] M. R. Genesereth y N. J. Nilsson. ((Logical Foundations of Artificial Intelligence)). Morgan Kaufmann (1987).
[2] J. E. Hopcroft, R. Motwani y J. D. Ullman. ((Introducción a la teoría de autómatas, lenguajes y computación)). Pearson - Addison Wesley, Madrid, España, 3a edición (2008).
[3] A. W. Roscoe. ((Understanding Concurrent Systems)). Springer (2010).
[4] J. Savage. ((Models of Computation. Exploring the power of computing)). Brown University Press (1998).
[5] Y. Shoham y K. Leyton-Brown. ((Multiagent Systems. Algorithmic, game theoretic, and logical foundations)). http://www.masfoundations.org (2011).
[6] M. Sipser. ((Introduction to the Theory of Computation)). PWS Publishing Company (1977).
[7] M. Sipser. ((Introduction to the Theory of Computation)). Thomson Course Technology, 2a edición (2005).
Este no es un documento oficial. Documentos oficiales se entregan en la secretaría de la escuela.