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 2021 |
| Erogato | Erogato nel 2022/23 |
| Erogato altro regolamento | Informazioni sull'attività didattica |
| 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 di media complessità per grafi pesati: albero dei cammini minimi, albero di copertura di costo minimo. |
| 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. I materiali didattici utilizzati durante le lezioni sono, solitamente, resi disponibili anche su Unistudium. |
| Obiettivi formativi | Il corso fornisce le competenze algoritmiche di base, caratterizzanti per il CdS. L'obiettivo principale dell’insegnamento consiste nel fornire agli studenti le basi per comprendere, valutare, e proporre tecniche (algoritmi), basate su procedimenti precisi, deterministici, strutturati in passi elementari e finiti, che risolvono classi di problemi. Le principali conoscenze acquisite saranno: capacità di valutare l'efficienza di un algoritmo; conoscenza approfondita algoritmi di base; conoscenza e utilizzo di strutture dati; e conoscenza algoritmi per la gestione dei grafi (esplorazione e cammini minimi). Le principali abilità (ossia la capacità di applicare le conoscenze acquisite) saranno: analizzare il comportamento in tempo e spazio di algoritmi già proposti; riconoscere l'applicabilità di algoritmi studiati; e sviluppare algoritmi originali per nuove classi di problemi. |
| Prerequisiti | Elementi di Analisi Matematica, Matematica Discreta e un linguaggio di programmazione imperativo. |
| Metodi didattici | Lezioni frontali in classe. |
| Altre informazioni | Frequenza consigliata. Tuttavia tutti gli argomenti trattati sono rintracciabili sui testi consigliati. |
| Modalità di verifica dell'apprendimento | L'esame è unico per i due moduli. 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 al più quattro esercizi (usualmente, da 8 punti ciascuno) per valutare la capacità di applicare le conoscenza acquisite e comprenderne il trasferimento a nuovi contesti. 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. La prova orale non è obbligatoria se il voto dello scritto è sufficiente. Alla prova orale si accede se il punteggio nella prova scritta è non inferiore a 15/30. Per gli studenti frequentanti è possibile sostenere due prove scritte in itinere, ciascuna composta da alcuni esercizi. Una prova orale conclusiva è prevista. Nel caso in cui lo studente intenda anticipare l’esame in un anno precedente a quello programmato nel piano di studio, si raccomanda di frequentare il ciclo delle lezioni e di sostenere l’esame nel primo appello utile dopo che le lezioni medesime siano terminate, nel rispetto quindi del semestre di programmazione dell’insegnamento. 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. Algoritmo di Djikstra. Albero di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim. Approfondimenti sui 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, Leftist Trees Alberi Binari di Ricerca Alberi Binari di Ricerca Bilanciati Tabele Hash Strutture Dati Union FInd Rivisitazione delle strutture dati nel contesto 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 I materiali didattici utilizzati durante le lezioni sono, solitamente, resi disponibili anche su Unistudium. |
| Obiettivi formativi | Il corso fornisce le competenze algoritmiche di base e caratterizzanti per il CdS. L'obiettivo principale dell'insegnamento è quello di fornire agli studenti le basi per la comprensione dell'organizzazione dei dati. Le principali conoscenze acquisite saranno: conoscenza delle strutture dati di base, delle operazioni che le caratterizzano e della complessità temporale delle operazioni. Le principali abilità (cioè la capacità di applicare le conoscenze acquisite) saranno: riconoscere la struttura dati utile in un determinato contesto. |
| 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). La prova nel suo insieme consente di accertare sia la capacità di conoscenza e comprensione, sia la capacità di applicare le competenze acquisite, sia la capacità di esposizione. Nel caso in cui lo studente intenda anticipare l’esame in un anno precedente a quello programmato nel piano di studio, si raccomanda di frequentare il ciclo delle lezioni e di sostenere l’esame nel primo appello utile dopo che le lezioni medesime siano terminate, nel rispetto quindi del semestre di programmazione dell’insegnamento. 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, mergeable heaps, 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. |