Teoria de la Complexitat (TC)
| Professors Responsables: |
ANTONI LOZANO BOJADOS (antoni lsi.upc.edu)
|
|
Crèdits: 6.0 (3.0 T 3.0 P 0.0 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
LPO
- Pre-requisit per la EI
|
|
|
MDIO1
- Pre-requisit per la EI
|
|
Objectius docents
La teoria de la complexitat estudia els problemes computacionals entesos
com objectes matemàtics que es poden analitzar i relacionar. És el terreny
on la computació, representada en classes de complexitat, es dóna cita amb
les aplicacions, els problemes. Té, per tant, un cert regust algorítmic, lògic
i combinatori.
Després de cursar aquesta assignatura, l'estudiant hauria de tenir, en
primer lloc, les intuïcions i les eines per esbrinar, donat un problema
concret, quina és la complexitat dels millors algorismes coneguts que el
resolen. En segon lloc, hauria de tenir una certa visió global de quina ha
estat l'evolució i quin és l'estat actual de l'àrea.
Programa
1. Preliminars
Problemes i algorismes. Notació.
Màquines de Turing deterministes, indeterministes i amb oracle.
2. Complexitat en temps i espai
Temps i espai en les màquines de Turing. Definicions.
Teoremes de compressió de cinta i acceleració lineal.
Constructibilitat en temps i espai.
Definició de les classes DTIME, NTIME, DSPACE i NSPACE.
Inclusions bàsiques.
Teorema de Savitch, d'Immerman/Szelepcsényi i de jerarquia.
3. Classes usuals
Definició de les classes més usuals en complexitat:
L, NL, P, NP, PSPACE, NPSPACE, E, NE, EXP i NEXP.
Inclusions.
4. La classe NP
Reduccions en temps polinòmic.
Completesa i dificultat.
Teorema de Cook.
Exemples de reduccions i de conjunts NP-complets.
Altres conjunts a NP: primalitat i isomorfisme de grafs.
Isomorfia i densitat dels NP-complets.
5. La classe P i les classes d'espai
Reduccions d'espai logarítmic.
Model de circuits.
Completesa a P del problema de l'avaluació de circuits.
Classes L, NL i PSPACE: problemes complets.
6. La jerarquia polinòmica
Definició i caracterització en termes de quantificadors.
7. Complexitat no uniforme
Classes definides amb funcions conselleres.
Caracterització de P/poly mitjançant circuits
polinòmics i clausures dels esparsos.
Relacions entre classes uniformes i no uniformes.
8. Classes probabilistes i de comptatge
Definicions i interrelacions bàsiques.
9. Altres temes d'interès
Presentació d'una línia de recerca actual en complexitat:
computació molecular, computació quàntica, complexitat
descriptiva, teoria de l'aprenentatge, etc.
Avaluació
A meitat de curs es reparteix a cada estudiant un article d'aparició
recent. Una de les darreres setmanes del curs (quan ja s'ha vist la teoria
necessària) es fan les presentacions públiques dels articles.
La nota es calcula a parts iguals entre:
(1) els exercicis proposats a classe i la nota de la presentació
(2) una prova bàsicament conceptual feta al final del quadrimestre
Càrrega
A partir del segon mes es lliura un exercici cada dues setmanes, per resoldre
fora de l'horari lectiu. Cap a meitat de curs s'assigna un article, que
l'estudiant haurà de presentar com si fos propi.
Bibliografia
Bibliografia bàsica
- BALCÁZAR, J.L., DÍAZ, J. i GABARRÓ, J. Structural complexity I Springer-Verlag, 1988
- PAPADIMITRIOU, C. Computational complexity Addison-Wesley, 1994
Bibliografia complementària
- GAREY, M. i JOHNSON, D. Computers and intractability, a guide to the theory of NP completeness Freeman, 1978
- KÖBLER, J., SCHÖNING, U. i TORÁN, J. The graph isomorphism problem: its structural complexity Birkhäuser, 1993
- KOZEN, D. The design and analysis of algorithms Springer-Verlag, 1991
- SIPSER, M. Introduction to the theory of computation PWS Publishing Company, 1997
Informació complementària
Les classes de problemes (3 crèdits del total de 6) es fan amb la
participació activa de l'estudiant, mitjançant la resolució i
discussió dels problemes en l'horari de classe, o amb la presentació
dels exercicis.
Les presentacions públiques dels articles s'organitzen en forma de
mini-congrés, és a dir, s'elabora un programa amb les xerrades,
que després és anunciat dins de la comunitat d'informàtica
teòrica de la UPC. D'aquesta manera, l'estudiant es pot fer una idea
de les tendències actuals en complexitat i de la manera en què es
dóna a conèixer la recerca a la comunitat científica.
|
