Algoritmi e strutture dati
A.A. 2018/2019
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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
Professor(s)