Insegnamento ALGORITMI E STRUTTURE DATI CON LABORATORIO
| Nome del corso di laurea | Informatica |
|---|---|
| Codice insegnamento | 55100615 |
| Curriculum | Comune a tutti i curricula |
| Docente responsabile | Maria Cristina Pinotti |
| CFU | 15 |
| Regolamento | Coorte 2020 |
| Erogato | Erogato nel 2021/22 |
| Erogato altro regolamento | |
| Anno | 2 |
| Periodo | Annuale |
| Tipo insegnamento | Obbligatorio (Required) |
| Tipo attività | Attività formativa integrata |
| Suddivisione |
ALGORITMI E STRUTTURE DATI CON LABORATORIO - MODULO I
| Codice | 55100609 |
|---|---|
| CFU | 9 |
| Docente responsabile | Maria Cristina Pinotti |
| Docenti |
|
| Ore |
|
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Tipo insegnamento | Obbligatorio (Required) |
| Lingua insegnamento | Italiano |
| Contenuti | Progettazione degli algoritmi e analisi della complessita' in tempo e spazio. Algoritmi di ordinamento. Strutture dati elementari: heap, tabelle hash, binary trees. Algoritmi elementari per i grafi: visita in larghezza e in profondità. Algoritmi avanzati per grafi pesati: albero di copertura di costo minimo, albero dei cammini minimi. |
| Testi di riferimento | T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduzione agli algoritmi e strutture dati (terza edizione), McGraw-Hill, 2010, ISBN: 978-88-386-6515-8 M. T. GOODRICH, R. TAMASSIA, Algorithm Design and Applications, Wiley, December 2014, ©2015, ISBN : 978-1-119-02861-1 Panos Louridas, Real-World Algorithms: A Beginner's Guide (MIT Press), ISBN: 9780262035705. |
| Obiettivi formativi | Capacità di valutare l'efficienza di un algoritmo. Conoscenza approfondita algoritmi di base. Utilizzo di strutture dati. Conoscenza approfondita algoritmi per la gestione dei grafi: esplorazione e cammini minimi. |
| Prerequisiti | Elementi di Analisi Matematica, Matematica Discreta e un linguaggio di programmazione imperativo. |
| Metodi didattici | Lezioni frontali in classe. |
| Altre informazioni | Frequenza consigliata. |
| Modalità di verifica dell'apprendimento | Le modalità di verifica includono sia una prova scritta sia una prova orale (tranne nel periodo dell'emergenza sanitaria). La prova scritta consiste nella risoluzione di quattro esercizi (usualmente, da 8 punti ciascuno). La prova orale verte su tutto il programma e consiste sia in domande di teoria, sia nella risoluzione di esercizi e ha una durata approssimativa di 20-25 minuti. Il voto finale è composto considerando sia l'esito della prova scritta sia l'andamento della prova orale. Alla prova orale si accede se il punteggio nella prova scritta è non inferiore a 15/30. Per gli studenti frequentanti è possibile sostenere tre prove scritte in itinere, ciascuna composta da alcuni esercizi. Una prova orale conclusiva è prevista. 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 | Algoritmi: correttezza, terminazione, complessità (caso pessimo, caso medio). InsertionSort: analisi della complessita' in tempo e spazio nel caso pessimo e nel caso medio. Fondamenti di Matematica: Principio di Induzione, Ordine di grandezza di funzioni. Base, tetto, esponenziali, Logaritmi. Sommatorie e serie. Metodi di progetto: Divide et Impera. MergeSort e Ricerca Binaria. Analisi di complessita' di algoritmi ricorsivi. Equazioni di ricorrenza. Il Teorema dell'esperto. Ordinamento: Quicksort con analisi della complessita' in tempo nel caso pessimo e nel caso medio. Costruzione di uno heap. HeapSort.Complessità delle operazioni di visita e di ordinamento utilizzando alberi binari di ricerca. Limiti teorici della complessità di ordinamento per confronto. CountingSort. Radix Sort. Limiti inferiori e superiori per la complessità in tempo per il calcolo del minimo e del massimo in una sequenza. Mediana e statistiche d'ordine. Grafi:generalità e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.Visita in ampiezza (BFS), visita in profondità (DFS) e loro proprietà (classificazione degli archi). Grafi aciclici e ordine topologico. Componenti fortemente connesse. Albero di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim. Cammini minimi fra tutte le coppie: algoritmo di Floyd-Warshall, algoritmo analogo alla moltiplicazione di matrici, algoritmo di Johnson per grafi sparsi. |
ALGORITMI E STRUTTURE DATI CON LABORATORIO - MODULO II
| Codice | 55107606 |
|---|---|
| CFU | 6 |
| Docente responsabile | Maria Cristina Pinotti |
| Docenti |
|
| Ore |
|
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Tipo insegnamento | Obbligatorio (Required) |
| Lingua insegnamento | Italiano |
| Contenuti | Heap. D-Ary heap Alberi Binari di Ricerca Alberi Binari di Ricerca Bilanciati Tabele Hash Strutture Dati Union FInd Rivisitazione delle strutture dati nel constesto degli algoritmi del modulo I. |
| Testi di riferimento | T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduzione agli algoritmi e strutture dati (terza edizione), McGraw-Hill, 2010, ISBN: 978-88-386-6515-8 M. T. GOODRICH, R. TAMASSIA, Algorithm Design and Applications, Wiley, December 2014, ©2015, ISBN : 978-1-119-02861-1 |
| Obiettivi formativi | Conoscenza e ruole delle strutture dati: loro ruolo e loro implementazione. |
| Prerequisiti | Elementi di Analisi Matematica, Matematica Discreta e Uso di un linguaggi di programmazione. |
| Metodi didattici | Lezioni frontali ed esercitazioni. |
| Altre informazioni | Questo modulo non può essere seguito indipendentemente dal primo modulo. |
| Modalità di verifica dell'apprendimento | Esame orale e/o scritto (integrato con Modulo 1) 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 | La parte teorica del modulo è dedicata all'approfondimento delle strutture dati. Oltre a vedere le strutture dati di base: array, pile, code heap, si approfondiranno tabelle hash, heap, d-ary heap, union find data structures, binary trees. Se possibile, anche cenni alle strutture dati per la ricerca efficiente multidimensionale. La parte di laboratorio è di supporto all'esercitazioni sui contenuti sia del Modulo 1 che del Modulo 2. |