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
  • Maria Cristina Pinotti
Ore
  • 78 ore - Maria Cristina Pinotti
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
  • Maria Cristina Pinotti
Ore
  • 42 ore - Maria Cristina Pinotti
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.
Condividi su