Algoritmi e strutture dati
A.A. 2018/2019
Obiettivi formativi
Il corso consiste di una parte di teoria e una di laboratorio. Obiettivo della prima parte è quello di presentare le strutture dati e gli algoritmi di base ponendo l'enfasi sui metodi di progettazione sull'analisi delle procedure. La parte di laboratorio ha invece come obiettivo la presentazione del linguaggio C e il suo utilizzo nella implementazione di strutture dati e algoritmi.
Risultati apprendimento attesi
Non definiti
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Primo semestre
Programma
Concetto di algoritmo. Algoritmi e programmi. Notazioni asintotiche. Stime di complessità di algoritmi.
La macchina RAM.
Strutture dati fondamentali: array, liste, pile, code, alberi.
Ricerca sequenziale e ricerca binaria. Strutture ad albero per ricerche.
Tecniche hash.
Algoritmi di ordinamento elementari. Algoritmi di ordinamento evoluti: mergesort, heapsort, quicksort.
Tecniche di ordinamento non basate su confronti.
Tecniche algoritmiche: divide-et-impera, programmazione dinamica, greedy.
Grafi.
Problemi e algoritmi fondamentali su grafi: albero di ricoprimento minimo, cammini minimi in grafi.
Problemi "difficili": algoritmi non deterministici e introduzione alla NP-competezza.
Un elenco dettagliato degli argomenti trattati nel corso, lezione per lezione, viene pubblicato e aggiornato sulla pagina web del corso.
La macchina RAM.
Strutture dati fondamentali: array, liste, pile, code, alberi.
Ricerca sequenziale e ricerca binaria. Strutture ad albero per ricerche.
Tecniche hash.
Algoritmi di ordinamento elementari. Algoritmi di ordinamento evoluti: mergesort, heapsort, quicksort.
Tecniche di ordinamento non basate su confronti.
Tecniche algoritmiche: divide-et-impera, programmazione dinamica, greedy.
Grafi.
Problemi e algoritmi fondamentali su grafi: albero di ricoprimento minimo, cammini minimi in grafi.
Problemi "difficili": algoritmi non deterministici e introduzione alla NP-competezza.
Un elenco dettagliato degli argomenti trattati nel corso, lezione per lezione, viene pubblicato e aggiornato sulla pagina web del corso.
Propedeuticità
Matematica del continuo
Matematica del discreto
Matematica del discreto
Prerequisiti
L'esame si articola in una prova scritta, una prova di laboratorio e si conclude con prova orale. Le prove riguardano tutti i contenuti del corso. Si accede alla prova orale dopo il superamento della prova scritta e della prova di laboratorio. La valutazione finale viene formulata al termine della prova orale.
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Lezioni: 72 ore
Docenti:
Lonati Violetta, Pighizzini Giovanni
Turni:
Docente:
Pighizzini Giovanni
Parte seconda - turno unico
Docente:
Lonati ViolettaPrima parte - Turno A
Docente:
Lonati ViolettaPrima parte - Turno B
Docente:
Lonati ViolettaDocente/i
Ricevimento:
Il ricevimento studenti viene svolto sia in presenza (modalità preferibile), sia a distanza. Consultare la pagina http://pighizzini.di.unimi.it/ricevimento.html per dettagli e informazioni aggiornate