On appelle algorithme une suite finie d'instructions précises et ordonnées qui permettent de résoudre un problème, d'accomplir une certaine tâche.
Les algorithmes sont la base de la programmation informatique et sont utilisés pour automatiser des processus complexes.
Les caractéristiques d'un algorithme :
De manière schématique, un algorithmes peut être vue comme une succession de trois étapes principales :
$$entrées \longmapsto procedure \longmapsto sortie$$
Un algorithme n'est correct à $90\%$, il est donc considéré incorrect.
Nous nous sommes demandés si il est possible de prouver qu'un algorithme est correct. Le logicien et mathématicien autrichien Kurt Gödel a démontré qu'aucun système formel suffisamment puissant pour décrire l'arithmétique ne peut prouver sa propre cohérence au sein de ce même système.
En France (mais pas que...), il existe un courant de recherche qui construit des programmes basés sur des algorithmes pour prouver des algorithmes.
L'assistant de preuve Coq.
Coq est un assistant de preuve formelle. Cela signifie que c’est un logiciel qui aide à prouver mathématiquement la correction d’algorithmes ou de théorèmes.
On écrit le programme ou la propriété qu’on veut vérifier sous forme mathématique. Coq permet alors de construire une preuve pas à pas, et vérifie automatiquement que chaque étape est correcte.
Vérifier la correction d’algorithmes : par exemple, s’assurer qu’un tri renvoie toujours une liste triée. Formaliser des théorèmes mathématiques complexes et prouver qu’ils sont corrects. Produire du code certifié à partir de ces preuves, qui est garanti correct par construction.
Si l’on fait un algorithme “soigné”, alors en théorie, il n’y a pas de problèmes pour que le programme le soit lui aussi. Malgré tout cela n’est pas toujours vrai, par contre avoir des bonnes bases est important pour faire un bon programme.
L'efficatité d'un algorithme c'est le fait de se demander si son programme nous donne une réponse dans un temps raisonnable.
Un programme informatique est un algorithme qui a été codé sur une machine à l'aide d'un langage spécifique.
Si l'on dit qu'un certain algorithme $\mathcal{A}$ s'exécute en $10s$ ceci n'a pas de sens, comme expliqué au dessus, l'efficacité d'un algorithme dépend de la machine. Ainsi, lorsque l'on étudie l'efficacité d'un algorithme, on doit répondre à plusieurs questions :
On considère que l’efficacité d’un algorithme se mesure grâce aux opérations que l’algorithme fait. Pour déterminer l’efficacité de ce dernier on va en fait calculer le nombre d’opérations effectuées.
On considère l'algorithme $\mathcal{A}_1$ suivant :
T un tableau d'entiers intAlgorithme A m = T[1] for i in [2,N] if m > T[i] : m = T[i] return m
On cherche a évaluer l'efficacité de l'algorithme en fonction de N.
Déroulement de l'algorithme :
m = T[1].m, l'entier minimum du tableau.int[] tab = { 1, 7, 0, 4, 9 };
minimum(tab); // retournerait 0
Hypothèse : On considère que le tableau est de taille $N=10$ et qu'il est trié dans l'ordre croissant.
Par exemple on pourrait avoir :
T = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
m le premier élément du tableau, ici 1.T trié dans l'ordre croissant implique que toutes les comparaisons m>T[i] seront forcément fausse. On ne change donc jamais la valeur de m.m=1.On peut aussi se demander combien de contrôle on fait.
Un contrôle représente simplement un test, une comparaison exécutée par l'algorithme.
Pour notre algorithme $\mathcal{A}_1$ on compte : $10$ contrôles pour la boucle for.
Dans notre cas, l'opération appelée contrôle, représente le nombre de fois que l'on vérifie si $i$ est inférieur ou égal à $N$.
En gros, notre boucle vas de $2$ jusqu'à $N$. Ainsi pendant l'exécution la variable $i$ va prendre les valeurs suivantes :
$$i : 2 \to 3 \to 4 \to \ldots \to N \to N+1$$
Okay, c'est là que ça se complique, vous allez sûrement me demander : Mais pourquoi on doit prendre $N+1$ ?
En fait, lorsque $i=N$ la boucle for va s'exécuter car on vérifie dans notre algo si $i\leq N$. Ainsi après l'exécution du rang $i=N$, la boucle incrément $i$ à $N+1$ et vérifie donc une $N$-ième fois si $i$ est inférieur ou égal à $N$. Ici, la condition est dépassée c'est donc après ce contrôle que l'on sort de la boucle.
On a donc effectué $c=10$ opérations de contrôles pour ce cas pour l'algorithme $\mathcal{A}_1$.
Hypothèse : On considère un tableau de taille $N=10$ et qu'il est trié dans l'ordre décroissant.
Par exemple on pourrait avoir :
T = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
m l'entier $10$.m l'entier courant du tableau. Au total pusiqu'on compare avec les éléments $2$ à $10$ il va y avoir $9$ comparaisons donc $9$ affectations.m=1 le dernier élément du tableau.Pour ce second cas de figure, on va avoir $1$ affectations au début de l'algorithme, $10$ contrôles pour la boucle for et $9$ affectations.
Ainsi on obtient : $10$ contrôles $+ 10$ affectations.
Si on considère un tableau d'entiers T de N éléments.
Dans le meilleur des cas on a $1$ seule affectation, et dans le pire des cas on en a $N$. Ainsi, on en conclu que le nombre d’affectation dépend de l’entrée même si l’entier N n’est pas fixé.
Quelques éléments de vocabulaire et de notation de base concernant l'écriture et l'évaluation d'algorithmes.
Dans nos différentes études, on va considérer que la taille de l'entier est minimal, même si cela dépend en faite du codage utilisé.
Considérons $n=14$.
On appelle ordre de grandeur la tendance d'une courbe quand $N$ augmente.
En algorithmique, L’ordre de grandeur est utilisée pour évaluer la tendance du temps d’exécution (ou de l’espace mémoire) requis par un algorithme en fonction de la taille donnée. Cela permet en fait de classer les algorithmes selon leur efficacité sans se soucier des constantes ou des termes qui influent peu. L’ordre de grandeur est notée $O$, avec la notation Big-O qui donne une approximation asymptotique de la complexité.
Dans ce cours, on utilisera la notation de Landau $\mathcal{O}$ créée par Brechmann en 1894 et popularisée par Landau, qui permet de décrire le comportement des fonctions selon la tendance de $N$, pour objectif de déterminer la complexité de certains algorithmes.
Dans l’objectif de mieux comprendre la notation $\mathcal{O}$ de Landau, nous allons utiliser quelques exemples.
Dans le cadre de l'unité d'enseignement MATHÉMATIQUES POUR L'INFORMATIQUE 1, la notion de suite/fonction dominée a été introduite.
Soient $f$ et $g$ deux fonction, on dit que $f$ est dominée par $g$ si et seulement si :
$$\exists C > 0, \; \forall n_0 \geq n \quad f(n)\leq C g(n)$$
Dans ce cas on notera : $f(n) = O(g(n))$.
En français, on cherche un rang strictement positif $n_0$ à partir duquel $f$ est plus petit ou égal à $g$.
En gros, si $f=\Theta(g)$ ça revient à dire que les fonctions $f$ et $g$ se dominent mutuellement, autrement dit qu'elles croient de manière proportionnelle, qu'elles ont la même allure, la même complexité.
Soit $\mathcal{A}$ un algorithme, on introduit ici trois complexités selon les cas :
Pour la complexité d’une boucle for à $n$ itérations et $k$ (constant) opérations élémentaire On va avoir une complexité en $\mathcal{O}(nk)$ mais, puisque $k$ est une constante, on peut la négliger et on se retrouve dans le pire, le meilleure des cas et en moyenne à $\mathcal{O}(n)$.
On considère les boucles suivantes :
for i de 1 à N-1 for j de 0 à N-i Comparer T[j], T[j+1] peut être changer j, j+1
Ici, on dispose de deux boucles : une sur i et une sur j. Puis on admet aussi deux opérations élémentaires qui s'effectue en un temps constant : comparer et changer.
Étudions les boucles de plus près :
i va de 1 à N-1. N-1 fois dans tous les cas.j va de 0 à N-ij démarre de 0 alors on ajoute obligatoirement un tour de boucle supplémentaire quelque soit N.N-i+1 fois pour tous les N.D'où les opérations élémentaires s'exécutent :
$$S_n=\underset{i=1}{\overset{N-1}{\sum}}(N-i+1) \times k$$
fois.
Où $k$ est constant et représente le nombre d'opération élémentaire.
La somme $S_n$ elle regroupe toutes les comparaisons effectuées pendant l'exécution de l'algorithme.
Calculons l'ordre de grandeur de l'exemple
On a :
$$\begin{align*}S_N &= \sum_{i=1}^{N-1} (N-i+1) \cdot k \\&= k \sum_{i=1}^{N-1} \big((N+1) - i\big) \\&= k \left( \sum_{i=1}^{N-1} (N+1) - \sum_{i=1}^{N-1} i \right) \\&= k \left( (N-1)(N+1) - \frac{(N-1)N}{2} \right) \\&= k \left( N^2 - 1 - \frac{N^2 - N}{2} \right) \\&= k \left( \frac{2N^2 - 2 - N^2 + N}{2} \right) \\&= k \cdot \frac{N^2 + N - 2}{2} \\&= O(N^2)\end{align*}$$
Ainsi la complexité des boucles précédentes est donnée par :
$$O(N^2)$$
à retenir sur les sommes, connu depuis algèbre de base… en ajoutant les aspects de l’algorithmique et des complexités
$$\underset{i=1}{\overset{N}{\sum}}k=k \times N = \mathcal{O}(N)$$
$$\underset{i=1}{\overset{N}{\sum}}ik = k \times \underset{i=1}{\overset{N}{\sum}}i=k \times \frac{N(N+1)}{2}=\mathcal{O}(N^2)$$
$$\begin{align*} \sum_{i=1}^{N-1}(N-i)k &= k \times \sum_{i=1}^{N-1}(N-i) \\ &= k \times \left( \sum_{i=1}^{N-1}N - \sum_{i=1}^{N-1}i \right) \\ &= k \times \left( N(N-1) - \frac{N(N-1)}{2} \right) \\ &= k \times \left( \frac{2N(N-1) - N(N-1)}{2} \right) \\ &= k \times \left( \frac{N(N-1)}{2} \right) \\ &= \mathcal{O}(N^2) \end{align*} $$
$$\begin{align*} \sum_{i=1}^{N}\sum_{i=1}^{N}k &= \sum_{i=1}^{N}1 \times \sum_{i=1}^{N}1 \times k \\ &= N \times N \times k \\ &= \mathcal{O}(N^2 + k) = \mathcal{O}(N^2) \end{align*}$$
On considère l'algorithme suivant :
for i de 1 à N for j de 1 à N for l de 1 à N // Instructions constantes OE
On a alors la complexité suivante :
$$\underbrace{\underset{i=1}{\overset{N}{\sum}}}_{for_i}\underbrace{\underset{j=1}{\overset{N}{\sum}}}_{for_j}\underbrace{\underset{l=1}{\overset{N}{\sum}}}_{for_l}k=\mathcal{O}(N^3+k)=\mathcal{O}(N^3)$$
Un algorithme récursif est une méthode permettant de resourdre des problèmes en s’appelant elle-même, afin de résoudre des sous-problèmes du même type. généralement la récursivité est utilisé pour des problèmes qui veut être divisés en sous-problèmes similaires.
Un algorithme récursif nécessite :
Pour mieux comprendre la notion de récursivité prenons un exemple concret
L'algorithme de recherche dichotomique (ou recherche binaire) est un algorithme efficace permettant de rechercher un élément dans un tableau trié. Il repose sur le principe des méthodes "diviser pour régner" en réduisant l'espace de recherche de moitié à chaque étape.
Principe de base :
Entrées :
Sortie :
Algorithme rechDico(D, x, debut, fin) if debut > fin return -1 // croisement d'indice, élément non trouvé milieu = (debut + fin) DIV 2 elemMiddle = D[milieu] if elemMiddle = x return milieu // élément trouvé, retourne sa position else if x < elemMiddle return rechDico(D, x, debut, milieu - 1) // chercher dans la moitié gauche else return rechDico(D, x, milieu + 1, fin) // chercher dans la moitié droite Fin Algorithme
Dans cet algorithme, la complexité du nombre d'OE (hors appels récursifs) ne sera pas la même selon els cas dans lesquels on se trouve.
Pour le cas le plus favorable, l'élément recherché $x$ se trouve au milieu de l'algorithme. Dans ces cas là on trouve directement l'élément. $$O(1)$$
on ne peut pas déterminer car on a pas d’informations sur la taille des l’entrées ou autre. Pour ce faire il faudrait que l'on sache la probabilité des entrées par exemple.
L'élément recherché est :
L'algorithme va alors découper le tableau de moitié à chaque appel récursif jusqu'à ce qu'il ne reste qu'un seul et unique élément à comparer pour enfin le trouver.
Autrement dit le nombre d'opérations va être :
$$N \to \frac{N}{2} \to \frac{N}{4} \to \frac{N}{8} \to\ldots \to1 = O(log(N))$$
Ainsi dans le pire des cas la complexité de la recherche dichotomique est donnée par $$O(log(n))$$
Avec un nombre d'opération élémentaires qui suit une fonction $f(N)$ avec $N$ la taille de l'entrée, alors la complexité sera $NbAppels \times f(N)$. Le nombre d'opérations peut dépendre aussi de la taille des données traitées.
La taille des données par appels récursifs sont donnés par $N, N-1, N-2, ...$ de taille respectivement $T1, T2, ...$ et $f(T_i) = k \times T_i$(linéaire).
Alors la complexité au pire, lorsque l'on fait tous les appels de $1$ à $N$ est donnée par :
$$C = \sum_{i=1}^{N} k \times T_i = k \times \sum_{i=1}^{N} T_i = k \times N\times\frac{N+1}{2} = O(N^2)$$
On peut aussi avoir le cas où 2 appels sur une taille $T_i$ contiennent deux appels sur deux tailles différentes.
On considère la suite de Fibonacci définie par :
$$u_0=u_1=1 \quad\quad\quad \forall n \geq 2, \quad u_n=u_{n-1}+u_{n-2}$$
Ainsi, on obtient l'algorithmique récursif suivant :
Entrée :
Sortie :
Algorithme fibo if N = 0 or N = 1 return 1 else return fibo(N - 1) + fibo(N - 2) fin Algo
Alors pour un appel de rang $N$, on peut avoir deux appels $N-1$ puis $N-2$.
Ce qui abouti pour $N=6$ à l'arbre d'appels suivant :
On peut conjecturer que le nombre d'appels devient exponentiel lorsque $N$ devient grand.
Un algorithme est une suite finie et ordonnée d’instructions permettant de résoudre un problème ou d’accomplir une tâche. La notion de finitude est centrale dans cette définition : un algorithme doit nécessairement se terminer après un nombre fini d’étapes.
La finitude distingue l’algorithme d’un simple processus ou d’une procédure indéfinie. Un programme qui boucle sans fin, même s’il suit des règles précises, n’est pas un algorithme au sens strict, car il ne produit jamais de résultat final. Ainsi, garantir la terminaison est une condition fondamentale pour pouvoir juger de la correction et de l’efficacité d’un algorithme.
Cette exigence soulève des questions théoriques importantes. Par exemple, peut-on toujours savoir à l’avance si un algorithme se terminera ? Les travaux d’Alan Turing ont montré que ce n’est pas le cas : le problème de l’arrêt prouve qu’il est impossible, en général, de décider automatiquement si un algorithme quelconque finira son exécution. La finitude n’est donc pas seulement une contrainte pratique, mais aussi une limite fondamentale du calcul.
En pratique, la finitude est liée à la conception même des algorithmes : choix des conditions d’arrêt, bornes sur les boucles, diminution progressive des données traitées. Elle permet d’assurer que les ressources (temps, mémoire) restent contrôlées et que le résultat attendu sera effectivement produit.
Ainsi, la finitude des algorithmes constitue à la fois un principe fondateur de l’informatique, une exigence méthodologique pour le programmeur, et un enjeu théorique majeur dans l’étude des capacités et des limites du calcul automatique.
Un variant est une valeur qui diminue à chaque étape d’un algorithme et qui permet de montrer que l’algorithme va finir.
Considérons l'algorithme suivant :
tant que n > 0 : n = n - 1
n reste positif et diminue à chaque tour de boucle, il est alors le variant de notre algorithme.
Pour montrer qu’un algorithme est fini (= terminaison) il faut analyser s’il comporte un nombre fini d’étapes et s’il s’arrête après un temps fini pour toutes les entrées possibles.
On dit d’un algorithme qu’il est fini s’il se termine après un nombre fini d’étapes, quelque soit l’entrée choisie.
Objectifs :
Considérons l'algorithme suivant :
var D = LT - LA tant que D > 0 LA = LA+D LT = LT + D/2 D = LT-LA retourner LA
Dans notre algorithme, $D=L_T-L_A$. À chaque itérations Achille avance de $D$ la tortue avance de $D/2$. La nouvelle distance entre Achille et la Tortue est donnée par :
$$D_{new} = (L_T+D/2)-(L_A+D)=D/2$$
La distance est divisée par $2$ à chaque tour de boucle.
Ainsi on va avoir :
$$\frac{D}{2} \to \frac{D}{4} \to \frac{D}{8} \to \ldots \to 1 \to \frac{1}{2} \to \ldots \to \sim 0$$
La distance tend vers $0$ mais sera toujours plus grande. Ainsi la condition : D > 0 dans la boucle tant que est toujours vraie l'algorithme ne se terminera donc jamais.
Achille ne rattrapera JAMAIS la tortue.
En pratique, on ne manipule pas des réels mathématiques, mais des nombres flottants.
Problème clé : la précision est finie
Un double en Java a une précision limitée $\sim 10^{-16}$, et ne peut pas représenter des valeurs arbitrairement petites.
À un moment donné $D$ devient si petit qu’il est :
Donc la boucle suivante devient fausse.
while (D > 0)
L'algorithme se termine, ce qui signifie qu'Achille rattrape la tortue numériquement mais pas mathématiquement comme expliqué au dessus.
La correction d’un algorithme désigne la propriété selon laquelle un algorithme produit systématiquement le résultat attendu. Autrement dit, un algorithme est dit correct lorsqu’il fournit toujours une solution correcte pour toute les entrées valides.
Vérifier la correction d’un algorithme, c’est montrer qu’il fait ce qu’il est censé faire, pour toutes les entrées valides. Il existe plusieurs méthodes pour le démontrer formellement.
Cette méthode est surtout utilisée pour les algorithmes récursifs ou itératifs.
Elle se déroule en trois étapes :
Si les trois étapes sont vérifiées, l'algorithme est correct pour toutes les valeurs $k$ possible.
Cette méthode s’applique aux algorithmes qui utilisent des boucles.
Un invariant de boucle est une propriété qui est :
La démarche est la suivante :
Considérons un algorithme $\mathcal{A}$.
Précondition : $\phi(e)$ est un prédicat vraie pour toutes les entrées $e \in D_e$. Elle décrit ce qui doit être vraie avant l'exécution de l'algorithme.
Postcondition : On note $\psi(e, s)$ un prédicat qui vérifie si la sortie $s$ est correcte pour l'entrée $e$. Elle décrit ce qui doit être vraie après l'exécution de l'algorithme.
On considère l'algorithme suivant :
Algo puissanceDeux m = x pair = VRAI tant que (m>1) et pair pair = m est pair ? m = m DIV 2 retourner pair
On peut analyser l'algorithme.
Les étapes de l'algorithme :
On commence par associer à la variable m l'entier x testé et pair est initialisé à vrai. Tant que m est plus grand que $1$ et pair est vrai, on vérifie si m est pair et on associe le résultat du test dans la variable pair. On divise m par $2$. Lorsque l'on sorte de la boucle tant que, on retourne la valeur de pair.
Pourquoi peut-on dire que l'algorithme fonctionne ?
Par définition, un entier $x$ est une puissance de $2$ si il est positif strict et si il peut être diviser un certain nombre de fois par $2$ jusqu'à obtenir $1$ sans jamais devenir impair.
m est égal à $1$, et on renvoie vraie car $8$ est une puissance de $2$.m donne un entier impair plus grand que $1$ alors on s'arrête et on renvoie faux.Pour la notation formelle on a :
Correction partielle
m=x et pair = vraipair reste à vrai alors cela signifie que tous les m précédents sont pairs, condition nécessaire pour qu'un nombre soit une puissance de $2$.m <= 1 ou lorsque pair = faux, c'est à dire une division par $2$ donne un résultat impair. On note $V=m$ le variant mis en jeu car il décroit à chaque tour de boucle d'au moins $1$, alors à un moment donné on aura forcément m <= 1 dans ce cas la boucle s'arrête et l'algorithme renvoie la valeur de la variable pair.pair = vrai, $x$ sera forcément une puissance de $2$.Correction totale
m est divisée par $2$ à chaque tour de boucle, donc elle décroit strictement et attendra forcément une valeur plus petite que $1$ ou alors $1$ lui même, assurant la fin de la boucle tant que.Cherchons un invariant...
On appelle invariant une propriété qui reste vraie tout le long de l’exécution d’une boucle ou d’un programme, à chaque itération.
Si on reprend la boucle tant que :
tant que (m>1) et pair pair = m est pair ? m = m DIV 2
On a :
m une variable divisée par $2$ à chaque itération.Essayons de montrer $I$ à l'aide d'une preuve par récurrence.
Ainsi $$I=m \times 2^{0}+r \times 2^{-1}=x \times 1+0\times 2^{-1}=x$$ l'invariant $I$ est donc correct au début de l'algorithme.
On par de l'hypothèse de récurrence :
$$I=m_k2^k+r_k2^{k-1}$$
Pour le rang suivant on va diviser $m_k$ par 2 d'où : $$m_{k+1}=\left\lfloor\frac{m_k}{2}\right\rfloor \quad r_{k+1}=m_k \text{ MOD }2 \Longleftrightarrow m_k=2m_{k+1}+r_{k+1}$$
D'où on a :
$$\begin{align*}I&=m_k2^k+r_k2^{k-1}\\ &= (2m_{k+1}+r_{k+1})2^{k}+r_k2^{k-1}\\&=\underbrace{2^{k+1}m_{k+1}}_{\text{pEntière }i=k+1}+\underbrace{2^kr_{k+1}+r_k2^{k-1}}_{\text{reste de toutes les div}}\end{align*}$$
Ainsi à l'itération $k+1$ on retrouve bien le quotient de la division euclidienne de l’itération courante ainsi que le reste des itérations précédentes. La structure de l'invariant est globalement respectée à chaque itération.