Algoritmi e strutture dati

A.A. 2019/2020
Insegnamento per
12
Crediti massimi
120
Ore totali
SSD
INF/01
Lingua
Italiano
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.

Struttura insegnamento e programma

Edizione attiva
Responsabile
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Turni:
Introduzione lab. - Turno A
Docente: Lonati Violetta
Introduzione lab. - Turno B
Docente: Lonati Violetta
Lab. turno unico
Docente: Lonati Violetta
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.
Propedeuticità
Matematica del continuo
Matematica del discreto
Prerequisiti e modalità di esame
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.
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
martedi' dalle 14,30 alle 16,30 - Consultare la pagina https://bit.ly/2GmQWl4 per informazioni su eventuali modifiche o sospensioni
via Celoria 18 - Stanza 8025 (ottavo piano)