Università degli Studi di Perugia

• Algoritmi e strutture dati con Laboratorio - Modulo II
• Algoritmi e strutture dati con Laboratorio - Modulo I

Per accedere all'esame orale, lo studente deve superare una prova scritta di 2 ore, senza possibilita' di consultare i testi. Una volta superata la prova scritta lo studente dovrà sostenere l'orale. Per chi frequenta, è possibile sostenere prove in itinere a carattere esonerante.

Saranno rese disponibili dal Corso di Laurea in Informatica

Procedure e funzioni,ricorsione,puntatori e variabili dinamiche.Tipi di dati astratti. Rappresentazione e algoritmi per liste,alberi binari,tavole hash,alberi binari di ricerca.

Procedure e funzioni,ricorsione,puntatori e variabili dinamiche.Tipi di dati astratti. Rappresentazione e algoritmi per liste,alberi binari,tavole hash,alberi binari di ricerca.

lezioni,esercitazioni,ricevimento studenti

Cormen,Leiserson,Rivest,Stein:Introduzione agli algoritmi e strutture dati 2/ed ,McGraw-Hill

gestione ed implementazione delle varie strurtture dati

consultare il calendario delle lezioni

consultare il calendario delle lezioni

consigliata

Dipartimento di matematica e Informatica

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.

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. Tecniche di programmazione: Programmazione dinamica. Tecnica Greedy.

Lezioni frontali ed esercitazioni in classe.

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

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. Conoscenza delle principali tecniche di programmazione.

Segue il calendario del Corso di Laurea in Informatica. Corso Annuale.

Martedi' 16-18
mercoledi' 9-11
Mercoledi' 14-16 per esercitazioni
(da confermare)

Esercitazioni in classe per verificare l'apprendimento delle abilità di programmazione.

Consigliata

Dipartimento di Matematica e Informatica
Via Vanvitelli 1
Perugia