Algorithmes en Python : définition, types, fonctionnement

Qu'est-ce qu'un algorithme ?

Un algorithme est un ensemble d'instructions destiné à résoudre un problème donné. La notion d'algorithme est omniprésente dans la vie quotidienne. Les algorithmes sont utilisés dans un large panel de situations : recommander des livres à des clients, reconnaissance d'image 3D par comparaison…

Les origines de l'algorithme

Le terme algorithme provient du domaine des mathématiques et est tiré du nom d'un mathématicien persan Muhammad ibn Moussa Al-Khuwarizmi né en 780, plus communément appelé Al-Khwârismî. Ce savant est notamment l'auteur de L'Abrégé du calcul par la restauration et la comparaison, l'ouvrage qui marque la genèse de l'algèbre. L'algorithme d'Euclide est sans doute l'un des plus vieux algorithmes connus à ce jour.

‍

‍

L'algorithme informatique

L'informatique est sans doute le domaine de prédilection de l'algorithme. L'écriture des programmes informatiques se fait désormais sur ordinateur afin d'effectuer une tâche spécifique. Il exécute mécaniquement différentes instructions pour atteindre l'objectif souhaité par l'utilisateur. Pour lui communiquer ces instructions, il est nécessaire d'utiliser un langage de programmation informatique comme Python.

L'algorithme informatique intervient lorsqu'on indique à l'ordinateur comment il doit accomplir une tâche. En programmation, les possibilités d'écriture d'un algorithme pour résoudre un problème donné sont infinies. À chaque instant, ce sont les algorithmes présents dans le code des programmes qui permettent aux ordinateurs, aux smartphones de fonctionner en prenant des décisions. Ils assurent entre autres la saisie des données, le calcul et l'affichage des résultats…

En informatique, tous les algorithmes ne se ressemblent pas. Une catégorie d'algorithme très populaire actuellement est celle des algorithmes autoapprenants. Principalement utilisés dans le domaine de l'intelligence artificielle ou du Machine Learning, ces algorithmes sont capables d'apprendre et d'affiner leur précision au fil du temps. Ils sont notamment utilisés pour la prédiction du trafic routier ou l'analyse d'images médicales.

En informatique, un tableau est une liste ordonnée de n valeurs du même type. Cette dénomination n désigne la taille du tableau et les valeurs internes représentent ses éléments. Ceux-ci sont repérés dans le tableau par leur indice (entre 0 et n-1 le plus souvent). Chaque élément est ainsi caractérisé par un indice unique.

Exemple d'algorithme pour parcourir un tableau

Le code suivant représente un exemple d'algorithme de base pour parcourir un tableau :

1. Algorithme AfficheTableau (t : tableau)
2. {affiche tous les éléments d'un tableau}
3. Variable i : entier
4. Début
5. Pour i ← 1 à taille (t) faire
6. Écrire (t [i])
7. Fin Pour
8. Fin

Ce code est ainsi très utile en informatique. C'est une fonction qui peut s'apprendre dès le début.

Exemple d'algorithme pour rechercher les plus petits et grands éléments d'un tableau

Pour rechercher les plus petits et grands éléments d'un tableau, il faut effectuer l'algorithme suivant :

1. Algorithme Maximum (t : tableau d'entiers)
2. {recherche l'élément le plus grand d'un tableau de taille n non nulle}
3. Variables i, max : entier
4. Début
5. max ← t [1]
6. Pour i ← 2 à taille (t) faire
7. Si (t [i] > max)
8. Alors max ← t [i]
9. Fin si
10. Fin Pour
11. Écrire (max)
12. Fin

Grâce à ce code, la recherche sera ainsi plus rapide pour un expert des sciences de données.

Comment construire un algorithme informatique ?

Un algorithme est un énoncé dans un langage de programmation bien défini, d'une suite d'opérations qui permettent de résoudre un problème. Pour construire un algorithme informatique de qualité, il est essentiel de connaître les caractéristiques d'un bon algorithme.

Un bon algorithme informatique doit être lisible, c'est-à-dire compréhensible pour des personnes qui n'évoluent pas en informatique. De même, il doit être de haut niveau, ce qui implique la possibilité qu'il soit traduit dans tout langage de programmation. Un algorithme doit également être précis. Aucune partie de son code ne doit prêter à confusion. Toutes les ambiguïtés doivent ainsi être enlevées. Le meilleur algorithme pour un problème donné est le plus concis, c'est-à-dire le moins long. Un bon algorithme doit enfin être bien structuré, c'est-à-dire décomposé en différentes parties aisément identifiables.

Dans l'optique de construire un algorithme qui respecte scrupuleusement ces caractéristiques, il est important de suivre une méthodologie stricte en plusieurs étapes.

‍

‍

Définir clairement le problème à résoudre par l'algorithme

Un algorithme sert à la résolution d'un problème. Il est donc tout à fait normal au début de poser clairement le problème avant de penser à écrire son algorithme. Une connaissance précise du problème permet de savoir exactement ce que doit faire le code de l'algorithme informatique. Cela rend également plus facile la détermination des différentes étapes par lesquelles doit passer l'algorithme pour résoudre le problème.

Après avoir défini le problème, il est recommandé de vérifier s'il n'existe déjà pas un algorithme informatique standard capable de le résoudre. Après tout, il serait contre-productif de vouloir écrire un algorithme si la tâche à résoudre peut être faite par un algorithme déjà existant.

Définition de l'interface

Pour garder une meilleure lisibilité, il est conseillé de copier autant que possible le style des algorithmes standards lors de l'écriture d'un algorithme. Pour la définition de l'interface de l'algorithme informatique, il faut effectuer la détermination du nom de la fonction et des arguments, l'identification du type de la valeur de sortie. Cette définition se termine par la détermination des contrats de l'interface, c'est-à-dire les exigences sur les valeurs des arguments et le résultat.

Écriture des tests

Beaucoup de programmeurs font l'impasse sur cette étape de conception d'un algorithme, mais elle n'en demeure toutefois pas moins importante. Les tests servent à s'assurer du fonctionnement de l'algorithme. Différents tests peuvent être écrits et le plus important est sans doute celui qui vérifie que l'algorithme fait ce qu'il est censé faire.

Écriture de l'algorithme informatique et son optimisation

À cette étape, le travail à faire consiste à écrire le code de l'algorithme. Le problème étant séquencé en différentes parties, il s'agit d'écrire le code approprié pour chacune d'elles. On passe ensuite à l'optimisation de l'algorithme. Celle-ci passe notamment par la vérification des entrées reçues par l'algorithme informatique et les résultats qu'il produit. L'exactitude de ceux-ci doit être garantie en toute circonstance.

À la fin l'algorithme devra respecter la structure tripartite suivante :

• Un entête : placé au début, il sert à donner un nom à l'algorithme,
• La partie déclarative de l'algorithme : déclaration des différents objets utilisés par l'algorithme informatique : constantes, variables, déclaration des fonctions et procédures,
• Le corps de l'algorithme : liste des instructions à exécuter par l'algorithme informatique.

Pour mieux connaître l'algorithmique, il est important de suivre des cours dans ce domaine.

Différents types d'algorithmes

Les algorithmes informatiques existants peuvent être classés en différents types. On distingue par exemple l'algorithme de tri et l'algorithme récursif. Ces différents types d'algorithmes peuvent être appris dans le cadre d'une formation certifiante à Python.

Algorithme de tri

En programmation informatique, un algorithme de tri est un algorithme capable d'organiser une collection d'objets en fonction d'une relation d'ordre déterminée. Le plus souvent, les objets à trier sont tous des éléments d'un ensemble fini souvent donné sous forme de tableau. Pour faire un tri, un algorithme de ce type procédera le plus souvent par comparaisons successives ou alors fera des hypothèses restrictives sur la structure des données à trier.

Différentes méthodes de tri sont utilisées par les algorithmes. La complexité de ceux-ci dépend notamment de la méthode utilisée. Il s'agit entre autres du tri par sélection, du tri bulle, du tri par insertion, du tri rapide…

Pour une meilleure compréhension des différents types d'algorithmes de tri, on suppose qu'on a à notre disposition un tableau t de n entiers numérotés de 1 à n. On cherche à trier ces différents éléments d'indice de 1 à n dans un ordre croissant.

‍

‍

Tri par sélection

Un algorithme de ce type cherche dans un premier temps le plus petit élément du tableau, c'est-à-dire un entier min tel que t [k] >= t [min] pour tous les k. Les éléments du tableau d'indice 1 et min sont ensuite échangés et la procédure reprend pour les éléments d'indice 2 à n.

Le tri bull

Avec le tri bull, l'algorithme parcourt du début à la fin le tableau t et permute toutes les paires d'éléments consécutifs non ordonnés. Autrement dit, si les éléments d'indice k et k+1 du tableau ne sont pas ordonnés, ce type d'algorithme leur permutera de place. Après une première itération, le plus grand élément du tableau se retrouve dans la dernière case, c'est-à-dire la case d'indice n. On reprend ensuite la procédure pour tous les éléments d'indice 1 à n-1 du tableau.

Tri par insertion

Un algorithme de ce type prend l'élément d'indice 1 du début du tableau, puis l'élément d'indice 2 qu'il place en fonction du premier élément. Il insère par la suite l'élément d'indice 3 du tableau à sa place en fonction des deux premiers. Le principe général est donc de considérer que les éléments d'indice 1 et i-1 sont triés, puis de placer l'élément d'indice i du tableau à sa place parmi les i-1 supposés triés.

Le Quiscksort

Inventée par Sir Charles Antony Richard Hoare en 1960, il s'agit de la méthode de tri la plus utilisée actuellement. Elle applique le principe de « diviser pour régner ». On considère un élément d'indice quelconque p dans le tableau qu'on partitionne en deux zones : les éléments d'indice inférieurs ou égaux à p et les éléments supérieurs ou égaux à p. La place définitive de l'élément p est trouvée en mettant les éléments les plus petits dans le peloton de tête du tableau et les plus grands en queue. La procédure est répétée sur chaque partition créée jusqu'à ce qu'elle soit réduite à un unique élément.

Algorithme récursif

En programmation informatique, un algorithme récursif est un type d'algorithme qui s'appelle lui-même à plusieurs reprises jusqu'à ce qu'il ait résolu le problème. Ce type d'algorithme se base sur la récursivité, c'est-à-dire la résolution d'un problème en le divisant en sous-problèmes du même type.

L'algorithme récursif est le type le plus simple à concevoir en programmation informatique puisqu'il ne nécessite pas de mener une réflexion spécifique à chaque sous-problème. Ce type d'algorithmes informatiques se sert le plus souvent d'une boucle ou de plusieurs pour accélérer la résolution de problèmes.

Les autres types d'algorithmes

De nombreux autres types d'algorithmes existent en programmation. C'est notamment le cas de l'algorithme gourmand et de l'algorithme de programmation dynamique.

L'algorithme gourmand est utilisé dans la résolution de problèmes d'optimisation. Avec ce type d'algorithmes, la solution est construite partie par partie. Une décision est prise lorsqu'elle est bonne à ce stade sans aucune considération de l'avenir. Ce type choisit la meilleure solution locale et la considère comme optimale.

Un algorithme de programmation dynamique tente de résoudre chaque sous-problème une seule fois et mémorise sa réponse dans un tableau. Cela lui évite de devoir calculer à nouveau la solution chaque fois qu'il résout un sous-problème en dessous d'un autre. En terme simple, un algorithme de programmation dynamique résout des problèmes complexes en les divisant en plusieurs sous-problèmes simples. Chacun de ces derniers est résolu puis stocké dans un tableau pour une utilisation ultérieure.

En définitive, les algorithmes sont des éléments de base en programmation. Ils assurent la résolution de problèmes dans de nombreux domaines. Les algorithmes emploient souvent des structures de données comme les tableaux, ce qui renforce davantage leur concision.

‍