AppuntiLezioni2002 < Bioperl

Tags: view all tags

---++ Appunti delle esercitazioni di Algoritmi per il Master in Bio Informatica
---
%TOC%
---
   * 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.WebHome][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
<verbatim>
1-2-5-3
  |  |
  0  4-6
</verbatim>
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:
<verbatim>
7
2
2
5 0 1
5
6 5
4 3 2
4
</verbatim>

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
   1 Leggere l'INPUT
   1 Ordinare la lista di adiacenza
   1 Creare un vettore con i gradi di connessione per ogni nodo
   1 Calcolare il codice di Prufer

   * Definire le Strutture Dati <br />
   Le strutture dati necessarie per costruire il codice di Prufer a partire dall'albero sono:
      1 una lista di adiacenza per rappresentare l'albero
      1 una lista di adiacenza "ordinata"
      1 un vettore che conterrà il codice di Prufer
      1 un vettore dei gradi di connessione dei nodi
      1 un vettore per gli eliminati
      1 una variabile che contenga il numero di nodi dell'albero

   * Leggere l'INPUT <br />
     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== <br />
      (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
      1 Leggere il codice di Prufer dall'input
      1 Costruire il vettore delle molteplicità
      1 Ricostruzione dell'albero (costruzione della matrice di adiacenza)
      1 stampa della matrice

   * Definire le strutture:
      1 il vettore del codice di Prufer
      1 la lista (o matrice) di adiacenza dove ricostruire l'albero
      1 il vettore di molteplicità dei nodi
      1 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
      1 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

----

<!--
   * Set ALLOWTOPICCHANGE = Users.LucaFerraro, Users.AndreaSterbini
-->

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pl	GCD.pl	r1	manage	1.1 K	2003-02-07 - 20:59	AndreaSterbini	lezione 1
pl	bubble-sort.pl	r1	manage	1.3 K	2003-02-20 - 21:51	AndreaSterbini	lezione 2
pl	count-sort.pl	r1	manage	2.1 K	2003-02-20 - 21:52	AndreaSterbini	lezione 2
pl	insertion-sort.pl	r1	manage	2.5 K	2003-02-07 - 21:00	AndreaSterbini	lezione 1
pl	media.pl	r1	manage	0.7 K	2003-02-07 - 20:59	AndreaSterbini	lezione 1
pl	merge-sort.pl	r1	manage	3.1 K	2003-02-20 - 21:52	AndreaSterbini	lezione 2
pl	min-max.pl	r1	manage	1.2 K	2003-02-20 - 21:51	AndreaSterbini	lezione 2
pl	prufer.pl	r1	manage	6.3 K	2003-03-25 - 14:45	LucaFerraro	Algoritmo in PERL codifica in codice di Prufer
pl	radix-sort.pl	r1	manage	2.7 K	2003-02-20 - 21:52	AndreaSterbini	lezione 2
pl	selection-sort.pl	r1	manage	1.6 K	2003-02-07 - 21:00	AndreaSterbini	lezione 1
pl	somma-N.pl	r1	manage	1.0 K	2003-02-07 - 20:59	AndreaSterbini	lezione 1