Algoritmi e strutture dati
A.A. 2018/2019
Obiettivi formativi
Il corso ha lo scopo di introdurre i concetti fondamentali riguardanti l'analisi ed il progetto di algoritmi e strutture dati e l'analisi della complessità computazionale degli algoritmi.
Risultati apprendimento attesi
Non definiti
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
1. Introduzione
Nozione di problema e algoritmo. Analisi di algoritmi, complessità in spazio e tempo di algoritmi ricorsivi e non. Notazioni asintotiche. Calcolo dei tempi di esecuzione di un programma.
2. Tipi di dati astratti di base
Liste, Stack, Code: definizione ed operazioni. Implementazione (array, puntatori) con esecuzione delle operazioni e vantaggi/svantaggi.
3. Alberi
Concetto di albero e definizioni. Tecniche di attraversamento (inorder, preorder, postorder). Operazioni su ADT albero. Tecniche di rappresentazione. Alberi binari di ricerca: definizione, rappresentazione, operazioni. Alberi binari rosso neri: definizione, rappresentazione, operazioni.
4. Insiemi
Definizione, operazioni e tecniche di rappresentazione. Dizionari: definizione e operazioni. Code di priorità: concetti, esempi di utilizzo e tecniche di rappresentazione. Heap: realizzazione e esecuzione delle operazioni.
5. Hashing
Tavole ad indirizzamento diretto. Tavole hash. Funzioni hash. Indirizzamento aperto.
6. Tecniche avanzate di progettazione ed analisi.
Programmazione dinamica. Algoritmi greedy.
7. Grafi
Grafi orientati e non orientati: definizioni e concetti principali. Tecniche di rappresentazione. Cammino minimo in grafi pesati: problema e soluzioni. Algoritmi di visita in ampiezza (BFS) e profondità (DFS). Esempi di applicazioni della DFS: test di aciclicità, ordinamento topologico, ritrovamento di componenti fortemente connesse. Esempi di applicazioni della BFS: calcolo cammino minimo in grafi non pesati. Minimo albero ricoprente: problema e soluzioni. Punti di articolazione: definizione e ritrovamento. Graph matching.
8. Ordinamento
Problema. Limite inferiore di complessità per gli algoritmi di ordinamento. Insertion sort, heapsort, quicksort, mergesort: descrizione ed analisi della complessità.
9. Gestione dei dati su memoria esterna
Problemi. B-alberi: definizione, proprietà e vantaggi. Esecuzione delle operazioni di ricerca, inserimento e cancellazione. Operazioni di concatenazione e bilanciamento nella cancellazione. Operazioni di divisione e promozione nell'inserimento.
Nozione di problema e algoritmo. Analisi di algoritmi, complessità in spazio e tempo di algoritmi ricorsivi e non. Notazioni asintotiche. Calcolo dei tempi di esecuzione di un programma.
2. Tipi di dati astratti di base
Liste, Stack, Code: definizione ed operazioni. Implementazione (array, puntatori) con esecuzione delle operazioni e vantaggi/svantaggi.
3. Alberi
Concetto di albero e definizioni. Tecniche di attraversamento (inorder, preorder, postorder). Operazioni su ADT albero. Tecniche di rappresentazione. Alberi binari di ricerca: definizione, rappresentazione, operazioni. Alberi binari rosso neri: definizione, rappresentazione, operazioni.
4. Insiemi
Definizione, operazioni e tecniche di rappresentazione. Dizionari: definizione e operazioni. Code di priorità: concetti, esempi di utilizzo e tecniche di rappresentazione. Heap: realizzazione e esecuzione delle operazioni.
5. Hashing
Tavole ad indirizzamento diretto. Tavole hash. Funzioni hash. Indirizzamento aperto.
6. Tecniche avanzate di progettazione ed analisi.
Programmazione dinamica. Algoritmi greedy.
7. Grafi
Grafi orientati e non orientati: definizioni e concetti principali. Tecniche di rappresentazione. Cammino minimo in grafi pesati: problema e soluzioni. Algoritmi di visita in ampiezza (BFS) e profondità (DFS). Esempi di applicazioni della DFS: test di aciclicità, ordinamento topologico, ritrovamento di componenti fortemente connesse. Esempi di applicazioni della BFS: calcolo cammino minimo in grafi non pesati. Minimo albero ricoprente: problema e soluzioni. Punti di articolazione: definizione e ritrovamento. Graph matching.
8. Ordinamento
Problema. Limite inferiore di complessità per gli algoritmi di ordinamento. Insertion sort, heapsort, quicksort, mergesort: descrizione ed analisi della complessità.
9. Gestione dei dati su memoria esterna
Problemi. B-alberi: definizione, proprietà e vantaggi. Esecuzione delle operazioni di ricerca, inserimento e cancellazione. Operazioni di concatenazione e bilanciamento nella cancellazione. Operazioni di divisione e promozione nell'inserimento.
Prerequisiti
L'esame si articola in una prova scritta obbligatoria, che consente di conseguire una votazione fino a 30 e Lode.
La prova scritta richiede:
· la risposta a quesiti teorici che spaziano su tutto il programma del corso;
· la soluzione di tre esercizi di tipo applicativo.
La prova scritta richiede:
· la risposta a quesiti teorici che spaziano su tutto il programma del corso;
· la soluzione di tre esercizi di tipo applicativo.
Metodi didattici
Lezioni frontali e laboratorio
Materiale di riferimento
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduzione agli Algoritmi e Strutture Dati," McGraw-Hill, 2a edizione (2005).
Lucidi e riferimenti disponibili sul sito del docente
Lucidi e riferimenti disponibili sul sito del docente
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Lezioni: 72 ore
Docente/i