Casse-tête de logique commune - Explication des problèmes des chevaliers et des chevaliers, de Monty Hall et des philosophes de la restauration

Bien que n'étant pas strictement liés à la programmation, les énigmes logiques sont un bon début pour votre prochaine session de codage. Vous pouvez rencontrer un casse-tête logique lors de votre prochain entretien technique pour juger de vos compétences en résolution de problèmes, il vaut donc la peine d'être préparé.

Dans cet article, nous avons rassemblé quelques énigmes logiques célèbres et leurs solutions. Pouvez-vous les résoudre sans jeter un œil à la réponse?

Chevaliers et fripons

Pour ce casse-tête logique, imaginez qu'il existe deux types de personnes, les chevaliers et les valets. Les chevaliers ne disent que la vérité, tandis que les Knaves ne disent que des mensonges.

Il existe de nombreuses variantes de ce puzzle, mais la plupart impliquent de poser une question pour savoir qui est le chevalier et qui est le valet.

Rouge et bleu

Il y a deux personnes debout devant vous, Rouge et Bleu. Blue dit: "Nous sommes tous les deux des coquins." Qui est vraiment le chevalier et qui est le valet?

Solution

Il est impossible pour Bleu d'être le chevalier. Si Bleu était un chevalier, la déclaration «Nous sommes tous les deux des coquins» serait en fait un mensonge. Par conséquent, Bleu est un valet car sa déclaration est un mensonge, et Rouge doit être un chevalier.

Deux chemins

Vous arrivez à un croisement de la route et devez choisir le bon chemin qui mène à votre destination. Il y a deux personnes debout à la fourche, et vous savez que l'un doit être un chevalier et l'autre doit être un valet.

Quelle question unique pourriez-vous poser à l'une des personnes pour déterminer le bon chemin, A ou B?

Solution

La question que vous pouvez poser à l'une ou l'autre personne est: "Quel chemin l'autre personne me dirait-il est le bon?" La réponse sera toujours le mauvais chemin à emprunter et vous pouvez emprunter l'autre chemin en toute sécurité.

Imaginez que le chemin correct soit A.

Si vous demandez directement, "Quel est le chemin correct?" le valet dira que B est correct tandis que le chevalier dira A.

Cependant, lorsqu'on lui demande quel chemin l' autre personne dirait est correct, le valet mentira et dira que le chevalier vous dira que le chemin B est correct. Pendant ce temps, le chevalier dira la vérité sur la réponse du valet et dira que le valet vous dira que le chemin B est le bon.

Dans les deux cas, vous savez que la réponse, le chemin B, est en fait un mensonge, vous devriez donc emprunter l'autre chemin.

Le problème de Monty Hall

Le problème de Monty Hall est une énigme sur les probabilités nommée d'après l'animateur du jeu télévisé des années 70 sur lequel il est basé, Let's Make a Deal . Ce problème particulier est un paradoxe véridique, ce qui signifie qu'il existe une solution qui semble contre-intuitive, mais qui s'est avérée vraie.

Imaginez que vous participez à un jeu télévisé et qu'il y a 3 portes, chacune avec un prix différent derrière elles. Derrière l'une des trois portes se trouve une voiture. Derrière les deux autres portes, il y a des chèvres.

Vous devez choisir l'une des 3 portes pour sélectionner votre prix.

Supposons que vous décidiez d'ouvrir la porte 1. L'hôte, qui sait où se trouve la voiture, ouvre une autre porte, la porte 2, qui révèle une chèvre. Il vous demande ensuite si vous souhaitez ouvrir la porte 3 à la place.

Devriez-vous choisir la porte 3 plutôt que votre choix initial? Cela a-t-il même une importance?

Solution

Il s'avère que votre choix compte vraiment, et il est en fait à votre avantage de choisir la porte 3 au lieu de la porte 1. Voici pourquoi.

Lorsque vous avez choisi la porte 1 parmi les 3 portes fermées, vous aviez 1 chance sur 3 que vous ayez choisi la bonne. La porte 2 et la porte 3 ont également 1 chance sur 3 d'avoir une voiture derrière.

Une autre façon de penser est que les portes 2 et 3 ont 2 chances sur 3 d'avoir une voiture derrière elles combinées .

Mais lorsque l'hôte ouvre la porte 2 et révèle la chèvre, vous avez soudainement plus d'informations sur le problème.

Rappelez-vous que les portes 2 et 3 ont une probabilité combinée de cacher la voiture aux 2/3 du temps. Lorsque la porte 2 a été ouverte, vous savez qu'il n'y avait pas de voiture derrière.

Mais cette révélation ne change pas la probabilité combinée des deux portes. C'est la clé à emporter ici!

Puisque vous savez que la porte 2 a 0/3 de chances de cacher la voiture, vous pouvez maintenant dire qu'il y a 2/3 de chance que la voiture soit derrière la porte 3. La porte 1 reste inchangée - il n'y a qu'un tiers de la voiture. derrière.

Donc, si vous décidez de changer, vous passez d'environ 33,33% de chances à 66,67% de chances de trouver la voiture. En d'autres termes, vous doublez vos chances de succès en ouvrant la porte 3 à la place!

Oui, il est possible que la porte 1 se soit cachée depuis le début et que l'hôte vous ait trompé. Cela n'a pas d'importance. Vous jouez en acceptant l'accord, mais vous jouez intelligemment. Vous devez prendre la meilleure décision avec les informations qui vous sont données et laisser les dés lancer.

À long terme, vous feriez mieux en changeant qu'un concurrent qui décide de faire son premier choix. Bien que ce ne soit pas immédiatement évident, l'hôte vous rend en fait une faveur en vous offrant une meilleure offre.

Le problème des philosophes de la restauration

Le problème des philosophes de la restauration est un exemple classique en informatique pour illustrer les problèmes de synchronisation. Il a été créé à l'origine par Edsger Dijkstra en 1965, qui l'a présenté à ses étudiants comme une poignée d'ordinateurs en compétition pour l'accès aux lecteurs de bande partagés.

Imaginez cinq philosophes silencieux assis autour d'une table, chacun avec un bol de spaghetti. Il y a des fourchettes sur la table entre chaque paire de philosophes adjacents.

Chaque philosophe ne peut faire qu'une chose à la fois: penser et manger. Cependant, un philosophe ne peut manger des spaghettis que s'ils ont les fourchettes gauche et droite. Une fourchette ne peut être tenue que par un philosophe à la fois.

Une fois qu'un philosophe a fini de manger, il doit poser les fourchettes gauche et droite pour être à la disposition des autres. Un philosophe peut prendre une fourchette dès qu'elle est disponible, mais ne peut commencer à manger qu'une fois qu'il a les deux fourchettes.

Les philosophes sont réputés pour leur appétit - ils peuvent tous manger à l'infini et ne jamais se rassasier. En plus de cela, les bols de spaghettis se reconstituent comme par magie, quelle que soit la quantité consommée.

Le problème est le suivant: comment pouvez-vous vous assurer qu’aucun philosophe ne mourra de faim et qu’il pourra continuer à manger et à penser pour toujours?

Synchronisation et blocage

En termes simples, le problème des philosophes de la restauration est une illustration de la façon dont l'accès synchronisé à une ressource partagée peut entraîner la création d'une situation de blocage.

La synchronisation est utilisée pour contrôler l'accès simultané à une ressource partagée. Cela est nécessaire dans toute situation où plusieurs acteurs indépendants peuvent être en concurrence pour l'utilisation d'une seule ressource comme les fourches. Puisqu'il n'y a qu'une seule ressource disponible, nous utilisons la synchronisation pour éviter la confusion et le chaos.

Un blocage est un état du système où aucune progression n'est possible. Cette situation peut se produire lorsque la synchronisation est appliquée et de nombreux processus finissent par attendre une ressource partagée qui est détenue par un autre processus. Comme pour les philosophes qui sont coincés à manger ou à réfléchir, les processus ne font qu'attendre et ne s'exécutent plus.

Solutions

À première vue, il semble que ce ne serait pas possible pour une impasse où tous les philosophes sont coincés soit en train de manger, soit de réfléchir. Par exemple, le modèle à suivre pour chaque philosophe pourrait être:

1: pensez jusqu'à ce que la fourche gauche soit disponible; quand c'est le cas, prenez-le;

2: réfléchissez jusqu'à ce que la bonne fourche soit disponible; quand c'est le cas, prenez-le;

3: lorsque les deux fourchettes sont tenues, mangez pendant une durée déterminée;

4: puis, posez la fourche droite;

5: puis, abaissez la fourche gauche;

6: répéter depuis le début.

Source: Wikipédia

Il existe de nombreuses solutions possibles pour éviter les blocages. Si nous regardons de près, un problème dans l'algorithme ci-dessus est que tous les philosophes ont la même chance (ont la même priorité) d'acquérir une fourchette. Cela empêche quiconque d'acquérir deux fourches et tout le système s'arrête.

Voici quelques solutions possibles:

  1. Priorité : certains philosophes se voient attribuer une priorité plus élevée, de sorte que les chances d'acquérir les deux fourches sont augmentées.
  2. Préemption (politesse): les philosophes renoncent à la fourchette acquise sans manger, au cas où l'autre fourchette ne serait pas disponible.
  3. Arbitrage : un médiateur attribue des fourchettes en veillant à ce que deux fourchettes soient données à une personne, au lieu d'une à plusieurs.

Maintenant que vous savez comment résoudre ces énigmes logiques, offrez-vous un bol sans fin de spaghettis. Vous l'avez mérité.