COURS/TP6 : dichotomie et applications

Introduction

Un problème courant en informatique est de trouver un élément vérifiant une certaine propriété. Par exemples, au Mastermind on cherche la bonne liste de couleurs, Akinator cherche le personnage auquel vous pensez, en mathématiques on peut chercher une approximation d'une racine d'un polynôme. Une manière de résoudre ces différents problèmes consiste à procéder par dichotomie. On décrit l'algorithme de dichotomie, qui permet de résoudre un certain nombre de problèmes informatiques.

Description générale

Le principe est le suivant : on recherche un élément $a$ d'un ensemble $E$ vérifiant une propriété $P$ et on dispose de la possibilité de choisir un élément quelconque $b$ de $E$ et de poser une question $Q$ sur $b$. Suivant la réponse, on sait que $a$ appartient à un sous-ensemble strict $F$ de $E$ ou bien à son complémentaire.

Exemples

Recherche d'un élément dans un tableau trié

On aimerait savoir si un élément $a$ appartient à un tableau $T$ qui est trié dans l'ordre croissant. On commence par comparer $a$ avec l'élément médian $b$ du tableau. Si $a<b$, on sait que $a$ est nécessairement dans la première partie du tableau, sinon $a$ est nécessairement dans la deuxième partie du tableau. On recommence le raisonnement précédent jusqu'à trouver $a$, ou jusqu'à ce qu'on peut affirmer que $a$ n'est pas un élément du tableau.

Un exemple typique qui peut se comprendre comme la recherche d'un élément dans un tableau trié correspond au jeu du "plus ou moins". Celui-ci se joue à deux : une personne $A$ pense à un nombre compris entre $0$ et $1000$ et l'autre $B$ doit essayer de trouver le nombre. À chaque tentative de $B$, la personne $A$ répond par "plus", "moins", ou "c'est le bon nombre".

Calcul d'un zéro d'une fonction f

On considère une fonction $f:[a,b]\rightarrow \mathbb{R}$ continue et strictment croissante sur le segment $[a,b]$ et vérifiant $f(a)<0$, $f(b)>0$. On cherche une valeur $c$ vérifiant $f(c)=0$. D'après le corollaire du théorème des valeurs intermédiaires, on sait que $c$ existe et est unique. En pratique, on obtient un encadrement $[\alpha,\beta]$ de la valeur $c$ et on peut choisir $[\alpha,\beta]$. Détaillons le procédé.On fixe $erreur>0$ qui est la longueur maximale de l'intervalle $[\alpha,\beta]$ recherché. Détaillons le procédé :

Recherche de la bonne combinaison au mastermind

On rappelle que le mastermind est un jeu à deux joueurs fonctionnant ainsi : le joueur $A$ construit une liste de couleurs de taille $6$ qu'il cache au joueur $B$. Le joueur $B$ propose une configuration. $A$ donne alors comme information le nombre de pions ayant la bonne couleur et bien placés ainsi que le nombre de pions ayant une bonne couleur et mal placés.

Une façon de résoudre de manière algorithmique est la suivante : on génère toutes les séquences possibles initialement qu'on stocke dans une liste. Ensuite, on propose une configuration choisie de manière aléatoire. Suivant la réponse obtenue, on élimine de la liste des séquences tout ce qui ne convient pas et on recommence jusqu'à trouver la bonne séquence.

Exercices

Exercice 1

Exercice 2

On cherche un encadrement d'une valeur $c$ vérifiant $c^3 = 3$.

Exercice 3

En vous inspirant de ce qui a été fait précédemment, trouver une approximation à $0.0001$ près de $\sqrt[7]{5}$.

Exercice 4

Pour tout $t\geq 0$ on définit la fonction $f_t:\mathbb{R} \to \mathbb{R}$ par : $$\forall x \in \mathbb{R}, f_t(x)=x^5 +tx-1$$

Exercice 5 (Pour les plus rapides)

On cherche à écrire un programme permettant de simuler un mastermind et de trouver une solution par une méthode de type dichotomie.

Compléter les différentes fonctions qui sont données dans le fichier mastermind.py.