Esercizi 2.4-2.5 Fondamenti di Ricerca Operativa Prof. E. Amaldi
2.4 Memorizzazione di sequenze in forma compatta. Nell’ambito degli studi sul genoma si presenta il problema di memorizzare in forma compatta un insieme molto grande di sequenze composte da elementi provenienti da un alfabeto di quattro simboli (le basi del DNA) che sono della stessa lunghezza e differiscono poco tra loro. Consideriamo la versione semplificata in cui le sequenze sono composte da due soli simboli (0 e 1). Dato un insieme di k sequenze di bit, calcoliamo per ogni coppia di sequenze i e j la distanza che le separa, ovvero quanti bit `e necessario commutare nella sequenza i per trasformarla nella sequenza j e viceversa. Ad esempio, in un insieme di sei sequenze binarie (1-6) come sotto, la matrice (simmetrica) delle distanze `e:
(a) 011100011101 (b) 101101011001 (c) 110100111001 (d) 101001111101 (e) 100100111101 (f) 010101011100
1 2 3 4 5 6 1 0 4 4 5 4 3
2 - 0 4 3 4 5
3 - - 0 5 2 5
4 - - - 0 3 6
5 - - - - 0 5
6 - - - 0
Per sfruttare le ridondanze fra le varie sequenze si pu`o memorizzare interamente una sequenza e le differenze che permettono di ricavare tutte le altre sequenze a partire da quella di riferimento.
Spiegare come si pu`o ricondurre il problema di scelta di quali differenze memorizzare al fine di minimizzare il numero totale di bit utilizzati al problema di determinazione di un albero di supporto di costo minimo in un grafo. Risolvere il problema per l’esempio citato.
2.5 Diffusione ottimale di un messaggio. Dato un grafo non orientato G = (V, E) con n nodi e m lati che rappresenta una rete di comunicazione, e per ogni lato {i, j} ∈ E la probabilit`a pij, con 0 ≤ pij ≤ 1, che un messaggio segreto venga inter- cettato lungo questo lato, determinare come fare arrivare ad ogni nodo il messaggio minimizzando la probabilit`a che esso venga intercettato. Formulare il problema in termini di ottimizzazione su grafi.
Documento preparato da Leo Liberti 1
