¿Que es la Teoría de la Computación?

Sergio RajsbaumInstituto de Matemáticas, UNAM

¿Cómo explicar que es la Teoría de la Computación?

• Definiciones• Breve introducción histórica• Ejemplos de problemas• Lista y clasificación de temas

En pocas palabras¿Que es la Teoría de la Computación?

Los cimientos del edificio

El Edificio

Ciencia e Ingeniería de la Computación:• conglomerado de disciplinas científicas y de

ingeniería relacionadas -- estudio y aplicación del cómputo.

• Desde– mas puras y básicas disciplinas científicas dedicadas

a los fundamentos de la computación– hasta las de ingenierías dedicadas a aplicaciones

especificas.

La Teoría de la Computación Pretende

Entender

Estudiando modelos matemáticos relacionados al cómputo

¿Qué es el cómputo?

– El interés por diseñar métodos y dispositivos para cálculos aritméticos y lógicos es antiguo, pero

– sin entendimiento de la naturaleza del cómputo en general

¿ método, dispositivo?

10o Problema de Hilbert(Paris, 1900)

un método mediante el cual se puede determinar en un número finito de operaciones”

“diseñar

si un polinomio tiene unaraíz entera

En 1970 el matemático de Leningrado de 22 años resolvió el problema al probar que no existe tal método

(basado en trabajo de Davis, Putnam y Robinson)

→ Lo cual hubiera sido difícil de lograr para los matemáticosde 1900 con su noción intuitiva de algoritmo …

Yuri Matijasevic

Alan Turing

En 1936 con la Máquina de Turingformalizó la noción de algoritmo (no tan chico − a la edad de 24 años)

Simultáneamente Alonzo Church con la noción equivalente de lambda-cálculo y otros…

Máquina de Turing

Inicialmente:– en el estado q0

– con entrada w

Operación, según δ(q,x)=(q’,x’,d):– si esta en estado q sobre el simbolo x

– cambia a q’, sobre-escribe x’ y se mueve una posición (der. o izq.)

…

q

0 01 22

entrada

control finitofunción de transición δ

q0 =

Máquina de Turing

Formalmente, no es mas que un conjuntode quintupletas que describen la funciónde transición δ

¡La mayoría de las funciones no son computables!

El conjunto de Máquinas de Turing es numerable; el de todas las funciones no lo es

Tesis de Church-Turing

Noción intuitivade algoritmo

= Máquina de Turing

Máquina de Turing Universal

…

q0

0 01 22

Descripción de M

Simula a una Máquina de Turing M

Máquina de Turing Universal

Feynman’sLectures on Computation

El Problema de la Detención no es computable

La idea:

¿ Qué pasa si a una M le damos como entradaa ella misma ?!

• No es mas que una diagonalización a la Cantor

Dada una M y una entrada w, M se detiene con entrada w?

Reducciones

P1 ≤ P2

• Problema P2 es al menos tan difícil como P1

• si P1 se puede resolver con P2 como oráculo

≤ induce clases de equivalencia

Problema de ladetención

Problemasequivalentesa este

Jerarquíainfinita deproblemasno computables

El mundo de los problemas computables

1900 … 1936 … 1965

noción formalde cómputo ?

Máquina deTuring

complejidad

Medir tiempo y espacio como una función del tamaño de la entrada ‘65

Juris Hartmanis, Cornell Richard Stearns, U. Albany

Dado mas tiempo o espacio se pueden computar mas cosas

Clases de ComplejidadTiempo o Espacio

Jerarquíainfinita deproblemascomputables

Utilizando reducciones

Eficiente = Polinomial

Para que una solución sea útil

– Su costo en tiempo/espacio debe crecer polinomialmente con respecto al tamaño de la entrada

Razón de crecimiento de funciones típicas 10 20 30 50 60

n .00001 .00002 .00003 .00005 .00006n2 .0001 .0004 .0009 .0025 .0036n3 .001 .008 .027 .125 .2162n .001 1.0 17.9 m 35.7 d 366 s3n .059 58 m 6.5 a 2*108 s 1.3*1013 s

todas las entradas en segundos [GJ]excepto m=min, d=dias, a=años, s=siglos (Función en micro-segundos)

El Mundo de la Computación

Jerarquíainfinita deproblemasno computables

Jerarquíainfinita deproblemascomputables

polinomiales

clase P

La Clase NP

• Para el final de los 60’s, se sabía de una variedad de problemas prácticos para los cuales no había solución polinomial

• Todos tienen un espacio exponencial de soluciones posibles

• Todos se pueden verificar en tiempo polinomial• Ejem: Encontrar un ciclo que pase por todos los

vértices de una gráfica

¿ P = NP ?

EXP

NP

P

Una de las 7 preguntasdel Premio del Milenio del Clay Mathematics Institutecon $1,000,000

EXP

NP

P

Resulta que los problemas prácticos mencionados, son los mas difíciles dentro de NP

NP-completos

El 1er problema NP-completo

Stephen Cook, TorontoProbado en 1971

Leonid Levin, BUProbado en 1973

SAT:Si un predicado booleano se puede satisfacer

)()()( 43132141 xxxxxxxx ∨∨¬∧¬∨¬∨∧∨

En ‘73 ocho problemas centrales en combinatoria probados NP-completos

• Reducciones: • Si P es NP-completo,• P’ es NP y P ≤ P’ ent. • P’ tambien

Richard Karp

Y Karp mencionó tres en NP sin lograr probarlos NP-completos

• Isomorfismo de gráficas • Primalidad• Programación lineal

EXP

NP

P

NP-completos

?

P ≠ NP =>num. ∞ de clases, inclusivealgunas no comparables entre si

Y Karp mencionó tres en NP sin lograr probarlos NP-completos

• Isomorfismo de gráficas • Primalidad• Programación lineal Siguieron abiertos hasta

’79 cuando aparece el libro de Garey-Johnson

PL en P ’84, por Karmarkar

Prim en P ’02, por Agarwal y estudiantes Saxena, Kayal

Narendra KarmarkarNitin Saxena Neeraj KayalManinda Agarwal(der a izq)

Isomorfismo de Gráficas Sigue Abierto

• Probablemente no en P

• Probablemente no sea NP-completo

─ es sensitivo localmente: si existe un isomorfismo, y se cambia un poquito la gráfica, deja de haberlo

─ si lo fuera se colapsa la jerarquía polinomial

Ejemplos clásicosP NP-completo

Camino mas corto entre u,v Camino mas largo entre u,v

Cubrir vértices con el menor número de aristas

Cubrir aristas con el menor número de vértices

Apareamiento de aristas Apareamiento de 3-aristas

Digráfica equivalente mínima(preserva conectividad entre todo u,v)

Subgráfica equivalente mínima

¿G es k-coloreable? G de comparabilidad; G de grado ≤ 3

G arbitraria:Para toda 3≤k fija; para k=3 en gráficas planas

¿Que es la Teoría de la Computación?

Pero volvamos a nuestra pregunta original

Se Divide en Dos

I. Teoría de la Programación– Estudiar los lenguajes para implementar

los cómputos

II. Teoría del Cómputo– Entender la naturaleza del cómputo, sus

posibilidades y limitaciones– Y el objeto del cómputo, la

información

Teoría de la Computación

I. Teoría de la Programación

• Modelos de cómputo• Lenguajes de programación• Semántica de lenguajes• Estilos de programación- Lógica, funcional…• Concurrencia• Especificación y verificación• Lógica y computación• Representación del conocimiento, bases de

datos

II. Teoría del Cómputo

El estudio de la propiedades generales del cómputo, ya sea

natural, artificial, o imaginario

• ¿Qué es un dispositivo de cómputo?– Secuencial, paralelo, distribuido, biológico, quántico

• ¿Cuál es el costo de un cómputo?– Tiempo, espacio, comunicación, tamaño del programa

• ¿ Qué se puede computar eficientemente y que no?– Ciclo mas corto vs. ciclo mas largo

• ¿ Como clasificar a todos los problemas de acuerdo a su dificultad?– Una jerarquía infinita y densa de clases de complejidad

• ¿ Qué no se puede computar?– Si un programa es correcto o no

• ¿ Qué es la información?– Como se mide, como se comprime y que tanto, – cual es la información de 01010101010101010 vs. 00101111000101100

Entender mejor el mundo, desde nuestra

perspectiva de computólogos

El Dilema del Esquiador

No sabe cuantos días va a querer esquiar. ¿Comprar o Rentar?

• Renta de esquís cuesta $1 por día. Comprarlos $10.• Lo óptimo es rentar hasta el día 10, y luego comprar

Análisis de Algoritmos En-Linea

¿donde estuvo la computadora? Pero hay aplicaciones- memoria cache

Mas Ejemplos:• Aparentemente hay funciones fáciles de calcular

pero difíciles de invertir (cripto)– e.g. multiplicar vs. factorizar

• Aparentemente hay problemas mucho mas fáciles de verificar que de resolver (P vs NP)– e.g. partir un conjunto de pesas en dos subconjuntos

que pesen lo mismo • La aleatoriedad puede ser expandida

arbitrariamente– usar una semilla chica para generar números

pseudoaleatorios• Una prueba de un enunciado puede no enseñarte

nada mas que la validez del enunciado – e.g este mapa se puede colorear con k colores

Y mas Ejemplos:

• Pruebas holográficas– Forma en la cual cualquier prueba puede ponerse, tal

que cualquier error se puede detectar (probabilisticamente) viendo solo una fracción pequeña de ella

– Pruebas tradicionales tiempo cuadrático (en su tamaño); estas toman tiempo polilogarítmico

– El log2 del numero de átomos en el universo es < 300 !

• Robótica– Un agente sin memoria puede moverse sobre una

gráfica y detectar su conexidad

Jorge Urrutia

Computación molecular:

• Solución de problemas NP completos – usando paralelismo masivo con DNA

• Diseño de drogas inteligentes– midiendo y corrigiendo la expresión genética

Ricardo Strausz

Computación Distribuida

Ejecuciones

Las ejecuciones de un algoritmo distribuido preservanLa topología de las entradas posibles, dependiendo del nivel de tolerancia a fallas del sistema

Entradas

Ejemplos muy prácticos

• El dilema de la memoria cache– Se tiene una cache (rápida pero cara) para k

páginas– Se va llenando con páginas del disco (lento

pero barato)– Una vez llena, cuando se pide una página que

no esta en el cache ¿cual sacar? La que haya estado en la memoria mas tiempo

Cache en el Web

• Poner copias de páginas usadas en lugares estratégicos de la Red

• caches en diversas partes de Internet

• Akamai, compañía fundada por un profesor de teoría de MIT T. Leighton y su alumno

Google

• Búsqueda basada en la importancia de una página: una liga de A a B se interpreta como un voto de A a B. Se obtiene la importancia de la página resolviendo una ecuación de + 500 millones de variables y 200 millones de términos

• Más de 60 doctores, además de asesores como R. Motwani, J. Ullman, profesores de teoría de Stanford

• “Google bombing”» NYT January 22, 2004

• En el Web: “Theoretical Computer Science On The Web”• Handbook of Theoretical Computer Science

– Vol. A: Algorithms and Complexity– Vol. B: Formal Models and Semantics

• Revistas: Journal of the ACM• Congresos: ACM STOC, IEEE FOCS, ICALP

• Artículos:– Goldreich, A Brief Introduction to the Theory of Computation

Referencias

• Sipser, Intro. Theory of Computation• Garey-Johnson, Computers and Intractability• Schoning, Pruim, Gems of Theoretical CS• Hromkovic, Theoretical CS• Kozen, Theory of Computation• Goldreich, Computational Complexity: a

Conceptual Perspective

Libros

Conclusiones

• De una Máquina de Turing a muchas

• ¿Para que la Teoría de la Computación ?

Ramon Llull Mallorca, 1232-1316

• Ars Magna, para automatizar todo el razonamiento

If understanding followed no rule at all, there would be no good in the understanding nor in the matter understood, and to remain in ignorance would be the greatest good

The Hundred Names of God

Ramon Llull Mallorca, 1232-1316

• En realidad, con el Ars Magna, pretendía apoyar la comunicación intercultural entre cristianos, judíos y musulmanes

• Una herramienta para discusión mediante comunicación, en lugar de mediante la fuerza

• La verdad no puede ser hallada mediante cómputo, sino mediante comunicación

Gottfried LeibnizLeipzig, 1646-1716

• Descubrió el sistema binario• Buscaba un alfabeto para todo el

pensamiento humano y un cálculo para manipular estos símbolos

Compartió el sueño de Llull la coexistencia pacifica entre personas de diferentes culturas, religiones y nacionalidades

Lo ambicioso del plan de la formalización de todo el razonamiento humano

Si resultara que la lógica básica de una máquina diseñada para la solución numérica de ecuaciones diferenciales coincidiera con la lógica de una máquina para sacar cuentas de una tienda comercial, me parecería esto la coincidencia más sorprendente que jamás me haya encontrado

Howard Aiken, 1956

El Entusiasmo del sueño de la comunicación

• Por 1era vez, las redes telegráficas de Europa y Norteamérica se conectaron, mediante un cable submarino agosto 5, 1858

“A Thread Across the Ocean” Steele

El Entusiasmo del sueño de la comunicación

• Celebraciones al borde de la histeria

It is impossible that old prejudices and hostilities should longer exist, while such an instrument has been created for the exchange of thought between all the nations of the world

Briggs, Maverick 1858

Y el Entusiasmo Continua

• Michael Dertouzos cuando fuera jefe del LCS de MIT en 1997

A common bond reached through electronic proximity may help stave off future flareups of ethnic hatred and national breakups

Libro “What Will Be”

¿ Para qué estudiarTeoría de la Computación?

¿ Para qué estudiarTeoría de la Computación?

• Una formación más sólida, un computólogo más profesional

• Problemas matemáticos interesantes• Mejorar aplicaciones

When you want to build a ship,then do not drum the men togetherin order to procure wood,to give instructions or to distribute the workbut teach them longing for the wide endless

sea.A. de Saint-Exupéry

Para qué estudiarTeoría de la Computación?

• Una formación más sólida, un computólogo más profesional

• Desarrollo y uso de herramientas complejas• Seguir adelante a un doctorado• Dedicarse a la teoría de la computación en

investigación y docencia• Evitar vergüenzas …

Autoexamen de Conciencia (lenguajes)

¿Hay cosas programables en unos lenguajes pero no en otros?

Autoexamen de Conciencia (computadoras)

¿Hay cosas que unas computadoras pueden hacer pero no otras?

F I N

Gracias por su atención