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
        • Definiciones básicas
      • 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
      • Motivación
      • Formulación
    • 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
      • Conjuntos ralos
Bibliografía:

     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"