dissabte, 26 d’octubre del 2013
Ara bé, imagina't per un moment que cada persona del planeta té un número d'identificació personal o un "DNI mundial", començant per la persona més vella de la Terra, que té el número 0.000.000.001 i acabant pel nadó que acaba de néixer, que s'identifica amb el 7.046.400.000.
Entre el total de les persones volem trobar-ne una d'especial que, com a habitant de la Terra, tindrà el seu propi número d'identificació. Per fer-ho, anem fent preguntes successives de doble resposta (Sí o No) sobre el seu número.
Exemple: El seu número és més gran que 5.000.000.000?
Exemple: El seu número és més gran que 5.000.000.000?
Quantes preguntes creus que hem de fer, per trobar-la?
Quin és el mètode més eficient?
Solució:
Potser hauràs pensat en 1000, 2000 o 3000 preguntes. Tanmateix, en tenim prou amb 33 preguntes per trobar una persona entre tota la població mundial.
La manera més eficient de fer-ho és coneguda com el mètode dicotòmic, i consisteix en prendre el valor mig del total ($N$) i anar fent mitjanes successives fins a trobar el número que busquem. D'aquesta manera, la primera pregunta que caldria fer és:
Potser hauràs pensat en 1000, 2000 o 3000 preguntes. Tanmateix, en tenim prou amb 33 preguntes per trobar una persona entre tota la població mundial.
La manera més eficient de fer-ho és coneguda com el mètode dicotòmic, i consisteix en prendre el valor mig del total ($N$) i anar fent mitjanes successives fins a trobar el número que busquem. D'aquesta manera, la primera pregunta que caldria fer és:
1. El seu número és més gran o igual que 3.523.800.000?
$$\frac{N}{2}$$
Si la resposta és "Sí", aleshores preguntaríem:
2. El seu número és més gran o igual que 5.285.200.000?
$$\frac{N+\frac{N}{2}}{2}=\frac{N}{2}+\frac{N}{4}$$
Si la resposta és "No", preguntarem:
3. El seu número és més gran o igual que 4.404.500.000?
$$\frac{\frac{N+\frac{N}{2}}{2}+\frac{N}{2}}{2}=\frac{N}{2}+\frac{N}{8}$$
I així successivament, fins a arribar al número que busquem. Per tant, com que en cada pas que fem reduïm el ventall de possibilitats a la meitat, el número de preguntes que haurem de fer serà:
$$2^{n}\ge7,0464·10^{9}$$
$$n\ge\frac{\log{7,0464·10^{9}}}{\log{2}}$$
$$n\ge32,71$$
Com a conclusió, tan sols caldran 33 preguntes per trobar qualsevol persona de la Terra. És més, gràcies a la potència dels ordinadors actuals, això es pot arribar a fer en poques mil·lèssimes de segons.
Mentre estava escrivint l'entrada, m'he adonat d'un detall curiós. Fixem-nos que, a les preguntes successives "El número és més gran o igual que $x$?", podem assignar el valor 1 a la resposta "Sí" i el valor 0 a la resposta "No". D'aquesta manera, un cop hàgim acabat les preguntes obtindrem una seqüència de zeros i uns (un codi binari) que, passant-lo a decimal, ens proporcionaria el número que busquem.
Per exemple, establim $N=8=2^{3}$ (3 preguntes necessàries), i el número que busquem és el 5. Preguntarem:
- El número és més gran o igual que 4? Resposta: Sí.
1- El número és més gran o igual que 6? Resposta: No.10- El número és més gran o igual que 5? Resposta: Sí101El número que busquem és el 5 o, el que és el mateix, l'101 en binari. Per tant, un mètode alternatiu d'identificar qualsevol persona del món és combinar 33 vegades el "Sí" i el "No" o l'1 i el 0.
T'ha agradat l'article?
Si us plau, ajuda'ns a difondre'l!
