Solution au problème de la célébrité

Bonjour,

Je me suis penché sur le problème de la célébrité et sa solution en 2N tests.

Pour ceux qui ne connaîtraient pas ce problème, il peut s'énoncer comme ça :
Soit un ensemble de N personnes parmi lesquelles figure peut-être une célébrité. Une célébrité est défini comme étant une personne que tout le monde connaît mais qui ne connaît personne.

On peut représenter ce problème sous forme d'une matrice NxN remplie comme suit. Si la personne de la j-eme colonne connaît la personne de la i-eme ligne, alors l'élément d'indice (i, j) est un 1, sinon c'est un 0.

Par exemple :

Code:

---

1 2 3 4 5 6 7

1 2 3 4 5   1 0, 1, 1, 0, 0 2 1, 0, 1, 0, 0 3 0, 0, 1, 0, 0 4 1, 1, 1, 1, 1 5 1, 1, 1, 0, 1

---

La personne numéro 2 connaît la personne numéro 1 mais ne connaît pas la personne numéro 3.

Chercher la célébrité (elle est forcément unique) revient à chercher dans la matrice un n tel que la n-ième ligne soit remplie de 1 et la n-ième colonne remplie de 0. (Bien évidemment sans s'occuper de savoir si on se connaît soi-même.)

Notre prof nous a indiquer comment procéder pour trouver la célébrité avec un maximum de 2N questions.

Code:

---

1 2 3 4 5 6 7 8 9 10

Soient A et B deux personnes prises au hasard dans la foule Si A connaît B alors A n'est pas la célébrité sinon Si B connaît A alors B n'est pas la célébrité sinon A n'est pas la célébrité fin si fin si

---

C'est là que commencent mes problèmes :
Si j'ai bien compris, à chaque itération on élimine une des deux personnes. Mais je ne comprend pas comment cet algorithme peut garantir qu'une fois terminé la personne restante est bien la célébrité sachant qu'on est pas sûr qu'il y ait une célébrité dans l'ensemble.

De plus je ne comprend pas pourquoi la deuxième question est indispensable car si A connait B, alors A n'est pas la célébrité, mais si A ne connait pas B, alors B n'est pas la célébrité.

Et aussi, je ne vois pas comment on peut peut-être trouver la célébrité en moins de 2N tests puisque à supposer qu'on tombe directement sur la célébrité, il faudra dans le pire des cas 2N tests pour vérifier qu'on est bien tombé sur la célébrité.


J'aimerais comprendre où mon raisonnement est faux.


Merci d'avance
Celelibi

D'accord avec toi. Pour moi, c'est par exemple

Code:

---

1 2 3 4 5 6 7 8 9

Soient A et B deux personnes prises au hasard dans la foule Si A connaît B alors A n'est pas la célébrité sinon B n'est pas la célébrité si B ne connait pas A A n'est pas la célébrité fin si fin si

---

l'énoncé est faux...

Forcément la personne se connait elle-même..

Donc il faut trouver une ligne ou il y a 1 seul 1 en position diagonale et une colonne avec que des 1 (ou l'inverse ça dépend comment on crée la matrice) passant à cette colonne (ligne respectivement). ici la personne 3

Donc le pseudo algo est :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Pour toutes les personnes i c'est une celebrite Si i different de j et i connait j alors pas une celebrite sortie de si fin si si celebrite indicateur = 0 pour toutes les personnes j si j connait i indicateur = indicateur + 1 fin si si indicateur different de nombre de personnes alors pas une celebrite fin si si celebrite sortie de pour fin si fin pour

---

Au maximum 2*N passages...

désolé c'est pas en 2*N.. Je vais réfléchir un peu...

tu es sûr que ce n'est pas N^2 ??

Il faut au moins passer une fois par ligne....

même si on ne teste pas la diagonale, ça fait quand même N*(N-1)....

y vous va pas mon algo en 6 lignes???
Bien sûr que la personne se connait elle-même, je n'avais même pas relevé!

Bon ok, admettons qu'une personne se connaisse elle-même (même si cette question est plus philosophique qu'algorithmique).

Personnellement j'ai un algo en 3*N questions.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

A = 1; B = 2; Tant que A <= N et B <= N faire Si A connait B alors A = MAX(A, B)+1; // A n'est pas la célébrité, on teste la prochaine personne sinon B = MAX(A, B)+1; fin si; fin tant que;   // Ici on a A ou B qui est inferieur à N et qui indique quelle est la dernière personne qui est peut-être une célébrité // On a juste à vérifier si c'en est une.   P = MIN(A, B); celebre = vrai; Pour I de 1 à N faire Si (I ne connait pas P) ou (P connait I et I != P) alors celebre = faux; fin si; fin pour;

---

Mais ce n'était pas l'objet de la question (cela dit si vous trouvez que mon algo ne marche pas dites-le).
Ma question était plutôt : il semblerait que la question réciproque de savoir si B connait A soit indispensable pour décider si oui ou non la célébrité existe sans devoir faire une vérification par la suite.

non je viens de comprendre l'algo initial...

Et le tien, Nemerle, oublie une possibilité (ou en tous est moins efficace)

Le principe est le suivant :

Si l'on fait un tableau d'indicateurs "est une célebrité" de N éléments

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

tous les indics initialisés à 1.   ligne 1 : pour j = 2 a N si 1 connait j indic 1 = 0 sinon si j connait 1 indic j = 0 sinon indic 1 = 0 fin si fin si fin pour

---

Donc ici on a fait (N-1) itérations, et on a déterminé si 1 ET si les autres POUVAIENT être des célebrités.

Il ne reste plus qu'à finir l'itération sur par exemple le tableau d'indic, pour voir si il reste un 1....

Brillant.... :king:

Citation:

---

Envoyé par Celelibi

Ma question était plutôt : il semblerait que la question réciproque de savoir si B connait A soit indispensable pour décider si oui ou non la célébrité existe sans devoir faire une vérification par la suite.

---

oui voir ci-dessus....

souviron34, selon ce que je comprend, cet algo reste en O(N^2)

Si on a la matrice suivante :

Code:

---

1 2 3 4 5 6 7

1 2 3 4 5   1 1, 0, 0, 0, 0 2 1, 1, 1, 0, 0 3 0, 0, 1, 0, 0 4 1, 1, 1, 1, 1 5 0, 1, 1, 0, 1

---

À la fin de l'itération on aura le tableau d'indicateurs suivant : [0, 1, 1, 1, 1]. On aura donc éliminé la personne numéro 1 en N-1 itérations.
Si après on doit recommencer l'algo avec la personne numéro 2 puis 3 etc... ça nous fera encore un algo en N^2.
Ou alors j'ai encore loupé un truc.

Je me permet de reposter l'algo du prof:

Code:

---

1 2 3 4 5 6 7 8 9 10

Soient A et B deux personnes prises au hasard dans la foule Si A connaît B alors A n'est pas la célébrité sinon Si B connaît A alors B n'est pas la célébrité sinon A n'est pas la célébrité fin si fin si

---

Cet algo permet de trouver la célébrité, si elle existe, en entre N et 2 N questions. Mais il faudrait plus pour démontrer que la personne restante soit la célébrité : en effet, la première personne interrogée ne nous a surement pas dit si elle connaissait ou pas la personne restante.

Sinon, l'algo de Nemerle n'est pas moins efficace que l'algo initial car il fait les même chose en tirant plus de conséquences des mêmes questions (donc il est encore mieux).

Citation:

---

Envoyé par souviron34

Et le tien, Nemerle, oublie une possibilité (ou en tous est moins efficace)

---

euh... faut que tu m'expliques!!! :mouarf:

Mais si tu veux optimiser, je peux faire encore mieux, mais on a le temps...

T'inquiète pas ton algo est plus performant que le premier Nemerle;)

Voilà un algo plus court:

Code:

---

1 2 3 4 5 6 7

Soient A et B deux personnes au hasard dans la foule Si A connait B A n'est pas la célébrité : on élimine A Sinon B n'est pas las célébrité : on élimine B finsi

---

Cet algo élimine en N-1 questions toutes les personnes sauf 1.

Après, pour savoir si cette personne est une célébrité ou non, il faut poser entre N-1 et 2N-1 questions (suivant quand on lui pose la question).