Appunti delle esercitazioni di Algoritmi per il Master in Bio Informatica

---

---

• In allegato in fondo alla pagina trovate i programmi Perl usati a lezione
• Un bel corso di Perl per Bio Informatici si trova a http://bioportal.weizmann.ac.il/course/prog/index.html
  • ne trovate una copia (compressa) da masterizzare in attachment alla pagina.
• Per informazioni su Linux esplorate le pagine del corso di Programmazione1 oppure consultate la splendida guida di Daniele Giacomini "Appunti di Informatica Libera" che trovate all'indirizzo http://ildp.pluto.linux.it/AppuntiLinux/ (Scaricabile anche in formato .PDF dal sito http://sansone.crema.unimi.it/linux/a2/PDF/ ).

Lezione 1

• media di più numeri
• somma dei numeri da 1 a N
• Massimo Comun Divisore
• selection sort
• insertion sort

Lezione 2

• ricerca di minimo e massimo
• bubble sort
• counting sort
• merge sort
• radix sort

Esame

• L'esame sarà formato da una domanda sulla teoria (lezioni di Rossella) ed una sulla pratica (il vostro programma).

---

Progetto: codifica e decodifica di un albero nel (dal) suo codice di Prufer

Il progettino da realizzare consiste nei due programmi che servono, dato un albero a codificarlo secondo il codice di Prufer (spiegato a lezione) ed a decodificarlo. Vi ricordo di che si tratta:

• l'albero non è radicato ed è fornito sotto forma di lista di adiacenza
• l'albero è formato da N nodi etichettati con i numeri da 1 a N

Codifica

Le operazioni di codifica si possono scomporre nei passi:

ordinamento delle liste di adiacenza in tempo O(N)

Date le liste di adiacenza non ordinate vogliamo costruire una nuova serie di liste di adiacenza in cui la lista dei vicini di un qualsiasi nodo sia ordinata in ordine crescente

• per ogni nodo x_i a partire da 1 fino a N
  • per ciascuno dei suoi vicini y_j
  • aggiungere x_i in fondo ai vicini di y_j nella nuova matrice
• dato che i nodi x_i vengono visitati in ordine, le liste di adiacenza prodotte saranno ordinate

costruzione del codice di Prufer

Il codice di Prufer di un albero è una successione (array) di numeri che si ottiene:

• si usano due array aggiuntivi:
  • per ogni nodo x_i si calcola il grado d_i del nodo (numero di vicini)
  • un array che indica per ogni nodo se esso è stato rimosso dall'albero
• Si ripete il passo che segue
  • si cerca la foglia y con etichetta minima (ovvero il primo nodo che ha d_i=1) e:
    • si aggiunge al codice di Prufer l'etichetta di z l'unico vicino di y
    • si marca y come rimosso e si decrementa di 1 il grado di z
  • si noti che a questo punto la prossima foglia può essere solo:
    • z se il suo grado è divenuto 1
    • oppure uno dei nodi che seguono y

Esempio

L'albero

1-2-5-3
  |  |
  0  4-6

Che ha matrice di adiacenza (disordinata):

riga	vicini
0	2
1	2
2	5 0 1
3	5
4	6 5
5	4 3 2
6	4

E che viene indicata dall'input:

7
2
2
5 0 1
5
6 5
4 3 2
4

Durante l'algoritmo di codifica avviene la rimozione successiva dei nodi: 0 1 2 3 5 4

Per cui il codice di Prufer ottenuto è: 2 2 5 5 4 6

---

Costruzione dell'albero a partire dal codice di Prufer

Vedete lo pseudocodice più sotto

Esempio

Supponiamo di dover partire dal codice precedente: 2 2 5 5 4 6

Calcoliamo le molteplicità: 0 0 2 0 1 2 1

La prima foglia è quella con indice 0, ed il suo vicino è il nodo 2 (primo elemento del codice)

---

Pseudo Codice

Costruzione del codice di Prufer

1. Definire le Strutture
2. Leggere l'INPUT
3. Ordinare la lista di adiacenza
4. Creare un vettore con i gradi di connessione per ogni nodo
5. Calcolare il codice di Prufer

• Definire le Strutture Dati
  Le strutture dati necessarie per costruire il codice di Prufer a partire dall'albero sono:
  1. una lista di adiacenza per rappresentare l'albero
  2. una lista di adiacenza "ordinata"
  3. un vettore che conterrà il codice di Prufer
  4. un vettore dei gradi di connessione dei nodi
  5. un vettore per gli eliminati
  6. una variabile che contenga il numero di nodi dell'albero

• Leggere l'INPUT
  Il file di ingresso (di INPUT) dovrebbe avere come prima riga il numero N dei nodi dell'albero. Quindi potete fare un ciclo for per le N righe, dove ciascuna riga può essere suddivisa nei vari elementi con l'istruzione split(/---+/,$riga)

• Ordinare la lista di adiacenza
  1. per N volte (y)
     • per ogni elemento x della lista corrente inserisco x come vicino di y (con il comando push)

• Calcolare i gradi
  1. Per N volte (x) abbiamo che:
     • $grado[x] = $#lista---+ 1
       (altrimenti potete contare direttamente quanti elementi ci sono sulla riga)

• Cercare il vicino y del nodo x
  1. Prendere la lista di adiacenza di x e per ogni y della lista bisogna controllare che y non sia stato eliminato (si può ottenere con un semplice ciclo while)

---

Dal vettore di Prufer all'albero (rappresentato come liste di adiacenza)

1. Anche qui è bene definire prima di tutto le strutture su cui operiamo e quelle di cui abbiamo bisogno. Questa volta

partiamo dal codice di Prufer (un vettore) di M elementi. L'albero che dobbiamo ricostruire ha un numero di nodi pari a N = M---+ 1.

Dobbiamo utilizzare un vettore di molteplicità in cui contiamo quante volte un singolo nodo è stato estratto. I nodi che erano foglie dell'albero avranno molteplicità zero. Quindi, per ricostruire l'albero, dobbiamo cercare nel vettore di molteplicità il nodo che ha l'etichetta più piccola e che ha molteplicità uguale a zero. Il vettore che contiene il codice di Prufer ci dice quale è la foglia vicina al nodo individuato.

• Decodifica
  1. definire e inizializzare le strutture dati usate
  2. Leggere il codice di Prufer dall'input
  3. Costruire il vettore delle molteplicità
  4. Ricostruzione dell'albero (costruzione della matrice di adiacenza)
  5. stampa della matrice

• Definire le strutture:
  1. il vettore del codice di Prufer
  2. la lista (o matrice) di adiacenza dove ricostruire l'albero
  3. il vettore di molteplicità dei nodi
  4. un vettore che indica quale nodo è stato eliminato

• Leggere il codice di Prufer
  • Si deve leggere la riga del codice ed utilizzare la funzione di split(/---+/, $riga) per dividerlo nei suoi elementi.

• Costruire il vettore delle molteplicità (si veda il codice del counting-sort)
  1. inizializzare a 0 tutti gli elementi del vettore
  2. per ogni valore letto in input
     • aumentare di uno la voce corrispondente nel vettore della molteplicità

• Ricostruzione dell'albero (costruzione della matrice di adiacenza)
  1. bisogna ripetere N - 1 volte l'operazione di ricerca della foglia di etichetta più bassa nel vettore di molteplicità, (chiamiamo i il contatore del ciclo)
     • cercare la prima x che ha: molteplicità==0 e che non è stata ancora eliminata
     • leggere dal codice di Prufer il valore y=c[i] che indica qual'e' il vicino di x
     • inserire (con push) nella matrice di adiacenza i due archi, ossia mettere:
       • nella riga y della lista di adiacenza il valore x
       • nella riga x della lista di adiacenza il valore y
     • marcare il valore x come eliminato
     • decrementare la molteplicità dell'elemento $codice[i]

• Stampare il risultato
  • stampate il numero di nodi N
  • per ciascuna delle N righe
    • usare la funzione join (e print) per stampare ciascuna lista di adiacenza separata da spazio

---