Programmation Algorithmique Introduction

Un livre de Wikibooks.

Algorithmique
Algorithmique
Sommaire
Modifier ce modèle

Sections

[modifier] 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.

[modifier] 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 décrivable à l'aide de trois structures fondamentales : la séquence, l'alternative et l'itération.

Un algorithme est dit structuré si il dispose d'un seul point d'entrée et un seul point de sortie et peut donc être schématisé comme un bloc d'instruction avec un début et une fin (interdiction d'utiliser le branchement explicite ou GOTO :).

[modifier] Analyse algorithmique

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.

[modifier] 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 ai 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) = θ(np). Cette notation est explicitée de manière plus formelle dans la définition suivante.

[modifier] 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 language 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.

[modifier] Types de données

[modifier] Types de données simples

Nous utiliserons cinq types de données.

  • Entier
  • Réel
  • Pointeur
  • Booléen
  • Caractère

Ils se définissent de la manière suivante :

unEntier : Entier
unRéel : Réel
unCaractère : Caractère
unBooléen : Booléen
unPointeur : Pointeur

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 contenue de la variable pointée par le pointeur unPointeur, on procèdera de la manière suivante :

* unPointeur

Ce qui correspond

  • 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 ?

[modifier] 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

[modifier] 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

[modifier] 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 :

[modifier] 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

[modifier] 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 A fin PAS pas
        // Faire quelque chose
FIN POUR

Par exemple :

i : Entier
 
POUR i DE 1 A 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 !

[modifier] Structure itérative Tant que

Cette structure itérative permet de répéter un ensemble d'instructions tant qu'une condition reste vrai.

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).

[modifier] Structure itérative Jusqu'à

Cette structure itérative permet de répéter un ensemble d'instructions jusqu'à ce qu'une condition devienne fausse.

La syntaxe générale d'une boucle jusqu'à est la suivante :

REPETER 
        // Faire quelque chose
JUSQU'A condition

Par exemple :

tab[MAX] : tableau d'entiers
élémentCherché : entier
i : entier

trouvé := FAUX
i := 1
REPETER 
        SI tab[i] = élémentCherché ALORS
                trouvé := vrai
        SINON
                i := i + 1
        FIN SI
JUSQU'A i > MAX OU trouvé

Remarque : le bloc d'instruction est exécuté une fois de manière inconditionnelle avant l'évaluation de la condition.

[modifier] Fonctions

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...

Par exemple, pour un produit de matrices, si l'on résonne 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 n \times n, on calcule n \times n coefficients multipliés par le nombre d'opérations pour le calcul du coefficient Cij. On arrive donc à une complexité en O(n3).

Récupérée de « http://fr.wikibooks.org/wiki/Programmation_Algorithmique_Introduction »