AAllggoorriittmmii

CCoommpplleemmeennttii

AAAA 22000088--22000099

• Programma del corso..........................pag 2 • Appunti …………………………………. .pag 3 • Riassunto Ricorsioni e Procedure viste a lezione ……………………. pag 51

• Domande di teoria in preparazione all’esame………………………………. pag 58

13.01 – Ripasso/Esercitazioni L01

• Introduzione al corso • Mutua ricorsione • Count&Sort • Problemi di decisione, di ricerca e di ottimizzazione

E01 • Crescita delle funzioni (cap. 3) • Richiami sulla ricorsione: calcolo del fattoriale • Ricerca dicotomica, calcolo altezza di un albero

binario (appendice B.5) E02

• Ricorrenze e tempi di calcolo di algoritmi ricorsivi (capp. 4.1, 4.2 e 4.3)

• Il metodo divide et impera: algoritmo Merge-sort (cap. 2.3)

16.01 – Introduzione alla programmazione dinamica L02

• Enumerazione e backtracking • Esempio numeri di Fibonacci, albero di ricorsione,

tabulazione (slides) L03

• Distanza di edit, importanza, ricorrenza, calcolo (slides)

20.01 – Programmazione dinamica 1 L04

• Programmazione delle catene di montaggio (cap. 15.1)

L05 • Prodotto righe per colonne di matrici: algoritmo base

(cap. 28.1) • Algoritmo di Strassen (cap. 28.2)

E03 • Esecuzione di procedure ricorsive: stack e record di

attivazione 23.01 – Programmazione dinamica 2 L06

• Catena di moltiplicazioni di matrici (cap. 15.2) • Determinazione della ricorrenza di programmazione

dinamica • Calcolo tabulare di m(i,j): programma, esecuzione

manuale L07

• Gli elementi della programmazione dinamica (cap. 15.3)

• Programmazione ricorsiva con memorizzazione • Iterazione vs. ricorsione

27.01 – Programmazione dinamica 3 - Grafi L08

• Il problema della LCS (cap. 15.4) L09

• Nomenclatura su grafi (appendice B.4) • Rappresentazione di grafi in memoria (cap. 22.1)

L10 • Visita in ampiezza (cap. 22.2): Schema generale

dell’algoritmo 30.01 – Algoritmi di visita di grafi 1 L11

• Correttezza di BFS (cap. 22.2) • BFS e cammini minimi (cap. 22.2)

L12 • Visita in profondità (cap. 22.3): Schema generale

dell’algoritmo 03.02 – Esercitazioni E04

• Calcolo della LCS crescente E05

• Calcolo della LCS crescente

06.02 – Esercitazioni E06

• Calcolo della sottosequenza comune più pesante (HCS) e confronto con LCS

E07 • Componenti connesse pari; SUBSETSUM

03.03 – Algoritmi di visita di grafi 2 - Problemi d i cammino minimo L13

• Classificazione degli archi in DFS (cap. 22.3) • Proprietà del DFS (cap. 22.3)

L14 • Applicazioni di DFS: Ordinamento topologico (cap.

22.4) • Ricerca delle componenti fortemente connesse in un

grafo orientato (cap. 22.5) L15

• Introduzione ai problemi di cammino minimo (capp. 24.1 e 25.1)

06.03 – Problemi di cammino minimo L16

• Algoritmo di rilassamento e proprietà L17

• Algoritmo di Dijkstra (cap. 24.4) 10.03– Esercitazioni E8

• Cammino minimo con almeno un arco rosso 1 E9

• Cammino minimo con almeno un arco rosso 2 13.03 – Problemi di cammino minimo L18

• Algoritmo di Bellman-Ford (cap. 24.3) L19

• Algoritmo di Floyd-Warshall (cap. 25.3) 17.03 – Esercitazioni E10

• Esercizi ricapitolativi sulla visita di un grafo E11

• Esercizi ricapitolativi su cammini minimi E12

• Esercizi ricapitolativi su cammini minimi

24.03 – Reti di flusso - NP completezza L20

• Introduzione alle reti di flusso (cap. 26.1) L21

• Algoritmo di Ford-Fulkerson (cap. 26.2) L22

• Tempo polinomiale (cap. 34.2) • Verifica in tempo polinomiale (cap. 34.3)

27.03 – NP completezza L23

• NP completezza e riducibilità (cap. 34.4) • Dimostrazione della NP completezza (cap. 34.5)

L24 • Problemi NP completi (cap. 34.6)

N.B. Le date delle lezioni e la suddivisione degli argomenti tra le lezioni sono indicative; potranno verificarsi piccoli cambiamenti dovuti ad eventuali indisposizioni del docente, scioperi, e altri eventi imprevedibili.

LCS Significato parametri coefficienti delle ricorrenze - X,Y sequenze di lunghezza |X|=n, |Y|=m - Xi sottosequenza da 1 a i, Yj sottosequenza da 1 a j - i in {1,...,n}, j in {1,...,m} - C[i,j] lunghezza dell’ottimo relativo a Xi e Yj (C[i,j]=|lcs(Xi,Yj)|) Caso base Se xi≠yj non esiste LCS tra Xi e Yj che termina sia con xi e yj, quindi C[i,j]=0. Equazioni delle ricorrenze c(i,j)={ se i=0,j=0 { se ai=bj, con i,j>0 c(i,j)=c(i-1,j-1)+1 { altrimenti c(i,j)=max { c(i-1,j), c(i,j-1)} Tempo di calcolo TETA(nm) LCS LUNGHEZZA>=K INPUT: 2stringhe X e Y e k>=0 OUTPUT: C[i,j,z]:{0,1} se esiste una sottoseq comune a X e Y >=z terminante con xi=yj Z € {0,….k} X=<x1,…..xn> Y=<y1,…..ym> Equazioni delle ricorrenze

{ se (i=0 V,j=0) and z=0 � 1 { se (i=0 V,j=0) and z≠0 � 0 c(i,j,k) = { se i,j>=1 and z=0 and xi=yj � 1

{ se xi=yj,e z>=1 con i,j>0 � c(i-1,j-1,z-1) { se xi≠yj,e z>=1 con i,j>0 � c(i-1,j,z) V

c(i,j-1,z) Soluzione C[m,n,k]={1 � esiste / 0 � non esiste} Tempo di calcolo TETA(nm) HCS – seq comune + pesante Caratterizzazione HCS Z=<z1,….zk> = HCS(X,Y) Se Xm=Yn � Zk=Xm=Yn Zk-1=HCS(Xm-1,Yn-1) Equazione ricorrenze Indico con c[i,j] il peso di una HCS tra Xi e Yj

{0 se i=0 V j=0 C[i,j] = {w(xi) + c[i-1,j-1] se xi=yj

{MAX (c[i-1,j], c[i,j-1]) se xi≠yj Tempo di calcolo TETA(nm) LECS – LCS crescente INPUT: 2stringhe X e Y X=<x1,…..xm> Y=<y1,…..yn> c[i,j] = lunghezza LECS tra Xi e Yj con xi=yj Ricorrenze

{0 se xi≠yj C[i,j] = {1+ MAX (c[s,t] con 1≤s≤I 1≤t≤j xs≤xi) se xi=yj Tempo di calcolo O((nm)2) CONCATENAZIONE OTTIMA MATRICI Significato parametri coefficienti delle ricorrenze - A1..An Matrici : p1 p2 pn p0[A1] * p1[A2] *...pn-1[An] - i,j indici indicanti le matrici 1<=i<=j<=n

- M[i,j] num minimo di prodotti scalari per la concatenazione Equazioni delle ricorrenze M(i,j)={ se i=j M(i,j)= 0 { min(i<=k<=j){M(i,k)+M(k+1,j)+pi-1*pk*pj} Caso base Se non ho matrici da moltiplicare M(i,j)= 0 ZAINO Input: n oggetti, ad ogni ogetto i € {1,2,….n} è associato un peso wi>0 e un valore vi>0 Contenitore capacità W Output: Riempire lo zaino max il val totale degli oggetti selezionati Def variabile M[i,q]=valore max oggetti compresi tra {1,…i} che possono entrare in un box grande q Con i:1….n q:0…..W Eq ricorrenza {se i=0 V q=0 � 0 M[i,q]= { se wi>q M[i-1,q] //nn c’è spazio non lo metto

{ se wi≤q MAX(M[i-1,q-wi]+vi, M[i-1,q]) Algoritmo For i=1 to m For q=1 to W If wi>q then M[i,q]=M[i-1,q] Else M[i,q]= MAX(M[i-1,q-wi]+vi, M[i-1,q]) VARIANTE dello zaino Esiste un sottoinsiem di {x1,…xn} i cui elementi danno somma k Def variabile E[i,k]={0,1} se esiste o no un sottoins….. Eq ricorrenza {se per ogni i=0 e k=0 � 1 {se i=0 e per ogni k>0 � 0 M[i,q]= { se xi>k E[i-1,k]

{ se xi≤k OR(E[i-1,k-xi], E[i-1,k]) 1)Cammini minimi tra tutte le coppie di vertici in G pesato. Significato parametri coefficienti delle ricorrenze - G=<V,E,w> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - i,j nodi del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j) costo cammino minimo i,j con vertici nell'intervallo 1...k Ricorrenza D(k)(i,j)={ se k non ϵ cammino minimo D(k)(i,j) =D(k)(i,j) { se k ϵ D(k)(i,j) =D(k-1)(i,t)+D(k-1)(t,j) D(k)(i,j)=min{D(k-1)(i,j), D(k-1)(i,k)+D(k-1)(k,j) se k>=1 Caso base D(0)(i,j)={w[i,j] per ogni(i,j) ϵ E { infinito altrimenti D(0)(i,j)={w[i,j] per ogni(i,j) ϵ E { infinito altrimenti D(0)(i,j)={infinito

Soluzione D(n)(i,j) 2)Cammini minimi tra tutte le coppie di vertici in G pesato t.c. contengano esattamente 2 archi rossi. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,col> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: E ->{R,N} funzione che associa un colore ad un arco - i,j vertici (nodi) del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,r) costo cammino minimo i,j con vertici nell'intervallo, con esattamente r archi rossi Ricorrenza D(k)(i,j,r)={ se k non ϵ D(k)(i,j,r) =D(k-1)(i,j,r) { se k ϵ D(k) (i,j,r) =min(r1+r2=r){D(k-1)(i,k,r1)+D(k-1)(k,j,r2)} D(k)(i,j,r)=min{D(k-1)(i,j,r) , min(r1+r2=r){D(k-1)(i,k,r1)+D(k-1)(k,j,r2)}} Caso base D(0)(i,j,0)={w[i,j] per ogni(i,j) ϵ E and col (i,j)=N { infinito altrimenti D(0)(i,j,1)={w[i,j] per ogni(i,j) ϵ E and col (i,j)=R { infinito altrimenti D(0)(i,j,2)={infinito Soluzione D(n)(i,j,2) 3)Cammini minimi tra tutte le coppie di vertici in G pesato t.c. contengano al più 2 archi rossi //cambio condizione e copio quello sopra Soluzione min{D(n)(i,j,r) | r <=2} 4)Cammini minimi tra tutte le coppie di vertici in G pesato t.c. contengano almeno 2 archi rossi. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,col> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: E ->{R,N} funzione che associa un colore ad un arco - i,j vertici (nodi) del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,r) costo cammino minimo i,j con vertici nell'intervallo, con almeno r archi rossi Ricorrenza D(k)(i,j,r)={ se k non ϵ D(k)(i,j,r) =D(k-1)(i,j,r) { se k ϵ D(k)(i,j,r) =min(*){D(k-1)(i,t,r1)+D(k-1)(t,j,r2)} * r1+r2>=r and 0<=r1<=k+1 and 0<=r2<=k+1 D(k)(i,j,r)=min{D(k-1)(i,j,r) , min(*){D(k-1)(i,t,r1)+D(k-1)(t,j,r2)}} Caso base D(0)(i,j,0)={w[i,j] per ogni(i,j) ϵ E and col (i,j)=N { inf altrimenti D(0)(i,j,1)={w[i,j] per ogni(i,j) ϵ E and col (i,j)=R { inf altrimenti

D(0)(i,j,2)={inf Soluzione D(n)(i,j,2) 5)Cammini minimi tra tutte le copie di vertici in G pesato t.c. contengano esattamente 2 vertici rossi, estremi esclusi. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,col> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: V ->{R,N} funzione che associa un colore ad un vertice - i,j vertici (nodi) del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,r) costo cammino minimo i,j con vertici nell'intervallo, con esattamente r vertici rossi Ricorrenza D(k)(i,j,r)={ se k non ϵ D(k)(i,j,r) =D(k-1)(i,j,r) { se k ϵ min 1{ se col(t)=N D(k)(i,j,r) = min(r1+r2=r){D(k-1)(i,t,r1)+D(k-1)(t,j,r2)}

2{ se col(t)=R e rƢ0 D(k)(i,j,r) = min(r1+r2=r){D(k-1)(i,t,r1)+D(k-1)(t,j,r2)} 3{ se col(t)=R e r=0 D(k)(i,j,r) =infinito D(k)(i,j,r)=min{D(k-1)(i,j,r) , min {1,2,3}} Caso base D(0)(i,j,0)={w[i,j] per ogni(i,j) ϵ E and col (i)=N and col (j)=N { infinito altrimenti D(0)(i,j,1)={w[i,j] per ogni(i,j) ϵ E and col (i)=R and col (j)=R { infinito altrimenti D(0)(i,j,2)={infinito Soluzione D(n)(i,j,2) 6)Cammini minimi senza archi rossi consecutivi. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,col> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: E ->{R,N} funzione che associa un colore ad un arco - a colore del primo arco nel cammino tra i,j - b colore dell'ultimo arco nel cammino tra i,j - i,j nodi del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,a,b) costo cammino minimo i,j con vertici nell'intervallo, con colore arco a diverso dal colore arco b Ricorrenza D(k)(i,j,a,b)={ se k non ϵ D(k)(i,j,a,b) =D(k-1)(i,j,a,b) { se k ϵ D(k)(i,j,a,b) =

min(cƢd){D(k-1)(i,t,a,c)+D(k-1)(t,j,d,b)} D(k)(i,j,a,b)=min{D(k-1)(i,j,a,b) ,

min(cƢd){D(k-1)(i,t,a,c)+D(k-1)(t,j,d,b)}} Caso base D(0)(i,j,a,b)={w[i,j] per ogni(i,j) ϵ E and w[i,j]=a=b { infinito altrimenti

Soluzione min{D(k)(i,j,R,R),D(k)(i,j,R,N),D(k)(i,j,N,R),D(k)(i,j,N,N) 7)Stabilire se esiste un cammino minimo senza archi consecutivi dello stesso colore. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,col> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: E ->{R,N} funzione che associa un colore ad un arco - a colore del primo arco nel cammino tra i,j - b colore dell'ultimo arco nel cammino tra i,j - i,j nodi del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,a,b) true se esiste un cammino minimo i,j con vertici nell'intervallo e con colore arco a diverso dal colore arco b Ricorrenza D(k)(i,j,a,b)={ se k non ϵ D(k)(i,j,a,b) =D(k-1)(i,j,a,b) { se k ϵ D(k)(i,j,a,b) =

or(cƢd){D(k-1)(i,t,a,c)and D(k-1)(t,j,d,b)} D(k)(i,j,a,b)=OR{D(k-1)(i,j,a,b) ,

or(cƢd){D(k-1)(i,t,a,c)and D(k-1)(t,j,d,b)}} Caso base D(0)(i,j,a,b)={true se (i,j)ϵ E and w[i,j]=a=b { false altrimenti Soluzione OR{D(k)(i,j,R,R),D(k)(i,j,R,N),D(k)(i,j,N,R),D(k)(i,j,N,N) 8)Stabilire se esiste un cammino minimo senza archi rossi consecutivi. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,a,b> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - col: E ->{R,N} funzione che associa un colore ad un arco - a colore del primo arco nel cammino tra i,j - b colore dell'ultimo arco nel cammino tra i,j - i,j nodi del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,a,b) true se esiste un cammino minimo i,j con vertici nell'intervallo e con colore arco a diverso dal colore arco b Ricorrenza D(k)(i,j,a,b)={ se k non ϵ D(k)(i,j,a,b) =D(k-1)(i,j,a,b) { se k ϵ D(k)(i,j,a,b) =

or(cƢd){D(k-1)(i,t,a,c)and D(k-1)(t,j,d,b)} D(k)(i,j,a,b)=OR{D(k-1)(i,j,a,b) ,

or(cƢd){D(k-1)(i,t,a,c)and D(k-1)(t,j,d,b)}} Caso base D(0)(i,j,a,b)={true se (i,j)ϵ E and w[i,j]=a=b

{ false altrimenti Soluzione OR{D(k)(i,j,R,R),D(k)(i,j,R,N),D(k)(i,j,N,R),D(k)(i,j,N,N)} 9)Stabilire se esiste per ogni coppia di vertici un cammino di costo minore o uguale di K>0. Significato parametri coefficienti delle ricorrenze - G=<V,E,w,> V insieme vertici, E insieme archi - w[i,j] funzione peso dell'arco tra i,j - i,j nodi del grafo; - 1...k intervallo dei vertici intermedi tra i,j -D(k)(i,j,h)=true se esiste un cammino minimo i,j con vertici nell'intervallo di costo <= h Ricorrenza D(k)(i,j,h)={ se k non ϵ D(k)(i,j,h) =D(k-1)(i,j,h) { se k ϵ D(k)(i,j,h) = or(h1+h2<=h){D(k-1)(i,t,h1)and D(k-1)(t,j,h2)} D(k)(i,j,a,b)=OR{D(k-1)(i,j,h) , or(h1+h2<=h){D(k-1)(i,t,h1)and D(k-1)(t,j,h2)}} Caso base D(0)(i,j,0)= false D(0)(i,j,h)={true se (i,j)ϵ E and w[i,j]<=K { false altrimenti con 1<=h<=K Soluzione D(n)(i,j,K) LCS (X, Y) n = length(X); m = length(Y); for i = 0 to n

C[i,0] = 0 End for for j = 0 to m

C[0,j] = 0 End for for i = 1 to n for j = 1 to m if ai = bj then C[i,j]=C[i-1,j-1]+1; D[i,j]= “freccia diag”; else if C[i-1,j] >= C[i,j-1] then

C[i,j]=C[i-1,j]; D[i,j]=↑;

else C[i,j]=C[i,j-1]; D[i,j]=←; End for End for procedura stampa_lcs(D, X, Y, i, j) if i = 0 OR j = 0 then return else if D[i,j] = then stampa_lcs(D, X, Y, i-1, j-1) print X[i]; else if D[i,j] = ↑ then stampa_lcs(D, X, Y, i-1, j) else stampa_lcs(D, X, Y, i, j-1)

Lcs_crescente(X as Array, Y as Array) m = length(X); n = length(Y); C as Matrix[m,n]; for i = 0 to n /* riempio la prima colonna di 0 */ C[i,0] = 0 End for for j = 0 to m /* riempio la prima riga di 0 */ C[0,j] = 0 End for for i = 1 to m for j = 1 to n if xi != yj then C[i,j] = 0 else max = 0 for s = 1 to i-1 for t = 1 to j-1 if C[s,t] > max AND xs < xi max = C[s,t] end for end for C[i,j]=1 + max; Return C Procedura BFS(G, s) For ogni vertice u € V – {s} Color[u] = white; d[u] = infinity; p[u] = nil; End for Color[s] = grey; d[s] = 0; p[s] = nil; Q = {s} while Q ≠ Ф u = Head(Q) for ogni vertice v € Adj[u] if color[v] = white then

p[v] = u color[v] = grey d[v] = d[v] + 1 Enqueue(Q, v) End for Dequeue(Q) color[u] = black end while BFS_scopre_vertici_distanza_k_da_s(G,s) For ogni vertice u € V – {s} Color[u] = white; d[u] = infinity; p[u] = nil; End for Color[s] = grey; d[s] = 0; p[s] = nil; Q = {s} while Q ≠ Ф u = Head(Q) for ogni vertice v € Adj[u] if color[v] = white then p[v] = u

d[v] = d[v] + 1 if d[v]<k then color[v] = grey Enqueue(Q, v) Else color[v]=black End for Dequeue(Q, u) //tolgo u dalla coda color[u] = black end while Procedura BFS_conta_raggiungibili_da_s(G, s) //scrivere il codice della BFS e dopo aggiungere N=0 For ogni vertice u € V – {s} If d[u] ≠ infinito then n=n+1 End for Return n Procedura BFS_stampa_vertici_distanza_pari_da_s(G, s) //scrivere il codice della BFS e dopo aggiungere For ogni vertice u € V – {s} If d[u] ≠ infinito and d[u] mod 2=0 then print u End for BFS_se_grafo_nn_orientato_è_connesso(G) //non ho la s,scelgo a random un vertice s=RANDOM(V) eseguo BFS(G,s) for ogni u € V – {s} if d[u]=infinito return false end for return true BFS_se_GnonOrientato_è_albero(G,s) Def di albero: grafo non orientato,connesso e aciclico Connesso lo controllo con la procedura sopra e per aciclico sfrutto il teorema: Se G è non orientato � G è un albero = G è connesso AND |E|=|V|-1 = G è aciclico AND |E|=|V|-1 Ricordo che se G non orientato ogni arco viene scoperto 2volte quindi pongo |E|=½∑u€V|Adj[u]| Connesso= BFS_se_grafo_nn_orientato_è_connesso(G) If(connesso=true) and (|E|=|V|-1) return true Else return false

BFS_GnonOrientato_albero_binario_completo_radiceS_altezzaK G albero=G connesso AND |E|=|V|-1 (con |E|=½∑u€V|Adj[u]|) G binario e completo: sorgente ha 2 archi incidenti: se d[u]=0 � |Adj[u]|=2 nodo intermedio ha 3 archi incidenti: se 0<d[u]<k � |Adj[u]|=3 foglia ha 1 arco incidente se d[u]=k � |Adj[u]|=1 e anche che 2livello ≠ n (n=numero vertici su un livello) altezza k: scopro solo i vertici che distano K da s For ogni vertice u € V – {s} Color[u] = white; d[u] = infinity; p[u] = nil; End for Color[s] = grey; d[s] = 0; p[s] = nil; liv=1 n=0 Q = {s} while Q ≠ Ф u = Head(Q) a=|Adj[u]| if(d[u]=0 AND a ≠ 2) OR (0<d[u]<k AND a ≠ 3) return false for ogni vertice v € Adj[u] if color[v] = white then

p[v] = u d[v] = d[v] + 1 if d[v]=liv then n=n+1 else if n≠2livello return false liv=liv+1 n=1 if d[v]<k then color[v]=gray Enqueue(Q) Else color[u]=black End for Dequeue(Q) color[u] = black end while if 2livello ≠ n return false for ogni vertice u € V – {s} if color[u]=white return false if (d[u]=k AND a≠1) return false end for if |E|=|V|-1 return true else return false DFS(G) for ogni vertice u € V color[u] = white; p[u] = null; end for time = 0; for ognivertice u € V if color[u] = white then DFS_visit(u)

end for DFS_visit(u) color[u] = grey; time = time + 1; d[u] = time; for ogni vertice v € Adj[u] if color[v] = white then p[v] = u; DFS_visit(v); end for time = time + 1; f[u] = time; color[u] = black; 1)DFS_VISIT(u) – stampa tutti gli archi classificandoli (G orientato) //aggiungere DFS senza modifiche color[u] = grey; time = time + 1; d[u] = time; for ogni vertice v € Adj[u] \ {p[u]} if color[v] = white print (u,v) è arco dell’albero p[v] = u; DFS_visit(v); Else if colour[v]=gray print (u,v) è arco all’indietro Else if d[u]<d[v] print (u,v) è arco in avanti Else print (u,v) è arco di attraversamento end for time = time + 1; f[u] = time; color[u] = black; 2)DFS – stampa tutti gli archi classificandoli (G non orientato) Dal teorema so che G non orientato ha solo archi all’indietro o archi dell’albero In questo G l’arco (u,v) e (v,u) sono lo stesso arco. Se allo stesso arco possono essere attribuiti 2 tipi diversi,la priorità verrà data a quello che compare per primo. Per dire che (u,v) è arco all’indietro devo controllare che V non è padre di u. se v è grigio e v è padre di u (u,v) è arco dell’albero (e non arco all’indietro) //aggiungo DFS(G) senza modifiche DFS_visit(u) color[u] = grey; time = time + 1; d[u] = time; for ogni vertice v € Adj[u] \ {p[u]} if color[v] = white print (u,v) è arco dell’albero p[v] = u; DFS_visit(v); Else print (u,v) è arco all’indietro end for time = time + 1; f[u] = time; color[u] = black;

3)DFS_conta_compConness(G) for ogni vertice u €V color[u] = white; p[u] = null; end for time = 0; cont = 0; for ogni vertice u € V If color[u] = white cont++; DFS_visit(u); end for return n 4)DFS_compConnes=k(G) for ogni vertice u €V color[u] = white; p[u] = null; end for time = 0; cont = 0; for ogni vertice u € V If color[u] = white cont++; DFS_visit(u); end for if(cont==k) then return true else return false 5)boolean DFS_aciclio(G orientato) Dal teorema dell’ordinamento topologico di un DAG affermo che: un grafo orientato è aciclico se e solo se la DFS su G non produce archi all’indietro boolean aciclico = true; for ogni vertice u €V color[u] = white; p[u] = null; end for time = 0; for ogni vertice u € V If color[u] = white DFS_visit(u); end for return aciclico DFS_visit(u) color[u] = grey; time = time + 1; d[u] = time; for ogni vertice v € Adj[u] if color[v] = white then p[v] = u; DFS_visit(v); else if color[v]=gray and aciclico =true aciclico =false; end for time = time + 1; f[u] = time; color[u] = black; 6)DFS_Visit(u) G non orientato aciclico(G) //aggiungere anche la DFS con var aciclico

color[u] = grey; time = time + 1; d[u] = time; for ogni vertice v € Adj[u] \ {p[u]} if color[v] = white p[v] = u; DFS_visit(v); else if color[v]=gray and aciclico =true aciclico =false; end for time = time + 1; f[u] = time; color[u] = black; 7)DFS - verifica se un grafo non orientato è formato da K alberi Bisogna controllare se G aciciclico e se ha k componenti connesse boolean procedura DFS(G) boolean aciclico =true; int count = 0; for each u € V color[u] = white; p[u] = null; end for for each u € V if color[u] = white then DFS_visit(u) count++; end for if (aciclico=true)AND(count ==k) return true else return false; DFS_VISIT(u) color[u] = grey; for ogni vertice v € Adj[u] \ {p[u]} if color[v] = white p[v] = u; DFS_visit(v); else if color[v]=gray and aciclico =true aciclico =false; end for color[u] = black; 8)DFSconta_compConnes_con_num_nodi_pari Cc=0 for ogni vertice u €V color[u] = white; p[u] = null; end for time = 0; cont = 0; for ogni vertice u € V If color[u] = white If DFS_VISIT(u) mod 2=0 cc=cc+1 cont++; end for return cc DFS_visit(u) c[u] = grey; cont = 0; for ogni vertice v € Adj[u]

if color[v] = white then p[v] = u; cont += DFS_visit(v); end for c[u] = black; return cont + 1; Dijkstra(G,s) For ogni v € V p(v) = nil; d(v) = infinity; End for d(s) = 0; S = Ф; Q = V while Q ≠ Ф u = ExtractMin(Q); S = S + {u}; for ogni v € Adj[u] Relax(u, v, w); end for End while Relax(u, v, w) if(d[v] > d[u] + w(u,v)) then d[v] = d[u] + w(u,v); p[v] = u;

DOMANDE TEORICHE IN PREPARAZIONE ALL’ESAME Algoritmi Complementi

1. Siano X=< x1, …, xm> e Y=< y1, …, yn> due sequenze e sia Z=< z1, …, zk> una LCS di X e Y. Scrivere la proprieta’ di sottostruttura ottima di Z. Più precisamente data una sequenza X=< x1, …, xm> diciamo che Xi è il prefisso i-esimo della sequenza X se e solo se Xi =<x1,x2,x3…..xi> con i=1….m. Per esempio se X=<A,B,C,B,D,A,B> allora X4=<A,B,C,B> e X0 è la sequenza vuota. Il problema della LCS soddisfa la proprietà della sottostruttura ottima come dimostrato dal teorema. TEOREMA Sottostrutta ottima di una LCS Siano X=< x1, …, xm> e Y=< y1, …, yn> due sequenze e sia Z=< z1, …, zk> una LCS di X e Y. 1). Se xm = yn allora zk=xm=yn e Zk-1 è una LCS di Xm-1 e Yn-1 2) Se xm ≠ yn e zk ≠ xm allora Z è una LCS di Xm-1 e Y 3) Se xm ≠ yn e zk ≠ yn allora Z è una LCS di X e Yn-1 Questo teorema dimostra che una LCS di due sequenze contiene al suo interno una LCS dei prefissi delle due sequenze. Quindi il problema della LCS soddisfa la propietà della sottostruttra ottima N.B. Questo teorema implica che se devo trovare una LCS tra X e Y devo considerare uno o due sottoproblemi: Infatti se xm = yn per trovare una LCS tra X e Y basta trovare una LCS tra Xm-1 e Yn-1 e concatenarci l’elemento xm = yn. Nel caso in cui xm ≠ yn devo risolvere due sottopb: bisogna trovare una LCS di Xm-1 e Y e una LCS di X e Yn-1. La più grande di queste due LCS è una LCS tra X e Y. Quindi la sottostruttra ottima del pb dell’LCS permette di derivare la formula ricorsiva richiesta nella domanda 2 2. Scrivere le equazioni di ricorrenza per risolvere il problema della LCS di due sequenze, specificando bene il significato delle variabili coinvolte. 0 se (i=0 o j=0) c[i,j] = c[i-1,j-1] +1 se i,j >0 e xi=yj max(c[i-1,j],c[i,j-1]) se i,j >0 e xi≠yj DEFINIZIONE VARIABILI c[i,j] è la lunghezza di una LCS delle sequenze xi e yi xi è l’elemento i-esimo del prefisso Xi con Xi =<x1,x2,x3…..xi> con i=1….m yj è l’elemento j-esimo del prefisso Yj con Yj =<y1,y2,y3…..yj> con j=1….n 3. Scrivere l’algoritmo che determina la lunghezza della LCS di due sequenze specificando il suo tempo di calcolo. matrice C: contiene i valori della lunghezza della LCS per ogni coppia di indici i e j matrice B: contiene le indicazioni su come ricomporre la LCS. Tempo di calcolo procedura: TETA(nm) 1° for -> 0<i<m 2° for -> 0<j<n Quindi ho (n+1)(m+1) chiamate ricorsive distinte -> TETA(nm) sottopb distinti

procedura calcola_lungh_it(X, Y) n = length(X); m = length(Y); for i = 0 to n /* riempio la prima colonna di 0 */

C[i,0] = 0 End for for j = 0 to m /* riempio la prima riga di 0 */

C[0,j] = 0 End for for i = 1 to n

for j = 1 to m if xi = yj then C[i,j]=C[i-1,j-1]+1; B[i,j]= ; else if C[i-1,j] >= C[i,j-1] then C[i,j]=C[i-1,j]; B[i,j]=↑; else C[i,j]=C[i,j-1]; B[i,j]=←;

End for End for 4. Definire qual e’ il sottografo dei predecessori (o albero BFS) prodotto dalla visita BFS di un grafo G=<V,E>, specificando bene da quali vertici e quali archi e’ composto. La vistita BFS(G,s) produce un albero BFS che ha s come radice e che contiene tutti i vertici V raggiungibili da s. L’albero BFS è rappresentato dal sottografo dei predecessori di G, cioè dal campo π di ogni vertice. All’inzio della visita l’albero contiene solo s. Durante la scansione della lista di adiacenza di un vertice u già scoperto (grigio), se trovo un vertice v non ancora scoperto (bianco), aggiungo all’albero il vertice v e l’arco (u,v). In questo caso dirò che u è il predecessore di v nell’albero BFS. Per ogni vertice v raggiungibile da s, il cammino nell’albero BFS da s a v corrisponde ad un cammino minimo da s a v in G 5. Scrivere qual e’ il tempo di calcolo dell’algoritmo BFS motivando la risposta. La complessità algoritmo BFS è O(V+E) cioè un tempo lineare Operazioni inserimento e eleminazione da Q per ogni vertice: ognuna ha tempo costante O(1), su un grafo con V vertici O(V) (perché il test if colour[v]=WHITE assicura venga inserito in Q – e quindi eliminato da Q- al max una volta) Scansione lista adiacenza di ogni vertice: scandisco la lista di adiacenza di ogni vertice una sola volta (perché lo faccio quando tolgo il vertice da Q) quindi: Tempo scansione della lista di v: O(1) Tempo scansione di tutte le liste di adiacenza: TETA(E) (devo sommare tutte le lunghezze delle liste di adiacenza - la lunghezza dipende dal numero di archi E) Quindi: tempo massimo scansione di tutte le liste: O(1*E)=O(E)

Tempo dedicato alla fase di inizializzazione (colorare tutti i vertici a bianco)=O(V) Quindi complessità algoritmo = O(V+E) 6. Spiegare il significato dei colori assegnati ai vertici dall’algoritmo BFS. Alla fine dell’esecuzione dell’algoritmo BFS su un grafo G=<V,E>, quali colori assumono i vertici? All’inizio della visita BFS tutti i vertici vengono colorati di bianco prechè non sono stati ancora scoperti. Appena un vertice viene scoperto viene colorato di grigio e viene quindi esaminata la sua lista di adiacenza. Quando sono stati scoperti tutti i vertici adiacenti ad un vertice grigio questo diventa nero. N.B: I vertici grigi rappresentano la frontiera tra i vertici scoperti e non. 7. Definire qual e’ il sottografo dei predecessori (o foresta DFS) prodotto dalla visita DFS di un grafo G=<V,E>, specificando bene da quali vertici e quali archi e’ composto. La visti DFS produce una foresta composta da alberi DFS La procedura DFS(G,s) si occupa di fare una visita in profondità su ogni vertice u non ancora scoperto, quindi ogni volta che invocherà la sottoprocedura DFS_VISIT(u) questa costruirà un albero di radice u. In ogni albero di radice u viene eseguita la scansione della sua lista di adiacenza: se trovo un vertice v non ancora scoperto (bianco) aggiungo all’albero il vertice v e l’arco (u,v). In questo caso dirò che u è il predecessore di v nell’albero DFS 8. Descrivere la classificazione degli archi che la visita in profondita’ produce a partire da un grafo G=<V,E>. Come si classifica un generico arco (u,v) del grafo? La DFS produce 4 tipi di archi:

• Archi dell’albero: sono gli archi della foresta DFS: un arco (u,v) è un arco dell’albero se v è stato scoperto esplorando l’arco (u,v)

• Archi all’indietro: sono archi (u,v) che connettono u ad un suo antenato v in un albero DFS. (i cappi vengono considerati alberi all’indietro).

• Archi in avanti: sono archi che NON sono dell’albero e che connettono un vertice u ad un suo discente v in un albero

• Archi di attraversamento: Sono tutti gli altri: o possono connettere vertici dello stesso albero DFS purchè un vertice non sia antenato

dell’altro o possono connettere vertici in alberi DFS distinti

9. Scrivere qual e’ il tempo di calcolo dell’algoritmo DFS motivando la risposta. Complessità algoritmo: TETA(V+E) – tempo lineare – Complessità DFS(G,s) = TETA(V) : i 2for vengono svolti V volte Complessità DFS_VISIT(u) = TETA(E) : la DFS_VISIT viene chiamata esattamente una volta per ogni vertice v in V (infatti prima o poi metto tutti i vertici a grigio). All’interno della procedura il for viene eseguito |Adj(v)| volte, quindi il costo totale è dato dalla somma di tutte le |Adj(v)| cioè TETA(E). 10. Esporre, motivando la risposta, qual’e’ la relazione tra il numero di componenti connesse di un grafo G non orientato ed il numero di volte che la procedura DFSVisit viene invocata all’interno della procedura DFS(G) eseguita su G. Ogni volta che viene invocata la DFS_VISIT(u) viene costruita una nuova componente connessa di G partendo da u. Quindi il numero di invocazioni corrisponde al numero di componenti connesse di G

11. Dare la definizione di ordinamento topologico, specificando bene a che tipo di grafo si applica. Descrivere come si ottiene l’ordinamento topologico sfruttando l’algoritmo DFS. Posso usare la DFS per effettuare un ordinamento topologico di GRAFI ORIENTATI ACICLICI chiamati DAG. Un ordinamento topologico di un DAG=(V,E) è un ordinamento lineare di tutti i suoi vertici tale che se G contiene un arco (u,v) allora u compare prima di v nell’ordinamento (se G non fosse aciclico un ordinamento di questo tipo sarebbe impossibile). Immagino questo ordinamento come un ordinamento di tutti i vertici di G lungo una linea orizzontale in modo tale che gli archi orientati vadano da sx verso dx (questo lo faccio ordinando il tempo f[u] (ottenuto dalla DFS) per ogni vertice v in modo decrescente) 12. Descrivere la caratterizzazione della struttura di un cammino minimo p=< v1, …,vl> utilizzata dall’algoritmo di Floyd-Warshall.

Contiene tutti i vertici intermedi nell’insieme {1,2,…k-1} Contiene tutti i vertici intermedi nell’insieme {1,2,…k-1} Cammino minimo p: contiene tutti i vertici intermedi in {1,2….k-1} L’algoritmo di Floyd_warshall sfrutta una relazione tra il cammino minimo p e i cammini minimi da i a j aventi vertici intermedi nell’insieme {1,2…..k-1} Questa relazione cambia a seconda se K è un vertice intermedio di p oppure no. Se K appartiene a P il costo del cammino minimo da i a j con vertici intermedi in {1….k} è uguale alla somma del cammino minimo da i a k con vertici intermedi in {1,2…..k-1} e del cammino minimo da k a j con vertici interme in {1,2,….k-1}. Se K non appartiene a P il costo del cammino minimo da i a j con vertici intermedi in {1….k} è uguale al costo del cammino minimo da i a j con vertici intermedi in {1….k-1} A priori non so se k è un vertice intermedio a p oppure no, quindi per trovare il cammino minimo considero entrambi i costi ottenuti dai due casi sopra e poi scelgo il minimo. 13. Illustrare e motivare le equazioni di ricorrenza su cui si basa l’algoritmo di Floyd-Warshall, specificando bene il significato delle variabili coinvolte. Le equazioni di ricorrenza su cui si basa l’algoritmo di Floyd – Warshall derivano dal ragionamento fatto nella domanda 12. Definizione variabili:

dij(k) = il costo del cammino minimo da i a j con vertici intermedi in {1….k}

wij = peso dell’arco (i,j) eq. Ricorrenza:

j i

k

wij se k=0 (non ho vertici intermedi)

dij(k) = min (dij

(k-1) , dik(k-1) + dkj

(k-1)) se k>=1 14. Illustrare un metodo per costruire i cammini minimi nell’algoritmo di Floyd- Warshall. 15. Che cos’e’ la chiusura transitiva di un grafo orientato? Descrivere un modo per calcolarla. La chiusura transitiva di un grafo G è un grafo G* che ha lo stesso insieme di vertici e un insieme di archi E* >= E E* è un ampliamento dell’insieme di archi E E* = {(i,j) : esiste un cammino da i a j in G} V={1,2,3,4} E= {(1,2), (2,3), (3,4)} Applicando la chiusura transitiva ottengo V*=V E*={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}

1 2

3 4

1 2

3 4

E’ transitiva perché se c’è la relazione 1R2 e 2R3 esiste anche la relazione 1R3 Aggiungo l’arco (1,4) solo se esiste un cammino minimo da 1 a 4 tramite vertici intermedi I grafi G e G* li rappresento con la matrice di adiacenza e la variabile t rappresenta le celle della matrice su G* La soluzione sta in tij (n) 16. Descrivere come modificare le equazioni di ricorrenza dell’algoritmo di Floyd-Warshall per calcolare la chiusura transitiva di un grafo orientato. La procedura scritta nella risposta 15 è la ricorrenza che risolve l’algoritmo di Floyd-Warshall con queste sostituzioni: Min -> OR + -> AND