Insegnamento ALGORITMI E STRUTTURE DI DATI

English version

Nome del corso di laurea	Ingegneria informatica ed elettronica
Codice insegnamento	70A00090
Curriculum	Ingegneria informatica
Docente responsabile	Emilio Di Giacomo
Docenti	Emilio Di Giacomo
Ore	81 Ore - Emilio Di Giacomo
CFU	9
Regolamento	Coorte 2020
Erogato	Erogato nel 2022/23
Erogato altro regolamento
Attività	Caratterizzante
Ambito	Ingegneria informatica
Settore	ING-INF/05
Anno	3
Periodo	Secondo Semestre
Tipo insegnamento	Obbligatorio (Required)
Tipo attività	Attività formativa monodisciplinare
Lingua insegnamento	ITALIANO
Contenuti	+ Introduzione agli algoritmi e alle strutture dati + Ordinamento + Strutture dati + Tecniche avanzate di progettazione di algoritmi + Grafi e algoritmi su grafi
Testi di riferimento	T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein "Introduzione agli Algoritmi e Strutture Dati", McGraw-Hill
Obiettivi formativi	L'obiettivo del corso è quello di fornire allo studente competenze di base sulla progettazione e l'uso delle principali strutture di dati, sulla progettazione e l'uso di algoritmi per la soluzione di problemi, e sulle tecniche per la valutazione delle loro prestazioni. Al termine del corso ci si aspetta che lo studente abbia le seguenti conoscenze: - conoscenza delle tecniche per l'analisi di complessità degli algoritmi e dei problemi - conoscenza di alcuni strutture dati fondamentali (code di priorità, albri di ricerca, ecc.) - conoscenza di alcuni problemi computazionali fondamentali (ordinamento, minimum spanning tree, shortest path, ecc.) - conoscenza di alcune tecniche per la progettazione di algoritmi per problemi di ottimizzazione (programmazione dinamica, tecniche greedy) Al termine del corso ci si aspetta che lo studente abbia le seguenti abilità: - capacità di valutare la complessità di un algoritmo (anche ricorsivo) - capacità di implementare e utilizzare le strutture dati viste nel corso - capacità di individuare soluzioni algoritmiche efficienti - capacità di progettare algoritmi per problemi di ottimizzazione utilizzando le tecniche generali viste nel corso (programmazione dinamica e tecniche greedy)
Prerequisiti	Al fine di comprendere gli argomenti trattati nel corso lo studente deve aver chiari i concetti di base della programmazione. Deve essere in grado di scrivere programmi per la soluzione di semplici problemi. In particolare deve saper utilizzare efficacemente la ricorsione. E' inoltre richiesta una certa conoscenza della matematica. Lo studente deve essere in grado di capire (e fare) una dimostrazione matematica. In particolare, deve conoscere il principio di induzione e deve essere in grado di capire (e fare) una dimostrazione per induzione. Infine sono richieste alcune conoscenze derivanti dall'analisi matematica, tra cui il concetto di funzione, di limite di una funzione, di serie e di integrale.
Metodi didattici	Il corso è organizzato nel seguente modo: 1- Lezioni frontali (69 ore) in cui vengono spiegati i vari argomenti del corso e in cui si svolgono alcuni esercizi per aiutare la comprensione degli argomenti e come preparazione all'esame. 2- Esercitazioni in laboratorio (12 ore) con uso del calcolatore. Gli studenti, supportati dal docente, mettono in pratica, programmando sul calcolatore, i concetti imparati durante le lezioni teoriche.
Altre informazioni
Modalità di verifica dell'apprendimento	L'esame consiste di un esame orale e di un progetto implementativo (tesina). L'obiettivo del colloquio orale è accertare la conoscenza dei concetti teorici impartiti nell'insegnamento e la capacità di individuare soluzioni algoritmiche per risolvere semplici problemi. Il progetto, da concordare con il docente, consiste nell'implementazione e sperimentazione di algoritmi e/o strutture dati. Il progetto viene svolto da soli o in gruppi di 2-3 persone. Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa
Programma esteso	+ Introduzione agli algoritmi e alle strutture dati - Introduzione agli algoritmi. - Analisi di complessità. - Notazione asintotica. - Ricorrenze. + Ordinamento - Algoritmi di ordinamento per confronti. - Algoritmi di ordinamento in tempo lineare. + Strutture dati - Strutture dati elementari: Pile, Code, Liste, Alberi. - Hashing. - Alberi binari di ricerca. - Alberi rosso-neri. - Code di Priorità: Heap. + Tecniche avanzate di progettazione di algoritmi - Programmazione dinamica. - Tecniche greedy. + Grafi e algoritmi su grafi - Grafi. - Algoritmi di visita per grafi. - Ordinamento topologico. - Minimum Spanning tree. - Cammini minimi da sorgente unica.