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
   
Modelli di Calcolo e Complessità Computazionale
Docente
Giancarlo Mauri
Data e luogo

Inizio corso: 10 dicembre 2008, ore 14.30 presso la Sala Seminari.

 A seguire le lezioni si svolgeranno secondo il seguente calendario, dalle 14.30 alle 18.30 presso la Sala Seminari del Dipartimento.:

  • 08.01.2009
  • 15.01.2009
  • 22.01.2009
  • 29.01.2009
  • 05.02.2009
  • 12.02.2009
  • 19.02.2009

 

Motivazioni e obiettivi
Programma
- Macchine di Turing deterministiche, non deterministiche e alternanti.
- Complessità in tempo e spazio: classi di complessità "centrali" (L, NL, P, NP,     PSPACE, ...) e loro relazioni.
- Riducibilità tra problemi; riducibilità polinomiale e problemi NP completi; teorema di Cook.
- Tecniche di dimostrazione di NP completezza.
- Complessità dei problemi di conteggio; la classe #P.
- Macchine con oracolo e classi di complessità relativizzate
- Macchine di Turing probabilistich
- La classe NC. Problemi aperti
- Altre nozioni di complessità: complessità di Kolmogorov
- Modelli di calcolo "non convenzionali":
  •         Automi cellulari
  •         DNA computing
  •         Sistemi a membrane
  •         Quantum computing
Modalità di svolgimento
Lezioni frontali e seminari su temi concordati.
Modalità d’esame
Seminario su argomento concordato
Materiale didattico
Lucidi delle lezioni
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 02/05/2012