Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Complexitat Computacional (COM)

Crèdits Dept.
7.5 (6.0 ECTS) CS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

La teoria de la complexitat estudia els problemes computacionals entesos com objectes matemàtics que es poden analitzar, relacionar i classificar en funció dels recursos computacionals requerits per a la seva resolució.
És el terreny on s'analitzaran els límits de la computació, representada en classes de complexitat i és on es donen cita els problemes i algorismes.
L'objectiu del curs és aprofondir en el coneixement de la dificultat inherent dels problemes i potenciar l'habilitat de l'estudiant per classificar problemes respecte de diferents criteris basats en la consideració de diferents recursos computacionals.

Objectius Específics

Coneixements

(Informació no introduïda)

Habilitats

(Informació no introduïda)

Competències

(Informació no introduïda)

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Classes de Complexitat bàsiques. Temps i Espai.
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Breu repàs de Maquines de Turing.
Temps de computació i espai de computació
Definició de les classes de TIME i SPACE.
Classes L, NL, P, NP PSPACE i EXP.
Relacions entre classes.

2. Reductibilitat i completesa.
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Reduccions.
Propietats de tancament de les classes respecte de reductibilitats.
Completesa.

3. NP-completesa.
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Problemes naturals:
-Satisfactibilitat de fórmules booleanes,
-Subgrafs,
-Particions,
-Recorreguts,
-Repartiment de recursos.

4. Problemes d'optimització. La Jerarquia Polinòmica.
T      P      L      Alt    L Ext. Est    A Ext. Total 
10,0 5,0 0 0 0 15,0 0 30,0
Problemes naturals.
Turing reductibilitat.
La jerarquia polinòmica.
Aproximabilitat.

5. Problemes de jocs i de comptatge
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
PSPACE-complets.
Complexitat de jocs com Go, Escacs, Dames.
La permanent.

6. Algorismes i Classes Probabilistes
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Exemples: Identitat de polinomis i aplicacions.
Classes RP i BPP.
Reducció d'error.
BPP, circuits polinòmics i la Jerarquia Polinòmica.

7. Sistemes Interactius de demostracions
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Exemples: grafs no isomorfs.
Classes AP i IP.
Protocol per a la Permanent.
Protocol per a QBF: IP=PSPACE.
Aplicacions: informació zero en criptografia.
Isomorfisme de grafs i no-completesa

8. Espai Logarítmic. Computació paral.lela
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Problemes naturals: Acessibilitat en grafs.
Espai Logarítmic: L i NL.
Models de Computació paral.lela: PRAM i Circuits.
Classes NC i AC


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
46,0 29,0 0 0 0 75,0 0 150,0
Hores addicionals dedicades a l'avaluació 3,0
Total hores de treball per l'estudiant 153,0

Metodologia docent

(-)

Mètode d'avaluació

Problemes:
La part de problemes consistirà a resoldre una petita llista de problemes que s'assignarà a cada estudiant (o cada petit grup de treball) al finalitzar cada tema de l'assignatura. Els estudiants podran discutir a classe de problemes els dubtes que se'ls hi poden anar presentant, però es considera un treball personal (o per grups) que s'haurà de completar a les seves hores d'estudi. En general seran problemes que la seva solució requerirà, a part dels conceptes que s'han anat introduint, l'ajut de bibliografia específica. Desprès d'un marge de temps raonable (entre 1 i 2 setmanes) hauran d'entregar les seves solucions i presentar a classe de problemes alguna d'elles, si es considera oportú (quan s'amplien els coneixements introduits en el tema actual i sobre tot quan el treball és en grup).

Examen:
També hi haurà un examen final en el que s'avaluarà si l'estudiant ha assolit els coneixements més generals introduits durant tot el curs. La nota final de l'assignatura es calcula a partir de la nota de problemes P i de la nota de l'examen final E de la manera següent:

Nota Final= MAX {(P+E)/2,E}

Bibliografía bàsica

  • Papadimitriou, C. Computational complexity, Addison Wesley, 1994.
  • Balcázar J. L., Díaz J., Gabarró J. Structural Complexity I, Springer-Verlag, 1995.
  • Sipser, M. Introduction to the theory of computation, 2nd Edition, PWS publishing Company, 2005.

Bibliografía complementària

(Informació no introduïda)

Enllaços web

(Informació no introduïda)

Capacitats prèvies

(-)


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil