Complementi di Algoritmi e Strutture Dati


Insegnamento complementare per il corso di laurea triennale di Informatica (6 crediti)
Dipartimento di Informatica
Università degli Studi di Milano
Anno accademico 2014/2015

Docenti: Massimiliano Goldwurm, Nicolò Cesa Bianchi




1. Obiettivi del corso
2. Programma preliminare
3. Propedeuticità consigliate
4. Testi di riferimento
5. Dispense
6. Prerequisiti
7. Appelli d'esame per l'a.a. 2015/2016
8. Altre informazioni



OBIETTIVI DEL CORSO

Questo insegnamento rappresenta la naturale continuazione del corso di Algoritmi e Strutture Dati (fondamentale del 2° anno della laurea triennale di informatica).
Esso mira a presentare alcuni algoritmi classici di particolare attualità non trattati nel corso precedente e nello stesso tempo a sviluppare temi di studio avanzati principalmente dedicati alla complessità computazionale e agli algoritmi probabilistici.
Il programma prevede tre parti: la prima è dedicata agli algoritmi di String-Matching, di forte interesse per le numerose applicazioni in svariati settori (per esempio in biologia computazionale) e allo studio di strutture dati efficienti e avanzate come i Suffix-tree.
La seconda prevede lo studio dei modelli di calcolo non deterministico e delle principali classi di complessità in tempo e spazio: P, NP, L, NL, Pspace e le relative famiglie di problemi completi.
La terza parte è dedicata alle procedure probabilistiche, quali per esempio l’algoritmo di Rabin per stabilire se un numero intero è primo.

PROGRAMMA PRELIMINARE



PROPEDEUTICITA' CONSIGLIATE

Algoritmi e strutture dati, Linguaggi formali e automi.



TESTI DI RIFERIMENTO



DISPENSE

Sono disponibili in formato pdf le dispense realizzate dagli studenti Simone Bossi e Alexandru Ivan, tratte dalle lezioni di Algoritmi e Strutture Dati II, tenute nell'a.a. 2013/2014 e scaricabili dal seguente sito:
Algoritmi_II_pdf .


PREREQUISITI


Le strutture dati di base e gli algoritmi fondamentali, gli automi a stati finiti e le loro principali proprietà.

APPELLI D'ESAME PER L'A.A. 2015/2016

Gli appelli per l'anno accademico 2015/2016 si svolgeranno secondo il calendario riportato nel sito del Collegio didattico di Informatica (pagina degli avvisi). In ogni appello l'esame consiste in una prova orale, la data e l'ora effettive vanno concordate con il docente per posta elettronica e saranno successive alla data che compare sul SIFA. Attualmente le date ufficiali (2016) sono: 21 aprile, 24 giugno, 28 luglio, 23 settembre. La chiusura delle iscrizioni avviene circa una settimana prima della data SIFA, mentre l'apertura avviene almeno un mese prima della stessa.

ALTRE INFORMAZIONI



Ultimo aggiornamento: 27 Febbraio 2016