Presentare le classi di complessità relative ai nuovi paradigmi computazionali. Al termine del corso gli studenti dovrebbero essere in grado di confrontare il potere computazionale dei nuovi paradigmi di calcolo con il potere computazionale dei paradigmi consolidati.
scheda docente materiale didattico
Complessità del Calcolo Randomizzato.
Complessità del Quantum Computing.
Programma
Paradigmi di complessità per Big Data e Cloud Computing: la classe Pspazio, Pspazio-completezza, teorema di Savitch, le classi L e NL, NL-completezza.Complessità del Calcolo Randomizzato.
Complessità del Quantum Computing.
Testi Adottati
Slide fornite dal docente.Modalità Erogazione
Lezioni ed esercitazioni in aula.Modalità Valutazione
L'esame è costituito da una prova scritta di 1 ora. Valutazione in itinere: alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie). La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere. Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato esclusivamente nella prima sessione d'esame. Si prevede 1 prova intermedia.