Quelques éléments d'algorithmique

Jusque là, nous nous sommes contentés de proposer de manière artisanale un ou des algorithmes pour répondre à un problème donné.

  • Qu’est ce qui prouve que ces algorithmes sont valides ? La vérification de jeux de tests n’est clairement pas suffisant !

  • Entre deux algorithmes valides, lequel s’exécute le plus rapidement ? Chronométrer les deux algorithmes sur un même jeu de tests serait intéressant, mais cela n’est clariement pas suffisant pour pouvoir évaluer dans l’absolu chacun des algorithmes.

Une seule solution pour répondre à ces deux questions: recourir aux Mathématiques !

L’informatique est aussi une science !


Traiter l’exemple suivant en premier lieu.

Exemple 1: pyramide de cubes

Pyramide de 5 étages

On a construit une pyramide avec un certain nombre d’étages.

a) Écrire une fonction cubes_pyramide() de paramètre nb_etages qui retourne le nombre de cubes qui a été nécessaire pour réaliser cette construction.
b) Réaliser votre propre jeu de tests.

Une réponse possible ?
Une seconde réponse possible ?
Une troisieme réponse possible ?
Une quatrième réponse possible ?

Prouver la validité d’un algorithme

Dans cette première partie, nous ne nous limiterons pas seulement aux séquences.

Pour prouver la validité d’un algorithme, cela se fait en deux étapes:
a) prouver la terminaison des boucles présentes: justifier que les boucles présentes se terminent effectivement;
b) prouver la correction de l’algorithme: justifier l’existence d’un invariant de boucle, c’est à dire d’une propriété qui sera constamment vérifiée à chaque étape de la boucle présente dans l’algorithme.

Terminaison d’une boucle ?

Pour une boucle Pour/for, la terminaison est évidente. En l’absence d’une sortie prématurée avec l’usage du break, on connaît exactement le nombre d’étapes à effectuer.

Avec une boucle TantQue/while, on utilisera essentiellement ce qui suit

a) Une suite de nombres entiers strictement croissante est non majorée.
b) Une suite de nombres entiers strictement décroissante est non minorée.

Par exemple, la suite des nombres entiers naturels paires définie par \(u_n=2n\) pour tout \(n \in \mathbb{N}\) est strictement croissante. Par conséquent, il y a un nombre fini d’entiers \(n\) tels que \(u_n < 10^6\).

a) On cherchera dans les instructions de la boucle while la présence d’une suite d’entiers strictement croissante (respectivement strictement décroissante) et majorée (respectivement minorée) dans la condition de la boucle.
b) Les égalités de flottants sont à proscrire absolument ! (voir 2.7)

Dans l’exemple précédent, justifier la terminaison de l’algorithme proposé.

Réponse ?

Correction d’un algorithme ? Existence d’un invariant de boucle?

Cela repose sur un type de raisonnement mathématique le raisonnement par récurrence. Celui-ci est au programme de Terminale.

Dans l’exemple précédent, justifions la correction de l’algorithme proposé.

Réponse ?

Complexité/coût d’un algorithme

Faisons quelques suppositions:

a) La vitesse d’exécution d’un algorithme ne dépend uniquement que du nombre \(n\) d’opérations élémentaires présentes dans celui-ci. La vitesse d’exécution s’exprime donc en fonction de \(n\). Ceci désigne la complexité ou le coût d’un algorithme.

b) Deux algorithmes où le nombre d’opérations diffère d’un nombre constant s’exécutent à une vitesse très semblable d’autant plus lorsque le nombre \(n\) d’opérations est grand;

Exemple : si l’algo1 présente \(n\) opérations et l’algo2 \(n+3\) opérations, alors pour un \(n\) assez grand, la diffèrence de vitesse est imperceptible.

c) Deux algorithmes où le nombre d’opérations diffère d’un multiple près ont des vitesses d’exécution de même catégorie: même niveau de complexité;

Exemples :

  • si l’algo1 présente \(1\) opération et l’algo2 \(3\) opérations, alors leurs vitesses d’exécution sont dans la même catégorie: complexité constante, notée \(\mathscr{O}(1)\);

  • si l’algo1 présente \(n\) opérations et l’algo2 \(2n+3\) opérations, alors leurs vitesses d’exécution sont dans la même catégorie: complexité linéaire, notée \(\mathscr{O}(n)\);

  • si l’algo1 présente \(n^2\) opérations et l’algo2 \(2n^2+3n+5\) opérations, alors leurs vitesses d’exécution sont dans la même catégorie: complexité quadratique, notée \(\mathscr{O}(n^2)\).

Remarque: un algo de complexité constante s’exécute plus rapidement qu’un algo dont la complexité est linéaire qui lui même s’exécute plus rapidement qu’un algo dont la complexité est quadratique.


Retour à l’exemple 1:

Déterminer le niveau de complexité de chacune des versions proposées.

Réponse ?

Exemple 2:

a) Écrire un algorithme de recherche d’une occurence dans une séquence. La fonction retourne la position de l’élément recherché si il se trouve dans la séquence, False sinon.
b) Quelle est son niveau de complexité/coût ?

Éléments de réponse ?

Remarques :

  • Peut on optimiser cette recherche dans le cas d’une séquence triée ?

  • Comment chercher un mot dans un texte ? Ceci sera traité en Terminale, mais vous pouvez déjà y réfléchir si vous le souhaitez !


Exemple 3:

a) Écrire un algorithme de recherche du maximum dans une liste.
b) Quelle est son niveau de complexité/coût ?

Réponse ?

Exemple 4:

a) Écrire un algorithme de calcul d’une moyenne de valeurs présentes dans une liste.
b) Quelle est son niveau de complexité/coût ?

Réponse ?