Algorithme de dichotomie

Ce deuxième projet d'approximation numérique va te faire découvrir un algorithme beaucoup plus rapide que le balayage.

Souviens toi du jeu que tu as créé dans le tout premier projet, le juste prix. Quelle était la meilleure stratégie, c'est-à-dire la stratégie qui gagne en général le plus rapidement ?

Le mieux c'est de choisir le centre de l'intervalle. On doit tout d'abord choisir un nombre entre 0 et 100 donc on prend le centre qui est 50. Si ce nombre est trop petit, le nouvel intervalle de recherche est [50; 100]. On choisi ensuite le centre de cet intervalle, ici 75. On continue comme ça jusqu'à trouver le nombre.

Voici un exemple d'une partie utilisant cette stratégie :

Nombre choisi par le joueur	Réponse ordinateur	Nouvel interval
$\frac{0 + 100}{2}=50$	Trop petit	$[50; 100]$
$\frac{50 + 100}{2}=75$	Trop grand	$[50; 74]$
$\frac{50 + 74}{2}=62$	Trop petit	$[62; 74]$
$\frac{62 + 74}{2}=68$	C'est ça !

Cette stratégie est la plus rapide car à chaque étape l'intervalle de recherche est deux fois plus petit qu'à l'étape précédente. On passe ainsi de l'intervalle [0; 100] à l'intervalle [50; 100] etc.

La procédure à suivre consiste à calculer les bornes de l'intervalle de recherche (initialement 0 et 100), puis à déterminer le centre de cet intervalle, et répéter ces étapes si besoin. Cette procédure porte un nom : c'est l'algorithme de dichotomie

1
J'ai redéfini la fonction jeu du juste prix. Appelle-la dans la console et fais une partie en appliquant l'algorithme de dichotomie.
Solution

On appelle la fonction jeu et on suit la procédure décrite dans l'introduction : prendre le milieu de chaque nouvel intervalle de recherche
```
>>> jeu()
```
2
Je viens de définir la fonction f dans ton éditeur. Cette fonction renvoie le carré d'un nombre, et comme dans le projet précédent, nous allons déterminer une approximation de $\sqrt{2}$ . Par dichotomie cette fois !

L'algorithme repose sur la présence d'un intervalle dont on calcule le milieu. Comme on souhaite calculer une approximation de $\sqrt{2}$ on choisit un intervalle de départ qui contient ce nombre. Par exemple on peut prendre l'intervalle [1; 2]

En-dessous de la fonction f défini une variable a initialisée à 1 et une variable b initialisée à 2. Ces variables représentent les bornes de l'intervalle de départ dans lequel on recherche l'approximation.
Solution

On initialise a à 1 et b à 2
```
def f(x):
    return x**2

a = 1
b = 2
```
3
L'algorithme consiste à répéter successivement une même procédure : déterminer l'intervalle de recherche puis prendre son milieu. Il faut donc qu'on utilise une boucle. Comme on ne sait pas à l'avance combien d'étapes sont nécessaires, on utilise une boucle while.

Pour le moment écrivons uniquement le code correspondant à la première itération pour bien comprendre. On ajoutera la boucle while à la prochaine question :
1. On commence par calculer le milieu de l'intervalle [a; b].
  Crée une variable m et utilise la formule du milieu pour lui assigner comme valeur le centre de l'intervalle [a; b].
2. Ensuite il faut déterminer si m est trop petit ou trop grand et en déduire les nouvelles bornes de l'intervalle de recherche, c'est-à-dire les nouvelles valeurs de a et b.
  Si f(m) < 2 alors m est trop petit puisque son carré (le nombre f(m)) est inférieur à 2. Dans ce cas, l'intervalle de recherche peut être réduit à [m; b]. Donc il faut réassigner la variable a pour qu'elle prenne la même valeur que m en faisant a = m
  
  Ajoute une instruction conditionnelle qui détermine si m est trop petit, puis réassigne les bornes de l'intervalle de recherche en conséquence. De même si m est trop grand (il faut adapter).
Solution

On commence par créer la variable m. C'est le milieu de l'intervalle [a;b] donc m vaut 1.5 mais l'idée est d'avoir une formule, car dans la question suivante, la valeur de m sera calculée automatiquement à chaque itération.

Donc on utilise la formule du milieu m = (a+b)/2

Ensuite l'instruction conditionnelle nous indique si m est trop petit ou trop grand, ce qui permet de déterminer le nouvel intervalle de recherche

On utilise la comparaison f(m)<2 pour savoir si m est trop petit. Dans ce cas le nouvel intervalle de recherche est [m ; b]. Donc on réassigne a en faisant a = m

Sinon, m est trop grand. Alors le nouvel intervalle de recherche est [a;m] et il faut réassigner b en faisant b = m
```
def f(x):
    return x**2

a = 1
b = 2

m = (a+b)/2
if f(m) < 2:
    a = m
else:
    b = m
```
4
Nous allons répéter la procédure de la question précédente à chaque itération de l'algorithme. Ainsi, à chaque itération on obtient une nouvelle valeur de m un peu plus proche du nombre cherché. À la fin du processus, la dernière valeur de m obtenue est notre approximation.

Nous allons créer une fonction dont le paramètre correspond à la précision de l'approximation recherchée. Ce paramètre va servir pour la condition d'arrêt : tant que l'écart entre a et b est supérieur à la précision voulue, c'est que l'intervalle de recherche n'est pas assez fin. Donc on fait une itération supplémentaire.

Défini une fonction dichotomie qui dépend d'un argument, le pas. Le corps de cette fonction reprend le code des questions précédentes que tu peux indenter : initialisation de a et b puis instruction conditionnelle. Enfin indente ton instruction conditionnelle et le calcul de m dans le corps d'une boucle while : tant que l'écart entre a et b est supérieur au pas (condition d'arrêt), alors calcule le milieu m puis réassigne les bornes de l'intervalle. N'oublie pas de renvoyer m à la fin.
Solution

On commence par définir la fonction dichotomie qui dépend d'un argument, le pas.

On indente le code des questions précédentes dans le corps de cette fonction : l'initialisation de a, de b etc.

Ensuite on crée une boucle while. Celle-ci s'exécute tant que l'écart entre a et b est supérieur au pas, donc tant que l'intervalle de recherche est plus large que la précision voulue. Ainsi la condition d'arrêt est b-a > pas

Le corps de la boucle while reprend les étapes de la question précédente : calculer le milieu m de l'intervalle puis déterminer si m est trop petit ou trop grand avec une instruction conditionnelle. On reprend le code de la question précédente.

À la fin de la fonction on renvoie m
```
def f(x):
    return x**2

def dichotomie(pas):
    a = 1
    b = 2

    while b-a > pas:
        m = (a+b)/2
        if f(m) < 2:
            a = m
        else:
            b = m

    return m
```
5
Appelle la fonction dichotomie dans la console avec différentes valeurs du pas (10**-1, 10**-2 etc.) pour obtenir des approximations de plus en plus précises de $\sqrt{2}$
Solution

Lorsque le pas diminue les approximations sont de plus en plus précises.
```
>>> dichotomie(10**-1)
1.4375
>>> dichotomie(10**-2)
1.4140625
>>> dichotomie(10**-3)
1.4150390625
```
6
Pour comparer la vitesse de calcul de la fonction dichotomie avec la fonction balayage du précédent projet, nous allons ajouter un compteur.

Dans le corps de la fonction dichotomie, initialise une variable compteur avant la boucle while avec une valeur de départ de 0. À chaque itération de la boucle while, incrémente ce compteur de 1. Enfin renvoie la valeur du compteur avec l'approximation. Rappel : tu peux renvoyer plusieurs valeurs en les séparant par une virgule. Renvoie le compteur en deuxième.
Solution

On initialise la variable compteur à 0 avant la boucle while. Ensuite on incrémente ce compteur de 1 à chaque itération de la boucle. Enfin on renvoie le compteur avec l'approximation m
```
def f(x):
    return x**2

def dichotomie(pas):
    a = 1
    b = 2
    compteur = 0
    while b-a > pas:
        compteur = compteur + 1
        m = (a+b)/2
        if f(m) < 2:
            a = m
        else:
            b = m

    return m, compteur
```
7
Dans le projet précédent, la fonction balayage avait besoin de 414214 calculs pour trouver une approximation de $\sqrt{2}$ à $10^{-6}$ près.
```
>>> balayage(10**-6)
1.414213999965924,414214
```
Qu'en est-il de la fonction dichotomie ? Appelle-la dans la console pour voir !
Solution

La fonction dichotomie a besoin de beaucoup moins de calculs que la fonction balayage : seulement 20 itérations pour une approximation à $10^{-6}$ , 34 itérations pour une approximations à $10^{-10}$ et 50 itérations pour un pas de $10^{-15}$ !
```
>>> dichotomie(10**-6)
1.4142141342163086,20
>>> dichotomie(10**-10)
1.4142135623260401,34
>>> dichotomie(10**-15)
1.414213562373095,50
```

Bonus : comme dans le précédent projet tu peux adapter ton code pour déterminer d'autres approximations.

Par exemple tu peux modifier le code de la fonction f pour calculer des approximations numériques de $\sqrt[3]{2}$ . Vérifie quand même s'il ne faut pas ajuster l'initialisation des variables a et b sinon tu risques une boucle infinie.

En terme de complexité, l'algorithme de dichotomie fait partie de la famille des algorithmes les plus rapides possibles. C'est un incontournable !