Voila un petit jeu pour commencer : le nombre à deviner.
Un nombre aléatoire compris entre 1 et 100 est généré aléatoirement.
Vous devez le retrouver en moins de 10 essais.
1
2
3
4
5
6
7
8
9
10
11
1 Si on avait utilisé la recherche séquentielle, combien d'essais auraient été nécessaires dans le pire des cas ?
2. Combien d'essais faut-il ici en moyenne pour deviner le nombre ?
3. Quelle est la précondition que respectent ( forcément...) les nombres qui fait que la technique utilisée ici est plus efficace que de proposer séquentiellement des valeurs ?
3. Un algorithme de recherche plus subtil : la recherche par dichotomie
Cet algorithme, ainsi que le précédent ( recherche séquentielle ) font partie de la liste des algorithmes à connaître pour
l'épreuve pratique du BAC.
3.1. Principe
On va donc se servir, pour rechercher la présence d'une valeur dans un tableau, du fait que si celui-ci a été préalablement trié, on va pouvoir utiliser une méthode de recherche beaucoup plus efficace, la
recherche par dichotomie. Dichotomie veut dire littéralement "couper en deux".
L'idée est de couper le tableau en 2 parties; on se retrouve avec 2 sous-tableaux de taille identique ( à un élément près dans le cas où le nombre total d'éléments du tableau est impair,
mais ça ne change rien ).
On garde uniquement le sous-tableau qui peut contenir la valeur recherchée : comme les sous-tableaux sont aussi triés, ce n'est pas difficile à déterminer, il suffit de
comparer la valeur recherchée avec l'élément délimitant les deux sous-tableaux, c'est à dire l'élément au milieu du tableau.
On recommence le processus jusqu'au moment où l'on se retrouve avec un tableau contenant un seul élément : si l'élément unique de ce tableau n'est pas l'élément recherché,
l'algorithme renvoie FAUX, et VRAI sinon ( et éventuellement, l'indice dans le tableau de la valeur recherchée ).
indice
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
valeur
1
11
17
26
28
32
40
43
43
43
47
55
57
60
62
66
70
71
75
76
77
78
82
83
85
86
87
87
93
94
Valeur à rechercher : 37
Nombre d'étapes : 0
3.2. Algorithme
Voici l'algorithme de la recherche dichotomique; la précondition est que le tableau est trié :
tant que le tableau n'est pas réduit à un seul ou deux élément(s) :
si la valeur est égale à l'élément au milieu du tableau :
alors on a trouvé la valeur, on renvoie VRAI et l'indice de la valeur
sinon :
si la valeur est PLUS PETITE que l'élément au milieu :
alors elle se trouve forcément dans la partie GAUCHE du tableau : on recommence la recherche dans la partie GAUCHE du tableau
sinon si la valeur est PLUS GRANDE que l'élément au milieu :
alors elle se trouve forcément dans la partie DROITE du tableau : on recommence la recherche dans la partie DROITE du tableau
on a réduit le tableau à un seul élément, et on n'a pas trouvé la valeur : on renvoie donc FAUX
Avant de se lancer dans le code, il faut bien comprendre comme nous allons pouvoir coder ce qui apparaît dans l'algorithme dans les expressions "la partie GAUCHE du tableau" et "la partie DROITE
du tableau".
Pour cela nous allons utiliser des variables g, m, d, désignant les extrémités gauche et droite du tableau courant et m son milieu.
Les trois variables g ( = gauche ), m ( = milieu ) et d ( = droite ) servent à "délimiter" les deux sous-tableaux :
g = indice du premier élément
d = indice du dernier élément
m = indice de l'élément au milieu
Dans l'image ci-dessous vous pourrez comprendre l'évolution des valeurs des variables g, m et d pour la recherche du nombre 16 dans le tableau fourni.
Compléter le tableau ci-dessus pour la recherche de la valeur 89 dans le tableau.
quelle condition sur les variables g et d est vérifiée "tant que le tableau n'est pas réduit à un seul ou deux élément(s)" ?
comment est calculée la valeur de m à partir de celle de g et d ?
lorsque la recherche doit se poursuivre ensuite sur "la partie GAUCHE du tableau", quelle variable faut-il modifier, et comment ?
mêmes questions pour la recherche sur "la partie DROITE du tableau"
On peut améliorer l'algorithme en modifiant légèrement les conditions précédentes :comment ? ( se poser la question : est-il indispensable de "garder" l'élément d'indice m dans
l'étape de recherche suivante ? )
écrire ensuite en pseudo-code l'algorithme complet de la recherche dichotomique.
On a déjà parlé de complexité d'un algorithme quand on a travaillé sur la recherche "naïve" dans un tableau non trié ( Rappel : c'est O(n) ).
Nous allons essayer de trouver la complexité de l'algorithme par dichotomie
Il faut donc trouver le nombre d'étape nécessaires pour trouver un élément par dichotomie dans le pire des cas.
Ce que l'on cherche ici c'est le nombre d'étapes maximum pour gagner au jeu "deviner un nombre" en jouant "par dichotomie" (si on commence à jouer au hasard ).
SUR PAPIER, compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 10
SUR PAPIER, compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 20
SUR PAPIER, compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 100
Mais on cherche une relation générale pour une partie de jeu avec un nombre compris entre 1 et n... La technique est donc de compter combien de fois il faut diviser par 2
le nombre n pour arriver à 1.
C'est assez simple quand on travaille avec des puissances de deux :
Compter combien de fois il faut diviser par 2 le nombre 1024 pour arriver à 1
Compter combien de fois il faut diviser par 2 le nombre 2048 pour arriver à 1
Compter combien de fois il faut diviser par 2 le nombre 4096 pour arriver à 1
Bon ça commence à être un peu long tout ces tâtonnements !
Heureusement il existe une fonction mathématique qui fait ce calcul à notre place : c'est le logarithme de base deux.
Pour le trouver sur votre calculatrice Numworks, c'est très simple :
Appuyez sur la touche toolbox puis choisissez la troisième possibilité dans le menu ( pour les autres calculatrices appelez le professeur ).
La complexité de la recherche dichotomique dans un tableau trié de n éléments est en O(log2(n)).
Vous pouvez simplement retenir que le logarithme en base 2 de n est le nombre de fois qu'il faut diviser n par 2 pour obtenir 1.
Conséquence : quand le nombre de données double, l'algorithme ne nécessite qu'une seule étape de plus; quand il est quadruplé, 2 étapes de plus, etc...
Cette notion est très importante, nous la retrouverons lors du tri de liste ou de l'étude des arbres binaires en terminale.
Et cette complexité est bien meilleure que celle de l'algorithme naïf, comme vous pouvez le voir ci-dessous :
Comme toujours quand on parle de complexité, la différence entre les deux algorithmes apparaît pour de grandes valeurs de n.
4. Mission fiscale : comparaison des méthodes de recherche
Aujourd’hui nous faisons partie de l'équipe de codeurs du ministère des finances qui lutte contre l'évasion fiscale.
Notre objectif :
Être capables de retrouver rapidement des numéros de compte ou des sommes précises dans des listings dont le volume peut quelquefois dépasser le Teraoctet !.
Pour cela nous allons, en amont de ces recherches, tester différentes techniques de recherche d'élément dans un tableau.
4.1. Le "pack" dont vous disposez
Vous pouvez télécharger ici un pack de fichiers.
Vous trouverez dans ce pack :
Un fichier python tests_recherche.py contenant des fonctions qui vous permettront de mener à bien votre recherche.
6 fichiers de 80 octets à 8Mo contenant des entiers triés par ordre croissant, pris entre 1 000 000 et 10 000 000.
4.2. Le travail à réaliser
Grâce à ce pack et à vos connaissances (et à votre travail de la semaine dernière !), vous devez rédiger un rapport sous open office présentant les différentes performances des trois fonctions de recherche :
La recherche naïve
La recherche par dichotomie
La recherche implémentée dans python
Vous devrez pour cela utiliser le module timeit dont vous pourrez trouver un exemple d'utilisation ici.
votre rapport devra contenir :
trois courbes présentées sur le même graphique montrant l'évolution de la durée de recherche d'un nombre non présentdans les fichiers en fonction de la taille du fichier.
Une prévision du temps d'exécution du même test pour un fichier de 80Mo pour chacune des fonctions testées.
Une conclusion quant au choix de la méthode de recherche à utiliser
En annexe : le code complet qui vous a permis de réaliser ce test.
