2014
2014
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Theory of Complexity
| Informazioni generali | |||
| Corso di Laurea | Computer Science | Percorso | Computer Science |
|---|---|---|---|
| CFU | 6 | Università | CAMERINO |
| Ore di didattica frontale per CFU | 7 | Settore Scientifico Disciplinare | INF/01 |
| Commento | A scelta per il curriculum BIS (Business Information Systems) | ||
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
- *
CAL - Calcolabilita'
Recall of Basic Computability Theory. The cost of computing. How to measure it: time, space, energy, other parameters. Complexity of a computation. Feasible problems. -
COM - Complessita'
Time: the class P, the thesis od Edmond-Cook-Karp, the class NP, the question P=NP, NP-complete problems, SAT, the Cook-Levin Theorem. NP-intermediate problems. The polynomial hierarchy. -
COM - Complessita'
Space: the classes L, NL, PSPACE. NL-complete problems and PSPACE-complete problems, QSAT. The Savitch Theorem. Oracles and the Baker-Gill-Solovay theorem. -
COM - Complessita'
Probabilistic procedures. The classes BPP, RP and ZPP. ZPP as the class of problems solvable in average polynomial time. -
COM - Complessita'
Interactive procedures. Arthur and Merlin. AM and MA. The class IP. Shamir's Theorem. The complexity zoo. -
COM - Complessita'
Complexity and circuits. Logical gates. The problem of unique satisfiability.
(*) Le sottoaree con asterisco sono quelle che il GRIN auspica facciano parte in via prioritaria dei sillabi degli insegnamenti assegnati all?area stessa
