Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Education
Complessità computazionale
Complessità computazionale

Nome Corso: Complessità Computazionale

Obiettivi e contenuti:

Lo studente acquisterà familiarità con le principali tecniche di riduzione tra problemi, e con le tecniche utilizzate per determinare la classe di complessita' di un problema computazionale. In particolare, verranno forniti i concetti fondamentali relativi alla teoria della computabilita',  della complessita' computazionale in termini di spazio e di tempo, e agli algoritmi di approssimazione.

 Programma esteso:

- Elementi di computabilità

- Classi di complessità computazionale: P e NP

- Riduzione tra problemi: problemi NP-completi

- Algoritmi di approssimazione

- Classi di complessità nello spazio

- Classi di complessità in spazio sub-lineare

Testo consigliato: C. Papadimitriou, Computational Complexity, Addison-Wesley

Tipo di esame: scritto

***********************************************************************************

Course name: Computational Complexity

Aims:

The student will become familar with the main techniques for reduction among problems and to evaluate the complexity of a computational problem.  The basic notions of computability, computational complexity (in space and time), and approximation algorithms will be presented.

Program:

- Computability theory elements

- Computational complexity classes P and NP

- Reduction between problems: NP-complete problems

- Approximation algorithms

- Space-complexity classes

- Sub-linear space complexity classes

Text: C. Papadimitriou, Computational Complexity, Addison-Wesley

Examination: written exam

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 28/03/2011