# Programmation algorithmique/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Programmation_algorithmique

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

# Nombre d'opérations optimal

La rapidité d'un algorithme est exprimée sous la forme du nombre d'opérations effectuées par celui-ci. En général, ce nombre dépend des données d'entrée.
Il existe différents nombres d'opérations :
* le nombre d'opérations minimal, qui se produit dans le meilleur des cas,
* le nombre d'opérations maximal, qui se produit dans le pire des cas,
* le nombre moyen d'opérations, qui est une moyenne de ce que l'on peut espérer d'un algorithme dans la plupart des cas.
Exemple : un algorithme de tri d'un tableau de n éléments effectuera un nombre moyen d'opérations dépendant de n (la taille du tableau) :
* L'algorithme de tri à bulle s'effectue en O(n²) ;
* L'algorithme de tri rapide (appelé Quicksort) s'effectue en moyenne en O(n*log(n)).

## Comparaison de quelques algorithmes
### Calcul de n$^p$

But: Élever un nombre entier n à la puissance p (entier également).

#### Algorithme simple

L'implémentation simple de cet algorithme est la suivante :
Cet algorithme s'effectue en O(p)

#### Algorithme plus compliqué

Cet algorithme est plus compliqué, mais effectue moins d'opérations que le précédent :
Cet algorithme s'effectue en O(log(p))
Cet algorithme fonctionne de la façon suivante :
* A chaque itération de la boucle, n vaut successivement $n$, $n^{2}$, $n^{4}$, $n^{8}$, ...
* La valeur de l'exposant p en binaire s'exprime de la façon suivante :
    $p=\sum _{i=0}^{\infty }p_{i}\times 2^{i}$
* Chaque bit $i$ de p est testé, s'il vaut 1, il faut multiplier le résultat temporaire par $n^{2^{i}}$. La relation mathématique entre les puissances est utilisée. Par exemple : $n^{2^{1}}\times n^{2^{3}}=n^{2^{1}+2^{3}}$. Donc pour tous les bits de $p$, on a :
    ${\begin{matrix}&&p_{0}\times n^{2^{0}}\times p_{1}\times n^{2^{1}}\times \cdots \\=&&n^{p_{0}\times 2^{0}+p_{1}\times 2^{1}+\cdots }\\=&&n^{p}\end{matrix}}$
Nous avons donc ici deux algorithmes qui calculent le même résultat mais en effectuant des opérations différentes. Le second algorithme est bien plus rapide que le premier car lorsque $n$ devient très grand, $log(n)$ devient négligeable devant $n$. Pour de petites valeurs de $n$, le second algorithme peut être plus lent.
Dans cet exemple, l'algorithme le plus rapide est aussi le plus compliqué à écrire et à comprendre, mais ce n'est pas toujours le cas.

## Machine séquentielle, machine parallèle, machine quantique

Toutes les complexités indiquées ici valent pour des machines séquentielles, c'est à dire une machine munie d'un seul processeur, ou bien une machine multi-processeurs sur laquelle on n'utiliserait qu'un seul cœur. D'ailleurs, le langage algorithmique que nous utilisons décrit uniquement des séquences d’instructions et d'opérations.
Notons que le facteur d'accélération amené par une machine parallèle, c'est-à-dire munie de plusieurs processeurs, est limité. Par exemple, pour une machine à 64 processeurs, on peut espérer aller 64 fois plus vite au maximum. Pour un algorithme en $O(2^{n})$ et $n$ valant 100, le nombre d'opérations sur une machine séquentielle est de l'ordre de $2^{100}$, tandis que sur une machine à 64 processeurs on peut espérer un ordre de $(2^{100})/64$ soit $(2^{100})/(2^{6})$ ou $2^{94}$ opérations. On voit bien ici que le nombre de processeurs, forcément limité, n'influence pas forcément la complexité en temps. Ceci s'explique également par le fait qu'un facteur multiplicatif constant (ici $1/64$) est négligeable devant un carré ou une exponentielle quand la taille du problème devient grande.
Quant aux machines quantiques, qui sont loin d'être exploitables actuellement, leur utilisation remettrait à plat l'état de l'art en algorithmique et en complexité. Par exemple, pour des problèmes dont on ne connaît que des algorithmes de complexité en temps exponentielle, on connaît des algorithmes quantiques de complexité linéaire. Alors qu'il faut actuellement des dizaines d'années à des machines parallèles surpuissantes pour casser une clé de chiffrement, un ordinateur quantique mettrait quelques instants.

# Maths 1
## Calcul de suites
### Suite récurrente niveau 1

On veut évaluer le N-ième terme de la suite définie par :
* U$_0$=1
* U$_{n+1}$=3.U$_n$+8
* Paramètres en entrée : l'entier N
* Paramètres en sortie : l'entier U
* Spécifications : U doit être égal à U$_N$.
* Algorithme :

### Suite récurrence niveau 2

On veut évaluer le N-ième terme de la suite définie par :
* U$_0$=1
* U$_{n+1}$=3.U$_n$+n+4
* Paramètres en entrée : l'entier N
* Paramètres en sortie : l'entier U
* Spécifications : U doit être égal à U$_N$.
* Algorithme :

### Suite récurrence niveau 3

On veut évaluer le N-ième terme de la suite de Fibonacci définie par :
* U$_0$=1
* U$_1$=1
* U$_{n+2}$=U$_{n+1}$+U$_n$
* Paramètres en entrée : l'entier N
* Paramètres en sortie : l'entier U
* Spécifications : U doit être égal à U$_N$.
* Algorithme :

### Suite récurrence niveau 4

On veut évaluer le N-ième terme de la suite définie par :
* U$_0$=1
* U$_1$=17
* U$_{n+2}$=(n+4)*U$_{n+1}$+2.U$_n$+n
* Paramètres en entrée : l'entier N
* Paramètres en sortie : l'entier U
* Spécifications : U doit être égal à U$_N$.
* Algorithme :

## Calcul de somme
### Somme des N premiers entiers

* Paramètres en entrée : l'entier N
* paramètres en sortie : l'entier S
* Spécifications : S doit être égal à la somme des N premier entiers
* Algorithme :

## Calcul polynomial
### Évaluation d'un polynôme par l'algorithme de Horner

* Paramètres en entrée : Un tableau de N+1 réels TABLEAU REEL a[0..N] et un réel X.
* Paramètres en sortie : le réel P
* Spécifications : P doit être égal à $\sum _{i=0}^{N}a[i].X^{i}$
* Algorithme :

# Tableaux
## Algorithmes sur les tableaux
### Recherche du plus petit élément d'un tableau

* Paramètres en entrée : un tableau t de N entiers. On pourra identifier ce tableau à une fonction totale de l'intervale entier de 1 à N vers les nombres naturels (on identifie les entiers machines aux nombres naturels). Ce qu'on l'on peut noter $t\in 1\ldots N\to \mathbb {N}$ avec $N\in \mathbb {N} \land N\geq 1$
* Paramètres en sortie : l'entier min. $min\in \mathbb {N}$
* Spécifications : min doit contenir la valeur du plus petit élément du tableau. Formellement : $min\in ran(t)\land \forall x\cdot (x\in 1\ldots N\Rightarrow min\leq t(x))$. Avec $ran$ le co-domaine (range en anglais)de t.
* Algorithme :
Soit $min_{t}(m,a,b)=m\in ran(t)\land \forall x\cdot (x\in a\ldots b\Rightarrow m\leq t(x))$

### Recherche d'une valeur dans un tableau

* Paramètres en entrée : un tableau t de N entiers (indicé de 1 à N) et une valeur v
* Paramètres en sortie : le booléen trouvé et l'entier indice.
* Spécifications : le booléen trouvé doit être à vrai si v se trouve dans le tableau. La valeur d' indice est alors le plus petit indice de la case contenant la valeur v dans le tableau.
* Algorithme :

### Somme des éléments d'un tableau

* Paramètres en entrée : un tableau de N entiers
* Paramètres en sortie : l'entier s.
* Spécifications : s doit être égal à la somme des éléments du tableau.
* Algorithme :

### Recherche du nombre d'occurrences

* Paramètres en entrée : un tableau de N entiers et une valeur v
* Paramètres en sortie : l'entier nb.
* Spécifications : nb doit être égal au nombre de fois que la valeur v apparait dans le tableau.
* Algorithme :

## Algorithme Recherche Dichotomique

fonction rechercheDicho(e : entier, n : entier, t : tableau entier[0..n-1]):entier
Lexique :

## Algorithme d'échange

Algorithme Echange (t : tableau d'entiers ; i,j : entiers) { Echange le contenu des cases i et j dans le tableau t } Lexique pro : entier Début
Fin

## Algorithmes de tri à Bulles

Algorithme TriBulles

# Tris

Les algorithmes de tri vise à ordonnancer une séquence, en suivant un ordre total. Pour pouvoir être trié avec ces algorithmes, un ordre doit donc être établi sur les éléments à trier.
Cet ordre est implicite pour des entiers, il peut l'être moins sur des données plus complexes comme par exemple des nombres flottants ou des textes.

## Les algorithmes de tri
### Tri par sélection

* Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
* Spécifications : en sortie t doit être trié du plus petit au plus grand.
* Intuition : On cherche (on sélectionne) le plus petit élément du tableau et on le place en début de tableau, puis on cherche le plus petit élément dans le reste du tableau et on le place en seconde position dans le tableau, et ainsi de suite.
* Complexité en temps: $O(n^{2})$

### Tri bulle

* Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
* Spécifications : en sortie t doit être trié du plus petit au plus grand.

### Tri par insertion

Paramètre en entrée/sortie : Un tableau t de N entiers T[0..N]

### Tri rapide

On choisit le pivot de manière aléatoire dans le tableau. Ensuite on inverse le pivot de sa position à celle du premier élément du tableau (indice 1) puis on fait une comparaison avec tous les éléments du tableau. S'il y a un élément du tableau qui lui est supérieur, alors il y a échange des éléments. Cette comparaison s'arrêtera quand l'indice gauche du tableau (ici i) sera plus grand que l'indice droit du tableau (ici j). Après cet arrêt de la fonction Partitionner, on retourne l'indice j et on rappel la procédure Tri_rapide
* Complexité en espace : En raison des appels récursif, on a besoin d'une pile dont la taille est en $O(log(n))$.
* Complexité en temps : $O(n.log(n))$ en moyenne, $O(n^{2})$ dans le pire cas.
* Nom anglais : quicksort.

### Tri fusion

* Complexité en temps : $O(n.log(n))$
* Nom anglais : merge sort.

### Tri par tas

* Complexité en temps : $O(n.log(n))$
* Nom anglais : heapsort.

### Tri de Shell

* Complexité en temps : la complexité en temps de ce tri dépend de son paramétrage et, selon les cas, on trouve $O(n^{2})$, $O(n^{3/2})$, ou $O(n^{4/3})$ par exemple. Voir w:Shellsort, w:Tri_de_Shell ou The art of Computer Programming volume 3, Donald E. Knuth, Addison-Wesley.

## Tri de fichiers en mémoire externe

Cette section concerne le tri de données trop grandes pour être stockées en mémoire vive de l'ordinateur, et étant donc stockées sur des supports physiques comme des disques durs.
Notons que les périphériques de stockage sont généralement plus lents que la mémoire vive. Par ailleurs, autrefois le support externe de référence était la bande magnétique, avec pour résultat que le temps d'accès à une donnée dépend de sa position sur la bande, alors qu'en mémoire vive, le temps d'accès aux données ne dépend pas de leur emplacement (si l'on fait abstraction des questions de mémoire tampon).

# Les structures de données

Cette page est considérée comme une ébauche à compléter . Si vous possédez quelques connaissances sur le sujet, vous pouvez les partager en éditant dès à présent cette page (en cliquant sur le lien « »).
Ressources suggérées : Aucune (vous pouvez indiquer les ressources que vous suggérez qui pourraient aider d'autres personnes à compléter cette page dans le paramètre « ressources » du modèle engendrant ce cadre)
Une structure de données permet de rassembler et d'encapsuler plusieurs données en un seul type, manipulé par des fonctions.

# Listes simplement chaînées

à étoffer, clarifier, reformuler, etc...
Une liste simplement chaînée est une structure de données pouvant contenir plusieurs éléments. Chaque élément possède un pointeur vers l'élément suivant. La liste est un pointeur vers le premier élément de la liste. Le dernier élément pointe vers une adresse spécifique (notée NIL) pour signifier la fin de la liste.
La clef d'un élément est d'un type quelconque. On peut ajouter des informations utiles aux éléments.

## Recherche dans une liste chaînée
### Recherche d'un élément ayant une clé CLEF dans une liste

Complexité : O(N)

### Recherche de l'élément suivant un élément ELEMENT dans une liste

Complexité : O(1)

### Recherche de l'élément précédent un élément ELEMENT dans une liste

Complexité : O(N)

## Itération contre récursion

De nombreux problèmes sur les listes chaînées peuvent se traiter aussi bien de façon itérative (à l'aide de boucles) que de façon récursive (à l'aide d'appels récursifs de fonctions). La récursion (ou récursivité) se rattache plus à l'algorithmique fonctionnelle qu'à l'algorithmique impérative. Toutefois, les langages impératifs offrent souvent la possibilité de programmer par récursion, alors il est intéressant de choisir entre itération et récursion en toute connaissance de cause.
Voici donc un exemple d'algorithme utilisant la récursion, il s'agit de rechercher un élément dans une liste, comme plus haut.

### Recherche d'un élément ayant une clé CLEF dans une liste (version récursive)

Complexité en temps: O(N). Complexité en espace : O(N) ou O(1) selon le support d'exécution.
On notera que dans cet exemple on ne trouve ni affectation (ou assignation), ni séquence (succession inconditionnelle de deux instructions). Il s'agit donc bien d'un algorithme fonctionnel.
Selon le langage et le compilateur utilisé pour réaliser cet algorithme, les appels récursifs successifs seront stockés ou non en mémoire. On parle de pile d'appels récursifs. Dans le cas où le support d'exécution (c'est à dire l'interprète ou le code compilé) utilise une pile d'appels récursifs pour exécuter la fonction RECH_REC, la complexité en espace sera O(N), car pour chaque élément de la liste, on devra stocker en mémoire, sur la pile, l'information sur l'appel en cours. Dans le second cas, où le compilateur est capable de générer du code qui utilise un espace limité sur la pile, la complexité en espace sera O(1), comme pour la version itérative. À titre d'exemple, le compilateur GCC est capable de compiler certaines fonctions récursives écrites en C pour qu'elles utilisent un espace constant sur la pile, alors que l'interprète standard du langage Python empile systématiquement les appels récursifs.

## Insertion
### Insertion d'un élément NOUVEL_ELEMENT en début de liste

Complexité O(1)

### Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT

Complexité : O(1)

### Insertion d'un élément NOUVEL_ELEMENT dans une liste avant un élément ELEMENT

Complexité : O(N)

## Suppression
### Suppression d'un élément ELEMENT_SUPPRIME d'une liste

Complexité : O(N)

# Listes doublement chaînées

Une liste doublement chaînée permet de gagner en complexité sur l'insertion et la suppression par rapport à la liste simplement chaînée, en plus de permettre un parcours des elements à l'envers. Mais on utilise un pointeur supplémentaire par élément. Il faut donc maintenir cohérentes deux fois plus de variables que dans une liste simplement chaînée.

## Recherche dans une liste chaînée
### Recherche d'un élément ayant une clé CLEF dans une liste

(Idem listes simplement chaînées) Complexité : O(N)

### Recherche de l'élément suivant un élément ELEMENT dans une liste

(Idem listes simplement chaînées) Complexité : O(1)

### Recherche de l'élément précédent un élément ELEMENT dans une liste

Complexité : O(1)

## Insertion
### Insertion d'un élément NOUVEL_ELEMENT en début de liste

Complexité O(1)

### Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT

Complexité : O(1)

### Insertion d'un élément NOUVEL_ELEMENT dans une liste avant un élément ELEMENT

Complexité : O(1)

## Suppression
### Suppression d'un élément ELEMENT_SUPPRIME d'une liste

Complexité : O(1)

# Arbres

Cette page est considérée comme une ébauche à compléter . Si vous possédez quelques connaissances sur le sujet, vous pouvez les partager en éditant dès à présent cette page (en cliquant sur le lien « »).
Ressources suggérées : Aucune (vous pouvez indiquer les ressources que vous suggérez qui pourraient aider d'autres personnes à compléter cette page dans le paramètre « ressources » du modèle engendrant ce cadre)
Un arbre est une structure de données hiérarchique sans cycle.

## Principes

Un arbre est constitué de nœuds. Chaque nœud contient lui-même un ensemble de nœuds "fils" (tableau ou liste selon l'implémentation).
Le premier nœud sans père, père de tous les autres est nommé "racine de l'arbre". Généralement, seul le nœud père est conservé dans une variable, car on peut obtenir les autres nœuds en parcourant l'arbre.
Il existe 2 méthodes classiques de parcours d'arbre :
* Parcours en Profondeur, on part de la racine et on descends jusqu'à une première feuille avant de passer aux nœuds suivants puis remonter. Dans cette représentation, les feuilles apparaissent aux côtés de leur arborescence.
* Parcours en Largeur, les élément du niveau courant sont traités puis on passe aux éléments du niveau suivant.
Les parcours en largeur sont plus difficiles à réaliser car, en l'absence de liens entre les nœuds d'un même niveau dans la structure de données, on utilise généralement une file pour stocker temporairement les nœuds à traiter dans l'ordre approprié. Cependant le parcours en profondeur peut avoir besoin d'une pile pour stocker les nœuds parents si le lien parent est absent de la structure de données des nœuds ; cette pile peut être implicite avec les algorithmes récursifs car il s'agit alors de la pile d'appel des fonctions.

## Intérêt

Certaines données présentent naturellement une structure d'arbre, par exemple les arbres de syntaxe dans un compilateur. Mais l'usage des arbres ne se limite pas à ces cas : ils sont notamment utilisés pour stocker des données de manière à accélérer leur temps d'accès par rapport au stockage dans un taleau ou dans une liste (complexité en temps logarithmique contre complexité en temps linéaire).
Le classement d'une série de données avec un arbre permet des recherches en log(N) si l'arbre est trié et « équilibré » (si dans tout l'arbre, pour 2 branches voisines, on a soit une longueur égale, soit une différence de longueur de 1 au maximum).
Il existe des algorithmes peu coûteux pour garder un arbre « équilibré » sur insertion ou suppression d'un élément.
Exemple :
Si chaque nœud a 2 fils, un arbre équilibré de 63 éléments aura une profondeur de seulement 6 :
* 1er niveau = 1 nœud racine
* 2e niveau = 2 nœuds
* 3e niveau = 4 nœuds
* 6e niveau = 32 nœuds
Une recherche d'un élément se fera donc bien en 6 tests, et
    $64=2^{6}\Longrightarrow \log(64)=6\times \log(2)$.

## Algorithmes
### Arbres binaires quelconques
#### Parcours en profondeur
##### Parcours préfixe

fonction préfixe( A: nœud)
si A ‡ nil /* condition */
traitement (A.¨info) /* afficher l'information contenue dans le nœud */
préfixe (A.sag) /* Parcours préfixe sur le sous arbre gauche */
préfixe (A.sad) /* Parcours préfixe sur le sous arbre droit */
fin si
fin