Siguiente:
Conceptos básicos
Un nivel arriba:
COMPUTABILIDAD Y COMPLEJIDAD
Anterior:
COMPUTABILIDAD Y COMPLEJIDAD
Contents
Contents
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
Semántica de los programas-
while
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
Numerabilidad de las funciones computables
Codificación de programas-
while
Primera lista de ejercicios
Primera lista de programas
Funciones recursivas primitivas
Conceptos básicos
Funciones elementales
Algunos otros esquemas de composición
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
Reiteración de funciones de apareamiento
Función
de Gödel
Nociones de divisibilidad
Teorema chino del residuo
Función
de Gödel
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
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
Teoremas de jerarquía
Ordenes de funciones
Definiciones básicas
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
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
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)
Ecuaciones diofantinas cuadráticas (EDC)
Divisibilidad simultánea de polinomios lineales (DSP)
DSP
Enteros algebraicos
Solubilidad de DSP
Algunos otros problemas
Tercera lista de programas
Complejidad en redes de Petri generalizadas
Nociones básicas
Ejemplo
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
Algunas inclusiones entre clases
Complejidad de Kolmogorov
Introducción
Presentación de la teoría
Complejidades condicionales
Incomprimibilidad
Descripciones auto-delimitadoras
Estimaciones de la complejidad
Kolmogorov
Propiedades
Bibliography
Guillermo Morales-Luna
2000-07-10