Computabilidad y Complejidad
CONTENIDO
TEMARIO (Tentativo)
Objetivos: 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.
Descripció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.
Temario:
-
- Conceptos básicos
- Pruebas por
contradicción
- Inducción matemática
- Inducción
numérica
- Inducción
recurrente
- Enumeración
de Cantor
- Lenguajes formales
de programación
- Programas-while
- Macros
- Asignamientos
- Operaciones
aritméticas
- Pruebas
compuestas
- Macros
de programación
- Semántica
de los programas-while
- Reglas
de transformación
- Funciones computables
- Máquinas de
Turing
- Introducción
a las máquinas de Turing
- Computaciones
en máquinas de Turing
- Modelos
restringidos de máquinas de Turing
- Computabilidad-Turing
- Tesis de Church
- Propiedades
de cerradura de funciones computables
- Esquema
de composición
- Esquema
de minimización
- Esquema
de minimización acotada
- Esquema
de recursión
- Esquema
de recursión acotada
- Computabilidad
de los esquemas
- Numerabilidad
de las funciones computables
- Codificación
de programas-while
- Escritura
de variables
- Codificación
de símbolos
- Codificación
de programas y tiras de símbolos
- Observaciones
sobre la codificación
- Primera lista
de ejercicios
- Primera lista
de programas
- Funciones recursivas
primitivas
- Conceptos básicos
- Dos esquemas
de reiteración
- Funciones elementales
- Algunos
otros esquemas de composición
- Esquemas
de sumatoria y productos acotados
- Esquema
de transformación explícita
- Clase de
funciones elementales
- Jerarquía de
Grzegorczyk
- Una escala
de funciones
- Propiedades
de la escala
- Niveles
de la jerarquía
- Función de Ackermann
- Segunda lista
de ejercicios
- Funciones de apareamiento
y universalidad
- Funciones de
apareamiento
- Algunas
funciones de apareamiento
- Exceso
de cuadrados
- Exceso
de potencias de 2
- Codificación
con primos
- Reiteración
de funciones de apareamiento
- Función beta
de Gödel
- Nociones
de divisibilidad
- Algoritmo
de Euclides
- Teorema
chino del residuo
- Función
de Gödel
- Codificación
con la función
- Codificación
de secuencias
- Universalidad
- Codificación
de programas por números
- Numerabilidad
de la clase de máquinas de Turing
- La noción
de ``Universalidad'' Máquina Universal de Turing
- Universalidad
en programas-while
- Teoría de la recursividad
- Funciones recursivas
- Problema de
la parada
- Decidibilidad
- Conjuntos
decidibles
- Proyecciones
- Problema
de la parada (otra vez)
- Teoremas de
recursión
- Teoremas de
autorreproducción
- Virus en programas-while
- Definiciones
básicas
- Matrices
infinitas
- Teoremas
de recursión
- Construcción
de virus
- Malas noticias:
No hay detección universal de virus
- Tercera lista
de ejercicios
- Segunda lista
de programas
- Irresolubilidad
- Teorema de Rice
- Problema de
la correspondencia de Post
- Presentación
del Problema de Post
- Una aplicación
de PCP
- Irresolubilidad
de problemas en GLC
- Reducción
de problemas al problema de la parada
- Problema
de ``gramáticas ajenas'' (PA)
- Problema
de totalidad (PT)
- Problema
de equivalencia (PE)
- Problema
de inclusión (PI)
- Problema
de regularidad (PR)
- Problema
de regularidad contenida (PRC)
- Algunos otros
problemas irresolubles
- Problema
de complemento libre de contexto (PCLC)
- Problema
de intersección libre de contexto (PILC)
- Irresolubilidad
en la Aritmética Aritmética de Peano
- Demostrabilidad
- Interpretaciones
- Incompletitud
- El teorema de
Goodstein
- Representación
formal en base m
- Sucesión
de Goodstein
- Ilustración
del Teorema de Goodstein
- Algunos
valores explícitos de la función
- La conjetura
de Catalan
- Clasificación
de problemas irresolubles
- Computaciones
con oráculos
- Enumerabilidad
recursiva relativa a oráculos
- Teoremas de jerarquía
- Ordenes de funciones
- Algunas clases
de funciones
- Constantes
- Funciones
polinomiales
- Funciones
exponenciales
- Funciones
logarítmicas
- Funciones
polilogarítmicas
- Límites inferiores
- Clases de problemas
- Problemas de
decisión
- Problemas de
solución
- Comprobadores
y resolvedores
- Complejidades
de tiempo y espacio
- Dispositivos
de cómputo
- Tiempos
y espacios
- Jerarquía en
espacio
- Jerarquía en
tiempo
- Algunas relaciones
entre clases
- Jerarquías en
clases no-deterministas
- Teorema de Borodin
y consecuencias
- Completitud-NP
- Clases de problemas
- Reducibilidades
- Problemas difíciles
y completos en clases polinomiales
- Formas proposicionales
y el teorema de Cook
- Formas
booleanas
- El primer
problema completo-NP
- Otros
problemas completos-NP en formas proposicionales
- Algunos problemas
principales completos-NP
- Programación
lineal
- Combinatoria
- Atercetamientos
- Atercetamientos
(3DM): Partición
- Problemas
en gráficas
- Problemas
de asignación de tareas
- Problemas
con varios procesadores
- Problemas
con un solo procesador
- Problemas
en teoría de números
- Congruencias
cuadráticas (CC) .
- Residuos
cuadráticos en general
- Procedimiento
de reducción de 3SAT
- Ecuaciones
diofantinas cuadráticas (EDC) .
- Ecuaciones
diofantinas en general
- Divisibilidad
simultánea de polinomios lineales (DSP) .
- DSP
Enteros algebraicos
- Solubilidad
de DSP
- Algunos
otros problemas
- Incongruencias
simultáneas
- Comparación
de factores de divisibilidad
- Divisibilidad
de expresiones exponenciales
- Ecuaciones
algebraicas en el campo de Galois
- No-divisibilidad
de un producto de polinomios
- MCD
no trivial
- Raices
de módulo 1
- Número
de raices para un producto de polinomios
- Soluciones
periódicas de relaciones recurrentes
- Tercera lista
de programas
- Complejidad en
redes de Petri generalizadas
- Nociones básicas
- Problemas de
acotación
- Problemas de
acceso
- Problema de
acceso generalizado
- Algoritmos probabilísticos
y su jerarquía
- 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
- Introducción
- Complejidades
condicionales
- Teorema de Invarianza
- Incomprimibilidad
- Descripciones
auto-delimitadoras
- Estimaciones
de la complejidad Kolmogorov
Bibliografía:
- Aho, Ullman: Foundations of computer science, W. H. Freeman & Co.,
1992
- Aho, Hopcroft, Ullman: The design and analysis of computer algorithms,
Addison-Wesley, Reading, MA., 1974
- Anderson, Turing et al: Mentes y máquinas, en la colección
Problemas científicos y filosóficos, Universidad Nacional
Autónoma de México, 1970
- Arbib, Kfoury, Moll: A basis for theoretical computer science, Springer-Verlag,
1981
- Balcázar. Díaz, Gabarró: Structural complexity I,
Springer-Verlag, 1988
- Barwise: Handbook of mathematical logic, North-Holland, 1977
- Chaitin: Algorithmic information theory, Cambridge University Press,
1987
- Cutland: Computability: An introduction to recursive function theory,
Cambridge University Press, 1980
- Davis: Computability and unsolvability, Mc-Graw Hill, 1958
- Davis: The undecidable, Raven Press, 1965
- Epstein: Degrees of unsolvability: Structure and theory, Lect. Notes
in Comp. Sci. Nr. 759, Springer-Verlag, 1979
- Garey, Johnson: Computers and intractability: A guide to the theory of
NP-completeness, Freeman, 1979
- Grzegorczyk: Some classes of recursive functions, Rosprawy matematyczne
Nr. 4, IMPAN, Warszawa, 1953
- Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit, Springer-Verlag,
1965 (English translation: Enumerability, decidability and computability,
Springer-Verlag, 1969, traduzione italiana Enumerabilitá, decidabilitá
computabilitá, Boringhieri, 1975)
- Hinman: Recursion-theoretic hierarchies, Springer-Verlag, 1978
- Hofstadter: Gödel, Escher, Bach: An eternal golden braid, Vintage
Books, 1980
- Hopcroft, Ullman: Introduction to automata theory, languages and computation,
Addison-Wesley, 1979
- Johnson: A catalog of complexity classes, in van Leeuwen.
- Johnson: The NP-completeness column: an ongoing guide, serie de artículos
publicados periódicamente en Journal of Algorithms, de 1981
a 1988.
- Kalmár: An argument against the plaussibility of Church's thesis,
in Heyting (ed.) Constructivity in matematics: Proceedings of the colloquium
held in Amsterdam, 1957, North-Holland, 1959
- Kfoury, Moll, Arbib: A programming approach to computability, Springer-Verlag,
1982
- Kleene: Introducción a la metamatemática, Col. Estructura
y Función, Ed. Tecnos, Madrid, 1974
- Lewis, Papadimitiou: Elements of the theory of computation, Prentice
Hall, 1981
- Malc'ev: Algorithms and recursive functions, Wolters-Noordhoff Publishing
Co, 1970
- Machtey, Young: An introduction to the general theory of algorithms,
North-Holland, 1978
- Papadimitiou, Steiglitz: Combinatorial optimization: Algorithms and complexity,
Prentice-Hall, 1982
- Penrose: The emperor's new mind: Concerning computers, minds and the
laws of physics, Oxford University Press, 1989
- Rogers: Theory of recursive functions and effective computability,
McGraw-Hill, 1967
- Rosenblueth: Mente y cerebro: Una filosofía de la ciencia,
Siglo XXI, 1970
- Savage: The complexity of computing, Wiley, 1976
- Salomaa: Formal languages, Academic Press, 1973
- Shanon, McCarthy (ed's): Automata studies, Princeton University Press,
1956
- Shoenfield: Degrees of unsolvability, North-Holland, 1971
- Soare: Recursively enumerable sets and degrees of unsolvability,
Springer-Verlag, 1987
- van Leeuwen (ed.): Handbook of theoretical computer science, North-Holland,
1990
- Yasuhara: Recursive function theory and logic, Academic Press, 1990
Retorno al inicio de esta página
Notas del curso
El libro "Computabilidad y complejidad", de Guillermo Morales-Luna,
es el texto del curso. Está disponible en varios formatos: PDF ,
y HTML.
Varios cuadernillos de Mathematica para practicar con los materiales
del curso estarán disponibles.
Retorno al inicio de esta página
Guillermo Morales-Luna
gmorales@cs.cinvestav.mx
(+52)-5747-7000 (Trabajo)
(+52)-5747-7002 (Fax)
Ultima actualización: Enero de 2008
Retorno a la página "domicilio"