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 2019
Erogato
2020/21
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
  • 63 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. Algoritmi elementari per i grafi: visita in larghezza e in profondità. Algoritmi avanzati per grafi e reti.
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 elementari. Conoscenza approfondita algoritmi per la gestione dei grafi.
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.
La prova scritta consiste nella risoluzione di quattro esercizi (da 8 punti ciuscuno).
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 due prove scritte in itinere, ciascuna composta da 3 o 4 esercizi. L'esame orale finale serve pricipalemnte a recuperare quella parte del programma in cui lo studente frequentante non ha raggiunta la piena sufficienza o a igliorare il voto finale.

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.
Heap: definizione e proprieta'. Procedura di mantenimento dalle proprietà delle chiavi dello heap e calcolo della sua complessità. Costruzione di un heap. HeapSort. Code di priorità. Inserimento e cancellazione da uno heap.D-ary heaps.
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.
Heap. Generalità sugli alberi ordinati, realizzazione.Complessità delle operazioni di visita e di ordinamento utilizzando alberi binari di ricerca.
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 (algoritmo con la cancellazione di sorgenti, algoritmo con i tempi di fine-visita DFS). Componenti fortemente connesse (algoritmo con i tempi di fine-visita DFS).
Alberi di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim.
Cammini minimi da sorgente unica: algorimi di Dijkstra, algoritmo di Bellman-Ford.
Cenni su heap binomiali, heap di Fibonacci e strutture dati per UnionFind.
Programmazione dinamica: moltiplicazione di matrici con il minimo numero di prodotti, problema dello zaino intero con/senza ripetizioni, palindrome, programmazione delle catene di montaggio.
Algoritmi Greedy: selezione delle attivita', colorazione di un grafo di intervalli, codici di Huffman.
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
  • 57 ore - Maria Cristina Pinotti
Attività Caratterizzante
Ambito Discipline informatiche
Settore INF/01
Tipo insegnamento Obbligatorio (Required)
Lingua insegnamento Italiano
Contenuti Alberi Binari di Ricerca
Alberi Binari di Ricerca Bilanciati
Tabele Hash
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 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 e strutture dati per la ricerca efficiente bidimensionale e ricerca multidimensionale.
La parte di laboratorio è di supporto all'esercitazioni sui contenuti sia del Modulo 1 che del Modulo 2.
Condividi su