Leçon 1: Un algorithme, c'est quoi ?

Leçon 1: Un algorithme, c'est quoi ?

Un algorithme est une procédure de calcul bien définie, qui prend en entrée une valeur, ou un ensemble de valeurs, et qui produit après un nombre fini d’opérations une valeur, ou un ensemble de valeurs.

Problèmes algorithmiques

2 sortes de problèmes : 

• les problèmes de décision : répondre par oui ou non 
• les problèmes d’optimisation : trouver la "meilleure" solution en fonction de données selon des critères bien définis. Chaque jeu de données fournit une instance du problème.

Algorithmes itératifs

Itération 

Une itération est la répétition d’un bloc d’instructions dans un programme informatique. Par abus de langage, on limitera les itérations aux répétitions dans les structures de contrôle Tant que (while) et Pour (for). 

Un algorithme itératif est un algorithme utilisant une ou plusieurs itérations

Exemple d’algorithme itératif

FONCTION : AlgoMul (E x : nombre, E n : entier) : nombre 

SPÉCIFICATIONS : Renvoie x n avec (x, n) 6= (0, 0)

Variable : y : nombre

DÉBUT

     y := 1 ; 

    pour i:=1 à n faire 

            y := y*x 

    fin pour; 

    Retourner : y 

FIN

Etude d’un algorithme

Critères d’un bon algorithme

On mesure la qualité d’un algorithme selon 3 critères : 

• Sa terminaison : est-ce que l’exécution de l’algorithme se termine ? 
• Sa correction : est-ce que l’algorithme renvoie le bon résultat ? 
• Sa complexité : est-ce que l’algorithme est efficace ? Nous évaluons ces trois critères sur l’exemple précédent.

Terminaison de l’algorithme AlgoMul

Méthode pour prouver une terminaison d’algorithme itératif

On montre que le nombre d’étapes est borné. Pour un Pour c’est évident, pour un Tant que on peut chercher une expression entière et positive qui décroît strictement à chaque itération.

 Exemple 

Dans l’algorithme algoMul, l’indice i parcourt tous les entiers de 1 à n et ainsi l’algorithme termine.

Correction d’un algorithme itératif

Un invariant de boucle est une égalité reliant les variables et les données de l’algorithme qui reste vraie à chaque itération

Notation

 On note Vi la valeur de la variable V à la fin de l’itération i.

Méthode pour prouver une correction d’algorithme itératif

• on conjecture un invariant
• on le montre par récurrence sur le nombre d’itérations
• on l’écrit à la fin des itérations
• on en déduit le résultat de l’algorithme.

Correction de l’algorithme AlgoMul

Eexemple

DEBUT

    y:=1;

    pour i := 1 à n faire

            y := y*x

    fin pour;

            Retourner : y 

FIN

1. On conjecture l’invariant Invi : "Après i tours de boucle, yi = x^i "
2. On le montre par récurrence sur i :
1.  Initialisation : pour i = 0, avant la boucle, y = 1 = x^0 donc Inv0 est vrai.
2. Récurrence : supposons Invi vrai : après i tours de boucle, yi = x i . Alors au tour de boucle suivant, yi+1 = yi × x = x^i × x = x^(i+1). Invi+1 est vrai. 
3. Conclusion : l’invariant est vrai sur toutes les itérations
3. A la fin des itérations, i = n et l’invariant devient yn = x^n . 
4. La valeur renvoyée par l’algorithme est bien x^n

Complexité de l’algorithme AlgoMul

La complexité en temps d’un algorithme est le nombre d’opérations élémentaires qu’il effectue. 

DEBUT

    y:=1;

    pour i :=1 à n faire

            y := y*x

    fin pour;

    Retourner : y 

FIN

AlgoMul effectue une affectation puis n itérations contenant chacune une multiplication et une affectation, soit 2n + 1 opérations. On dit qu’AlgoMul est de l’ordre de n.

Correction : L’algorithme mystère

DEBUT

    n := 0;

    tant que n < r faire

            n := n+1

    fin tq;

    Retourner : n 

FIN

• A(1, 6) = 2, A(2) = 2, A(r) = dr e partie entière supérieure de r
• Pour chaque itération, r − n > 0 donc dr e − n est un entier positif, qui décroît de 1 à chaque itération. Donc il y a un nombre fini d’itérations et l’algorithme s’arrête. 
• Comme n augmente de 1 en 1, n est le plus petit entier tel que la condition du Tant que est fausse i.e. tel que n ≥ r. C’est donc [r]