Progettazione di algoritmi - appunti corso

Formattazione del testo

FFprimi j elementi, per un certo j≧0. E’ possibile costruire uno scheduling ridotto S’ che fa lestesse scelte di S per i primi j+1 elementi (una scelta in più) con n° di cache miss nonFFmaggiore di quello determinato da S. Quindi assumiamo che S’ fa già le stesse scelte di S finoffa j+1.Dim: Produciamo S’. Consideriamo la (j+1)-esima richiesta e sia d=dj+1 l’elemento richiesto.Siccome, per ipotesi, S e S hanno fatto le stesse scelte fino a j, quando arriva la richiesta (j+1)FFle due cache per i due scheduling sono identiche (stessi elementi). Quando arriva la richiestadi d:Caso 1: d è già nella cache, qui sia S che S non fanno niente perché entrambi sono ridottiFF(uguali)Caso 2: d non è nella cache. S espelle lo stesso elemento di S (uguali anche per la j+1FFscelta)In questi due casi basta porre S’=S visto che S ed S hanno lo stesso comportamento ancheFFper j.Caso 3: d non è nella cache ma S

espelle e mentre S espelle f!=e (espellono elementiFFdifferenti)Costruiamo S’ a partire da S modificando la (j+1)-esima scelta inmodo che S’ espella e invece di f. Così S’ fa la stessa scelta di S perFFle prime j+1 richieste. Occorre dimostrare che S’ riesce ad effettuaresuccessivamente delle scelte che non determinano un n° di cachemiss S’ NON> di S.DIM: Dopo la (j+1)-esima richiesta facciamo fare ad S’ le stesse scelte di S fino a che, atempo j’, accade per la prima volta che S ed S’ non fanno la stessa scelta. A questo punto S’deve fare una scelta diversa da quella di S; però S’=S. Da questo punto in poi ilcomportamento di S’ sarà identico a quello di S per cui andrà incontro allo stesso numero dicache miss. Quindi si deve far fare una scelta diversa lasciando che gli elementi nelle duecache siano identici.S’ e S fino a tempo j’ si sono comportati in modo diverso 1 volta

al tempo j+1 quindi differiscono di un solo elemento, e in S ed f in S'. g è l'elemento richiesto al tempo j'. I casi che avrebbero permesso a S' di fare la stessa scelta di S sono:

• g ≠ e, g ≠ f, g è presente nella cache di S: in questo caso g è in S', sia S che S' non fanno nulla;
• g ≠ e, g ≠ f, g non è presente nella cache di S ed S espelle un elemento ≠ e: g non è neanche nella cache di S' ed S' può espellere lo stesso elemento espulso da S.

Caso in cui S' al tempo j' non riesce a fare la stessa scelta di S (quello che ci interessa)

Caso 3.1: g ≠ e, g ≠ f, g non è presente in S ed S espelle e; g non è in S'. Facciamo in modo che S' espella f (elemento diverso). In questo modo dopo j' S = S'. Il numero di cache miss S = S'.

Caso 3.2: g=f ed S espelle e. S' non fa niente (ha

già f) e quindi S=S'. Il n° di cache miss di S'<S.

Caso 3.3: g=f ed S espelle e≠e (le due cache divergono ancora di più, poiché non si espelle e che era l'unico elemento discostante, per aggiungere f che le renderebbe uguali). In questo caso è presente in S'. Al tempo j', S' espella e ed inserisca e. Così S=S' e n° cache miss sono uguali. Così però lo scheduling S' NON È RIDOTTO, poiché è stato inserito un elemento non richiesto. Però per il caso 1 il n° di inserimenti non è aumentato, quindi si può trasformare S' in uno ridotto che farà le stesse scelte di S per i primi j+1 elementi in quanto =S' fino al tempo j'-1.

Caso g=e: Al tempo j' non può accadere che g=e. Al tempo j+1, S ha espulso e al posto di f per cui, dopo j+1, e viene richiesto più tardi di f o non viene richiesto.

ALGORITMO DI BELADY con liste e coda a priorità. La chiave serve a capire chi si deve espellere. Richieste in ordine di arrivo

L[d] posizioni in cui d appare nella sequenza

Estrae elemento con chiave >

Scandisce l'intera sequenza I,

Se elemento d è presente per la 1° volta, aggiunta della coppia in coda, e aggiunta j nella lista L (dov'è l'elemento)

Se l'elemento è già nella cache si toglie

Se la lista è vuota si rimpiazza d

Altrimenti si rimpiazza la chiave di d con quella del primo elemento in testa alla lista

Si estrae da q

L'elemento max messo in dhSi rimuove il primo elemento da LSe l non è vuota si mette il primo elemento (p)in q altrimenti si inserisce infinito (?)Le chiavi sono importanti per scegliere quale elemento rimuovere dalla coda, cioè l'elemento con chiave > (richiesto più tardi). Le chiavi sono l'indici della posizione in cui si incontra l'elemento quando si fa richiesta.

Analisi: primo for, la coda contiene gli elementi in cache (con k

è costante,insert log k. La cache è più piccola della coda quindi il costo del primo for viene dominato dal secondo. Tempo totale: O(m log k).

Per ogni elemento d nella sequenza delle richieste; la lista L[d] contiene le posizioni in cui d appare nella sequenza. Nel 1° for viene scandita la sequenza delle richieste e per ogni elemento d della sequenza vengono inserite in L[d] tutte le posizioni in cui d appare nella sequenza.

Es: se la sequenza delle richieste è a, b, c, b, c, a, a, b allora L[b]=< 2 4 8>, 2 è in testa e 8 in coda alla lista.

Nella j-esima iterazione del secondo for viene eliminato l’intero in testa a L[dj] in modo che in testa alla lista venga a trovarsi l’intero che indica la prossima posizione della sequenza in cui ci sarà nuovamente dj.

Per ogni elemento d in cache, Q contiene un’entrata (k,d), dove la chiave k è un intero che indica il punto della sequenza in cui verrà richiesto.

nuovamente d. Se k=m+1 allora d non verrà richiesto.

Nel primo for vengono inserite le entrate per gli elementi già presenti in cache con chiave=1° posizione in cui questi appaiono nella sequenza delle richieste. Es: se la sequenza delle richieste è a, b, c, b, c, a, a, b e inizialmente la cache contiene gli elementi a e b allora inizialmente Q contiene le entrate (a,1) (b,2).

Nella j-esima iterazione del secondo for, l'if-else gestisce i due seguenti casi:

1. dj è presente in cache: In questo viene rimosso l'intero in testa a L[dj] e viene aggiornata la chiave di dj con il nuovo intero in testa, se è vuota allora la chiave di dj viene sostituita con m+1.
2. dj non è presente in cache: In questo caso viene estratta da Q l'entrata (h,dh) con chiave max e h viene espulso dalla cache. Viene poi rimosso l'intero in testa a L[dj]. Se dopo questa rimozione L[dj] non è vuota allora viene inserita in Q l'entrata (p, dj), con nuova chiave max+1, dove p è la posizione in cui l'intero è presente nella sequenza delle richieste.

Interoin testa a L[dj], se è vuota allora in Q viene inserita l'entrata (m+1, dj). Il farthest and future non è un problema molto realistico in quanto nelle situazioni reali non sono conosciute in anticipo le prossime entry, si conoscono man mano che va avanti il programma. L'algoritmo usato nella realtà è l'LRU, che estrae dalla cache la pagina che è stata richiesta meno recentemente; è simile all'FF sostituendo la direzione del tempo (consideriamo il passato).

LEZIONE 17: Input: Grafo direzionato G=(V,E). Per ogni arco e, valore l (costo, peso, lunghezza dell'arco e). es=sorgente. Def: il costo di un percorso P direzionato (da s a un vertice), l(P)=somma lunghezze archi in P. NB: Se G non è direzionato possiamo sostituire ogni arco (u,v) con i 2 archi direzionati (u,v) e (v,u).

Varianti del problema dei cammini minimi: più corti

1. Single Source Shortest Paths: percorsi per andare da altri vertici

versodestinazione t;

2. Destination Shortest Paths: Da t fino ad altri vertici; come il 1° invertendo le direzioni degli archi; più corto

3. Single-Pair Shortest Path: il percorso per andare da una coppia di vertici (u,v) ad un'altra. I migliori algoritmi per questo problema hanno la stessa complessità dei migliori del 1°.

4. All Pairs Shortest Paths: per ogni coppia di vertici (u,v), determinare un cammino minimo da u a v

Single Source Shortest Paths: è inefficiente considerare tutti i possibili percorsi; il BFS è un algoritmo per il SSSP solo nel caso in cui tutti gli archi hanno lo stesso peso.

Se i cammini minimi NON esistono significa che all'interno di un grafo è presente un ciclo negativo quindi la somma dei costi degli archi negativa. Basta che esista un percorso che va da s a v che attraversa un ciclo negativo che non è possibile definire un percorso minimo tra i due.

L'algoritmo greedy che risolve il problema è

L'Algoritmo di Dijkstra (1959). Ad ogni passo mantiene l'insieme S dei nodi esplorati, cioè quei nodi u per cui è già stata calcolata la distanza minima d(u) da s. Inizializzazione S={s}, d(s)=0. Ogni passo, sceglie il nodo che può essere raggiunto ad S (scelta greedy). Sceglie v che minimizza:

La somma è la lunghezza di un percorso più corto d(u) ad un arco l con e che va da u a v ed e, aggiunge v a S e pone d(v)=d'(v). d'(v) rappresenta la lunghezza del percorso più corto da s a v (con v non raggiungibile da s) tra quelli che passano solo per nodi di S.

ES: Funziona solo con archi lunghi maggiori o uguali di zero

1. S={s} computo d'(2)=9 , d'(6)=14, d'(7) =15, scelgo 2 e pongo d(2)=9, shortest path= s-2;
2. S={s,2} computo d'(6)=14, d'(7) =15, scelgo 6 e pongo d(6)=14, shortest path= s-2-6;