# Programmation algorithmique/Introduction

* 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
* 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
[ Modifier le sommaire ]

## Introduction

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 :
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 :
Ces notations se déclinent différemment dans différents langages :
* En langage C++
* En Pascal
* 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 :

#### Tableaux

On déclarera un tableau de la manière suivante :
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 :
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 :
Ce qui correspond
* En langage C ou C++
* En Pascal
* En Assembleur Intel

### Notation des instructions et structures de contrôle
#### Affectations

Nous noterons les affectations de la manière suivante :
Ce qui correspond
* En langage C ou C++
* En Pascal
* En Assembleur Intel

#### 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é.
Il est aussi possible de décrire des branchements alternatifs
Ce qui correspond
* En langage C ou C++
* En Pascal
* En Assembleur Intel

#### 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).
Il est aussi possible de décrire le cas ou aucune valeurs n'est trouvée
Par exemple :

#### 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 :
Par exemple :
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 :
Par exemple :
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 :
Par exemple :
Remarque : le bloc d'instruction est exécuté une fois de manière inconditionnelle avant l'évaluation de la condition.