Lezione del 29/3/2010

Complessita' ammortizzata. Implementazione dell'algoritmo di Kruskal con struttura union-find implementata con liste disgiunte: complessita' dell'algoritmo.

from disjoined_list import *
from heapq import heappush, heappop


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

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

Lezione del 24/3/2010

L'algoritmo di Kruskal per il calcolo del minimo albero ricoprente: correttezza e complessita' di una implementazione ingenua. Verso una implementazione piu' efficiente: Struttura union-find con liste disgiunte. Costo computazionale di una sequenza di operazioni union.

Implementazione delle liste disgiunte in python:

from collections import deque

class elem:
   def __init__(self, nm):
      self.name = nm
      self.list = 0

class disjoinedlist:
   def __init__(self, e):
      self.L = deque()
      self.L.append(e)
      self.len = 1
      self.L[0].list = self
   
def find(x, y):
   if x.list == y.list:
      return True
   else:
      return False

def union(x, y):
   if x.list.len < y.list.len:
      shortest = x.list
      longest = y.list
   else:
      shortest = y.list
      longest = x.list

   for z in shortest.L:
      z.list = longest
      longest.L.append(z)

   shortest.L.clear()
   longest.len = longest.len + shortest.len

Lezione del 22/3/2010

Il problema del minimo albero coprente (MST): perturbare i pesi degli archi in modo che questi risultino tutti distinti e l'MST dell'istanza perturbata sia un MST dell'istanza originale; regola del taglio e regola del ciclo.

Lezione del 17/3/2010

Esercizio: I grafi a torneo sono Hamiltoniani. Algoritmo per la verifica della forte connessione di un grafo diretto: si veda l'esercizio 3 della prova scritta del 10/6/2008.

Lezione del 15/3/2010

Utilizzo di una coda nella visita: visita in ampiezza. Le proprieta' dell'albero di visita in ampiezza.

L'algoritmo di visita in ampiezza:

from collections import deque

def bfs(G,s):
   n = len(G)
   S = deque()
   S.append(s) # aggiunge un elemento alla fine della struttura

   X = [False]*n
   T = [-1]*n

   while len(S)>0:
      u = S.popleft() # estrae il primo elemento
      if X[u]== False:
         X[u] = True
         for v in G[u]:
            if X[v] == False and T[u] == -1:
               T[v] = u
                S.append(v)
   return T

Lezione del 10/3/2010

Correttezza dell'algoritmo di visita: Tutti i nodi della componente connessa C a cui appartiene il nodo di partenza sono visitati; T e' un albero i cui nodi sono quelli della componente connessa C. Implementazione della visita che utilizza una coda pila come insieme di appoggio: complessita' computazionale; visita in profondita'.

Codice python della visita in profondita'.

from collections import deque

def dfs(G, s):
   n = len(G)
   S = deque()
   S.append(s) # aggiunge un elemento alla fine della struttura

   X = [False]*n
   T = [-1]*n

   while len(S)>0:
      u = S.pop() # estrae l'ultimo elemento inserito
      X[u] = True
      for v in G[u]:
         if X[v] == False:
            T[v] = u
             S.append(v)
   return T

Lezione del 8/3/2010

Verifica della connessione di un grafo calcolando le potenze della matrice di adiacenza. Verifica della connettivita' utilizzando gli algoritmi di visita di un grafo. Codice python di un algoritmo di visita:

def visit(G):
   n = len(G)
   A = set()
   A.add(0)

   X = [False]*n
   T = [-1]*n

   while len(A)>0:
      u = A.pop()
      X[u] = True
      for v in G[u]:
         if X[v] == False:
            T[v] = u
             A.add(v)
   return T

Il grafo G e' rappresentato come una lista (indicizzata) di liste di adiacenza. Per esempio

G = [[1,2,3,4], [0,2], [0,1,4], [0,4], [0,2,3]]

Il nodo 0 ha per vicini i nodi 1, 2, 3 e 4 e cosi' via.

Cambio aula

Da lunedi 8 marzo le lezioni si svolgeranno in aula 14 anziche' aula 11.

Lezione del 3/3/2010

Operatori su grafi; Rappresentazione dei grafi con lista di archi, liste di adiacenza e matrice di adiacenza; Complessita' computazionale degli operatori nelle tre rappresentazioni; Esercizi sulle proprieta' dei grafi: un grafo connesso di n nodi ha almeno n-1 archi; un grafo aciclico di n nodi ha massimo n-1 archi; un albero di n nodi ha n-1 archi; Il quadrato della matrice di adiacenza di un grafo rappresenta cammini di lunghezza due: come estendere il risultato.

Lezione del 1/3/2010 (Prima lezione a.a. 2009-2010)

Concetti e definizioni preliminari sui grafi: grafi diretti e non diretti; vicinato di un nodo; cammini e cicli; grafi pesati; connettivita' e componenti connessi.

Risultati della prova scritta del 2 Febbraio 2010

Gli studenti Lesles e Stand-by hanno superato la prova scritta, il primo con la votazione di 28 ed il secondo 29.

L'orale si terra' il 10/2 in aula 9 dalle 12:00 alle 13:00. Gli studenti che desiderano visionare lo scritto possono farlo durante l'orale.

Appello straordinatio & prova intermedia

Il 2 Febbraio 2010 alle ore 14.00 nell'aula 12 si terrà l'esonero di Algoritmi e strutture dati con laboratorio riservato agli studenti immatricolati con D.M. 270/04.

Contemporaneamente e nella stessa aula si terrà un appello straordinario dell'esame di Algoritmi e strutture dati con laboratorio riservato agli studenti immatricolati con D.M. 509/99.

Si ricorda che la prenotazione e' obbligatoria (Totem).

Nuova struttura del corso

A partire dall'anno accademico 2009/2010 il corso di "Algoritmi e strutture dati con laboratorio" da 6 cfu viene rimosso e sostituito dall'omonimo corso da 12 cfu composto da due moduli divisi nei due semestri. Il primo modulo copre gli argomenti del vecchio corso di "Elementi di algoritmi e strutture dati" (anche questo rimosso) ed il secondo copre gli argomenti del corso "Algoritmi e strutture dati con laboratorio".

Pertanto gli studenti di qualsiasi anno che non hanno sostenuto nessuno dei vecchi due corsi di algoritmi dovranno sostenere l'esame del nuovo corso da 12 cfu. Mentre gli altri studenti - ovvero quelli che hanno sostenuto l'esame di uno soltanto dei due corsi - potranno seguire il modulo mancante del nuovo corso da 12 cfu e sostenere l'esame soltanto su questo modulo.

Se ci sono domande piu' specifiche prego gli studenti di porle come commento a questo post in modo che siano utili anche per altri studenti.

Risultati della prova scritta del 7 Settembre 2009

Lo studente col nick 0113601 ha superato la prova scritta del 7 Settembre 2009 con la votazione di 21/30 pertanto e' ammesso all'orale del 8/9/2009 nello studio 0117 alle ore 15:30. Gli studenti che desiderano visionare la prova possono farlo durante l'orale.

Avviso: orale del 8/9/2009

Causa concomitanza con il test di ingresso, la prova orale del 8/9/2009 e' spostata alle ore 15:30.