dijkstra Tag

Tempi di esecuzione (teoria)

Alcune soluzioni si trovano qui.

27/05/2015

Si confrontino le seguenti funzioni utilizzando le relazioni O, Ω e Θ (giustificando le risposte):

f(n)	g(n)
10n3 + log n + 2n	n2 + log n5
n!	2n
2n	2n+100

28/01/2015

Si risolvano le seguenti ricorrenze:

• T(n) = 3T(n/2) + n²
• T(n) = 4T(n/2) + n²
• T(n) = T(n/2) + 2ⁿ

23/01/2014

Si definiscano formalmente le relazioni O, Ω, Θ e, utilizzando le definizioni date e
nient’altro, si dimostri la verità o la falsità di ciascuna delle seguenti affermazioni:

1. n logn = Θ(n²)
2. n + √3n = Ω(logn)
3. 4n log n = Ο(4n + log n²)
4. 2n+k = Ο(2n ), dove k è una costante intera positiva
5. 2ⁿ⁺ⁿ = Ο(2ⁿ)

08/09/2014

Per un certo problema sono stati trovati due algoritmi risolutivi (A1 e A2) con i seguenti tempi di esecuzione:

A1 : T(n) = 3·T(n/2) + n²
A2 : T(n) = 4·T(n/2) + n²

Si dica, giustificando tecnicamente la risposta, quale dei due algoritmi è preferibile per input di dimensione sufficientemente grande.

12/06/2014

Si confrontino le seguenti funzioni utilizzando le relazioni O, Ω e Θ:

f(n)	g(n)
100 n + log n	n + (log n)2
log n	log n3
2n	3n

01/09/2015

Utilizzando la definizione di O, e nient’altro, si stabilisca se le seguente affermazioni sono vere o false:
a) f(n) = O(n)
b) f(n) = O(n²)
dove f(n) = (2n − 1) / 2.

Costi di esecuzione (strutture dati)

27/05/2015

Completare la seguente tabella indicando la complessità delle operazioni che si riferiscono a un dizionario di n elementi. Per l’operazione Successore si assuma di essere sull’elemento x a cui si applica l’operazione.

	Ricerca	Massimo	Successore	Minimo	Costruzione
Albero binario di ricerca
Min-Heap

Soluzione: https://diario.softml.it/costi-di-esecuzione-strutture-dati-27-05-2015/

Funzioni efficienti (grafi)

27/05/2017

Il seguente algoritmo accetta in ingresso la matrice di adiacenza di un grafo non orientato e restituisce un valore Booleano (TRUE / FALSE)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.   for j = 1 to n
5.     b[i,j] = 0
6.     for k = 1 to n
7.       b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.  for j = i + 1 to n
11.     if a[i,j]*b[i,j] <> 0 then
12.return FALSE
13.return TRUE

Si calcoli la complessità computazionale di MyAlgorithm e si determini la sua funzione (in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la   complessità si ignori per comodità la complessità delle istruzioni 1 e 2).
Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

La soluzione è riportata qui: https://diario.softml.it/funzioni-efficienti-grafi-27-05-2017/

28/01/2015

Si scriva l’algoritmo di Floyd-Warshall, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo:

28/01/2015

Un piroscafo collega regolarmente n città portuali. Ad ogni porto u il proprietario del piroscafo ricava P(u) euro, ma per andare dal porto u al porto v spende in totale C(u,v) euro. Se P(u)/C(u,v) > 1, il proprietario del piroscafo ha quindi realizzato un guadagno. Si vuole stabilire se esiste un itinerario ciclico di k città (x0, x1, ..., xk = x0) per il quale

$\frac{\sum _{i=1}^{k}P\left(x_i\right)}{\sum _{i=1}^{k}C\left(x_{i-1},x_i\right)}$

dove μ ≥ 1 è una quantità stabilita a priori che rappresenta il guadagno minimo che il proprietario del piroscafo intende realizzare.

Si scriva un algoritmo che accetti in ingresso i ricavi P per ogni porto, i costi C per ogni coppia di porti e la costante μ, e stabilisca se un tale itinerario esiste o meno. Si discuta la correttezza dell'algoritmo proposto e la sua complessità computazionale.

08/09/2014-1

Sia G = (V, E) un grafo orientato e pesato, sia s∈V un vertice “sorgente” e si supponga che G sia stato inizializzato con INIT-SINGLE-SOURCE(G, s). Si stabilisca se la seguente affermazione è vera o falsa: «Se G non contiene un ciclo di peso negativo raggiungibile dalla sorgente s, allora nessuna sequenza di passi di rilassamento potrà assegnare al campo d[s] un valore diverso da 0.»

Nel primo caso si fornisca una dimostrazione, nel secondo un controesempio.

08/09/2014-2

Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):

	A	B	C	D	E
A	0	3	5	11	9
B	3	0	3	9	8
C	5	3	0	+∞	10
D	11	9	+∞	0	7
E	9	8	10	7	0

Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.

29/05/2014

Si scriva un algoritmo di complessità O(n2 log n) per determinare le distanze tra tutte le coppie di vertici in un grafo sparso G avente pesi sugli archi positivi, dove n è il numero di vertici in G.

12/09/2016

Si stabilisca quale problema risolve il seguente algoritmo, che accetta in ingresso un grafo non orientato G = (V, E):

MyAlgorithm(G)
1. A = ∅
2. ordina i vertici di G per grado crescente
3. for each u ∈ V[G] do /* vertici estratti secondo l’ordine stabilito nel passo 2 */
4.    if MyFunction(G,A,u) then
5.       A = A ∪ {u}
6. return A

MyFunction(G,A,u)
1. for each v ∈ A do
2.    if (u,v) ∈ E[G] then
3.       return FALSE
4. return TRUE

Si dimostri la correttezza dell’algoritmo, si determini la sua complessità e si simuli infine la sua esecuzione sul seguente grafo:

01/09/2015

Il seguente algoritmo accetta in ingresso la matrice di adiacenza A di un grafo orientato ed un intero k (con k ≥ 2), e restituisce un valore Booleano (TRUE / FALSE):

MyAlgorithm(A,k)
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B be the n x n identity matrix
3. for i = 1 to k - 1
4.   B = MyFunction(A,B)
5.   for i = 1 to n
6.     for j = i + 1 to n
7.       if B[i,j]*A[j,i] ≠ 0 then
8.       return FALSE
9. return TRUE

L’algoritmo utilizza la seguente funzione che accetta in ingresso due matrici quadrate (di dimensione identica) e restituisce un’altra matrice quadrata della stessa dimensione:

MyFunction(X,Y)
1. n = rows(X)
2. for i = 1 to n
3.   for j = 1 to n
4.     Z[i,j] = 0
5.     for k = 1 to n
6.       Z[i,j] = Z[i,j] + X[i,k]*Y[k,j]
7. return Z

Si calcoli la complessità computazionale complessiva di MyAlgorithm e si determini qual è il problema che risolve (ovvero: in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la complessità si ignori per comodità la complessità delle istruzioni 1 e 2 di MyAlgorithm e dell’istruzione 1 di MyFunction).

Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

Grafi (cammini minimi)

27/05/2015-1 e 12/06/2014 e 12/09/2016

Il problema di determinare i cammini minimi tra tutte le coppie di vertici di un grafo pesato G=(V, E, w) con pesi positivi si può risolvere iterando |V| volte l'algoritmo di Dikstra oppure utlizzando l'algoritmo di Floyd-Warshall. Si riempia la tabella sottostante, specificando le complessità degli algoritmi indicati in funzione della
tipologia di grafo utilizzato:

	Grafo sparso	Grafo denso
Iterated_Dijkstra (array)
Iterated_Dijkstra (heap)
Floyd-Warshall (27/05/15)
Bellman-Ford (12/06/14)

Supponendo che il grafo sia aciclico, quale algoritmo conviene usare? Perché?

27/05/2015-2

Sia G = (V, E) un grafo non orientato, connesso e pesato e sia (S, V \ S) un taglio di G. Si supponga che l'arco leggero che attraversa il taglio sia unico e lo si denoti con (u,v). In altri termini, per tutti gli altri archi (x,y) che attraversano il taglio, si avrà w(u,v) < w(x,y). Si dimostri che tutti gli alberi di copertura minima di G dovranno necessariamente contenere l'arco (u,v).

28/01/2015

Si determinino due diversi alberi di copertura minimi nel seguente grafo:

12/06/2014-1

Si scriva l’algoritmo di Kruskal, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo:

12-06-2014-2

Si supponga di voler cambiare una banconota da P euro in monete da a1, a2, …, ak euro. E’ possibile? In caso affermativo, qual è il minimo numero di monete da utilizzare per effettuare il cambio? Per esempio, se si volesse cambiare una banconota da 5 euro in monete da 1 e da 2 euro, sarebbero necessarie almeno 3 monete.

Se si disponesse soltanto di monete da 2 euro, invece, il cambio non sarebbe possibile.

Si formuli questo problema come un problema di cammini minimi su grafi. (Suggerimento: si costruisca un grafo con P + 1 vertici numerati da 0 a P e si inseriscano archi e pesi in modo tale che i cammini dal vertice 0 al vertice P corrispondano a possibili sequenze di monete da utilizzare per il cambio.)

A titolo esemplificativo, si consideri il caso di una banconota da P = 10 euro e monete da a1 = 1 e a2 = 2 euro.

Si costruisca il grafo corrispondente e si utilizzi l’algoritmo di Dijkstra per risolvere il problema.

29/05/2014-1

Si scriva l’algoritmo di Bellman-Ford, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo (utilizzando il vertice A come sorgente):

29/05/2014-2

Sia G = (V, E) un grafo pesato non orientato e connesso e sia w : E → R la funzione peso.
Sia Tmin un albero di copertura minimo di G e sia T un qualsiasi altro albero di copertura (non necessariamente minimo). Inoltre sia (u,v) ∈ E un arco di peso massimo in Tmin e (x,y) ∈ E un arco di peso massimo in T. Si dimostri che:

w(u,v) ≤ w(x,y).

In altri termini, fra tutti gli alberi di copertura, l’albero di copertura minimo ha il più piccolo arco di peso massimo. (Suggerimemto: si ragioni per assurdo e si usi la classica tecnica del “taglia-e-incolla”.)

12/09/2016

Si determini un albero di copertura minimo nel seguente grafo:

01/09/2015

Sia G = (V, E) un grafo non orientato, connesso e pesato. Dato un taglio (S, V \ S) di G, sia (u,v) un arco che lo attraversa tale che per tutti gli altri archi (x,y) che attraversano il taglio risulta w(u,v) ≤ w(x,y) (arco leggero). Si stabilisca, giustificando formalmente la risposta, se la seguente affermazione è vera o falsa: «Se T è un albero
di copertura di G che non contiene (u,v), allora T non è un albero di copertura minimo.»

Si può affermare la stessa cosa se si assume che tutti i pesi di G siano distinti? Perché?

Nota: nel fornire le giustificazioni non si faccia ricorso al teorema fondamentale degli MST.

Funzioni efficienti (alberi)

27/05/2015

Dato un albero binario, i cui nodi sono colorati di bianco, rosso o verde:

a. scrivere una funzione efficiente che stabilisca se esiste un cammino di tre nodi nell’albero i cui colori formano la bandiera italiana. (Il cammino può partire da un nodo qualsiasi, non necessariamente dalla radice.)

b. Fornire la chiamata della funzione dal programma principale.

c. Analizzare la complessità di tale funzione.

Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:


typedef struct node{
char * colore;
struct node * left;
struct node * right;
} * Node;


28/01/2015

Un nodo di un albero binario u è detto intermedio se la somma delle chiavi contenute nei nodi del sottoalbero di cui u è radice è uguale alla somma delle chiavi contenute nei nodi sul percorso che collega u alla radice dell’albero (u escluso).

a) Scrivere un algoritmo efficiente che restituisca il numero di nodi intermedi.

b) Analizzare la complessità della soluzione trovata. Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:

typedef struct node{
int key;
struct node * left;
struct node * right;
} * Node;


23/01/2014

Dato un albero binario i cui nodi sono colorati di bianco o di nero, scrivere una funzione C efficiente che calcoli il numero di nodi aventi lo stesso numero di discendenti bianchi e neri. (Un nodo è discendente di se stesso.)

Inoltre analizzare la complessità di tale algoritmo.

Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:

typedef struct node{
char * colore;
struct node * left;
struct node * right;
} * Node;

Si può ordinare un dato insieme di n numeri costruendo un albero binario di ricerca che contiene questi numeri (usando ripetutamente Tree-Insert per inserire i numeri uno alla volta) e stampando poi i numeri utilizzando un certo tipo di visita. Scrivere l’algoritmo che realizza questo ordinamento e specificare il tipo di visita effettuata e il relativo algoritmo.

Quali sono i tempi di esecuzione nel caso peggiore e nel caso migliore per questo algoritmo di ordinamento?

08/09/2014

Dato un albero binario, scrivere un procedura efficiente che cancelli il figlio sinistro di ogni nodo se è una foglia e contiene la stessa chiave del nodo padre.

Calcolare la complessità al caso pessimo della funzione indicando la corrispondente relazione di ricorrenza.

La rappresentazione dell’albero binario utilizza esclusivamente i campi left, right e key e il prototipo della procedura è:

void cancella(Node u)

12/06/2014-1

Dato un albero binario di ricerca T, scrivere la funzione Tree-maximum(Node x) che restituisce un nodo con chiave massima di un sottoalbero di T radicato nel nodo x (x è un nodo dell’albero T e x ≠ NULL). Quale è la complessità di questa funzione? Quale è il caso migliore? E il caso peggiore?

12/06/2014-2

Progettare un algoritmo efficiente per stabilire se un albero binario è quasi completo, cioè tutti i livelli dell’albero sono completamente riempiti, tranne eventualmente l’ultimo che ha le foglie addossate a sinistra.

Calcolare la complessità al caso pessimo dell’algoritmo indicando, e risolvendo, la corrispondente relazione di ricorrenza.

La rappresentazione dell’albero binario utilizza esclusivamente i campi left, right e key.

12/09/2016

Scrivere una funzione efficiente check che dato un albero binario di ricerca verifica se è soddisfatta la seguente condizione: per ogni intero k, se le chiavi k e k+2 sono nell'albero allora anche la chiave k+1 è nell'albero.

Analizzare la complessità della funzione. È preferita una soluzione con spazio aggiuntivo O(1).

Funzioni efficienti (divide-et-impera e altro)

28/01/2015

Scrivere un algoritmo efficiente, di tipo divide et impera, che conta il numero di occorrenze della sequenza ‘a’ ‘r’ memorizzata in posizioni adiacenti in un array di caratteri.

Analizzare la complessità indicando e risolvendo la corrispondente relazione di ricorrenza.

Esempio:

Per l’array ‹a, b, c, r› la risposta sarà 0.
Per l’array ‹b, a, r, c, a, r› la risposta sarà 2.

08/09/2014

Progettare un algoritmo efficiente che, dato un array A di n numeri interi e un intero x, determini se esistono due elementi in A (in posizioni diverse) la cui somma è esattamente x.

Calcolare la complessità al caso pessimo dell’algoritmo.

29/05/2014-1

Si determini la complessità asintotica dell’algoritmo AlgA definito come segue:

AlgA(n)
1. s ← 0
2. for i ← 1 to n
3. do s ← s + AlgB(n)
4. return s
AlgB(m)
1. if m = 1
2. then return 0
3. else return B(m/2) + m

29/05/2014-2

Progettare un algoritmo efficiente di tipo divide et impera che dato un vettore di interi restituisce true se tutti i valori sono distinti, false altrimenti. Analizzare la complessità dell’algoritmo proposto.

12/09/2016

Un collezionista di figurine possiede K figurine, non necessariamente distinte. Le figurine vengono stampate con un numero di serie, impresso dal produttore. I numeri di serie sono tutti gli interi compresi tra 1 e N. La collezione sarebbe completa se ci fosse almeno un esemplare di tutte le N figurine prodotte. Purtroppo la collezione non è completa: sono presenti dei duplicati, mentre alcune figurine mancano del tutto. Il vostro compito è di indicare i numeri di serie delle figurine mancanti.

Scrivere un algoritmo efficiente che dato N e l'array S[1..K], ove S[i] è il numero di serie della i- esima figurina posseduta, stampa l'elenco dei numeri di serie mancanti.

L'array S non è ordinato. Ad esempio, se N=10 e S=[1, 4, 2, 7, 10, 2, 1, 4, 3], l'algoritmo deve stampare a video i numeri di serie mancanti 5, 6, 8, 9 (non necessariamente in questo ordine).

Determinare la complessità dell'algoritmo di cui sopra, in funzione di N e K.

Attenzione: K potrebbe essere minore, uguale o maggiore di N.

01/09/2015

Progettare un algoritmo di ordinamento che si comporti come MergeSort, ma che divida ricorsivamente l’array in tre pari anziché due.
a. Scrivere lo pseucodice della nuova procedura MergeSort3.
b. Scrivere lo pseudocodice della nuova procedura Fusione3.
c. Scrivere e risolvere l’equazione di ricorrenza associata.

Hash

28/01/2015

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:
18, 36, 155, 19
La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:
h(k, i) = (k mod m + i * 2^{k mod 5}) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

27/05/2015

Nell’ipotesi di indirizzamento aperto, scrivere uno pseudocodice per HASH-DELETE e modificare HASHINSERT per gestire il valore DELETED. Analizzare la complessità delle due procedure nel caso pessimo.

12/06/2014

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi
numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Heap

09/09/2014

Dare la definizione di max-heap e dire se ‹23,17,14,6,13,10,1,5,7,12› è un max-heap giustificando la risposta.

29/05/2014

L’operazione Heap-Delete(A, i), cancella l’elemento nel nodo i dall’heap A. Implementare la procedura Heap-Delete in modo che il suo tempo di esecuzione sia O(lg n) per un max-heap di n elementi.

01/09/2015

Supponete di avere un min-heap di n elementi, e di cercare il valore massimo. In quali posizioni del vettore cercate? Giustificare la risposta.

Scrivere un algoritmo che dato un min-heap non vuoto restituisca il massimo. Calcolare la complessità.

Problemi P/NP/NPC

01/09/2015

Si definiscano le classi P, NP, NPC e si stabilisca, giustificando formalmente la risposta, quale delle seguenti relazioni è ritenuta vera (o verosimile):

12/09/2016

Si definisca formalmente la relazione di riducibilità polinomiale tra problemi decisionali ( ≤P ) e si stabilisca se le seguenti affermazioni sono vere o false:

1) La relazione ≤P è transitiva
2) La relazione ≤P è riflessiva
3) Se ≤P è simmetrica, allora P = NP
4) Se P ≤P Q e Q ∈ P, allora P ∈ P
5) Se P, Q ∈ NPC, allora P ≤P Q se e solo se Q ≤P P

Nel primo caso si fornisca una dimostrazione rigorosa, nel secondo un controesempio.

Nota: in caso di discussioni poco formali l’esercizio non verrà valutato pienamente.