Complexitat ( COM )
| Crèdits: |
Departament: |
Tipus: |
Requisits: |
| 7.5 |
LSI |
Optativa per l'EI
|
|
ADA
- Pre-requisit per l' EI
|
|
|
TC
- Pre-requisit per l' EI
|
|
|
Professors
| Responsable: | M. Carmen Alvarez Faura (alvarez lsi.upc.edu). |
| Altres: | Dimitrios Thilikós Touloupas (sedthiilklsi.upc.edu)
M Jose Serna Iglesias (mjsernalsi.upc.edu). |
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. NP i co-NP. Problemes funcionals.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 3,0 |
2,0 |
0 |
0 |
0 |
5,0 |
0 |
10,0 |
|
NP i co_NP
Problemes naturals.
Versió funcional de la classe NP.
|
5. Aproximabilitat.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
10,0 |
0 |
20,0 |
|
Algorismes d'aproximació.
Problemes aproximables.
No-aproximabilitat.
|
|
6. Problemes d'optimització.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
10,0 |
0 |
20,0 |
|
Problemes naturals.
La jerarquia polinòmica.
|
|
7. 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.
|
|
8. Complexitat parametritzada
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
10,0 |
0 |
20,0 |
|
Problema parametritzat.
Classes de problemes.
Problemes complets.
|
|
9. Computació paral.lela: P versus NC.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
10,0 |
0 |
20,0 |
|
Models de computació paral.lela.
Computació Paral.lela: P versus NC.
Classes NC i AC.
Espai logarítmic.
|
| - Total per tipus |
T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 45,0 |
30,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
(Informació no introduïda)
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
(Informació no introduïda)
Bibliografía complementària
(Informació no introduïda)
Enllaços web
(Informació no introduïda)
Capacitats prèvies
(Informació no introduïda)
|
fib.upc.edu