Rappels d'algorithmique
Algorithmique
Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions à réaliser afin de résoudre un problème.
En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .
Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de vérifier :
- Sa finitude : Il doit se terminer en un temps fini.
- Sa correction : Il doit (généralement) donner le bon résultat.
- Sa performance : Plusieurs algorithmes peuvent permettre de résoudre une même classe de problèmes. Ils ne nécessiteront cependant pas tous l’utilisation de la même quantité de mémoire ou le même nombre d’étapes de calcul, donc la même durée.
Remarques
- Ce n’est pas toujours une mauvaise nouvelle si certains algorithmes ont besoin d’un « temps infini » pour résoudre un problème : certains choix en cryptographie reposent sur l’idée que « casser » la protection nécessite une durée de calcul trop grande, pour le matériel dont on dispose aujourd’hui.
- Pour certains problèmes on doit se contenter d’une solution approchée et pas d’une solution exacte.
La performance d’un algorithme porte sur deux aspects : la durée du calcul et la quantité de mémoire nécessaires à la résolution du problème. Malheureusement ces deux points s’opposent . Il est souvent nécessaire d’occuper davantage de mémoire pour gagner en temps de calcul, ou d’écrire plus d’instructions, et donc faire plus de calculs, pour aboutir à une gestion de la mémoire optimale.
Conformément au programme, on limite la performance algorithmique à la complexité algorithmique.
Notion de complexité algorithmique
Introduction
La complexité algorithmique donne des informations sur la durée du calcul nécessaire à la résolution du problème. Plus la complexité algorithmique est petite, moins de calculs sont effectués et plus l’algorithme est performant (sous réserve que la gestion de l’espace mémoire utilisé par l’implémentation de l’algorithme ne constitue pas un problème).
On exprime la complexité d’un algorithme en fonction de la taille (nombre) des données qu’il manipule en considérant que chaque instruction élémentaire s’effectue en temps constant.
Il existe plusieurs méthodes pour analyser la complexité d’un algorithme, comme :
-
L’analyse moyenne : Il s’agit d’évaluer comment varie la durée moyenne des calculs à effectuer en fonction du nombre de données manipulées.
-
L’analyse optimiste Il s’agit d’évaluer comment varie le nombre de calculs à effectuer, dans le scénario le plus favorable, en fonction du nombre de données manipulées.
Par exemple, on cherche une valeur dans une liste et c’est la première qui apparaît lors de cette recherche. -
L’analyse pessimiste (ou du pire cas) : Il s’agit d’évaluer comment varie le nombre de calculs à effectuer, dans le scénario le moins favorable, en fonction du nombre de données manipulées. Par exemple, on cherche une valeur dans une liste alors qu’elle n’est pas présente dans la liste.
Lorsqu’on utilise le résultat de l’analyse du « pire cas », aucune mauvaise surprise ne peut intervenir, le pire cas à été envisagé à l’avance.
Les complexités des différents algorithmes varient beaucoup. On peut néanmoins regrouper les algorithmes en quelques grandes familles :
-
Complexité constante : Leur notation est de la forme . Ces algorithmes sont indépendants du nombre de données à traiter.
InfoLa complexité constante apparaît dans la recherche par index dans un tableau.
La complexité constante est la plus « performante ». -
Les algorithmes logarithmiques : Leur notation est de la forme . Ces algorithmes sont très performants en temps de traitement. Le nombre de calculs dépend du logarithme du nombre de données à traiter.
Sur la Figure ci-dessous, on peut constater que, plus le nombre de données à traiter est important, moins le nombre de calcul à effectuer augmente rapidement — la valeur de la dérivée est de moins en moins grande.
La fonction logarithme à utiliser dépend du problème étudié mais, comme la complexité est définie à un facteur près, la base du logarithme n’a pas d’importance.
La complexité logarithmique apparaît dans les problèmes dans lesquels
l’ensemble des données peut être décomposé en deux parties égales, qui
sont elles-mêmes décomposées en 2 (recherche par dichotomie, recherche dans un arbre binaire, etc.).
La complexité logarithmique est très « performante ».
Le logarithme à utiliser est alors
la fonction réciproque de , c’est à dire
(aussi appelé logarithme entier).
Le logarithme entier d’un nombre supérieur ou égal à 1 est le nombre de fois qu’il faut le diviser par deux pour obtenir un nombre inférieur ou égal à 1.
- Les algorithmes linéaires : Leur notation est de la forme . Ces algorithmes sont rapides. Le nombre de calculs dépend, de manière linéaire, du nombre de données initiales à traiter.
La complexité linéaire apparaît dans les problèmes dans lesquels on
parcourt séquentiellement l’ensemble des données pour réaliser une
opération (recherche d’une valeur, par exemple).
La complexité linéaire est considérée comme « efficace ».
- Les algorithmes linéaires et logarithmiques (quasi-linéaire) : Leur notation est de la forme .
La complexité linéaire et logarithmique apparaît dans des problèmes dans lesquels on découpe répétitivement les données en deux parties, que l’on parcourt
séquentiellement ensuite (tri Quicksort par exemple).
La complexité quasi-linéaire est considérée comme « assez efficace ».
- Les algorithmes de type polynomiale : Leur notation est de la forme où est la puissance.
Une complexité quadratique apparaît, par exemple, lorsqu’on parcourt un
tableau à deux dimensions, lorsqu’on effectue un tri par comparaison, etc.
La complexité polynomiale est considérée comme « moyennement efficace ».
- Les algorithmes exponentiels ou factoriels : Leur notation est de la forme ou . Ce sont les algorithmes les plus complexes.
Le nombre de calculs augmente de façon exponentielle ou factorielle en fonction du nombre de données à traiter. Un algorithme de complexité exponentielle traitera, dans le pire des cas, un ensemble de 10 données en effectuant 22026 calculs ; un ensemble de 100 données en effectuant calculs !!! On dit généralement que les problèmes produisant ce type d’algorithmes sont « non calculables ».
On rencontre les algorithmes de type exponentiels ou factoriels dans les problématiques liées à la programmation de fonctions humaines comme la vision, la reconnaissance des formes ou l’intelligence artificielle.
| Complexité | Durée pour |
|---|---|
| Logarithmique : | 10 ns |
| Linéaire : | 1 ms |
| Quadratique : | 1/4 heure |
| Polynomiale : | 30 ans si |
| Exponentielle : | plus de milliards d’années |
Ordres de grandeur des durées d’exécution d’un problème de taille sur un ordinateur à un milliard d’opérations par seconde (« Informatique pour tous en CPGE », éditions Eyrolles).
Quelques règles simples permettant de déterminer la complexité d’un algorithme
Nous allons introduire, dans cette partie, quelques règles simples qui permettent de se faire une idée de l’efficacité d’un algorithme :
- Une affectation ou l’évaluation d’une expression ont un temps d’exécution petit. Cette durée constitue souvent l’unité de base dans laquelle on mesure le temps d’exécution d’un algorithme.
- Le temps pris pour exécuter une séquence d’instrutions
p qest la somme des temps pris pour exécuter les instructionsppuisq. - Le temps pris pour exécuter un test
Si (b) Alors p Sinon q FinSiest inférieur ou égal au maximum des temps pris pour exécuter les instructionspetq, plus une unité qui correspond au temps d’évaluation de l’expressionb. - Le temps pris pour exécuter une boucle
Pour i variant de 1 à m par pas de 1 Faire p FinPourest fois le temps pris pour exécuter l’instruction p si ce temps ne dépend pas de la valeur de i. En particulier, quand deux boucles sont imbriquées, le corps de la boucle interne est répété à cause de cette boucle, mais aussi parce qu’elle-même est répétée dans son intégralité. Ainsi, si les deux boucles sont répétées respectivement et fois, alors le corps de la boucle interne est exécuté fois en tout.
Quand le temps d’exécution du corps de la boucle dépend de la valeur de l’indice , le temps total d’exécution de la boucle est la somme des temps d’exécution du corps de la boucle pour chaque valeur de . - Le cas des boucles
Tantqueest plus complexe puisque le nombre d’itérations n’est en général pas connu à priori. Il doit être évalué au cas par cas.
Pour chacun des programmes suivants, dire en fonction de quel est le nombre d’opérations op que le programme effectue. Justifier votre résultat.
Comment illustrer l’influence du nombre d’éléments passés en entrée
En utilisant la fonction time du module time, écrire le code de fonctions qui :
- montre que le temps d’accès à un élément d’une liste est en ;
- montre que la recherche linéaire dans une liste est en ;
- met en évidence la complexité de l’opérateur Python
in; - montre que la recherche linéaire dans une liste à deux dimensions est en ;
- montre que la recherche dichotomique dans une liste triée est en .
Terminaison d’un algorithme itératif : variant de boucle
La structure qui généralement doit retenir l’attention lors de l’analyse de la terminaison d’un algorithme est la structure de boucle.
On appelle variant d’une boucle une fonction qui a pour variables les variables du problème, qui retourne une valeur entière positive et qui décroît à chacune des itérations de la boucle, jusqu’à s’annuler ou prendre une valeur constante négative qui dépend de la condition d’arrêt de la boucle.
La découverte d’un variant de boucle permet de conclure que la boucle se termine puisqu’il n’existe aucune suite infinie strictement décroissante d’entiers naturels.
Exemple 1 : Calcul de la plus petite puissance de deux supérieure ou égale à un entier
Algorithme 1
Fonction : plusPetitePuissance(n)
Entrée : entier naturel n
Sortie : entier naturel dont la valeur est égale à la plus petite
puissance de deux supérieure ou égale à .
Début
TantQue Faire
FinTantQue
Fin
La fonction d’expression est-elle un variant de boucle ?
- est un entier positif.
- Tant que ,
- décroît sur l’ensemble des valeurs de puisque
- Condition d’arrêt : , donc .
La fonction est un variant de boucle et la boucle se termine donc bien.
Exemple 2 : Palindrome
Algorithme 2
Fonction : palindrome(m)
Entrée : chaîne de caractères m
Sortie : booléen Vrai si la chaîne de caractères m est un palindrome, Faux sinon
Début
TantQue Faire
Si Alors
Sinon
Renvoyer Faux
FinSi
FintantQue
Renvoyer Vrai
Fin
-
Décrire au moyen d’un tableau indiquant l’évolution des valeurs des variables le fonctionnement de l’algorithme 2 pour la chaîne de caractères « sauras » puis pour la chaîne de caractères « radar ».
Remarque : Le premier élément d’une chaîne a pour indice 0. -
Montrer que est un variant de la boucle TantQue.
-
En déduire que la boucle TantQue se termine.
Correction d’un algorithme itératif : invariant de boucle
On appelle invariant d’une boucle une propriété qui, si elle est vraie avant l’exécution d’une itération, le demeure après l’exécution de l’itération. Un invariant de boucle doit être vrai avant de commencer la boucle et est alors garanti de rester correct après chaque itération de la boucle. En particulier, l’invariant sera toujours vrai à la fin de la boucle.
Les boucles et la récursivité étant fondamentalement similaire, il y a peu de différence entre démontrer un invariant de boucles et prouver qu’un programme est correct en utilisant un raisonnement par récurrence.
Exemple 3 : Calcul de
Algorithme 3
Fonction : calculPuissanceDeux(n)
Entrée : entier naturel
Sortie : entier naturel dont la valeur est égale à
Début
Pour allant de 1 à faire
FinPour
Fin
La propriété « À chaque tour de boucle est une puissance de 2 » est un invariant de boucle. En effet :
-
Initialisation : Avant d’entrer dans la boucle : .
-
Conservation : On suppose l’invariant vérifié au tour de la boucle : . Au tour , .
-
Terminaison : La boucle réalise tours ; au dernier tour
La proposition est donc bien un invariant de boucle et on peut conclure que l’algorithme est correct.
Exemple 4 : Quotient et reste de la division euclidienne d’un entier positif par un entier strictement
Algorithme 4
Fonction : division(a, b)
Entrée : entiers naturels et
Sortie : Quotient et reste de la division euclidienne
de l’entier naturel par l’entier naturel
Début
TantQue Faire
FinTantQue
Renvoyer
Fin
-
Décrire le fonctionnement de l’algorithme pour l’entrée (
a = 17,b = 5) au moyen d’un tableau indiquant l’évolution des valeurs des variables au fil des itérations. -
Montrer que la boucle TantQue se termine en utilisant un variant de boucle.
-
Montrer que la propriété est un invariant de la boucle TantQue, en déduire que l’algorithme produit le résultat attendu.
- Écrire le code Python implémentant l’algorithme 4. La spécification de la fonction est la suivante :
- Écrire un jeu de tests pour la fonction
division_euclidienne.
Exercices
On considère la fonction suivante :
-
Quel calcul ce code réalise-t-il ?
-
Écrire un jeu de test pour cette fonction.
-
Démontrer que l’algorithme se termine.
-
Démontrer que l’algorithme est correct.
-
Déterminer la complexité de cet algorithme.
On considère la suivante :
-
Quelle opération ce code réalise-t-il ?
-
Écrire un jeu de test pour cette fonction.
-
Démontrer que l’algorithme se termine.
-
Démontrer que l’algorithme est correct.
-
Déterminer la complexité de cet algorithme.
-
Existe-t-il un ou des algorithmes qui réalisent la même opération plus efficacement ?
On considère la fonction somme_premiers_entiers qui implémente l’algorithme :
Algorithme 5
Fonction : somme_premiers_entiers(n)
Entrée : entier naturel
Sortie : somme des n premiers entiers naturels
Début
TantQue Faire
FinTantQue
Renvoyer somme
Fin
-
Implémenter en Python l’algorithme proposé. Ne pas oublier la spécification de la fonction.
-
Écrire un jeu de test pour cette fonction.
-
Prouver que la boucle se termine à l’aide du variant de boucle où est le compteur de la boucle.
-
Prouver que la proposition : « au début du tour du kième tour de la boucle, la variable somme est égale à la somme des premiers entiers naturels » est un invariant de boucle. En déduire que l’algorithme est correct.
-
Quelle est la complexité de cet algorithme ?