Algoritmi e strutture dati
A.A. 2020/2021
Obiettivi formativi
L'insegnamento ha l'obiettivo di introdurre i concetti fondamentali relativi alla progettazione e analisi di algoritmi e delle strutture dati che questi utilizzano. L'insegnamento illustrerà le principali strutture dati e si focalizzerà su alcuni algoritmi specifici, studiandone anche la complessità computazionale.
Risultati apprendimento attesi
Lo studente dovrà conoscere e saper utilizzare le strutture dati e gli algoritmi di base presentati nell'insegnamento. Lo studente dovrà inoltre essere in grado di proporre soluzioni algoritmiche adeguate, utilizzando le strutture dati più appropriate, a problemi semplici, stimandone la complessità computazionale.
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
Didattica a distanza in streaming.
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. Ordinamento
Problema. Limite inferiore di complessità per gli algoritmi di ordinamento. Insertion sort, heapsort, quicksort, mergesort: descrizione ed analisi della complessità.
4. Hashing
Tavole ad indirizzamento diretto. Tavole hash. Funzioni hash. Indirizzamento aperto.
5. 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.
6. 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.
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. Ricorsione
Definizione di ritorsione diretta ed indiretta. Tecnica di tail recursion.
9. Tecniche avanzate di progettazione ed analisi.
Programmazione dinamica. Algoritmi greedy.
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. Ordinamento
Problema. Limite inferiore di complessità per gli algoritmi di ordinamento. Insertion sort, heapsort, quicksort, mergesort: descrizione ed analisi della complessità.
4. Hashing
Tavole ad indirizzamento diretto. Tavole hash. Funzioni hash. Indirizzamento aperto.
5. 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.
6. 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.
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. Ricorsione
Definizione di ritorsione diretta ed indiretta. Tecnica di tail recursion.
9. Tecniche avanzate di progettazione ed analisi.
Programmazione dinamica. Algoritmi greedy.
Prerequisiti
E' obbligatorio il superamento dell'esame di Programmazione ed è consigliato il superamento degli esami di Matematica del Continuo e di Matematica del Discreto.
Metodi didattici
Lezioni frontali in aula ed attività pratiche in 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 disponibili sul sito Ariel dell'insegnamento: http://sdecapitaniasd.ariel.ctu.unimi.it/
Lucidi disponibili sul sito Ariel dell'insegnamento: http://sdecapitaniasd.ariel.ctu.unimi.it/
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste nello svolgimento di una prova scritta che include sia domande teoriche a risposta aperta sia esercizi. La prova scritta, della durata di due ore e mezza, ha lo scopo di accertare la preparazione e la comprensione della materia. La valutazione, espressa in trentesimi, terrà conto della correttezza, completezza e chiarezza espositiva delle risposte alle domande di teoria e della capacità di ragionamento e di utilizzo delle conoscenze acquisite per la risoluzione degli esercizi. Durante la prova scritta non è consentito l'utilizzo di alcun materiale. I risultati delle prove scritte saranno comunicati tramite la pubblicazione di un file pdf sul sito Ariel dell'insegnamento.
INF/01 - INFORMATICA - CFU: 12
Laboratori: 48 ore
Lezioni: 72 ore
Lezioni: 72 ore
Docenti:
De Capitani Di Vimercati Sabrina, Frasca Marco
Docente/i