Computabilidad y Complejidad
Objetivo:
Conocer los diversos paradigmas de computación formal, entre éstos las funciones recursivas. y las máquinas de Turing. Examinar las limitaciones de la noción de computabilidad y los criterios diversos de clasificación de problemas atendiendo a la complejidad de sus procedimientos de solución. Se presenta a las funciones recursivas siguiendo el enfoque de máquinas de Turing, de programas-while y el puramente formal. Luego se presenta los grados de irresolubilidad para pasar después las jerarquías temporal y espacial de los problemas tratables. Ya para terminar, presentaremos una colección de problemas completos-NP. Al último presentamos la noción de complejidad abstracta debida a Kolmogorov.
Contenido:
- Conceptos básicos
- Pruebas por contradicción
- Inducción matemática
- Enumeración de Cantor
- Lenguajes formales de programación
- Funciones computables
- Máquinas de Turing
- Tesis de Church
- Propiedades de cerradura de funciones computables
- Numerabilidad de las funciones computables
- Primera lista de ejercicios
- Primera lista de programas
- Funciones elementales
- Jerarquía de Grzegorczyk
- Función de Ackermann
- Segunda lista de ejercicios
- Funciones de apareamiento
- Función beta de Gšodel
- Universalidad
- Funciones recursivas
- Problema de la parada
- Decidibilidad
- Teoremas de recursión
- Teoremas de autorreproducción
- Virus en programas-while
- Tercera lista de ejercicios
- Segunda lista de programas
- Teorema de Rice
- Problema de la correspondencia de Post
- Irresolubilidad de problemas en GLC
- Algunos otros problemas irresolubles
- Irresolubilidad en la Aritmética Aritmética de Peano
- El teorema de Goodstein
- La conjetura de Catalan
- Clasificación de problemas irresolubles
- Computaciones con oráculos
- Enumerabilidad recursiva relativa a oráculos
- Ordenes de funciones
- Algunas clases de funciones
- Límites inferiores
- Clases de problemas: Problemas de decisión, problemas de solución
- Comprobadores y resolvedores
- Complejidades de tiempo y espacio
- Jerarquía en espacio
- Jerarquía en tiempo
- Algunas relaciones entre clases
- Jerarquías en clases no-deterministas
- Teorema de Borodin y consecuencias
- Clases de problemas
- Reducibilidades
- Problemas difíciles y completos en clases polinomiales
- Algunos problemas principales completos-NP
- Tercera lista de programas
- Nociones básicas
- Problemas de acotación
- Problemas de acceso
- Problema de acceso generalizado
- Algoritmos probabilísticos
- Expresiones polinomiales nulas
- Método de Monte-Carlo para probar primicidad
- Máquinas probabilísticas
- Máquinas del tipo 1
- Máquinas-p
- Computabilidad con mTp's
- Algunas inclusiones entre clases
- Complejidad de Kolmogorov
- Conjuntos ralos
Bibliografía:
1. Aho, Ullman: Foundations of computer science, W.H. Freeman & Co., 1992
2. Aho, Hopcroft, Ullman: The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974
3. Anderson, Turing et al: Mentes y máquinas, en la colección de problemas cientícos y filosóficos, Universidad Nacional Autónoma de México, 1970
4. Arbib, Kfoury, Moll: A basis for theoretical computer science, Springer-Verlag, 1981
5. Balcazar. Diaz, Gabarro: Structural complexity I, Springer-Verlag, 1988
6. Barwise: Handbook of mathematical logic, North-Holland, 1977
7. Chaitin: Algorithmic information theory, Cambridge University Press, 1987
8. Cutland: Computability: An introduction to recursive function theory, Cambridge University Press, 1980
9. Davis: Computability and unsolvability, Mc-Graw Hill, 1958
10. Davis: The undecidable, Raven Press, 1965
11. Epstein: Degrees of unsolvability: Structure and theory, Lect. Notes in Comp. Sci. Nr. 759, Springer
-Verlag, 1979.
12. Garey, Johnson: Computers and intractability: A guide to the theory of NP-completeness, Freeman, 1979
13. Grzegorczyk: Some classes of recursive functions, Rosprawy matematyczne Nr. 4, IMPAN, Warszawa, 1953
14. Hermes: Aufzahlbarkeit, Entscheidbarkeit, Berechenbarkeit, Springer-Verlag, 1965 (English translatio
n: Enumerability, decidability and computability, Springer-Verlag, 1969, traduzione italiana Enumerabili
t´a, decidabilit´a computabilit´a, Boringhieri, 1975)
15. Hinman: Recursion-theoretic hierarchies, Springer-Verlag, 1978
