Progettazione di Algoritmi a.a. 2015-2016

Appunti

  1. 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]
  2. 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].
  3. 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].
  4. 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].
  5. 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].
  6. 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].
  7. 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].
  8. 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].
  9. 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].
  10. 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].
  11. 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].
  12. 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].
  13. 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].
  14. Appunti (pdf) Breve Discussione degli esercizi della prova intermedia. Divide et Impera. Master Theorem. Il problema del Massimo Sottovettore. Esercizio [salto].
  15. 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].
  16. 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].
  17. 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].
  18. Appunti (pdf) Discussione esercizio [resto 2]: applicazione Programmazione Dinamica. Longest Path in DAG. Pianificazione di Attivitą (CPM). Sistemi con Vincoli di Differenza. Esercizio [viaggio].
  19. Appunti (pdf) Discussione esercizio [viaggio]: dalla rappresentazione tramite DAG alla Programmazione Dinamica. Cammini minimi con pesi anche negativi. Algoritmo di Bellman-Ford. Esercizio [cammini].
  20. 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].
  21. Appunti (pdf) Discussione esercizio [prezzi]: applicazione Programmazione Dinamica. Massima Sottosequenza Comune (LCS). Edit Distance. Esercizio [senza spazi].
  22. Appunti (pdf) Discussione esercizio [senza spazi]: applicazione Programmazione Dinamica. Prodotto di Matrici. Esercizi sulla Programmazione Dinamica: [massima sottosequenza crescente] e [gettoni]. Esercizio [palindroma].
  23. Appunti (pdf) Discussione esercizio [palindroma]: applicazione Programmazione Dinamica. Backtracking: Generare sottoinsiemi, colorazioni, permutazioni e combinazioni. Esercizio [cassaforte].
  24. 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].
  25. RETI DI FLUSSO: parte1 (pdf), parte2 (pdf), parte3 (pdf)

Topic attachments
I Attachment History ActionSorted ascending Size Date Who Comment
PDFpdf reti_di_flusso1.pdf r1 manage 1902.0 K 2017-02-21 - 14:57 AngeloMonti  
PDFpdf reti_di_flusso3.pdf r1 manage 1977.1 K 2017-02-21 - 15:00 AngeloMonti  
PDFpdf reti_di_flusso_2.pdf r1 manage 1475.7 K 2017-02-21 - 14:58 AngeloMonti  

This topic: Algoritmi2 > WebHome > PALGappunti2014
Topic revision: r36 - 2017-02-21 - AngeloMonti
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback