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 » 05 apr 2008, 16:00

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 » 07 apr 2008, 13:58

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 » 07 apr 2008, 14:32

ricerca binaria no?
paolo

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

Messaggio da edriv » 07 apr 2008, 15:03

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.

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 08 apr 2008, 20:24

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 » 09 apr 2008, 19:04

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 » 09 apr 2008, 19:09

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: 3329
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 09 apr 2008, 19:31

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 » 09 apr 2008, 19:33

ah e' vero non avevo notato! :oops:
paolo

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 09 apr 2008, 20:26

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 » 09 apr 2008, 21:10

A questo punto son curioso di sapere che è un centro...

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 10 apr 2008, 00:35

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

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite