Nous allons maintenant voir ce qu'est l'algorithmique.
Après avoir vu cette partie en 1er, vous pourrez répondre à ces questions
Un algorithme est un ensemble fini (au sens dénombrable) d'instructions précises permettant de résoudre une classe de problèmes.
L'algorithme doit être écrit sans ambiguïté, et être facilement transposable dans n'importe quel langage de programmation.
Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.
Une manière de calculer 5 x 4 n'est pas un algorithme.
Par contre, une façon de calculer a x b pourrait être vue comme un algorithme.
De façon plus précise, un algorithme fournit une SORTIE en fonction des données fournies en ENTREE.
ENTREE(S) → Algorithme → SORTIE
Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.
On sépare réflexion et exécution.
La réflexion est utilisée par l'informaticien lors de la création de l'algorithme.
Lors du déroulement, l'ordinateur exécute.
C'est tout.
L'algorithmique consiste à étudier des problèmes en vue de les résoudre à l'aide d'un algorithme le plus efficace possible.
On cherche donc :
Certains pensent que l'un des algorithmes les plus anciens est l'algorithme d'Euclide.
Cet algorithme permet de trouver le plus grand diviseur commun (PGDC) de deux entiers a et b.
Par exemple, pour a = 15 et b = 20, il s'agit de 5.
En effet,
Cet algorithme date de -300 et se trouve dans les écrits du mathématicien Euclide d'Alexandrie.
Il a été découvert de façon autonome en Inde et en Chine quelques siècles plus tard.
Vers 800, WMuhammad Ibn Mūsā al-Khuwārizmī dit Al-Khwarizmi, mathématicien, né dans dans l'actuel Ouzbékistan et mort à Badgad, publie de nombreux textes.
Son nom est bien entendu à l'orgine d'algorithme.
Depuis, bien des gens ont travaillé et travaillent toujours pour trouver, créer ou améliorer les algorithmes.
L'un des grands noms de l'algorithmie est Donald Knuth, informaticien et mathématicien américain de renom.
Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique (fondements logiques et mathématiques de l'informatique).
Pour en savoir plus sur son oeuvre
The Art of Computer Programming
Beaucoup. Il existe notamment une catégorie entière de problèmes dits NP-complets qui posent problème.
L'exemple typique de ce type de problème est le problème du voyageur de commerce : un commercial doit passer par toutes les villes de son secteur.
Il cherche à optimer son parcours de façon à ce qu'il prenne le moins de temps possible.
Comment trouver la solution optimale ?
Avec 15 villes, on peut énumérer tous les cas possibles et prendre le meilleur.
Mais avec 20 000 villes à parcourir, on obtient un temps de calcul beaucoup trop grand pour être exploitable : les tracés routiers risquent d'avoir changé entre temps !
Les propriétés de ces problèmes complexes ?
L'algorithmique est donc un domaine d'études très riche en recherches passées et futures.
Si vous aimez les maths, l'informatique et les casses-têtes, c'est un domaine fait pour vous !
On souhaite écrire une fonction recherche(element,liste) en Python qui renvoie True ou False suivant que element se trouve ou non dans liste.
On donne ci-dessous la réponse d'un élève :
1
2
3
4
5
6
7
8 | |
recherche(3,[3,10,7]) et recherche(4,[3,10,7]) renvoient les valeurs attendues.False si le premier élément testé est différent de celui recherché comme indiqué dans le commentaire ligne 4 ?...CORRECTION...
1
2
3
4
5
6 | |
Nous allons maintenant tenter de réaliser un algorithme qui signale si un élément existe dans un tableau (et renvoie son index) ou renvoie -1 (ou renvoie VIDE) sinon.
Nous allons utiliser une BOUCLE NON BORNEE
Cette méthode se nomme également méthode par balayage ou recherche linéaire.
En anglais, on parle de linear search.
Vous allez comprendre tout de suite pourquoi en utilisant l'animation suivante : créer un tableau avec l'un des boutons aléatoires, choisir une valeur à chercher et appuyer sur le bouton lançant l'animation.
Valeur cherchée :
| ↓ | ||||||||||||||||||||
| Indice i | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
BUT : trouver la position de la première occurrence de l'élément x recherché dans un tableau t.
PRINCIPE (en 4 étapes) :
Prenons t = [13, 18, 89, 1024, 45, -12, 18]
| Indice i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Case t[i] | 13 | 18 | 89 | 1024 | 45 | -12 | 18 |
Voici trois exemples de réponses attendues :
Recherche de 89 (présent une fois) :
| t = [13, 18, 89, 1024, 45, -12, 18] | ⇒ | RECHERCHER | ⇒ | |
| et | 2 | |||
| x = 89 |
Recherche de 18 (présent deux fois) :
| t = [13, 18, 89, 1024, 45, -12, 18] | ⇒ | RECHERCHER | ⇒ | |
| et | 1 | |||
| x = 18 |
Recherche de 100 (non présent) :
| t = [13, 18, 89, 1024, 45, -12, 18] | ⇒ | RECHERCHER | ⇒ | |
| et | -1 | |||
| x = 100 |
But : trouver si un élément recherché existe bien dans un tableau. S'il existe, on fournit l'index de la première occurence trouvée. Sinon, il renvoie une réponse vide.
Principe : lecture séquentielle et progressive des différents éléments. On renvoie l'index du premier élément qui correspond. VIDE si aucun des éléments n'a correspondu à la recherche.
Avec une réponse -1 en cas de valeur non trouvée.
i ← 0
reponse ← -1
TANT QUE i < longueur du tableau ET que t[i] est différent de x
i ← i + 1
Fin TANT QUE
SI i < longueur
reponse ← i
Fin Si
Renvoyer reponse
01 Appliquer l'algorithme à la main avec une recherche sur 1024.
Vous devriez trouver qu'il renvoie 3.
Quelle est la condition qui provoque l'arrêt du TANT QUE : la valeur de la variable index ou le contenu qui correspond à la valeur voulue ?
...CORRECTION...
t ← [13, 18, 89, 1024, 45, -12, 18]
x ← 1024
longueur ← 7
i ← 0
Début du TANT QUE car 0 est inférieur à longueur et t[0] vaut 13 ce qui est différent de 1024
Du coup, i ← 1
Suite du TANT QUE car 1 est inférieur à longueur et t[1] vaut 18 ce qui est différent de 1024
Du coup, i ← 2
Suite du TANT QUE car 2 est inférieur à longueur et t[2] vaut 89 ce qui est différent de 1024
Du coup, i ← 3
Arrêt du TANT QUE car t[3] vaut 1024 !
Evaluation de la condition du SI : i (valant 3) est inférieur à longueur est évaluée à VRAI.
On renvoie 3
02 Appliquer l'algorithme à la main avec une recherche sur 1025.
Vous devriez montrer qu'il renvoie VIDE.
Quelle est la condition qui provoque l'arrêt du TANT QUE : la valeur de la variable index ou le contenu qui correspond à la valeur voulue ?
...CORRECTION...
t ← [13, 18, 89, 1025, 45, -12, 18]
x ← 1025
longueur ← 7
i ← 0
Début du TANT QUE car 0 est inférieur à longueur et t[0] vaut 13 ce qui est différent de 1025
Du coup, i ← 1
Suite du TANT QUE car 1 est inférieur à longueur et t[1] vaut 18 ce qui est différent de 1025
Du coup, i ← 2
Suite du TANT QUE car 2 est inférieur à longueur et t[2] vaut 89 ce qui est différent de 1025
Du coup, i ← 3
Suite du TANT QUE car 3 est inférieur à longueur et t[3] vaut 89 ce qui est différent de 1025
Du coup, i ← 4
Suite du TANT QUE car 4 est inférieur à longueur et t[4] vaut 45 ce qui est différent de 1025
Du coup, i ← 5
Suite du TANT QUE car 5 est inférieur à longueur et t[5] vaut -12 ce qui est différent de 1025
Du coup, i ← 6
Suite du TANT QUE car 6 est inférieur à longueur et t[6] vaut 18 ce qui est différent de 1025
Du coup, i ← 7
Arrêt du TANT QUE car i vaut 7, ce qui n'est pas inférieur strictement à longueur !
Condition du SI non validée : i (valant 7) inférieur à longueur est évaluée à FAUX.
On renvoie VIDE
03 18 apparaît deux fois dans le tableau. La valeur renvoyée par cet algorithme sur une recherche sur 18 donne :
Rappel du contenu
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Elément | 13 | 18 | 89 | 1024 | 45 | -12 | 18 |
...CORRECTION...
On lit le contenu progressivement de façon séquentielle.
En lisant l'algorithme, on voit qu'on renvoie la première occurence trouvée, soit 1.
04 ✎° Compléter la fonction Python rechercher() fournie pour qu'elle fasse correctement le travail demandé.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | def rechercher(t:list, x:'Element') -> int:
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
i = ...
reponse = ...
longueur = ...
while i < ... and ...:
i = ...
if i < ...:
reponse = ...
return ...
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | def rechercher(t:list, x:'Element') -> int:
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
i = 0
reponse = -1
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
return reponse
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)
|
Attention à l'une des erreurs typiques lors de l'utilisation d'une boucle non bornée TANT QUE : le fait d'oublier de donner une valeur par défaut permettant de rentrer dans la boucle à la variable qui gère la boucle.
4
5
6
7
8 | i = 0
reponse = -1
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
|
On voit bien que les lignes 4 et 6 permettent de rentrer une première fois dans la boucle.
Sans ces lignes, ça ne peut pas fonctionner.
Conclusion : Ne négligez pas cette phase d'initialisation.
Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme de recherche sequentiel
On remarquera que puisqu'il s'agit de lire les éléments sans savoir à l'avance où s'arrêter, on utilise une boucle non bornée TANT QUE.
On peut alors l'implémenter de différentes façons en fonction du langage utilisé.
On fera donc bien la différence entre l'algorithme qui impose de faire une boucle non bornée et l'implémentation de cet algorithme en Python qui permet :
1
2
3
4
5
6
7
8 | def rechercher(t, x):
i = 0
reponse = -1
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
return reponse
|
On peut faire plus simple en Python en profitant des boucles FOR et du fait qu'on sorte immédiatement des fonctions dès qu'on rencontre un return.
De l'extérieur, ça ne change rien : seul le code interne est différent.
1
2
3
4
5
6
7 | def rechercher(t, x):
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent
for i in range( len(t) ):
if t[i] == x:
return i
return -1
|
1° Au niveau algorithmique, quelle est la version la plus rigoureuse : celle avec le while ou celle avec for + return ?
...CORRECTION...
Sur le principe de la recherche, on doit interrompre la recherche dès qu'on trouve le bon élément. Il s'agit donc d'une boucle non bornée.
Donc, le while est le plus adapté.
2° Au niveau programmation, quelle est la version la plus lisible : celle avec le while ou celle avec for + return ?
...CORRECTION...
Cette fois, la version avec le for est plus lisible : pas besoin de noter l'initialisation, l'incrémentation et de tester s'il reste encore une case ou non.
Activité publiée le 12 02 2021
Modifié le : 31 03 2026
Auteur : Andjekel
Source : Infoforall - ows. h.