(r35) PALGappunti2014 < Algoritmi2

Tags: view all tags

<H1>Progettazione di Algoritmi a.a. 2015-2016</H1>

<H2>Appunti</H2>
<DIV ALIGN="justify"  style="margin-left:5%; margin-right:10%">
<ol>
<li>
[[%ATTACHURL%/grafi_1.pdf][Appunti (pdf)]] *Grafi*: diretti e non diretti, adiacenza, grado, cammino, ciclo. *Rappresentazione di grafi*: *matrice di adiacenza* e *liste di adiacenza*. I concetti di *Connessione*, *forte connessione* e *componenti connesse*. Esempio [9-puzzle]. Esercizio [acqua]
</li>
<li>
[[%ATTACHURL%/grafi_2.pdf][Appunti (pdf)]] Discussione esercizio [acqua]: modellare un problema tramite un grafo. *Visita di un grafo*: *DFS*. *Albero di visita*. Determinazione delle *componenti connesse*. Esempio [2-colorazione, bipartizione]. Esercizio [ordine].
</li>
<li>
[[%ATTACHURL%/grafi_3.pdf][Appunti (pdf)]] Discussione esercizio [ordine]: grafi aciclici o DAG e ordinamento topologico. Proprietà DFS: *tempi di inizio e fine visita*. *Classificazione degli archi di una DFS*: attraversamento, indietro e avanti. Algoritmo per trovare cicli, vettore dei padri. Algoritmo per *ordine topologico* basato su DFS. Esercizio [gradi].
</li>
<li>
[[%ATTACHURL%/grafi_4.pdf][Appunti (pdf)]] Discussione esercizio [gradi]: implementazione efficiente dell'algoritmo non basato sulla DFS per l'ordine topologico. *Esercizi* discussi: [archi] (conta gli archi per tipo di una DFS), [trasposto] (calcolo grafo trasposto), [grado due] (sui cicli), [ponte] (archi ponte), [pozzo] (pozzi universali). Esercizio [strade critiche].
</li>
<li>
[[%ATTACHURL%/grafi_5.pdf][Appunti (pdf)]] Discussione esercizio [strade critiche]: algoritmo per trovare archi ponte. Esempio [snodi critici]: punti di articolazione. Algoritmo per trovare i punti di articolazione. Biconnessione. Esercizio [sensi unici].
</li>
<li>
[[%ATTACHURL%/grafi_6.pdf][Appunti (pdf)]] Discussione esercizio [sensi unici]: modellazione tramite grafo e introduzione alla forte connessione. *Componenti fortemente connesse*: *algoritmo di Tarjan*. DAG delle componenti fortemente connesse. Esercizio [broadcast].
</li>
<li>
[[%ATTACHURL%/grafi_7.pdf][Appunti (pdf)]] Discussione esercizio [broadcast]: applicazione dell'algoritmo di Tarjan. *Distanze in un grafo*. Visita *BFS*: cammini minimi e calcolo delle distanze da un nodo. Esempio[reve's puzzle]. Esercizio [labirinto].
</li>
<li>
[[%ATTACHURL%/grafi_8.pdf][Appunti (pdf)]] Discussione esercizio [labirinto]: conteggio numero cammini minimi, variazione BFS. Esercizi discussi: [DFS vs BFS] (confronto tra le visite DFS e BFS), [dall'albero alle distanze] (calcolare le distanze dall'albero di visita di un BFS), [stessa distanza] (i nodi a uguale distanza da due nodi dati), [distanza tra insiemi] (distanza tra due insiemi di nodi), [Roma] (cammini minimi che passano per un nodo dato). Esercizio [acqua 2].
</li>
<li>
[[%ATTACHURL%/grafi_greedy.pdf][Appunti (pdf)]] Discussione esercizio [acqua 2]: applicazione BFS. *Cammini minimi in grafi pesati*. *Algoritmo di Dijkstra* e un'implementazione efficiente. Introduzione agli algoritmi *Greedy*. Esercizio [pesi].
</li>
<li>
[[%ATTACHURL%/greedy.pdf][Appunti (pdf)]] Discussione esercizio [pesi] modi diversi di pesare un cammino. Problema *Selezione Attività*: discussione di tre algoritmi. *Schema generale per dimostrare la correttezza di algoritmi Greedy*, correttezza di un algoritmo per Selezione Attività e un'implementazione efficiente. Correttezza dell'algoritmo di Dijkstra. Esercizio [rifornimenti].
</li>
<li>
[[%ATTACHURL%/greedy2.pdf][Appunti (pdf)]] Discussione esercizio [rifornimenti]: applicazione dello schema generale per dimostrare la correttezza. *Minimo Albero di Copertura* (MST). *Algoritmo di Prim*: correttezza e implementazione efficiente. Esercizi [MST].
</li>
<li>
[[%ATTACHURL%/greedy3.pdf][Appunti (pdf)]] Discussione esercizio [MST]: proprietà di MST. *Algoritmo di Kruskal*: correttezza e implementazione efficiente. *Ricoprimento tramite nodi* (VC). *Algoritmi di approssimazione*. Un algoritmo di approssimazione per VC. Esercizio [file].
</li>
<li>
[[%ATTACHURL%/esercizi.pdf][Appunti (pdf)]] Discussione esercizio [file]: un algoritmo di approssimazione. Esercizi di preparazione alla prova intermedia discussi: [sempre connesso] (visite, DFS), [super-minimo] (modellazione e Dijkstra), [arco massimo] (proprietà di MST), [Universa] (sull'algoritmo di Prim), [sicurezza] (modellazione e Prim), [univoco] (Greedy e correttezza). Altri esercizi [cicli diretti], [resto], [k-MST], [teatro].
</li>
<li>
[[%ATTACHURL%/divide.pdf][Appunti (pdf)]] Breve Discussione degli esercizi della prova intermedia. *Divide et Impera*. *Master Theorem*. Il problema del Massimo Sottovettore. Esercizio [salto].
</li>
<li>
[[%ATTACHURL%/divide2.pdf][Appunti (pdf)]] Discussione esercizio [salto]: applicazione Divide et Impera. Il problema della Coppia di punti più vicini (*Closest Pair*). Calcolo della *mediana* e del *k-esimo elemento*. Esercizio [mediana].
</li>
<li>
[[%ATTACHURL%/pd.pdf][Appunti (pdf)]] Discussione esercizio [mediana]: applicazione Divide et Impera. Ricerca esaustiva (ricorsiva) e *Memoizzazione*: esempio problema File. *Programmazione Dinamica*. Dal valore ottimo alla soluzione ottima. Eserczio [resto].
</li>
<li>
[[%ATTACHURL%/pd2.pdf][Appunti (pdf)]] Discussione esercizio [resto]: dalla Memoizzazione alla Programmazione Dinamica. Problema *Zaino*. Riduzione a problemi su grafi per i problemi Zaino e resto. Esercizio [resto 2].
</li>
<li>
[[%ATTACHURL%/pd3.pdf][Appunti (pdf)]] Discussione esercizio [resto 2]: applicazione Programmazione Dinamica. *Longest Path in DAG*. *Pianificazione di Attività* (CPM). *Sistemi con Vincoli di Differenza*. Esercizio [viaggio].
</li>
<li>
[[%ATTACHURL%/pd4.pdf][Appunti (pdf)]]  Discussione esercizio [viaggio]: dalla rappresentazione tramite DAG alla Programmazione Dinamica. *Cammini minimi con pesi anche negativi*. *Algoritmo di Bellman-Ford*. Esercizio [cammini].
</li>
<li>
[[%ATTACHURL%/pd5.pdf][Appunti (pdf)]]  Discussione esercizio [cammini]: applicazione di Bellman-Ford. *Cammini minimi tra tutte le coppie di nodi*. *Algoritmo di Floyd-Warshall*. Massimo sottovettore. Esercizio [prezzi].
</li>
<li>
[[%ATTACHURL%/pd6.pdf][Appunti (pdf)]]  Discussione esercizio [prezzi]: applicazione Programmazione Dinamica. *Massima Sottosequenza Comune* (LCS). *Edit Distance*. Esercizio [senza spazi].
</li>
<li>
[[%ATTACHURL%/pd7.pdf][Appunti (pdf)]]  Discussione esercizio [senza spazi]: applicazione Programmazione Dinamica. *Prodotto di Matrici*. _Esercizi_ sulla Programmazione Dinamica: [massima sottosequenza crescente] e [gettoni]. Esercizio [palindroma].
</li>
<li>
[[%ATTACHURL%/bt.pdf][Appunti (pdf)]]  Discussione esercizio [palindroma]: applicazione Programmazione Dinamica. *Backtracking*: Generare sottoinsiemi, colorazioni, permutazioni e combinazioni. Esercizio [cassaforte].
</li>
<li>
[[%ATTACHURL%/bt2.pdf][Appunti (pdf)]]  Discussione esercizio [cassaforte]: applicazione Backtracking. Sfrondare lo spazio di ricerca: *3-Colorazione*, *Cicli Hamiltoniani*, *Zaino*. Esercizi Backtracking: [cricca], [regine], [parità]. Esercizi Programmazione Dinamica: [numero sottosequenze crescenti], [cammino], [somma].
</li>
</ol>
</div>