In questa sezione sono disponibili le presentazioni utilizzate durante il corso di Algoritmi 2.
Per ogni presentazione è riportata una breve descrizione degli argomenti trattati e un collegamento alle relative slide in formato PDF.
Una stessa presentazione può essere utilizzata in più lezioni. Per conoscere le date e gli argomenti effettivamente svolti in ciascuna lezione, consultare il Diario delle lezioni.
PL1 -Presentazione del corso
Presentazione del corso e introduzione agli obiettivi, all'organizzazione e ai principali contenuti di Algoritmi 2.
Introduzione ai grafi e ai principali concetti necessari per lo studio degli algoritmi su grafi. Vengono presentate le principali rappresentazioni e le proprietà fondamentali dei grafi, orientati e non orientati.
Introduzione alla visita in profondità (DFS) e alla sua implementazione, sia ricorsiva sia iterativa. Viene inoltre presentata la 2-colorazione dei grafi come applicazione della DFS.
Prima parte delle applicazioni della DFS alla soluzione di problemi sui grafi. Vengono introdotti l'albero DFS e le componenti connesse, con particolare attenzione al problema dell'individuazione dei ponti.
Applicazioni della DFS ai grafi diretti. Vengono affrontati il riconoscimento dei cicli, i grafi aciclici orientati (DAG) e l'ordinamento topologico.
Introduzione alle componenti fortemente connesse nei grafi diretti e presentazione dell'algoritmo di Kosaraju per il loro calcolo.
Introduzione alla visita in ampiezza (BFS) e confronto con la DFS. Viene mostrato come la BFS permetta di calcolare i cammini minimi da una sorgente in grafi non pesati e di costruire il relativo albero dei cammini minimi. La lezione si conclude con il problema del diametro di un grafo.
Il problema dei cammini minimi da singola sorgente nei grafi pesati e l'algoritmo di Dijkstra per grafi con pesi positivi.
Il problema del minimo albero di copertura nei grafi pesati e l'algoritmo di Kruskal per la sua soluzione.
Introduzione alla tecnica greedy per la progettazione di algoritmi. Vengono illustrati il principio della scelta locale e le condizioni che consentono di ottenere una soluzione ottima, attraverso esempi quali la selezione e l'assegnazione di attività.
Introduzione agli algoritmi di approssimazione per problemi per i quali non è nota una soluzione efficiente. Viene discussa la differenza tra euristiche e algoritmi di approssimazione e vengono introdotti i concetti di qualità della soluzione e rapporto di approssimazione, con riferimento al problema della copertura minima tramite nodi.
Analisi di tre algoritmi di approssimazione per problemi computazionalmente difficili. Gli esempi mostrano come ottenere soluzioni efficienti, anche quando non è possibile garantire l'ottimalità.
Introduzione alla tecnica Divide et Impera e sua applicazione al problema della selezione. Vengono presentati un algoritmo con tempo O(n) nel caso medio e un algoritmo con tempo O(n) nel caso pessimo.
Applicazione della tecnica Divide et Impera al problema della coppia di punti più vicini. La lezione mostra come la suddivisione del problema consenta di ottenere una soluzione efficiente nell'ambito della geometria computazionale.
Introduzione alla Programmazione Dinamica e ai concetti di sottoproblemi sovrapposti e memoizzazione. Vengono confrontati gli approcci top-down e bottom-up.
Approfondimento della Programmazione Dinamica attraverso l'utilizzo di tabelle bidimensionali. Vengono analizzati, tra gli altri, il problema del cammino di somma massima in una matrice, il problema dello zaino e quello della più lunga sottosequenza comune.
Applicazione della Programmazione Dinamica al problema dei cammini minimi nei grafi. Vengono presentati gli algoritmi di Bellman-Ford e Floyd-Warshall per il calcolo delle distanze in grafi pesati, anche in presenza di archi con peso negativo.
Introduzione alla tecnica del backtracking per la soluzione sistematica di problemi combinatori. Vengono presentate la costruzione incrementale delle soluzioni, la visita DFS dell'albero di ricerca e le funzioni di potatura, utilizzate per evitare l'esplorazione di percorsi che non possono portare a una soluzione valida.
Applicazioni del backtracking alla generazione di strutture combinatorie, tra cui stringhe, matrici e permutazioni, con particolare attenzione alla gestione dei vincoli e alla complessità degli algoritmi.
Approfondimento del backtracking applicato a problemi decisionali e di ottimizzazione. Vengono analizzate strategie di ricerca nello spazio delle soluzioni e tecniche per ridurre lo spazio esplorato, attraverso esempi quali il ciclo hamiltoniano, la 3-colorazione dei grafi e il problema dello zaino.