Alla ricerca del frutto avvelenato

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Alla ricerca del frutto avvelenato

Messaggio da rand »

Sia dato un albero T (grafo connesso aciclico). Tra i nodi di T ce n'è uno cattivo, chiamiato BAD. Il nodo BAD è assolutamente anonimo e non possiamo distinguerlo dagli altri guardando solamente la struttura di T. Fortunatamente ci è dato anche un "oracolo" che, interrogato su un nodo x, svela se x = BAD oppure qual è il primo arco da seguire nel cammino che congiunge x e BAD. Dimostrare che possiamo scoprire l'identità di BAD interrogando l'oracolo al più O(log n) volte.

Hint:
A cosa si riduce il problema se l'albero è una catena?
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Forza, immaginate che in quel nodo ci sia un gattino rimasto intrappolato e voi dovete salvarlo, non è certamente un hint ma forse vi sentirete più motivati...
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

ricerca binaria no?
paolo
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Dato un nodo v, chiamo $ ~ f(v) $ il rapporto tra l'ordine della più grande componente connessa di T \ v ed n.

Ora dimostrare che in ogni albero c'è un nodo con $ ~ f(v) \le \frac 12 $. Ma è semplice: parto da un nodo a caso, e seguo il figlio con la discendenza più grande finchè ad un certo punto devo trovare un nodo buono.

Poi, trovato questo, chiedo all'oracolo se c'è per caso un gatto, ed itero il procedimento.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Ogni albero ha un "centro" o un "bicentro" (che sono i nodi che hai chiamato "buoni"). Osservato questo, la ricerca si riduce ad una ricerca binaria.
rand è sempre fonte di bei problemi. :D
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Che vi sia piaciuto o meno, la fonte non sono io. L'ho presa dal sito di E.Demaine, era in una delle lezioni del corso di strutture dati che tiene al mit. Viene usata per illustrare un'applicazione giocattolo del fatto che ogni albero contiene un nodo separatore (o centro).
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

una cosa pero': d'accordo la ricerca binaria pero' come si fa a trovare il centro in tempo costante senza un preprocessing?
paolo
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

Ricontrolla il testo, non c'è scritto che devi impiegarci tempo O(log n), c'è solo scritto che puoi chiedere indicazioni al più O(log n) volte.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

ah e' vero non avevo notato! :oops:
paolo
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Pardon, ho detto una fesseria anch'io: i nodi di edriv ovviamente non sono centri e bicentri, ma i due metodi (quello di edriv e quello dei centri) risolvono entrambi il problema. Quello dei centri però è più efficiente.
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

A questo punto son curioso di sapere che è un centro...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Pag. 9 del Diestel. :wink:
Un nodo di un grafo è centrale se minimizza la massima distanza da un altro nodo del grafo. Si dimostra che ogni albero ha un solo centro, oppure due centri adiacenti.
Rispondi