Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
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

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 28/03/2011