Download ppt - Posgrado en Ciencia e Ingeniería de la Computación

Presentación del Área de Teoría de
la Computación en la UNAM
Sergio Rajsbaum
Instituto de Matemáticas, UNAM
Enero 29, 2004
La Presentación
¿Que es la Teoría de la Computación?
En general
– Definición
– Ejemplos de Problemas
– Lista de Temas
En la UNAM
– Tutores, sus temas y sus cursos
En pocas palabras
¿Que es la Teoría de la Computación?
Los cimientos del edificio
Entender
Definición de Teoría de la
Computación
Oded Goldreich, A Brief Introduction to the Theory of Computation
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.
Se Divide en Dos
I. Teoría de la Programación
Teoría de la
Computació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
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
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 aplicacionesmemoria 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
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?
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
Referencias
• 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
Teoría de la Computación
en la
UNAM
Tutores
• Francisco Hernández Quiroz
• Julio Peralta
• Sergio Rajsbaum
• David Rosenblueth
• Jorge Urrutia
• Carlos Velarde
semántica de lenguajes
lenguajes, prolog, autómatas
computo distribuido, algoritmos
lenguajes, inteligencia artificial, Prolog
geometría computacional, algoritmos
combinatoria, lenguajes, etc.
Cursos
(negritas este semestre)
•
•
•
•
•
•
•
•
•
•
Teoría de la complejidad
Algoritmos y estructuras de datos
Teoría de la computación
Geometría computacional
Cómputo distribuido
Teoría de la información
Lenguajes formales y autómatas
Especificación formal
Programación lógica
Programación funcional
Teoría del
cómputo
Teoría de
programación
Cursos Relacionados
(negritas este semestre, rojo otras partes de la UNAM)
• Matemáticas:
– lógica, lógica borrosa, probabilidad, estadística,
categorías, teoría de gráficas, combinatoria, álgebra,…
• Procesamiento de señales:
– Reconocimiento de patrones, proc. digital de
imágenes (2), proc. señales, sistemas adaptables
• Redes neuronales y sistemas adaptables (5)
• Modelación matemática y cómp. científico (4)
Conclusiones
¿Para qué estudiar
Teoría de la Computación?
• Una formación más sólida, un computólogo
más profesional
• Seguir adelante a un doctorado
• Dedicarse a la teoría de la computación en
investigación y docencia
¿Para qué estudiar
Teoría de la Computación?
FIN
Gracias por su atención