Algoritmi e strutture dati
A.A. 2018/2019
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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 ViolettaProfessor(s)
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