Lezione del 28/04/2010

Esercizi: ricerca del secondo cammino minimo (esercizio 3 del 7 settembre 2009); algoritmo per la ricerca dell'albero dei cammini minimi in un ciclo.

Aggiornamento raccolta esercizi

E' stato aggiunto un nuovo esercizio nella raccolta.

Lezione del 26/04/2010

Algoritmo di Bellman-Ford per il calcolo dell'albero dei cammini minimi in un grafo senza cicli negativi: correttezza e complessita'. Algoritmo di Floyd-Warshall per il calcolo dei cammini minimi tra tutte le coppie di nodi: correttezza e complessita'.

Lezione del 21/04/2010

Albero dei cammini minimi. Esercizio: calcolo dell'albero dei cammini minimi da un insieme dei cammini minimi. Prime considerazioni sull'algoritmo per il calcolo dell'albero dei cammini minimi in grafi con pesi negativi.

Ufficio oggetti smarriti

Oggi (21 aprile) qualcuno ha lasciato sulla scrivania dell'aula 14 degli appunti. Li ho lasciati nella mia cassetta delle lettere (di fronte la copiatrice nelle segreterie di matematica) in una busta chiusa con su scritto "Appunti trovati in aula 14".

Lezione del 15/04/2010

L'algoritmo di Dijkstra per il calcolo di tutti i cammini minimi da una sorgente in grafi con pesi positivi: correttezza e costo dell'implementazione con 2-Heap e d-Heap.

Nuova versione della raccolta esercizi

Nella raccolta e' stato aggiunto il secondo esercizio svolto nella lezione del 12 Aprile 2010 (esercizio 18).

Lezione del 14/04/2010

Indicizzare gli elementi di uno Heap in modo che in tempo costante si possa accedere alla posizione di un determinato elemento nello Heap. Heap di grado d (d-Heap) generico: complessita' delle funzioni di gestione ed impatto sull'algoritmo di Prim.

Il problema della ricerca dei cammini minimi in un grafo: definizioni preliminari.

Lezione del 12/04/2010

Esercizi: progettazione di un algoritmo di complessita' lineare per il calcolo dell'MST su grafi di peso 1 o 2 (esercizio 3 della prova scritta del 18 Settembre 2007); ricerca del grafo geometrico minimo connesso (esercizio 18 nella raccolta).

Nuova versione raccolta esercizi

E' stata aggiornata la raccolta di esercizi. In particolare e' stata aggiunta la dimostrazione (Esercizio 17) fatta nella lezione del 22 marzo del fatto che, per il calcolo dell'MST di un grafo, si puo' assumere senza perdere di generalita' che i pesi degli archi sono tutti distinti. Infatti si dimostra che se si modificano i pesi di un grafo in modo da renderli tutti distinti senza alterare l'ordinamento originale si ha che l'MST del grafo modificato e' un MST del grafo di partenza.

Lezione del 7/4/2010

Soluzione dell'esercizio lasciato per casa. Algoritmo di prim per il calcolo del minimo albero coprente: complessita' di una implementazione ingenua; implementazione con heap e relativa complessita'.

Lezione del 31/3/2010

La struttura Union-Find con foresta di alberi bilanciati: costo computazionale logaritmico delle due operazioni (si veda l'esercizio 3 del 2008-09-15). Esercizio: Un grafo pesato connesso e non diretto con pesi distinti ha un unico minimo albero coprente. Esercizio per casa: Dimostrare che il minimo albero coprente minimizza l'arco di costo massimo rispetto tutti gli alberi coprenti del grafo.


Descrizione python della struttura Union-Find con alberi:

class unionfind:
   def __init__(self, n):
      self.T = [-1]*n
      self.H = [0]*n
   
   def root(self, x):
      px = x
      while self.T[px] != -1:
         px = self.T[px]
      return px   
   
   def find(self, x, y):
      if self.root(x) == self.root(y):
         return True
      else:
         return False

   def union(self, x, y):
      px = self.root(x)
      py = self.root(y)

      if self.H[px] > self.H[py]:
         self.T[py] = px
      else:
         self.T[px] = py
         if self.H[px] == self.H[py]:
            self.H[px] = self.H[px] + 1

L'algoritmo di Kruskal modificato per utilizzare la nuova struttura

from union_find import *
from heapq import heappush, heappop


def kruskal(G):
   n = len(G)
   heap = []
   T = []
   for u in range(n):
      for v in G[u]:
         edge = v[0], u,  v[1] # peso, nodo, nodo
         heappush(heap, edge)

   UF = unionfind(n)

   while heap:
      edge = heappop(heap) 
      u, v, w = edge[1], edge[2], edge[0]
      if UF.find(u, v) == False:
         UF.union(u, v)
         T.append((u,v))
   
   return T