Cambiamento data orale

L'orale del II modulo di ASDL del 23/9 e' spostato al 24/9 ore 15 presso lo studio 0117. Chi avesse altri impegni (altri esami) puo' contattare il docente per fissare una data alternativa.

Risultati prova scritta del 21/9/2010

I seguenti studenti hanno superato positivamente la prova scritta del 21/9/2010

Biancardi, D'Ambrogio, De Santis, Di Fonzo, Marianeschi e Speranza.

Pertanto sono ammessi all'orale.

Inoltre si comunica che l'orale e' spostato a venerdi' 24/9. Gli studenti che hanno altri esami sono pregati di contattarmi per fissare un'altra data.

Risultati della prova scritta del 15/7/2010

Elenco degli studenti che hanno superato il secondo modulo della prova scritta del 15/7/2010.

Camillacci, 24
Fenaroli, 27,
Fortuna, 25
Giovannotti, 26
Proietto, 24
Volpi, 24

Avviso

E' stato pubblicato il testo ed una possibile soluzione dell'esame del 16 Giugno 2010.

Risultati della prova scritta del 16/6/2010

I risultati sono divisi in tre gruppi: il primo gruppo riguarda gli studenti che hanno sostenuto l'esame intero; il secondo gruppo riguarda gli studenti che avevano superato la prova intermedia di febbraio e che hanno sostenuto la prova del II modulo; il terzo gruppo riguarda gli studenti che hanno gia' superato l'esame di EASD (o simili) nei precedenti anni accademici.

Gruppo1: Studenti ammessi all'orale che hanno sostenuto l'intero esame:

- Totino, 15

Gruppo2: Studenti ammessi all'orale che hanno gia' superato la prova intermedia di febbraio. Il voto indicato e' relativo alle due prove.

- Valentini, 21
- Volpi, 18
- Postoronca, 16

In ogni caso gli studenti che hanno superato la prova di Febbraio possono ripetere l'esame del II modulo mantenendo il voto della prima parte.

Gruppo3: Studenti che hanno gia' superato EASD e che sono ammessi all'orale sul II modulo di ASDL

- Red83, 18
- Serrago, 20

Aggiornamento raccolta esercizi

Nella raccolta sono state aggiunte le soluzioni delle ultime esercitazioni svolte a lezione.

Primo appello sessione estiva

E' stata attivata la prenotazione per lo scritto di giugno sul Totem.

Si ricorda che la prenotazione allo scritto e' obbligatoria.

Fine lezioni

Il corso e' terminato con la lezione di oggi 26/5. In bocca al lupo per l'esame.

Lezione del 26/5/2010

Correzione esercizio della lezione del 24.

Esercizio: Modificare tutti i costi degli archi di un grafo sommando una costante C non mantiene il cammino minimo; sommare a tutti i costi w(u,v) degli archi (u,v) la quantita' alfa(v) - alfa(u) per qualche funzione alfa sui nodi mantiene il cammino minimo; non esiste una funzione alfa sui nodi tale che w(u,v) - alfa(u) + alfa(v) > 0 per ogni arco (u,v).

Lezione del 24/5/2010

Esercizio in aula: l'algoritmo di codifica di Huffmann crea codici tutti di lunghezza k nel caso di alfabeto di dimensione 2^k e caratteri con la stessa frequenza.

L'algoritmo di Graham per il calcolo del minimo insieme convesso ha complessita' ottimale.

Dispense

Nella sessione Materiale Didattico di questo blog si possono trovare degli appunti sugli ultimi argomenti del corso non coperti dai libri consigliati.

Lezione del 20/5/2010

Il problema del minimo insieme convesso: l'algoritmo di Graham.

Cambio aula di domani

Gli uffici della presidenza mi comunicano che l'aula T8 domani non e' piu' disponibile quindi, contrariamente a quanto comunicato nel post di ieri, l'aula della lezione di domani (20/5) e' la 3 e non la T8. Mi scuso per la confusione e mi raccomando di divulgare il piu' possibile la notizia.

Recupero lezione di mercoledi' 19

La lezione di mercoledi' 19 verra' recuperata giovedi' 20 dalle ore 15.00 in aula T8.

Avviso

In occasione della settimana di mobilitazione degli Atenei Italiani contro il DDL Gelmini, e' stata deliberata la sospensione della didattica nei giorni 18 e 19 maggio. Pertanto La lezione del 19/5 non si svolgera'.

Probabilmente (se ci verra' concessa un'aula) verra' recuperata giovedi' 20 maggio. Quindi vi invito a consultare questo blog per avere ulteriori informazioni.

Avviso

Il ricevimento studenti di oggi (17/5) non si terra'.

Avviso

Lunedi prossimo in aula 12 a partire dalle ore 14.00 si terra' una assemblea degli studenti e lavoratori della Facolta' in cui si discutera' del nuovo Disegno di Legge in merito alla riforma della Universita' Pubblica.

Per dare la possibilita' di partecipare all'evento la lezione di ASDL di lunedi' viene rinviata.

Lezione del 12/5/2010

Ottimalita' dei codici di Huffmann.

Lezione del 3/5/2010

La tecnica per la progettazione degli algoritmi Divide-et-Impera: l'algoritmo per il problema del closest pairs (dato un insieme di punti del piano, trovare la coppia a distanza minima).

Lezione del 10/5/2010

La tecnica Greedy per la progettazione degli algoritmi: l'algoritmo di codifica di Huffman per la compressione di dati.

Lezione del 5/5/2010

Esercizi: Progettare un algoritmo per decidere se un grafo e' bipartito (rielaborazione dell'esercizio 2 del 10 giugno 2010); Progettare un algoritmo per decidere se un grafo ha o non ha cicli di lunghezza dispari.

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

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).