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 $\beta$ de Gödel
    • Nociones de divisibilidad
    • Teorema chino del residuo
    • Función $\beta$ 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