π
<-
Chat plein-écran
[^]

Python_m_dichol


File hierarchy

 Downloads
 Files created online(37439)
 HP-Prime(10822)

 mViewer GX Creator App(9947)

DownloadTélécharger


LicenceLicense : Non spécifiée / IncluseUnspecified / Included

 TéléchargerDownload

Actions



Vote :

ScreenshotAperçu


Informations

Catégorie :Category: mViewer GX Creator App HP-Prime
Auteur Author: zidane13ES
Type : Application
Page(s) : 12
Taille Size: 537.49 Ko KB
Mis en ligne Uploaded: 29/06/2020 - 00:14:54
Uploadeur Uploader: zidane13ES (Profil)
Téléchargements Downloads: 24
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a2632716

Description 

Professeur B. Articles IPT Sup IPT Spé




articles / dichoto



Recherche dichotomique dans
une liste triée
Où l'on fait une recherche efficace, et l'on prouve que ce que l'on fait est correct…

IPT Sup NSI 1ère Algo




Dans cet article, nous nous intéressons à l'algorithme de recherche dichotomique dans une liste triée.
Nous présentons l'algorithme de base, quelques variantes en comparant leurs vitesses, et parlons preuve
de programme.



Présentation de l'algorithme
L'idée de base est simple :

On dispose d'un tableau t trié de valeurs, et on cherche à déterminer si une valeur v est présente
dans le tableau.
Pour cela, on procède par dichotomie :
On regarde l'élément du milieu du tableau et on le compare à v .
S'ils sont égaux, on a gagné, sinon, on poursuit la recherche dans la première ou la second
moitié du tableau.
Si à la fin, on a réduit la portion du tableau au point qu'il ne contient plus aucun élément, la
recherche s'arrête sur un echec : v n'est pas présent dans t .

Illustrons cela :



22




3 7 11 17 18 19 24 26 30 32 38 39
1 2 3 4 5 6 7 8 9 10 11 12



Nouvelles valeurs Rechercher

Voilà pour la théorie, passons à la pratique. Et là, cela se complique. C'est un problème connu que cet
algorithme est délicat à programmer sans erreur (voir la page Wikipedia en anglais à ce sujet et plus
particulièrement là).


Although the basic idea of binary search is comparatively straightforward, the details can be
surprisingly tricky, and many good programmers have done it wrong the first few times they
tried.
— D. E. Knuth, The Art of Computer Programming
Pour bien comprendre le comportement de l'algorithme et donc le programmer correctement, il est
indispensable d'avoir au moins une petite idée de la correction et de la terminaison de l'algorithme. Pour
le premier, la notion d'invariant de boucle permet de formaliser cela.


Invariants de boucle, petit rappel
Exposons brièvement quelques idées sur les invariants de boucle. On peut les voir comme la version
« preuve de programmes » de l'hypothèse de récurrence. Dans une démonstration par récurrence, on a
typiquement une hypothèse de récurrence Pn que l'on utilise dans deux étapes :

lors de l'initialisation, pour montrer qu'à un certain rang n0 de départ, l'hypothèse de récurrence est
bien vérifiée,
lors de l'hérédité, pour montrer que que si l'hypothèse de récurrence est vrai à un certain rang n
(supérieur ou égal à n0 ), elle est aussi vraie au rang suivant n + 1 :

Pn ⟹ Pn+1

On peut alors en déduire que l'hypothèse de récurrence est vrai pour tout rang supérieur à n0 :

∀ n ≥ n0 , Pn

Un invariant de boucle procède de la même idée :

Si une propriété est vrai en entrant dans une boucle,
et si elle est préservée par le corps de la boucle (autrement dit si elle est vérifiée au début, elle l'est
encore après exécution du corps de la boucle),

alors elle vérifiée à chaque entrée de boucle… et aussi en sortant de la boucle (on parle ici d'une boucle
while ).
La version classique de l'algorithme
On peut écrire l'algorithme ainsi :


def dichotomie(t, v):
a = 0
b = len(t) - 1
while a <= b:
m = (a + b) // 2
if t[m] == v:
# on a trouvé v
return True
elif t[m] < v:
a = m + 1
else:
b = m - 1
# on a a > b
return False


Les variables a et b représentent les bornes entre lesquels on recherche v dans t . Autrement dit,
avec les notations de Python, on cherche v dans t[a:b + 1] . Comment exprimer cela proprement en
termes d'invariants ?


Preuve de correction
Ici, notre invariant est :

v ∈ t ⟹ v ∈ t[a : b + 1]

Autrement dit, si v est présente dans t , alors c'est nécessairement entre les indices a et b (inclus).
Pour prouver qu'il s'agit bien d'un invariant de boucle, on va supposer que notre propriété est vérifiée au
début du corps de la boucle, et on va prouver que c'est encore le cas à la fin.

Après avoir défini m , examinons les tests successifs. Tout d'abord, si l'on a bien t[m] == v , alors on
renvoie True ce qui est correct, ayant effectivement m dans t . Dans ce cas, l'invariant ne sert à rien
puisque l'on a effectivement trouvé l'élément recherché.

Maintenant, deux cas sont possibles :

si t[m] < v , puisque t est trié, la valeur v ne peut pas être présente dans t[a:m + 1] . Ainsi,
si v in t[a:b + 1] , alors nécessairement v in t[m + 1:b + 1] . Ainsi, en posant a = m +
1 , on a v in t[a:b + 1] .
Sinon, sachant de plus que t[m] != v , cela signifie que t[m] > v et donc que si v in t[a:b
+ 1] , alors v in t[a:m] . Ainsi, en posant b = m - 1 , on a v in t[a:b + 1] .

Dans tous les cas, à la fin de l'exécution de la boucle (si l'on y est toujours), la propriété

v ∈ t ⟹ v ∈ t[a : b + 1]

est encore vérifiée. C'est donc bien un invariant de la boucle.

Ce que l'on vient de prouver correspond à la phase d'hérédité d'une démonstration par récurrence. Pour
terminer ce type de démonstration, il faut aussi une phase d'initialisation. Ainsi, si notre hypothèse de
récurrence est vérifiée pour un certain rang, et qu'elle est préservée en passant d'un rang au suivant,
alors elle est vérifiée pour tous les rangs suivants.

De même, vérifions que notre invariant est vérifié avant d'entrer dans la boucle. À ce moment, on a a ==
0 et b == len(t) - 1 et donc t[a:b + 1] == t[0:len(t)] == t . Notre invariant correspond
alors à la tautologie

v ∈ t ⟹ v ∈ t,

il est donc bien vérifié.
Pour résumer, notre propriété est vérifiée en entrée de boucle et c'est un invariant de la boucle. En
conséquent, elle reste vérifiée en sortant de la boucle (quelque soit le nombre d'itérations effectué). De
plus, à ce moment, on a a > b et donc t[a:b + 1] = [] et on peut donc affirmer que v in t =>
v in [] .

Comme v in [] est nécessairement faux, puisque la liste vide ne contient aucune valeur, on en déduit
que v not in t : on peut conclure qu'en sortie de boucle, v n'est pas présent dans la liste.

Comme annoncé précédemment, notre invariant de boucle ne sert pas à montrer la correction en cas de
succés (puisque l'on a effectivement trouvé un indice m tel que t[m] == v ) mais en cas d'échec : bien
que l'on n'a pas inspecté toutes les valeurs de t , on a prouvé que v n'est pas présent dans t . On a
cherché aux bons endroits et puisque l'on n'a pas trouvé cette valeur, cela signifie qu'elle n'y est pas.


Terminaison
Insistons sur le fait que la présence d'un invariant de boucle ne présume en rien de la terminaison de
l'algorithme ; il ne prouve pas que l'on va sortir de la boucle. Par contre, si l'on sort de la boucle, alors le
résultat est correct.

Pour la terminaison, prouvons que si au début d'une itération, a et b sont tels que b − a ≤ 2n − 2
pour un certain entier n, alors à la fin de l'itération, on a

b − a ≤ 2n−1 − 2

En effet, on a

b−a b−a
m−a=⌊ ⌋ et b−m=⌈ ⌉
2 2
et, par croissance de ⌊⋅ ⌋ et ⌈ ⋅ ⌉, si b − a ≤ 2n − 2, alors m − a et b − m sont tous les deux
inférieurs ou égaux à 2n−1 − 1. Ainsi, dans tous les cas, après l'affectation a = m + 1 ou b = m -
1 , on a bien
1
b − a ≤ 2n−1 − 2

L'exposant de 2 dans la majoration décroit donc de 1 à chaque itération, etaprès un nombre
suffisamment grand d'itérations, l'écart b - a va donc devenir négatif, ce qui est incompatible avec la
condition de boucle b >= a .

Ainsi, on est sûr de sortir de la boucle, l'algorithme termine.


Analyse de complexité
La preuve précédente de terminaison nous permet de déterminer la complexité au pire des cas de
l'algorithme. En effet, le corps de la boucle est en O(1) et si ℓ − 1 ≤ 2n − 2 (avec ℓ la longueur de t ),
alors on effectue au maximum n itérations successives avec

n = ⌈log2 (ℓ + 1)⌉ = ⌊log2 (ℓ) + 1⌋

La complexité au pire des cas est donc en O(log2 ℓ).



Une autre version
Dans la version « classique » de l'algorithme, on effectue deux tests par itération, puisque l'on effectue le
test d'égalité à chaque fois. On peut accélerer l'algorithme en ne faisant qu'un unique test d'égalité, en
sortie de boucle. Elle décrite ici et peut s'écrire ainsi en Python (avec un peu de refactoring, puisque la
variable a correspond à L du code original tandis que b correspond à R + 1 ) :


def dicho2(t, v):
a = 0
b = len(t)
if b == 0:
# il faut traîter le cas
# où la liste est vide
return False
while b > a + 1:
m = (a + b) // 2
...

Archive contentsContenu de l'archive

Action(s) SizeTaille FileFichier
3.06 Ko KB readme.txt
3.65 Ko KB lisezmoi.txt
1.09 Ko KB Python_m.hpprgm
534.69 Ko KB Python_m.hpappdir.zip
95 octets bytes appslist.txt

Pub / Ads

-
Search
-
Social TI-Planet
-
Featured topics
"1 calculatrice pour tous", le programme solidaire de Texas Instruments. Reçois gratuitement et sans aucune obligation d'achat, 5 calculatrices couleur programmables en Python à donner aux élèves les plus nécessiteux de ton lycée. Tu peux recevoir au choix 5 TI-82 Advanced Edition Python ou bien 5 TI-83 Premium CE Edition Python.
Enseignant(e), reçois gratuitement 1 exemplaire de test de la TI-82 Advanced Edition Python. À demander d'ici le 31 décembre 2024.
Offre de test des nouveautés de rentrée 2024 par Casio. Enseignant(e), reçois gratuitement 1 exemplaire, à ton choix, de la Graph Light ou bien de la Graph Math+
14€ remboursés par Casio sur l'achat de ta calculatrice Graph 35 d'ici le 31 Octobre 2024
10€ remboursés par Casio sur l'achat de ta calculatrice Graph 90+E d'ici le 31 Décembre 2024
10€ remboursés par Casio sur l'achat de ta calculatrice Graph 25 d'ici le 31 Décembre 2024
8€ remboursés par Casio sur l'achat de ta calculatrice Graph Math+ d'ici le 31 Octobre 2024
Reprise de ton ancienne fx-92 Collège ou Graph 25/35/90 à 3€ peu importe son état. Même non fonctionnelle et donc invendable, même ancienne Graph 35 non conforme aux programmes (pas de Python), même ancienne Graph 25/35 inutilisable aux examens (pas de mode examen) et donc invendable. Etiquette de retour fournie, pas de frais de port à payer.
3€ remboursés par Casio sur l'achat de ta calculatrice fx-92 Collège d'ici le 30 Septembre 2024
5€ de remise immédiate sur l'achat de ta calculatrice TI-83 Premium CE Edition Python chez les revendeurs partenaires
4€ de remise immédiate sur l'achat de ta calculatrice TI-82 Advanced Edition Python chez les revendeurs partenaires
3€ de remise immédiate sur l'achat de ta calculatrice TI-82 Advanced chez les revendeurs partenaires
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
1234567891011121314
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1619 utilisateurs:
>1569 invités
>45 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)