MaterialiDidattici < Algoritmi2

---+ Esercitazioni 2020:

---+ Materiali
   * *Didattica a Distanza* ai tempi della pandemia 2020:
      * *Esercitazione 2*: BFS, DFS e topological sort: [[%ATTACHURL%/lezione0417.pdf][slides Lezione 17/4]].
      * *Esercitazione 3*: BFS, DFS, topological sort e SCC: [[%ATTACHURL%/lezione0424.pdf][slides Lezione 24/4]] e [[%ATTACHURL%/tarjan.pptx][animazione esecuzione di Tarjan]].
      * *Esercitazione 4*: Cammini minimi da sorgente unica: Dijkstra e Bellman-Ford. Proprietà degli MST: [[%ATTACHURL%/lezione0508.pdf][slides lezione 8/5]].
      * *Esercitazione 5*: Cammini minimi tra tutte le coppie. Altri esercizi su MST, Dijkstra e Bellman-Ford [[%ATTACHURL%/lezione0515.pdf][slides lezione 15/5]].
      * *Esercitazione 6*: Reti di Flusso. Altri esercizi su MST, Dijkstra e Bellman-Ford [[%ATTACHURL%/lezione0522.pdf][slides lezione 22/5]].
      * *Esercitazione 7*: Il problema dell'accoppiamento su grafi bipartiti. Esercizi su Reti di Flusso, MST, BFS, chiusura transitiva [[%ATTACHURL%/lezione0529.pdf][slides lezione 29/5]].

---+ Diario

*Venerdì 24 febbraio 2020: Esercitazione 1 (aula III Castelnuovo)*
   * *Dimostrazioni*
      * Dato un grafo non orientato _G_, almeno uno tra _G_ e il suo complementare è connesso.
      * Dato un grafo non orietnato _G_ = (_V_, _E_), esistono sempre almeno due nodi in _V_ con lo stesso grado.
   * *Rappresentazioni*: complessità di alcuni semplici problemi su *grafi diretti* con matrici e liste di adiacenza.
      * grado entrante/uscente; [ *Cormen, 22.1-1* ]
      * grafo trasposto [ *Cormen, 22.1-3* ]
      * grafo quadrato [ *Cormen, 22.1-5* ]
   * *Perle*: problema del pozzo universale (grafo diretto rappresentato con matrice di adiacenza) [ *Cormen, 22.1-6* ].
   * *Alberi e vettori di padri*: calcolare la distanza tra due nodi [e problemi collegati: minimo antenato comune e distanza dalla radice].

   * *Esercizi per casa*: in un albero rappresentato con vettori di padri, dato un nodo _u_ calcolare l'insieme dei nodi del sottoalbero radicato in _u_.

*Venerdì 17 aprile 2020: Esercitazione 2 (a distanza)*
   * *Capire la BFS*
      * In una BFS, gli alberi di visita dipendono dall'ordine delle liste di adiacenza, ma non le distanze dalla radice [ *Cormen, 22.2-5* ].
      * Alberi di cammini minimi potrebbero non essere il risultato di nessuna BFS [ *Cormen, 22.2-6* ].
      * Usare la BFS per determinare i nodi equidistanti da due nodi.
      * Distanza tra due sottoinsiemi di nodi.
      * Data la BFS di un grafo come vettore di padri, determinare se eliminare un arco modifica le distanze.
   * *Capire la DFS*
      * verificare se alcuni alberi possono essere la visita DFS di un grafo (orientato o meno).
      * fenomeni apparentemente contro-intuitivi nei tempi di entrata e di completamento in una DFS [ *Cormen, 22.3-8, 22.3-9, 22.3-11* ]
      * In un grafo non orientato, trovare un cammino che attraversa tutti gli archi 1 volta in entrambe le direzioni.
   * *Topological Sort* e *Componenti Fortemente Connesse*
      * Orientare gli archi di un grafo indiretto per ottenere un DAG.
      * Determinare se un nodo è _principale_. Trovare un nodo principale. Trovare l'insieme minimo di nodi principali.
   * *Dimostrazioni*
      * BFS(G)=DFS(G) sse G è un albero.

*Venerdì 24 aprile 2020: Esercitazione 3 (a distanza)*
   * *BFS & DFS*
      * Diametro di un albero: soluzione con doppia BFS [ *Cormen, 22.2-8* ] e con DFS che calcola simultaneamente diametro e profondità.
      * cammini minimi di archi rossi in grafo con archi rossi e neri [ *Monti* ].
   * *Topological Sort*
      * Contare gli ordinamenti topologici in un DAG [ *Monti* ].
      * Eliminare il numero minimo di archi per ottenere un DAG [ *Monti* ].
      * Contare i cammini da _u_ a _v_ in un DAG [ *Cormen, 22.4-2* ]: versione efficiente con Programmazione Dinamica.
      * Algoritmo alternativo per Topological Sort [ *Cormen, 22.4-5* ]: strutture dati per renderlo efficiente.
   * *Componenti Fortemente Connesse*
      * Esempio di esecuzione dell'algoritmo di Tarjan.
      * Come cambia il numero di SCC aggiungendo un arco [ *Cormen, 22.5-1* ].
      * Dato G, trovare un grafo G' con le stesse SCC, ma un numero minimo di archi [ *Cormen, 22.5-6* ].
      * Classificare archi interni/esterni alle SCC [ *Monti* ].
   * *Esercizi aperti (discussi ma non risolti)*
      * Determinare se un grafo diretto è semi-connesso [ *Cormen, 22.5-7* ].
      * Determinare se un grafo diretto è singolarmente connesso [ *Cormen, 22.3-13* ].
      * Alcuni problemi su grafi s-t connessi: trovare il ciclo più vicino alla sorgente _s_, determinare cammini disgiunti [ *Salvo* ].
      * Altri problemi: determinare distanza media, nodi a distanza massima, grafo parzialmente orientato.

*Venerdì 8 maggio 2020: Esercitazione 4 (a distanza)*
   * *Afffinità e divergenze: Dijkstra vs MST*
      * Dijkstra e pesi negativi. Aggiungere costanti additivi nei cammini minimi e negli MST [ *Monti* ].
      * Alberi minimi e DAG di cammini minimi [ *Monti* ]. Problemi sull'unicità dell'MST [ *Monti* e *Cormen, 23.1-6* ]
   * *Algoritmo di Dijkstra*
      * Verifica di una soluzione di cammini minimi in _O(n+m)_ [ *Cormen, 24.4-4* ].
      * Contare i cammini minimi [ *Monti* ].
      * Cammino super-minimo [ *Monti* ].
   * *Proprietà degli MST*
      * Controesempio al converso del Teorema dell'arco leggero [ *Cormen, 23.1-2* ].
      * Proprietà degli archi leggeri [ *Cormen, 23.1-3* ] e [ *Cormen, 23.1-4* ]. Sottoinsiemi di archi di peso minimo [ *Cormen, 23.1-7* ]
      * Archi pesanti [ *Cormen, 23.1-5* ].
   * *Algoritmo di Bellman-Ford*
      * Terminazione di Bellman-Ford in un numero di iterazioni pari al cammino minimo di lunghezza massima [ *Cormen, 24.2-3* ]
      * Marcare i nodi raggiungibili dalla sorgente attraverso un ciclo negativo [ *Cormen, 24.2-4* ].
      * Elencare i vertici *appartenenti* a un ciclo di peso negativo [ *Cormen, 24.2-6* ].

*Venerdì 15 maggio 2020: Esercitazione 5 (a distanza)*
   * *Cammini minimi tra tutte le coppie*
      * `Moltiplicazione' di matrici e generalizzazione di Bellman Ford: algoritmo naif. Ottimizazzione con Programmazione Dinamica [ *Cormen, 25.2* ].
      * Ricostruire la matrice dei padri dalla matrice dei costi [ *Cormen, 25.2-6* ]
      * Rilevare la presenza di un ciclo negativo [ *Cormen, 25.2-9* ]
      * Determinare la lunghezza minima di un ciclo negativo [ *Cormen, 25.2-10* ]
      * Floyd-Warshall e chiusura transitiva di un grafo diretto [ *Cormen, 25.4* ]. Il caso dei cicli negativi [ *Cormen, 25.3-6* ].
      * Chiusura transitiva di un DAG in _O(nm)_.
   * *Cammini minimi da sorgente unica* e *MST*
      * Cammini minimi in un DAG [ *Cormen, 24.3* ]
      * Unicità della sequenza dei pesi degli archi in un MST [ *Cormen, 23.1-9* ].
      * Perché fallisce il Divide et Impera nel calcolo dell'MST [ *Cormen, 23.3-8* ]
      * Algoritmo di Kruskal con pesi limitati sugli archi [ *Cormen, 23.3-4* ]

*Venerdì 22 maggio 2020: Esercitazione 6 (a distanza)*
   * *Reti di Flusso*
      * Reti, flusso, tagli, rete residua, cammini aumentanti. Massimo flusso/taglio minimo.
      * Algoritmi di Ford-Fulkerson ed Edmonds-Karp per il massimo flusso.
      * Esercizi: two disjoint paths problem: varie versioni.
   * *Cammini minimi da sorgente unica* e *MST*
      * Affidabilità di un canale di comunicazione [ *Cormen, 24.4-6* ]
      * Dijkstra con pesi interi limitati [ *Cormen, 24.4-7*, *24.4-8*, *24.4-9* ]
      * Algoritmo di Prim con pesi limitati sugli archi [ *Cormen, 23.3-5* ]
      * Algortimi alternativi per MST: corretti o meno? [ *Cormen, 23.4* ]

*Venerdì 29 maggio 2020: Esercitazione 7 (a distanza)*
   * *Reti di Flusso*
      * Accoppiamento su grafi bipartiti: uso di Ford-Fulkerson.
      * Esercizi: basterebbero sempre _E_ cammini aumentanti per trovare il flusso massimo [ *Cormen, 26.2-10* ]
      * Arco-connettività con Reti di flusso [ *Cormen, 26.2-11* ]
      * Taglio super-minimo [ *Cormen, 26.2-13* ]
      * Massimo flusso dopo aver modificato la capacità di un arco [ *Cormen, 26.4* ]
   * *Potpourri* finale
      * MST dopo aver diminuito il peso di un arco [ *Cormen, 23.1-11* ]
      * Distanze minime su grafo che rovescia archi al tempo T [ *Monti*, esonero *2019* ]
      * Ridurre il problema della chiusura transitiva alla chiusura transitiva di un DAG [ *Cormen, 25.3-9* ]


-- %USERSIG{IvanoSalvo - 2020-04-18}%

<!--
---++ Comments

%COMMENT%
 -->
This topic: Algoritmi2 > WebHome > MaterialiDidattici
Topic revision: r8 - 2020-05-29 - IvanoSalvo