Insegnamento ALGORITMI E STRUTTURE DATI CON LABORATORIO
- Corso
- Informatica
- Codice insegnamento
- 55100615
- Curriculum
- Comune a tutti i curricula
- Docente
- Maria Cristina Pinotti
- CFU
- 15
- Regolamento
- Coorte 2020
- Erogato
- 2021/22
- Tipo insegnamento
- Obbligatorio (Required)
- Tipo attività
- Attività formativa integrata
ALGORITMI E STRUTTURE DATI CON LABORATORIO - MODULO I
Codice | 55100609 |
---|---|
CFU | 9 |
Docente | 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 | 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. |