Responsable: | (-) |
Altres: | (-) |
Crèdits | Dept. |
---|---|
7.5 (6.0 ECTS) | CS |
Responsable: | (-) |
Altres: | (-) |
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.
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 |
|
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. |
|
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. |
|
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. |
|
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. |
|
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. |
|
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 |
|
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 |
(-)
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}
(-)