Programmation algorithmique/Introduction

Programmation algorithmique

• Introduction
• Nombre d'opérations optimal
• Mathématiques simples
• Tableaux : parcours, recherches
• Tris de tableaux
• Structures de données
  • Listes simplement chaînées
  • Listes doublement chaînées
  • Arbres

Introduction

«
	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

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é

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

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 $C_{ij}=\sum \limits _{k=1}^{n}{A_{ik}B_{kj}}$. Sur une matrice de taille $n\times n$, on calcule $n\times n$ coefficients multipliés par le nombre d'opérations pour le calcul du coefficient $C_{ij}$. On arrive donc à une complexité en $O(n^{3})$.

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

Lorsque la complexité d'un algorithme, en temps ou en espace, est exprimée sous la forme d'un polynôme $E/T(n)=\Sigma _{i=0}^{p}a_{i}n^{i}$ où $n$ est la taille de l'entrée et les $a_{i}$ 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 $T/E(n)\in \theta (n^{p})$ et par abus de langage $T/E(n)=\theta (n^{p})$. Cette notation est explicitée de manière plus formelle dans la définition suivante.

Complexité d'un problème

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

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

Types de données simples

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

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

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

Affectations

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

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

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

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

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'à

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.