Tags:
create new tag
view all tags

Esercitazioni 2020:

Materiali

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 ]

-- Ivano Salvo - 2020-04-18

-->

Edit | Attach | Watch | Print version | History: r8 < r7 < r6 < r5 < r4 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r8 - 2020-05-29 - IvanoSalvo






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback