Algorithmes - Généralités


Notion d'algorithme


Structures de contrôle

Tous les langages de programmation contiennent ces concepts. Nous présentons ici la syntaxe Maple qui nous servira de support à ce cours. Maple nous permettra d'écrire et de tester des algorithmes.
Les algorithmes que nous écrirons comportent avant tout des variables (chaînes de caractère) dont la valeur est modifiée lors de l'exécution de l'algorithme. On ne confondra pas l'affectation
> x:=3 ;
qui affecte la variable x à la valeur 3 à l'égalité
> x=3 ;
dont la valeur est vrai ou faux selon que x est égal ou pas à 3.
De plus en Maple, on peut manipuler le nom de la variable en l'entourant par le caractère '. On peut également vider le contenu d'une variable par la primitive unassign.

Procédures.

On peut regrouper certaines opérations dans des procédures autonomes.
Exemple
double:=proc(x)
         RETURN(2*x) ;
end;
sera utilisable de la manière suivante:
>double(5);
                         10
>i:=6:double(i);
                         12
Les procédures peuvent avoir plusieurs paramètres.

Complexité d'un algorithme

La complexité d'un algorithme se mesure essentiellement en calculant le nombre d'opérations élémentaires pour traiter une donnée de taille n. Les opérations élémentaires considérées sont
Le coût d'un algorithme A pour une donnée D est le nombre d'opérations élémentaires nécessaires au traitement de la donnée D et est noté coûtA(D).
MaxA(n)=max{coûtA(d),d donnée de taille n}
MinA(n)=min{coûtA(d),d donnée de taille n}
Il est quelquefois nécessaire d'étudier la complexité en mémoire lorsque l'algorithme requiert de la mémoire supplémentaire (tableau auxiliaire de même taille que le tableau donné en entrée par exemple).


Exemple de calcul de complexité d'un algorithme : apparition d'un nombre dans une liste.


Soit L une liste de taille N contenant des nombres entiers de 1 à k. Soit a un entier entre 1 et k.
La fonction suivante retourne true lorsque l'un des éléments du tableau est égal à a, et false sinon.

Trouve:=proc(L,a)
        local i;
        for i from 1 to nops(L) do
                if op(i,L)=a then RETURN(true) fi;
        od;
        RETURN(false);
end;
Cas le pire : N (la liste ne contient pas a)
Cas le meilleur : 1 (le premier élément de la liste est a)
Complexité moyenne : Si les nombres entiers de 1 à k apparaissent de manière équiprobable, on  peut montrer que le coût moyen de l'algorithme est k (1 - (1 - 1/k)N).


 L'étude de la complexité est un domaine à part entière de l'algorithmique que nous n'aborderons pas dans ce cours.