Algoritmi e Strutture Dati

B C

D E

Dromedario Cammello

F Megattera Balenottera

Mucca

Capra Pecora

Un esempio di albero filogenetico

Figura 1. 1/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Un albero filogenetico rappresenta le relazioni di tipo evolutivo tra specie sulla base di similarità

genomiche (un esempio è mostrato in Figura 1). Le foglie dell’albero sono specie viventi, mentre i nodi

interni rappresentano antenati comuni a diverse specie e non necessariamente corrispondono a specie

realmente esistite nel passato. In altre parole un nodo interno rappresenta un ipotetico antenato a

partire da quale un “porzione” del genoma si è modificato dando luogo a due diverse linee evolutive

(l’albero è pertanto binario). Si scriva lo pseudo-codice di un algoritmo che dato un nodo interno

dell’albero, cioè una ipotetica specie vissuta nel passato, stampi tutte le secie viventi che da essa si

sono evolute. Con riferimento alla figura, se il nodo di input fosse C le specie da stampare sarebbero

“Capra”, “Pecora”, “Mucca”, “Megattera” e “Balenottera”.

N.B. L’input è costituito dal nodo rappresentante la specie potetica e non dalla stringa che la

identifica. 2/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Esame di Algoritmi e Strutture Dati

20/01/2016

Domanda 1 (7.5 punti) Utilizzando il teorema dell’esperto determinare un limite asintotico esatto

n 2

per la funzione T (n) definita dall’equazione di ricorrenza T (n) = 6T ( ) + n lg n.

3

Domanda 2 (7.5 punti) Dare la definizione di albero rosso-nero e dimostrare che in un albero

rosso-nero l’altezza h è al più 2 log (n + 1).

2 ×

Domanda 3 (7.5 punti) Data una matrice di interi A = [a ] di dimensione n m, una V-sequenza

i,j

≤ ≤ ≤ ≤ ≤

è una sequenza (a , a , . . . , a ) (con 1 j m) tale che j j per ogni 1 i n. In altre

1,j 2,j n,j i i+1 i

n

1 2

parole un V-sequenza è una sequenza contenente un elemento per ogni riga e tale che ogni elemento

si trova alla sinistra o sulla stessa colonna del precedente. Il valore di una V-sequenza verticale è

dato dalla somma degli elementi che la compongono. Una V-sequenza massima di una matrice A è

una V-sequenza di valore più alto tra tutte le V-seqeunze possibili in A. Ad esempio, nella matrice

seguente, la V-sequenza massima è costituita dagli elementi a , a , a , a che sono evidenziati.

1,3 2,1 3,1 4,1

 

1 5 8 6

4 3 1 2

 

 

 

6 6 0 3

 

2 3 6

4

Utilizzando la programmazione dinamica, si vuole risolvere il problema di individuare una V-

sequenza massima di una matrice A. Indichiamo con v(i, j) il valore della V -sequenza massima che

≤ ≤ ≤ ≤

ha come ultimo elemento a con 1 i n e 1 j m. Si chiede di:

i,j

• scrivere un’equazione ricorsiva per v(i, j); ∗

• scrivere un’equazione per determinare il valore v della V-sequenza massima di A;

• Scrivere un algoritmo basato sulla programmazione dinamica che risolve il problema ricevendo

in input la matrice A.

• Valutare la complessità dell’algoritmo.

Domanda 4 (7.5 punti)

Un albero di decisione è uno strumento di supporto alle decisioni e rappresenta una collezione

progressiva di domande rispondendo alle quali si giunge ad una decisione. Un albero di decisione è

un albero binario in cui ogni nodo interno n corrisponde ad una domanda la cui risposta può essere

sı̀ o no. Il figlio destro di n è il nodo da considerare se la risposta è no, mentre il figlio sinistro di

1/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

n è il nodo da considerare se la risposta è sı̀. Le foglie dell’albero corrispondono alle decisioni finali.

L’albero in figura rappresenta un albero di decisione per decidere la forma di investimento dei propri

risparmi. Sei una persona

ansiosa?

sı̀ no

Avrai bisogno del

tuo denaro nei

Conto di prossimi 5 anni?

risparmio no

sı̀ Sei disposto ad

accettare rischi per

Fondo avere maggiori

monetario guadagni?

sı̀ no

Portafoglio Portafoglio

azionario diversificato

Scrivere lo pseudo-codice di un algoritmo che ricevuto in ingresso un albero di decisione restituisce

il numero massimo di domande cui è necessario rispondere per arrivare ad una decisione. Nell’esempio

in figura il numero massimo di domande è tre. 2/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Esame di Algoritmi e Strutture Dati

15/06/2016

Domanda 1 (8 punti) Utilizzando il teorema dell’esperto determinare un limite asintotico esatto

√

n

per la funzione T (n) definita dall’equazione di ricorrenza T (n) = 2T ( n.

) + n

3

Domanda 2 (8 punti) Dare la definizione di heap binomiale e dimostrare che uno heap binomiale

blg

con n nodi è formato al più da nc + 1 alberi binomiali.

Domanda 3 (8 punti) Una società che produce biscotti vuole effettuare una campagna di marketing

basata su spot pubblicitari da mandare in onda sulle principali reti televisive nazionali. Ci sono n reti

{r }.

televisive , r , . . . , r Mandare in onda uno spot sulla rete r ha un costo pari a c ma garantisce un

1 2 n i i

numero di telespettaori pari ad a . La società ha un budget di B euro e deve decidere le reti televisive

i

su cui mandare in onda gli spot massimizzando il numero di telespettarori che li vedranno. Più

precisamente si indichi con T (i, b) il numero massimo di telespettatori che si può ottenere scegliendo

{r }

un numero qualunque di reti nell’insieme , r , . . . , r spendendo al più b euro. Si chiede di:

1 2 i

• scrivere un’equazione ricorsiva per T (i, b); ∗

• scrivere un’equazione per determinare il valore T della soluzione ottima del problema generale;

• scrivere un algoritmo basato sulla programmazione dinamica per risolvere il problema, rice-

vendo in input l’array C dei costi, l’array A degli spettatori previsti per ogni rete, e il budget

B.

Domanda 4 (8 punti) Un albero di gioco (game tree) è un albero utilizzato per rappresentare le

possibili configurazioni di un gioco (come scacchi, dama, ecc.). Ogni nodo dell’albero rappresenta

una possibile configurazione dello schema di gioco; i figli di un nodo v rappresentano tutte le possibili

configurazioni raggiungibili effettuando una sola mossa a partire dalla configurazione rappresentata da

v. La radice dell’albero rappresenta la configurazione iniziale e le foglie dell’albero rappresentano le

possibili configurazioni finali. I livelli pari corripondono ai turni in cui deve muovere il primo giocatore

(giocatore A), mentre i livelli dispari corripondono a turni in cui deve muovere il secondo giocatore

(giocatore B). La figura seguente mostra una porzione dell’albero di gioco del filetto.

1/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Per stabilire una strategia di gioco si assegna un punteggio ad ogni nodo come segue:

• a ciascuna foglia v viene assegnato il valore:

– 1 se la configurazione di v rappresenta una vittoria del giocatore A;

−1

– se la configurazione di v rappresenta una vittoria del giocatore B;

– 0 se la configurazione di v rappresenta un pareggio.

• ad ogni nodo interno viene assegnato:

– un punteggio pari al massimo tra i punteggi dei suoi figli, se il nodo corrisponde ad un

turno in cui deve muovere A (livello pari);

– un punteggio pari al minimo tra i punteggi dei suoi figli, se il nodo corrisponde ad un turno

in cui deve muovere B (livello dispari);

Scrivere lo pseudo-codice di un algoritmo che ricevuto in ingresso un albero di gioco T alle cui

foglie sono già stati assegnati i punteggi come descritto in precedenza, calcola i punteggi dei nodi

interni.

Si assuma che l’albero sia rappresentato mediante la rappresentazione filgio-sinistro-fratello-destro

e che il punteggio di ogni nodo sia memorizzato in un campo score.

2/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Esame di Algoritmi e Strutture Dati

29/06/2016

Domanda 1 (8 punti) Dimostrare usando il metodo di sostituzione che la funzione T (n) definita

2

dalla seguente equazione di ricorrenza è O(n lg n).

(

0 n = 1, 2

T (n) = n n 2

c) c)

T (b + T (b + n lg n n > 2

2 3

Domanda 2 (8 punti) Dare la definizione di albero rosso-nero e dimostrare che in un albero rosso-

nero l’altezza h è al più 2 lg(n + 1).

Domanda 3 (8 punti) Dato un intero x di n cifre definiamo sequenza cancellativa di x una sequenza

di n interi tale che il primo intero della sequenza è x e ogni elemento successivo si ottiene dal precedente

eliminando la cifra più significativa o quella meno significativa. Il valore della sequenza cancellativa

è dato dal numero di quadrati perfetti che vi compaiono. Ad esempio per x = 32492 due possibili

sequenze cancellative sono: → → → →

32492 3249 324 24 4

→ → → →

32492 2492 492 49 9

Il valore della prima sequenza è 3, quello della seconda è 2 (in grassetto sono evidenziati i quadrati

perfetti).

Dato un intero x di n cifre si vuole individuare una sua sequenza cancellativa di valore massimo.

Più precisamente, indicata con c c . . . c la sequenza di cifre che rappresenta x (per x = 32492

n−1 n−2 0

si avrebbe c = 3, c = 2, c = 4, c = 9 e c = 2), si denoti con x il numero c c . . . c

4 3 2 1 0 ij j j−1 i

≤ ≤ ≤ −

(0 i j n 1). Si indichi con s(i, j) il valore della sequenza cancellativa di valore massimo per il

≤ ≤ ≤ −

numero x (0 i j n 1). Si chiede di:

ij

• scrivere un’equazione ricorsiva per s(i, j);

∗

• indicare come si determina il valore s della soluzione ottima del problema generale;

• scrivere un algoritmo basato sulla programmazione dinamica per risolvere il problema, rice-

vendo in input l’intero x rappresentato mediante un array X il cui i-esimo elemento è la cifra

≤ ≤ −

c (0 i n 1) ed assumendo di avere a disposizione una procedura sqr() che dato un intero

i

restituisce true se il numero è un quadrato perfetto e false altrimenti.

1/2

Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Algoritmi e Strutture Dati

Domanda 4 (8 punti) La distanza tra due foglie di un albero T è la lunghezza, cioè il numero di

archi, del cammino che collega una foglia all’altra in T . Si scriva lo pseudo-codi