Algorithmique

Définition

Un algorithme est un dispositif formel qui, pour chaque entrée issue d'un ensemble déterminé, exécute une suite finie d'instructions élémentaires et termine au bout d'un nombre fini d'étapes, en produisant une sortie (ou un état final).

Un dispositif formel désigne une structure logique qui sert à décrire et étudier de façon rigoureuse un calcul.

En pratique, on s'appuie sur cette méthode pour construire un algorithme:

Lister des étapes finies et exécutables clairement
Garantir une terminaison pour toute entrée (ou au moins pour toutes celles qu'on considère valides)
Garantir une réponse correcte vis-à-vis du problème initial

Un algorithme peut être spécifié en langage humain ou en langage informatique, mais peut aussi être basé sur un système matériel. L'unique obligation est que sa spécification fournisse une description précise de la procédure de calcul à suivre.

Nous nous appuierons sur des algorithmes simples que vous avez déjà implémentés.

Problème informatique

Problème

Un problème informatique est une question bien définie, pour laquelle on cherche une méthode systématique (un algorithme) permettant de produire une solution valide pour toutes les données d'entrée possibles.

Les problèmes bien définis, connus et étudiés possèdent des noms. Ils sont universellement reconnus par la communauté scientifique.

Nom du problème	Description
TSP (Travelling Salesman Problem)	Trouver le plus court chemin passant par toutes les villes une seule fois.
PRIME	Déterminer si un entier donné est un nombre premier.
SORTING	Trier une liste d'éléments selon un ordre.
SEARCH	Trouver un élément dans une structure (tableau, graphe, arbre, …).
FACTORING	Décomposer un nombre en facteurs premiers.
SAT (Satisfiability)	Savoir s'il existe une affectation qui rend une formule logique vraie.
CLIQUE	Trouver un ensemble de sommets tous adjacents dans un graphe.
PATH	Savoir s'il existe un chemin entre deux nœuds dans un graphe.
SUBSET SUM	Trouver si une somme d'éléments d'un ensemble donne une valeur cible.

Une partie importante de la recherche en informatique consiste à trouver des algorithmes de plus en plus efficaces pour résoudre des problèmes donnés.

Correction totale d'un algorithme

On ne peut pas déterminer qu'un algorithme est bon juste parce qu'il marche intuitivement sur quelques entrées qu'on a testé. Certains outils humains peuvent causer des pertes humaines et/ou économiques importantes s'ils sont mal programmés. Il est donc nécessaire de s'assurer que les algorithmes utilisés sont toujours totalement corrects. C'est à dire qu'ils résolvent toujours le problème qu'ils sont censés résoudre.

Nous travaillerons sur base du problème FIND-MIN afin de découvrir comment on démontre qu'un algorithme est totalement correct.

Definition: tableau

Un tableau (ou array en anglais) est une structure de données qui permet de stocker plusieurs valeurs du même type, organisées de manière ordonnée, et accessibles via un indice (ou index).

En python, nous utilisons le type list pour modéliser des tableaux.

Le problème FIND‑MIN

But: Déterminer la valeur minimale d’un tableau $T$ de taille $n$.

Précondition : $n > 0$.

Post-condition
Si $m$ est le résultat, alors
$$ \huge m \;=\; \min_{0 \le i < n}\, \color{red}T[i] $$

Considérons l'entrée $[4, 9, 3, 19]$

L'algorithme renvoie $3$

Considérons l'entrée $[]$.

C'est un cas non défini. En pratique, l'algorithme produira une erreur ou une valeur spéciale en sortie.

Voici l'algorithme que nous avons déjà vu:

# Algorithme - Calculer le minimum de T
# Entrée: Un tableau T de taille n
# Sortie: Le plus petit élément de T
# Pré-condition: n>0
# Post-condition: sortie = min(T)
1. mini ← T[0]
2. POUR i allant de 1 à n-1:
3.     SI T[i] < mini
4.          mini ← T[i]
5. RETOURNER mini

Terminaison

Un algorithme doit se terminer

Si toutes les boucles d'un algorithme se terminent, alors l'algorithme se termine.

Boucles

Boucle bornée

Une boucle bornée est une boucle dont le nombre d'itérations est déterminé ou limité avant l'exécution, et qui s'exécute donc un nombre fini de fois garanti.

Le compteur de boucle n'est pas modifié par les instructions internes à la boucle.

exemple:

for i in range(10):      # exactement 10 itérations
    faire_quelque_chose()

Une boucle while est aussi considérée comme bornée dans le cas où un compteur garantit sa terminaison à la façon d'une boucle for.

i = 0
while i < 10:
    faire_quelque_chose()
    i += 1

Une boucle bornée dont l’indice de départ est strictement supérieur à l’indice d’arrivée est parfaitement définie en algorithmique. Elle est simplement vide d’exécution : le corps de la boucle ne s’exécute jamais.

Le code suivant ne renvoie pas d'erreur, mais n'affiche rien.

for i in range(10,2):
    print("instruction")

Fondements mathématiques de cette assertion

De même, $\displaystyle \sum_{k=6}^{2}k=0$. Il n'existe aucun $k$ tel que $6 \le k \le 2$. L'ensemble des $k$ est donc l'ensemble vide. La somme de l'ensemble vide est 0. On pose parfois ceci comme une convention, mais c'est en réalité bien plus profond que ça. Cette convention est bien fondée par définition des propriétés fondamentales d'une somme. La somme vide est nécessaire pour que les règles de manipulation des sommes soient universelles et sans cas particulier. C'est une exigence de cohérence interne dans les mathématiques. On peut rapprocher cette nécessité de la nécessité d'avoir été conduit à admettre l'existence de zéro dans l'histoire. Le zéro et la somme vide émergent naturellement d'une même nécessité: donner un sens cohérent et neutre à l'absence.

Imaginez une tirelire. Mettez-y quelques pièces chaque jour et faites en la somme. Mais si vous ny avez rien mis du tout, combien y a-t-il ?

Zéro. C’est une somme vide, et elle a un sens.

On peut également rapprocher cette nécessité de celle de l’infini. Si la somme vide donne un sens à l’absence de termes, l’infini donne un sens à l’absence de borne. Ce n’est pas un nombre en soi, mais un concept qui permet de prolonger les raisonnements mathématiques au-delà de toute limite finie. Zéro, somme vide, infini : autant de manières pour les mathématiques de donner forme à ce qui, à première vue, pourrait sembler impensable — l’absence, l’incomplétude, ou l’illimité — tout en gardant une structure cohérente, rigoureuse, et manipulable.

Boucle non bornée

Une boucle non bornée est une boucle dont le nombre d'itérations n'est pas déterminé à l'avance. On ne peut pas savoir a priori combien de fois elle va s'exécuter : cela dépend d'une condition d'arrête dynamique, qui évolue pendant l'exécution.

while not condition_arret():
    faire_quelque_chose()

Ici, la terminaison dépend d'une condition d'arrêt dont on ne peut pas a priori si elle sera vraie un jour.

Variant de boucle

Un variant de boucle est une quantité entière positive strictement décroissante qui assure la terminaison d'une boucle lorsqu'elle atteint une limite inférieure (souvent 0).

Pour prouver qu'un algorithme se termine, on exhibe un variant de boucle et on montre que cette quantité est strictememnt décroissante, pour atteindre son minimum.

Puor FIND-MIN, Le variant de boucle est $n-i-1$. et il assure la terminaison du programme.

Quoi qu'il arrive, $i$ va aller de $0$ à $n-1$, donc le variant de $n-1$ à 0, puis la boucle se termine, car elle n'est composée que d'instructions élémentaires qui se terminent.

D'un point de vue général:

Théorème

Toute boucle bornée composée d'instructions se terminant se termine.

Invariant de boucle

Un invariant de boucle est une propriété qui :

Est vraie au début de chaque itération d'une boucle.
Reste vraie après chaque itération.

Pour le problème FIND-MIN, l'invariant de boucle est la propriété:

"Au début de l'itération $i$, $mini$ contient le minimum de $T[0..i-1]$"

Correction totale

Afin de montrer qu'un algorithme est totalement correct, si on note $I$ l'invariant, il doit vérifier :

Initialisation : Au moment d'entrer dans la boucle (avant la première itération), $I$ est vrai.
Conservation : Si $I$ est vrai au début d'une itération, alors il reste vraie à la fin de cette itération (Donc au début de la suivante).
Terminaison : Quand la boucle s'arrête (car on a préalablement porouvé la terminaison ou on le prouve ici), la propriété $I$ et la condition de sortie permettent de conclure sur le résultat de l'algorithme.

Ce procédé est un raisonnement dit inductif, ou récurrent (voir annexe), auquel on ajoute l'étape de terminaison.

Ces trois phases nous permettent de prouver qu'une boucle fait bien ce qu'on voulait qu'elle fasse. On dit que la boucle est partiellement correcte lorsqu'on a démontré la conservation de l'invariant.

Une boucle partiellement correcte qui se termine est totalement correcte.

Un algorithme est dit totalement correct si toutes ses boucles sont totalement correctes.

Notations

$T[i..j]$ représente le sous-tableau de $T$ de l'indice $i$ à l'indice $j$ inclus.
$T[i..i]$ reprrésente le sous-tableau de $T$ ne comportant que $T[i]$.
Attention, contrairement aux slices, la borne supérieure est incluse.

INITIALISATION

Si le tableau n'a qu'un élément, la boucle ne s'exécute pas et le minimum est correctement renvoyé.
Si le tableau a au moins un élément, $i=1$ et $mini$ est bien le minimum de $T[0..0]$, le tableau constitué d'un seul élément.

L'invariant est donc vérifié pour $\bold{i=1}$.

CONSERVATION On suppose que pour $i\ge1$ quelconque, l'invariant est vrai.

Donc en début d'itération $i$, "$mini$ est le minimum de $T[0..i-1]$" est vrai

On veut alors prouver qu'après une itération, "$mini$ est le minimum de $T[0..i]$" est vrai

Déroulons l'algorithme:

Si $T[i] \gt mini$, alors $mini$ est aussi le $minimum$ de $T[0..i]$ et l'invariant est vérifié en sortie d'itération, car on ne fait rien dans ce cas.
Sinon, $T[i] \le mini$, et donc $mini$ n'est pas le minimum de $T[0..i]$. Mais nous rétablissons immédiatement l'invariant en affectant $T[i]$ à $mini$ qui devient bien le minimum de $T[0..i]$.

Dans tous les cas, en sortie de boucle, "$mini$ est le minimum de T[0..i]" est vrai, ce que nous voulions démontrer.

L'invariant est donc conservé. L'algorithme est partiellement correct.

TERMINAISON Nous avons déjà prouvé la terminaison de l'algorithme.

Lors de sa dernière itération, $i=n-1$ et l'invariant reste vrai pour $i=n$ par conservation.

Donc mini est le minimum de $T[0..n-1]$

Notre algorithme de recherche de minimum est donc totalement correct.

Le problème de l'indice du minimum - ARGMIN

Description du problème ARGMIN

But: Déterminer le plus petit indice de la valeur minimale d’un tableau $T$ de taille $n$ à partir d'un indice $k$.

Préconditions : - $n > 0$ - $0 \le k < n$

Post-condition Si $imin$ est le résultat, alors voici la notation utilisée $$ \huge imin^{\star} \; \in \; \argmin_{k \le {\color{red}i} < n}\, T[i] $$

Qui signifie que $imin$ est le plus petit minimisant de l'ensemble des minimisants.

Par exemple, si $T=[4, 1, 1, 5, 9, 1]$, alors l'ensemble des indices minimisants à partir de $k=0$ est $[1, 2, 5]$, et donc $imin$ vaudra $1$.

Considérons l'entrée $T=[0, 9, 3, 19]$ et $k=1$

La sortie de l'algorithme pour cette entrée est 2, car à partir de l'indice 1, 3 est le minimum, et son indice dans le tableau est 2.

Note: Habituellement, argmin renvoie l'ensemble des minimisants, mais on peut préciser qu'on ne cherche qu'un minimisant, ce qui est notre cas.

Nous voulons prouver que cet algorithme que nous avons déjà programmé résoud ARGMIN

# Algorithme - Calculer l'indice du minimum de T à partir de l'indice k
# Entrées:
   Un tableau T de taille n
   Un indice de départ k
# Sortie: L'indice imin du minimum de T à partir de l'indice k
# Pré-condition: n>0 et 0<=k<n
1. imini ← k
2. Pour i allant de k+1 à n-1:
3.     Si T[i] < T[imini]
4.          imini ← i
3. Retourner mini

Exercice

Reprendre la méthode précédente pour prouver la correction totale de l'algorithme de recherche d'indice minimum:

Formulation de l'invariant
Initialisation
Conservation
Terminaison

Introduction à la complexité en temps

Ici, il s'agit d'estimer le temps que va prendre un algorithme à s'exécuter. Il existe aussi une complexité spatiale, mais nous ne l'aborderons pas.

Dans le cadre de ce cours, on assimilera le temps au nombre d'instructions élémentaires nécessaires à l'exécution d'un algorithme, dans le pire des cas. Le pire des cas est celui d'une entrée qui va nécessiter le plus d'instructions.

Il existe d'autres cas de figure que le pire des cas, mais nous ne les aborderons pas.

Lorsque nous parlerons de complexité, nous entendrons donc toujours complexité temporelle dans le pire des cas.

Taille d'une instance

La taille d'une instance d'un problème algorithmique est une grandeur représentant une mesure pertinente (nombre d'éléments, nombre de bits, longueur d'une chaîne, etc.) associée aux données en entrée de l'algorithme.

En pratique, la taille est souvent notée $n$. $n$ est choisie de façon à être fonction de la quantité de travail que doit effectuer l'algorithme.

Pour le problème du minimum, la taille de l'instance est celle du tableau en entrée.

# Algorithme - Calculer le minimum de T[0..n-1]
1. mini ← T[0]
2. Pour i allant de 1 à n-1:
3.     Si T[i] < e
4.          mini ← T[i]
3. Retourner mini

Pire des cas

Quelle est la caractéristique d'une instance représentant le pire des cas pour le problème du minimum?
A côté de chaque instruction de ce programme, indiquer le nombre de fois où elle sera exécutée en fonction de la taille $n$ de l'instance.
En déduire le nombre d'instructions élémentaires $T(n)$ exécutées par l'algorithme dans le pire des cas en fonction de $n$
- Vous devez trouver $T(n)=3n+2$

Attention: On note souvent $T(n)$ le temps en fonction de $n$. Aussi en français, on appelle souvent les tableaux $T$. Ce qui peut porter à confusion.

Complexités élémentaires

Lorsqu'on trouve que $T(n)=a$, on dit que l'algorithme est à coût constant.
- On dira aussi que la complexité est un $\mathcal{O}(1)$ (grand O de 1)
Lorsqu'on trouve que $T(n)=an+b$, on dit que l'algorithme a un coût linéaire.
- On dira aussi que la complexité est un $\mathcal{O}(n)$ (grand O de n)
Lorsqu'on trouve que $T(n)=an^2+bn+c$, on dit que l'algorithme a un coût quadratique.
- On dira aussi que la complexité est un $\mathcal{O}(n^2)$ (grand O de $n$ carré)

Si un algorithme est en $\mathcal{O}(n^2)$, ça veut dire que sa fonction de temps est dominée par $n^2$. Elle ne peut pas être plus "grande".

Ces 3 types de complexités font partie de la même classe de complexité. On l'appelle la classe P. Elle englobe tous les algorithmes qui calculent en temps polynômial.

Le petit outil ci-dessous permet de comparer la croissance de 2 fonctions quand $x$ tend vers l'infini positif. C'est ce qui nous intéresse en complexité.

Sélectionnez donc $x^2$ et $2^x$. Lorsque vous appuyez sur Démarrer, une animation se lance. Vous visionnez alors la courbe représentative des fonctions à travers une fenêtre de largeur 2 qui se déplace vers la droite sur l'axe des abscisses. Vous pouvez régler la vitesse de déplacement de cette fenêtre avec le curseur.

Attention, la hauteur du graphique ne change pas mais ymax croît en permanence. Toutes ces fonctions sont croissantes et ne cesseront jamais de l'être. Elles tendent toutes vers $+\infin$ quand $x$ tend vers $+\infin$.

On peut se rendre compte que plus $x$ grandit, plus certaines fonctions sont "négligeables" devant d'autres. Ca explique par exemple pourquoi on ne conservera que l'information $n^2$ dans l'expression $an^2+bn+c$ quand on s'occupe de valeurs de $n$ tendant vers $+\infin$. Car le reste est négligeable par rapport à l'expression $an^2$. Il y a même une notation pour ça. $o(n^2)$ (petit o de $n^2$) représente les fonctions négligeables devant $n^2$. Toutes ces fonctions s'éloignent infiniment l'une de l'autre à mesure que x tend vers l'infini.

Complexité du minimum

Quelle est la complexité de l'algorithme de recherche de minimum?

Exercice

Objectif : Étant donné un tableau de taille $n$, afficher toutes les paires possibles d'éléments.

Entrée : Un tableau T[0..n-1] Sortie imprécise : Toutes les paires d'éléments possibles

Voici 2 algorithmes possibles selon qu'on considère ou non des répétitions.

Algo 1

1. Pour i allant de 0 à n-1 :
2.     Pour j allant de 0 à n-1 :
3.         afficher(T[i], T[j])

Ecrivez l'affichage obtenu pour T=[2, 4, 6]
Estimer $T(n)$ et en déduire la complexité de l'Algo1

Algo 2

1. Pour i allant de 0 à n-1 :
2.     Pour j allant de i à n-1 :
3.         afficher(T[i], T[j])

Ecrivez l'affichage obtenu pour T=[2, 4, 6]
Estimer $T(n)$ et en déduire la complexité de l'Algo2

Exercice

Ensembe des minimisants

Ecrire et tester une fonction python argmin qui résoud le problème ARGMIN en renvoyant cette fois-ci l'ensemble des minimisants.

\[ ens\_min = \argmin_{k \le {\color{red}i} < n}\, f[i] \]

Moyenne mobile d'un tableau

Les moyennes mobiles sont utilisées dans divers domaines pour lisser des fluctuations à court terme et ainsi révéler clairement les tendances globales à moyen ou long terme. Par exemple, en finance, elles servent à identifier les tendances du marché boursier sur des périodes précises. En météorologie, elles permettent de mieux discerner les tendances saisonnières des températures ou précipitations. En santé publique, elles facilitent le suivi des épidémies, en compensant les variations dues aux week-ends ou aux jours fériés. De même, en électronique et traitement du signal, elles sont utilisées pour filtrer le bruit des données issues de capteurs. Enfin, en économie et en marketing digital, elles aident à repérer les cycles économiques et à analyser le trafic web pour une meilleure prise de décision stratégique.

Définition :
Étant donné un tableau de nombres réels $ T[0..n-1] $, le tableau $M$ de moyennes mobiles de taille $ k $ est défini ainsi:

\[ M[i] = \frac{T[i+k-1] + T[i+k-2] + \dots + T[i]}{k} \]

Ainsi, le tableau des moyennes mobiles $ M $ aura pour taille $ n-k+1 $.

Question 1 :
Calculer les tableaux de moyennes mobiles $M$ pour le tableau T suivant :

$ T = [2, 4, 6, 11, 10, 12] $
1. pour $ k = 3 $
2. pour $ k = 4 $

Question 2 :
Écrire en pseudocode simple un algorithme permettant de calculer la moyenne mobile d'un tableau $ T[0..n-1] $ avec une fenêtre de taille $ k $.

Question 3 :
Ecrivez une fonction permettant de tester votre pseudo code.

Question 4 :
Étudier et exprimer la complexité temporelle de l'algorithme en fonction des variables $ n $ et $ k $.

Question 5 (Bonus) :
Proposer une amélioration de l'algorithme pour réduire sa complexité temporelle, en expliquant le principe et la complexité obtenue.

Pour aller plus loin - python

En python, étant donné unne fonction f, l'expression

\[ mini \;=\; \min_{k \le i < n}\, f(i) \]

peut s'écrire

mini = min(f(i) for i in range(k,n))

Et l'expression suivante $$ imin^{\star} \; \in \; \argmin_{k \le {\color{red}i} < n}\, f[i] $$

peut s'écrire

imin = min(range(k, n), key=f)

On essaie, quand la pratique et le langage utilisé rend ça possible, de privilégier ces écritures mathématiques afin de gagner en compacité dans les programmes, ce qui limite les erreurs potentielles, favorise la lisibilité du code, et conserve le code proche de sa définition rigoureuse.

Pour aller (beaucoup) plus loin - Preuve automatique

Il existe des langages conçus pour pour écrire des programmes corrects par construction.

Par exemple, Why3 intègre la preuve de correction totale en se servant de programmes "prouveurs".

Ici, voici un programme écrit en Why3 version 1.8.0 qui permet de prouver la correction totale de l'algorithme présenté de recherche du minimum à l'aide du prover alt-ergo version 2.6.0

use int.Int
use array.Array
use ref.Ref

let min (a: array int) : (res: int)
  requires {length a>0}
  ensures {exists i. 0 <= i < length a && res = a[i]}
  ensures {forall i. 0<=i<length a -> res <= a[i]}
=
  let n = length a in
  let ref res = a[0] in
  for i=1 to n-1 do
    invariant {exists j. 0 <= j < i && res = a[j]}
    invariant {forall j. 0<=j<i -> res<=a[j]}
    if a[i]<res then res := a[i]
  done;
  return res

Lors de la vérification, la console affiche

Prover result is: Valid (0.05s, 82 steps).

Ce qui nous indique que notre algo est totalement correct.

Why3 et Alt-Ergo sont issus du travail de recherche du Laboratoire de Méthodes Formelles du CNRS. Le LMF est formé du Laboratoire Spécification et Vérification (LSV, ENS Paris-Saclay, CNRS, Inria) et de l’équipe Vals du Laboratoire de Recherche en Informatique (LRI, Université Paris-Saclay, CNRS, Inria, CentraleSupélec) soit une centaine de personnes.