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.
Dans la suite, cette fonction sera notée cubes_pyramide_v2().
Une troisieme réponse possible ?
Le nombre de cubes à chaque étage définit une seuite arithmétique de premier
terme 1 et de raison 2. On peut donc appliquer la propriété sur la somme des
termes d’une telle suite.
defcubes_pyramide(nb_etages):
return nb_etages**2
Dans la suite, cette fonction sera notée cubes_pyramide_v3().
Une quatrième réponse possible ?
On peut faire appel aux listes.
defcubes_pyramide(nb_etages):
liste_etages = [2*i-1for i in range(1,nb_etages+1)]
return sum(liste_etages)
Dans la suite, cette fonction sera notée cubes_pyramide_v4().
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 ?
Dans la version 1, avec la boucle while, la suite associée à etage définit
une suite strictement croissante (suite arithmétique de raison \(1>0\)) et
celle-ci est majorée par nb_etages (condition de la boucle). La boucle se
termine donc.
Dans la version 2, avec la boucle for, la terminaison est immédiate. Il y a
exactement \(n\) passages dans la boucle où on réalise à chaque passage une
seule opération (addition).
Dans la version 3, pas de boucle donc pas de problème de terminaison.
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 ?
Pour les versions qui présentent une boucle (v1, v2 et v4):
À chaque étape de la boucle, on calcule invariablement somme.
Prouvons que \(\mathscr{P}_n : “\text{somme} = 1 + 3 + … + 2n-1” \text{ est
vraie quelque soit l’étage } n \geq 1\).
Ainsi \(\mathscr{P}_{n+1}\) est vraie. L’hérédité est prouvée.
La correction de l’algorithme est ainsi justifiée.
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 ?
Les algorithmes v1, v2 et v4 ont une compléxité linéaire
\(\mathscr{O}(n)\).
Le niveau de compléxité de l’algorithme v3 est en \(\mathscr{O}(1)\)
(compléxité constante) puisqu’il n’y a qu'1 opération indépendamment du nombre
d’étages de la pyramide.
Bilan : comme on pouvait s’y attendre puisqu’il n’y a pas de boucle, la v3 est
préférable aux autres versions en terme de vitesse d’exécution.
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 ?
La séquence peut tout aussi bien être une chaîne de caractère, un uplet ou
encore une liste.
defest_present(sequence, element):
n = len(sequence)
i =0while i < n:
if sequence[i] == element:
return i
i = i +1return False
L’algorithme est valide:
la terminaison est assurée par la présence de la suite définie par les entiers
\(i\) strictement croissante et majorée par \(lg\);
la correction de l’algorithme est faite en prouvant que
\(\mathscr{P}_i:“sequence[j] \neq element \text{ pour tout entier } j<i”\)
est un invariant de boucle.
En considérant une comparaison comme une opération élémentaire et i=i+1 comme
2 opérations (1 somme et 1 affectation), le nombre d’opérations varie entre
\(2\) dans le meilleur des cas (element est le premier élément de
sequence) et \(4n\) dans le pire des cas (on a parcouru toute la séquence
alors que element n’est pas un élément de sequence).
Le niveau de complexite de l’algorithme est en \(\mathscr{O}(n)\).
Autre possibilité d’algorithme:
defest_present(sequence, element):
n = len(sequence)
for i in range(n):
if sequence[i] == element:
return i
return False
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 ?
Une solution avec une boucle while. Choisir une boucle for est évidemment
possible.
defmaximum(liste):
n = len(liste)
maxi = liste[0]
i =1while i < n:
if liste[i] > maxi:
maxi = liste[i]
i = i +1return maxi
L’algorithme est valide:
la terminaison est assurée par la présence de la suite définie par les entiers
\(i\) strictement croissante et majorée par \(lg\);
la correction de l’algorithme est faite en prouvant que
\(\mathscr{P}_i:“maxi \text{ est le maximum de }liste[0:i]"\) est
un invariant de boucle.
Dans le pire des cas, on doit parcourir toute la liste afin d’obtenir son
maximum. Le coût de l’algorithme est linéaire (\(\mathscr{O}(n)\)).
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 ?
Une solution avec une boucle for. On peut proposer de façon similaire à
l’exemple précédent une boucle while.
defmoyenne(liste):
n = len(liste)
somme =0for i in range(n):
somme = somme + liste[i]
return somme/n
La validité de l’algorithme se prouve de manière similaire que précédemment,
ainsi que la détermination de son niveau de complexité qui est linéaire.