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
   
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
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 02/05/2012