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 2022 |
| Erogato | Erogato nel 2023/24 |
| 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 complessità in tempo e spazio. Algoritmi di ordinamento. Heapsort. Tecnica Divide-et-impera. Algoritmi elementari per i grafi: visita in larghezza e in profondità. Algoritmi per grafi pesati: albero dei cammini minimi da sorgente singola, 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 Corso di Studio. L'obiettivo principale dell’insegnamento consiste nel fornire agli studenti le basi per comprendere, valutare, e proporre algoritmi deterministici, simili a quelli studiati nel corso, ma estesi a nuovi contesti. Le principali conoscenze acquisite saranno: la capacità di valutare l'efficienza di un algoritmo; la conoscenza degli algoritmi per l'ordinamento; la conoscenza e l' utilizzo di strutture dati; la conoscenza di algoritmi per la gestione dei grafi. La principali abilità sarà quella di applicare le conoscenze acquisite a nuovi contesti attraverso lo sviluppo di algoritmi originali (rivisitazioni degli algoritmi studiati), di cui si saprà valutare l'efficienza e derivarne l'ottimalità. |
| 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 una prova scritta e una prova orale, su richiesta dello studente. La prova scritta consiste nella risoluzione di esercizi 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. Per gli studenti frequentanti è possibile sostenere due prove scritte in itinere, ciascuna composta da alcuni esercizi. 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. 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. |
| Obiettivi Agenda 2030 per lo sviluppo sostenibile | Questo insegnamento concorre alla realizzazione degli obiettivi ONU dell'Agenda 2030 per lo Sviluppo Sostenibile |
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 | Approfondimenti per le strutture dati. Algoritmi per calcolare i cammini minimi fra tutte le coppie di vertici nei grafi pesati. |
| 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) volto a misurare la capacità di applicare le conoscenza acquisite e comprenderne il trasferimento a nuovi contesti. 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, a seconda del tempo a disposizione, si faranno anche cenni alle strutture dati per la ricerca efficiente multidimensionale. Si studieranno poi gli algoritmi per i cammini minimi fra tutte le coppie degli archi pesati: algoritmo di Floyd-Warshall, algoritmo analogo alla moltiplicazione di matrici, algoritmo di Johnson per grafi sparsi. La parte di laboratorio è di supporto all'esercitazioni sui contenuti sia del Modulo 1 che del Modulo 2. |
| Obiettivi Agenda 2030 per lo sviluppo sostenibile | Questo insegnamento concorre alla realizzazione degli obiettivi ONU dell'Agenda 2030 per lo Sviluppo Sostenibile |