Programmation algorithmique/Introduction
Introduction[modifier | modifier le wikicode]
| « | |
|
I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know. | |
| » | |
| — Jack Edmonds |
Tout comme l'homme, la machine calcule !
Si vous avez déjà ouvert un livre de recettes de cuisine ou déchiffré un mode d'emploi traduit directement du coréen pour faire fonctionner un magnétoscope ou un répondeur téléphonique réticent, sans le savoir, vous avez déjà exécuté des algorithmes.
Les algorithmes sont des outils pour la résolution de problèmes.
Évaluer leur efficacité permet de classer ces problèmes selon leur difficulté intrinsèque.
Nous allons dans un premier temps définir précisément ce qu'est un algorithme. Nous présentons ensuite les outils mathématiques nécessaires à l'évaluation de leur efficacité. Nous proposons une typologie des problèmes de décision qui s'appuie sur la difficulté calculatoire de leur résolution. Nous proposons également ce même type de typologie pour les problèmes de recherche.
Algorithme[modifier | modifier le wikicode]
Un algorithme est une procédure de calcul constituée d'une suite d'instructions, qui prend en entrée une valeur ou un ensemble de valeurs et qui une fois exécutée correctement, conduit à un résultat donné : une valeur ou un ensemble de valeur appelé sortie. Un algorithme est un outil de résolution d'un problème abstrait bien défini. Celui-ci doit énoncer la relation désirée entre l'entrée et la sortie en des termes généraux mais non-ambigus. Si l'algorithme est correct, la sortie correspond au résultat désiré. On dit alors que l'algorithme résout le problème posé. Un algorithme décrit une procédure de calcul spécifique pour établir cette relation. Il peut exister plusieurs algorithmes candidats pour un problème donné. Il est alors nécessaire de les évaluer.
L'objectif fondamental de l'algorithmique est de permettre la description d'un module de traitement indépendamment du langage de codage. La phase de codage ne devant alors pas remettre en cause l'algorithme initial.
Tout algorithme est descriptible à l'aide de trois structures de contrôle fondamentales : la séquence, l'alternative (si/alors) et l'itération (boucle). Il existe d'autres structures de contrôle, comme le branchement explicite (GOTO), mais nous ne les utiliserons pas. Le GOTO est un peu tombé en désuétude car il est avantageusement remplacé dans les langages de programmation par des appels de sous-programmes (procédures, fonctions) ou des déclenchements d'exceptions.
Un algorithme est dit structuré s'il dispose d'un seul point d'entrée et un seul point de sortie et peut ainsi être schématisé par un bloc d'instructions avec un début et une fin (interdiction d'utiliser le branchement explicite GOTO pour entrer n'importe où dans l'algorithme ou pour en sortir de n'importe où). Cette contrainte a pour but d'améliorer la facilité de compréhension et d'analyse des algorithmes.
Analyse algorithmique et complexité[modifier | modifier le wikicode]
Analyser un algorithme consiste à prévoir les ressources qui lui seront nécessaires, en temps et en espace, pour résoudre le problème. La taille de l'entrée est le nombre d'éléments constituant l'entrée. Elle dépend du problème, par exemple, la somme des tailles des listes dans le cas d'un problème de fusion de deux listes. Dans la plupart des cas le temps d'exécution et l'espace mémoire de stockage d'un algorithmique croissent en fonction de la taille de son entrée.
L'analyse empirique consiste à étudier la complexité d'un algorithme, en temps et en espace, de manière expérimentale. À cet effet, l'algorithme doit être implémenté et testé sur un ensemble d'entrées de tailles et de compositions différentes. Toutefois cette méthode ne permet de comparer des algorithmes qu'à la condition de disposer d'implémentations réalisées dans un même environnement informatique. D'autre part, les résultats obtenus ne sont pas nécessairement représentatifs de toutes les entrées.
L'analyse théorique consiste à évaluer un pseudo-code de l'algorithme. Le temps d'exécution d'un algorithme sur une instance, i.e. une donnée particulière de toutes les données, est le nombre d'opérations élémentaires exécutées, appelées précédemment instructions. L'espace mémoire d'un algorithme sur une instance est le nombre d'éléments manipulés en mémoire à un instant donné de la résolution. Le temps d'exécution pour une entrée quelconque est estimé par une borne supérieure : le temps d'exécution dans le pire des cas, en d'autres termes le plus long temps d'exécution pour une entrée quelconque. Le temps d'exécution peut parfois être estimé à l'aide du temps d'exécution moyen (ou espéré). Il en va de même pour l'espace mémoire.
Dans la grande majorité des cas, seul l'ordre de grandeur nous intéresse.
Complexité d'un algorithme[modifier | modifier le wikicode]
La notion de complexité est très importante en algorithmique. Elle consiste à compter le nombre d'opérations d'un algorithme en comptant par exemple les additions, les multiplications, les divisions, les puissances etc... Considérons par exemple un produit de matrices et résonnons d'une manière simple d'après la formule de base pour calculer la valeur d'un coefficient . Sur une matrice de taille , on calcule coefficients multipliés par le nombre d'opérations pour le calcul du coefficient . On arrive donc à une complexité en .
Chaque opération effectuée prend un certain temps. Cette durée étant variable selon la machine utilisée, on ne s'intéressera qu'au nombre d'opérations pour représenter la durée d'exécution d'un algorithme. On parle alors de complexité en temps. On peut aussi s'intéresser à la quantité de mémoire nécessaire pour exécuter un algorithme. On parlera alors de complexité en espace.
Efficacité asymptotique[modifier | modifier le wikicode]
Lorsque la complexité d'un algorithme, en temps ou en espace, est exprimée sous la forme d'un polynôme où est la taille de l'entrée et les sont des constantes, nous négligerons non seulement le coefficient constant du premier terme mais également les termes d'ordre inférieur. On note alors et par abus de langage . Cette notation est explicitée de manière plus formelle dans la définition suivante.
Complexité d'un problème[modifier | modifier le wikicode]
La complexité d'un algorithme destiné à résoudre un problème ne doit pas être confondue avec la complexité intrinsèque de ce problème. En effet, on peut concevoir plusieurs algorithmes de complexités différentes pour résoudre un même problème. Voir Théorie_de_la_complexité_ pour plus d'information sur la notion de complexité intrinsèque d'un problème algorithmique.
Notation[modifier | modifier le wikicode]
Nous utiliserons dans la suite de ce livre un formalisme permettant l'abstraction des algorithmes que nous décrirons, de telle sorte qu'ils soient utilisables quel que soit le langage utilisé. Nous donnerons l'équivalence en langage C++, en Pascal et en langage assembleur Intel pour chaque mot clef. Le but n'est pas ici d'apprendre, ou bien de comparer ces différents langages, mais de fournir des repères, des illustrations au formalisme choisi.
Notation des types de données[modifier | modifier le wikicode]
Types de données simples[modifier | modifier le wikicode]
Nous utiliserons cinq types de données :
- Entier
- Réel
- Pointeur
- Booléen
- Caractère
On peut déclarer des variables de ces types de la manière suivante :
unEntier : Entier unRéel : Réel unCaractère : Caractère unBooléen : Booléen unPointeur : Pointeur
Pendant l'exécution d'un programme, la valeur associée à chaque variable est stockée en mémoire. La position de cette valeur dans la mémoire est appelée son adresse. Selon le langage de programmation utilisé, les adresses peuvent être manipulées comme les autres données (cas de C et C++), et on parle alors de pointeurs, ou bien les adresses ne sont pas directement manipulables (cas de Java, de Python, et généralement des langages fonctionnels).
Pour accéder au contenu de la mémoire pointée par une variable de type Pointeur, nous utiliserons le caractère «*». Ainsi pour accéder au contenu de la variable pointée par le pointeur unPointeur, on procèdera de la manière suivante :
* unPointeur
Ces notations se déclinent différemment dans différents langages :
- En langage C++
int unEntier; double unRéel; char unCaractère; bool unBooléen; void * unPointeur;
- En Pascal
unEntier : INTEGER; unRéel : REAL; unCaractère : CHAR; unBooléen : BOOLEAN; unPointeur : ^VOID;
- En Assembleur Intel
L'assembleur Intel ne prend pas en compte les types de données, mais la taille des données à réserver dans la mémoire. Ainsi, sur les architectures Intel 32 bits, la taille des données est la suivante :
- Entier : 4 octets ;
- Réel : 8 octets ;
- Caractère : 1 octet ;
- Pointeurs : 4 octets.
En assembleur, la notion de booléen est exprimée par un entier égal (faux) ou différent de zéro (vrai).
La traduction des déclarations proposées donne donc :
unEntier DD ? unRéel DQ ? unPointeur DD ?
Tableaux[modifier | modifier le wikicode]
On déclarera un tableau de la manière suivante :
t[N] : tableau d'Entier
t est la variable et N est la taille du tableau. Si i est un entier inférieur à la taille du tableau, t[i] désigne la valeur de la case i du tableau.
Types de données composés[modifier | modifier le wikicode]
Les types de données composés permettent de rassembler plusieurs variables sous un même nom. Les variables ainsi rassemblées sont appellées les champs de l'enregistrement. Ils sont définis de la manière suivante :
unEnregistrement : Enregistrement unPremierEntier : Entier unDeuxièmeEntier : Entier unRéel : Réel Fin Enregistrement
On accède aux membres d'un enregistrement en utilisant un «.». Dans l'enregistrement
précédement défini, pour accéder au champs unPremierEntier, on procèdera donc de la manière
suivante :
unEnregistrementInstancié : unEnregistrement unEnregistrementInstancié.unPremierEntier
Ce qui correspond
- En langage C ou C++
typedef struct unEnregistrement
{
int unPremierEntier ;
int unDeuxiemeEntier ;
double unReel ;
} unEnregistrement ;
- En Pascal
TYPE unEnregistrement=RECORD unPremierEntier :INTEGER ; unDeuxiemeEntier :INTEGER ; unReel :REAL ; END ;
- En Assembleur Intel
unEnregistrement STRUC unPremierEntier DD unDeuxiemeEntier DD unReel DQ unEnregistrement ENDS
Notation des instructions et structures de contrôle[modifier | modifier le wikicode]
Affectations[modifier | modifier le wikicode]
Nous noterons les affectations de la manière suivante :
uneVariable := uneExpression
Ce qui correspond
- En langage C ou C++
uneVariable = uneExpression
- En Pascal
uneVariable := uneExpression
- En Assembleur Intel
MOV AX, uneExpression MOV uneVariable, AX
Structure alternative Si[modifier | modifier le wikicode]
Les structures alternatives correspondent à des branchements dans l'exécution du code du programme, activés ou non en fonction d'une condition booléenne. La condition correspond à l'évaluation d'une instruction dont la valeur finale est booléenne (vrai ou faux), comme par exemple : un test d'égalité ou d'infériorité.
SI condition // Faire quelque chose FIN SI
Il est aussi possible de décrire des branchements alternatifs
SI condition // Faire quelque chose SINON // Faire autre chose FIN SI
Ce qui correspond
- En langage C ou C++
if (/*condition*/)
{
// Faire quelque chose
}
else
{
// Faire autre chose
}
- En Pascal
IF TEST THEN
BEGIN
{Faire quelque chose}
END
ELSE
BEGIN
{Faire autre chose}
ELSE
END ;
- En Assembleur Intel
CMP AH, AL ; comparaison des registres AH et AL JE SI ; si les deux registres sont égaux ; aller à l'étiquette SI SINON : ; Faire autre chose JMP FIN_SI SI : ; Faire quelque chose FIN_SI :
Structure alternative Suivant[modifier | modifier le wikicode]
La structure suivant permet d'éviter une suite de Si imbriqués dans le cas fréquent où l'on doit réaliser des traitements différents en fonction des valeurs d'une variable énumérable (entier).
unEntier : Entier SUIVANT unEntier val1 : // faire une chose val2 : // faire autre chose val3, val4, val5 : // faire autre chose, ici une énumération de valeurs val6..val7 : // faire autre chose, ici un intervalle de valeurs FIN SUIVANT
Il est aussi possible de décrire le cas ou aucune valeurs n'est trouvée
unEntier : Entier SUIVANT unEntier val1 : // faire une chose val2 : // faire autre chose val3, val4, val5 : // faire autre chose, ici une énumération de valeurs val6..val7 : // faire autre chose, ici un intervalle de valeurs SINON // encore autre chose FIN SUIVANT
Par exemple :
choix : entier afficher menu lire choix suivant choix 1 : ajouter 2 : supprimer 3,5,6 : insérer 4 : copier 7..10 : fin := VRAI sinon: afficher 'Entrer un nombre valide' finsuivant
Structure itérative Pour[modifier | modifier le wikicode]
Cette structure itérative permet de répéter de façon inconditionnelle un nombre de fois connu à priori un ensemble d'actions (ou instructions).
La syntaxe générale d'une boucle Pour est la suivante :
unEntier : Entier
POUR unEntier DE début À fin PAS pas
// Faire quelque chose
FIN POUR
Par exemple :
i : Entier
POUR i DE 1 À 100 // la pas vaut 1 par défaut
afficher i
FIN POUR
Remarque : le pour incrémente automatiquement la variable unEntier d'un pas à chaque itération, cette variable ne doit donc pas être modifiée par ailleurs !
Structure itérative Tant que[modifier | modifier le wikicode]
Cette structure itérative permet de répéter un ensemble d'instructions tant qu'une condition reste vraie.
La syntaxe générale d'une boucle TantQue est la suivante :
TANTQUE condition
// Faire quelque chose
FIN TANTQUE
Par exemple :
tab[MAX] : tableau d'entiers
élémentCherché : entier
i : entier
i := 1
TANTQUE i <= MAX ET tab[i] != élémentCherché
i := i + 1
FIN TANTQUE
Remarque : si dès le début la condition est fausse, le bloc d'instruction du tant que n'est jamais exécuté (test préventif de condition avant toute action).
Structure itérative Jusqu'à[modifier | modifier le wikicode]
Cette structure itérative permet de répéter un ensemble d'instructions jusqu'à ce qu'une condition devienne vrai.
La syntaxe générale d'une boucle jusqu'à est la suivante :
RÉPÉTER
// Faire quelque chose
JUSQU'À condition
Par exemple :
tab[MAX] : tableau d'entiers
élémentCherché : entier
i : entier
trouvé := FAUX
i := 1
RÉPÉTER
SI tab[i] = élémentCherché ALORS
trouvé := vrai
SINON
i := i + 1
FIN SI
JUSQU'À i > MAX OU trouvé
Remarque : le bloc d'instruction est exécuté une fois de manière inconditionnelle avant l'évaluation de la condition.