Lezione del 17 ottobre mi sono svegliato così tardi che praticamente ho skippato tutto quanto. Devo recuperare dagli appunti
Si parla sempre di alberi, in questo caso mi pare che si stia trattando di saturation technique
Schemino carino per andare a vedere la differenza tra rooted e unrooted tree
L’idea è quella di andare a trovare il minimo. Perché questo? Perché io ho delle entità che hanno tutte un valore v(x), non per forza distinto. Alla fine di questa procedura dobbiamo sapere se ha il valore più piccolo o meno in assoluto.
Come possiamo fare questa operazione?
“La computazione parte dalle foglie, che mandano il proprio valore al proprio vicino (unico). Il vicino prende il minimo tra il proprio valore e quello dei vicini e lo manda al padre. Le entità interne aspettano di ricevere i valori di tutti i vicini tranne uno e, una volta ricevuti, manda il minimo al vicino mancante. Una volta che un’entità interna riceve messaggi da tutti i vicini manda il valore minimo calcolato ai vicini, per diffonderlo a tutto l’albero.”
qui praticamente mi conviene inserire direttamente il riassuntone visto che è molto chiaro
La tecnica della saturazione si dice “full saturation” quando può essere iniziata in modo autonomo e indipendente da un numero qualsiasi di inizializzatori.
Abbiamo varie fasi all’interno di questo algoritmo:
Fase di attivazione: iniziata da tutti gli inizializzatori -> tutte le entità vengono attivate. Il wake-up viene iniziato dagli inizializzatori e in un tempo finito tutte le entità diventano attive.
Fase di saturazione: iniziata dalle foglie -> alla fine una coppia di entità vicine viene selezionato. Le foglie mandano messaggi di saturazione al loro unico vicino. I nodi interni aspettano di ricevere da tutti i vicini-1 il messaggio di saturazione e lo manda al vicino rimanente. Una volta mandato il messaggio di saturazione l’entità diventa “processing”. Se un’entità “processing” riceve un messaggio di saturazione, diventa “saturato”.
Fase di risoluzione: iniziato dalle entità selezionate (saturate). Dipende dall’applicazione ma, solitamente, è una notifica.
