Algoritmi e strutture dati
A.A. 2023/2024
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 quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo quadrimestre
Programma
1) Introduzione. Algoritmi e rappresentazione dei dati. Tempo di calcolo. Complessità computazionale. Strutture Dati Elementari e rappresentazione in memoria.
2) Strutture di tipo lineare. Specifica e realizzazione di liste, pile e code.
3) Strutture di tipo ad albero. Alberi: algoritmi di visita, realizzazioni. Heap ed HeapSort.
4) Strutture di tipo reticolare. Grafi: specifica, realizzazioni, algoritmi di visita, componenti connesse.
5) Strutture di tipo insieme. Insiemi: specifica e realizzazione, Mfset. Dizionari: specifica e realizzazioni, tabelle hash. Alberi bilanciati di Ricerca.
6) Complessità di algoritmi. Relazioni per la complessità di algoritmi ricorsivi.
7) Impatto delle strutture dati sulla complessità di un algoritmo. Il problema dei cammini minimi. Schema generale di algoritmo basato sul teorema di Bellman. Algoritmi: Dijkstra, Johnson, Bellman-Ford-Moore, con pila ed Pape-D'Esopo.
8) Divide et impera. Descrizione del paradigma. Esempi: Mergesort, Quicksort.
9) Backtrack. Descrizione del paradigma. Esempio: String matching.
10) Programmazione Dinamica. Descrizione del paradigma. Esempio: String matching approssimato.
11) Greedy. Descrizione del paradigma. Esempi: Minimo Albero di Copertura, Scheduling di Programmi.
12) Non determinismo ed enumerazione. Certificati polinomiali. Non determinismo. Enumerazione.
13) Problemi NP-completi. Classi P e NP. Riducibilità polinomiale.
2) Strutture di tipo lineare. Specifica e realizzazione di liste, pile e code.
3) Strutture di tipo ad albero. Alberi: algoritmi di visita, realizzazioni. Heap ed HeapSort.
4) Strutture di tipo reticolare. Grafi: specifica, realizzazioni, algoritmi di visita, componenti connesse.
5) Strutture di tipo insieme. Insiemi: specifica e realizzazione, Mfset. Dizionari: specifica e realizzazioni, tabelle hash. Alberi bilanciati di Ricerca.
6) Complessità di algoritmi. Relazioni per la complessità di algoritmi ricorsivi.
7) Impatto delle strutture dati sulla complessità di un algoritmo. Il problema dei cammini minimi. Schema generale di algoritmo basato sul teorema di Bellman. Algoritmi: Dijkstra, Johnson, Bellman-Ford-Moore, con pila ed Pape-D'Esopo.
8) Divide et impera. Descrizione del paradigma. Esempi: Mergesort, Quicksort.
9) Backtrack. Descrizione del paradigma. Esempio: String matching.
10) Programmazione Dinamica. Descrizione del paradigma. Esempio: String matching approssimato.
11) Greedy. Descrizione del paradigma. Esempi: Minimo Albero di Copertura, Scheduling di Programmi.
12) Non determinismo ed enumerazione. Certificati polinomiali. Non determinismo. Enumerazione.
13) Problemi NP-completi. Classi P e NP. Riducibilità polinomiale.
Prerequisiti
È obbligatorio il superamento dell'esame di Programmazione ed è consigliato il superamento degli esami di Matematica del Continuo e di Matematica del Discreto
Metodi didattici
Video lezioni
Materiale di riferimento
A. Bertossi, "Algoritmi e Strutture Dati", UTET, 2000.
Materiale disponibile sulla piattaforma di e-learning.
Materiale disponibile sulla piattaforma di e-learning.
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.
È inoltre possibile sostenere l'esame svolgendo due prove in itinere così come previsto dalla erogazione online. Se lo studente supera entrambe le prove in itinere, la media dei due risultati costituisce il voto finale d'esame. La singola prova in itinere si ritiene superata se si raggiunge un punteggio maggiore o uguale a 15, mentre la media delle due prove in itinere deve essere maggiore o uguale a 18 per poter passare l'esame. I risultati delle prove scritte saranno comunicati tramite la pubblicazione di un file pdf sul sito Ariel dell'insegnamento.
È inoltre possibile sostenere l'esame svolgendo due prove in itinere così come previsto dalla erogazione online. Se lo studente supera entrambe le prove in itinere, la media dei due risultati costituisce il voto finale d'esame. La singola prova in itinere si ritiene superata se si raggiunge un punteggio maggiore o uguale a 15, mentre la media delle due prove in itinere deve essere maggiore o uguale a 18 per poter passare l'esame. I risultati delle prove scritte saranno comunicati tramite la pubblicazione di un file pdf sul sito Ariel dell'insegnamento.
Docente/i