Insegnamento ALGORITMI E STRUTTURE DI DATI
- Corso
- Ingegneria informatica ed elettronica
- Codice insegnamento
- 70A00090
- Curriculum
- Ingegneria informatica
- Docente
- Emilio Di Giacomo
- Docenti
-
- Emilio Di Giacomo
- Ore
- 81 ore - Emilio Di Giacomo
- CFU
- 9
- Regolamento
- Coorte 2020
- Erogato
- 2022/23
- Attività
- Caratterizzante
- Ambito
- Ingegneria informatica
- Settore
- ING-INF/05
- 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.