Ceci est la version imprimable de Programmation algorithmique.

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.

Programmation algorithmique

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

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

Introduction

Introduction modifier

«
	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

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

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

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 modifier

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 modifier

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

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

Types de données simples modifier

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

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

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

Affectations modifier

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

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

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

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

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

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.

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 modifier

Calcul de n^p modifier

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

Algorithme simple modifier

L'implémentation simple de cet algorithme est la suivante :

ENTIER resultat
resultat <- 1
pour i de 1 à p
faire
  resultat <- resultat * n
finfaire

Cet algorithme s'effectue en O(p)

Algorithme plus compliqué modifier

Cet algorithme est plus compliqué, mais effectue moins d'opérations que le précédent :

ENTIER resultat
resultat <- 1
tantque p > 0
faire
  si p ET 1 <> 0 alors          # test du bit 0 de p
    resultat <- resultat * n
  finsi
  n <- n * n
  p <- p / 2   # division entière ou décalage de bits
finfaire

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 modifier

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 modifier

Suite récurrente niveau 1 modifier

On veut évaluer le N-ième terme de la suite définie par :

U₀=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 :

0/ début suite-1
1/ écrire ("n=")
   lire (n)
2/ U<-1 
  pour i de 1 a (n-1) faire :
  U<- 3*U+8
  fin pour
3/ fin suite-1

Suite récurrence niveau 2 modifier

On veut évaluer le N-ième terme de la suite définie par :

U₀=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 :

u,n,i : Entier

u := 1
pour i de 0 à n - 1
   u := 3*u + i + 4
fin Pour

Suite récurrence niveau 3 modifier

On veut évaluer le N-ième terme de la suite de Fibonacci définie par :

U₀=1
U₁=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 :

u,v,w,n,i : entier

v := 1
w := 1
si u=0 alors 
     u := w
sinon 
     si u = 1 alors
           u := v
     sinon 
           pour i de 2 à N - 2
                u := v+w
                w := v
                v := u
          fin pour
     fin si
fin si

Suite récurrence niveau 4 modifier

On veut évaluer le N-ième terme de la suite définie par :

U₀=1
U₁=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 :

u,v,w,n,i : Entier

v := 17
w := 1

si u = 0 alors 
     u := w
sinon 
     si u := 1 alors 
           u=v
     sinon 
           pour i de 2 à N - 2
                u := (i + 4)*v + 2*w + i
                w := v
                v := u
           fin pour
     fin si
fin si

Calcul de somme modifier

Somme des N premiers entiers modifier

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 :

n,s,i : Entier

s := 0
pour i de 1 à N
     s := s + i
fin pour

Calcul polynomial modifier

Évaluation d'un polynôme par l'algorithme de Horner modifier

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 :

a[0..N] : tableau de réel
x, i, p : réel

p := 0
pour i de 0 à n
   p := p*x + a[n - i]
fin pour

Tableaux

Algorithmes sur les tableaux modifier

Recherche du plus petit élément d'un tableau modifier

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

t[N] : Tableau d'Entier
// Soit  $t\in 1\ldots N\to \mathbb {N}$ 
min : Entier
// Soit  $min\in \mathbb {N}$ 
i : Entier
// Soit  $i\in \mathbb {N}$ 
min := t[1];
//  $min=t(1)$ 
pour i de 2 à N
      //  $i\in 2\ldots N\land min_{t}(m,1,i-1)$ 
      si t[i] < min alors
            //  $i\in 2\ldots N\land min_{t}(m,1,i-1)\land t(i)<min$ 
            min := t[i]
            //  $i\in 2\ldots N\land min_{t}(m,1,i)\land t(i)=min$ 
      finsi
      //  $i\in 2\ldots N\land min_{t}(m,1,i)$ 
finPour
// $min_{t}(m,1,N)$

Recherche d'une valeur dans un tableau modifier

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 :

t[N] : Tableau d'Entier
v : Entier
i, indice : Entier
trouve : Booleen;

trouve := FAUX
indice := -1
i := 0
tant que non trouve ET i <= N
    si t[i] = v alors 
          trouve := true
          indice := i
    sinon 
          i := i+1
    finsi
fin tant que

Somme des éléments d'un tableau modifier

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 :

t[N] : Tableau d'Entier
i : Entier

s := 0;
pour i de 1 à N
  s := s + t[i]
fin pour

Recherche du nombre d'occurrences modifier

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 :

t[N] : Tableau d'Entier
v : Entier
i, nb : Entier

nb := 0
pour i de 1 à N
   si t[i] = v alors
        nb := nb+1
   finsi
fin pour

Algorithme Recherche Dichotomique modifier

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

   début
       debut <- 0
       fin <- n-1
       trouve <- faux
       tant que debut <= fin et non trouve faire
           i <- (debut+fin)÷2
           si t[i] = e
               alors trouve <- vrai
               sinon si t[i] > e
                   alors fin <- i-1
                   sinon debut <- i+1
               fsi
           fsi
       ftant
       si trouve
           alors indice <- i
           sinon indice <- -1
       fsi
       retourne indice
   fin

Lexique :

   - e : entier, élément recherché
   - n : entier, taille du tableau
   - t : tableau entier[0..n-1], tableau trié par ordre croissant
   - debut : entier, début de la zone de recherche
   - fin : entier, fin de la zone de recherche
   - trouve : booléen, faux tant que l'élément cherché n'est pas trouvé
   - i : entier, indice de la case du milieu de la zone de recherche
   - indice : entier, indice de l'élément recherché ou -1 s'il n'est pas trouvé

Algorithme d'échange modifier

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

 pro  := t[i]
 t[i] := t[j]
 t[j] := pro

Fin

Algorithmes de tri à Bulles modifier

Algorithme TriBulles

Var i, X, c, n: Entier;
    tableau t[100]: Entier;
Début
    Ecrire("Saisir la borne supérieur du tableau :");
    Lire(n);
    Pour i := 1 à n Faire
        Ecrire("Donner la valeur de l’élément :");
        Lire(t[i]);
    Fin de Pour
    Faire
       Pour i := 1 à n-1 Faire
           c := 0;
           Si t[i] > t[i+1] Alors
               X := t[i];
               t[i] := t[i+1];
               t[i+1] := X; 
               c := 1;
           Fin de Si
       Fin de Pour
    Tant que (c = 1)
Fin

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 modifier

Tri par sélection modifier

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.

t[N] : tableau d'Entier
i, j, min, temp, indicemin : Entier

Pour i de 1 à N - 1
    //chercher le plus petit entier entre la position i et la fin du tableau
    min := t[i]
    indicemin := i
    Pour j de i + 1 à N
          Si t[j] < min 
             min := t[j]
             indicemin := j
          Fin si
    Fin pour
    // Échanger t[i] et t[indicemin]
    temp := t[i]
    t[i] := t[indicemin]
    t[indicemin] := temp 
Fin pour

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 modifier

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.

t[N] : tableau d'entier
i, nb, temp : entier

repeter
    nb := 0
    pour i de 1 à N - 1
        si t[i] > t[i+1] alors
          temp := t[i]
          t[i] := t[i+1]
          t[i+1] := temp
          nb <- nb + 1
        fin si
    fin pour
jusqu'à nb = 0

Tri bulle bidirectionnel modifier

Tri linéaire modifier

Tri par insertion modifier

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

i ,j ,x :Entiers;
pour i de 1 à n - 1 
    debut pour
         # mémoriser T[i] dans x
         x ← T[i];
         # décaler vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que x
         j ← i;
         tant que j > 0 et T[j - 1] > x
             T[j] ← T[j - 1];
             j ← j - 1;
         fin tant que;
         # placer x dans le "trou" que ça a laissé
         T[j] ← x;
    fin pour;  Fin;

Tri rapide modifier

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

FONCTION Partitionner ( A : tableau [1..n] d’Entiers, p : Entier, r : Entier) : Entier  
x, i, j, temp: Entier
bool: Booleen
Début
  x :=	A[p]
  i :=	p-1
  j :=	r+1
  bool := vrai
  Tant que (bool) Faire
    Répéter j := j-1 Jusqu'à A[j] <= x
    Répéter i := i+1 Jusqu'à A[i] >= x
    bool := faux
    Si  i < j  
      temp := A[i]
      A[i] := A[j]
      A[j] := temp
      bool := vrai
    Sinon
	Retourner j
    Fin si
  Fin tant que 
Fin

PROCÉDURE Tri_rapide(A : tableau [1..n], p : entier, r : entier) 
q : Entier
Début 
  Si  p < r  
    q := Partitionner(A,p,r)
    Tri_rapide(A,p,q)
    Tri_rapide(A,q+1,r)
  Fsi
Fin

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 par base modifier

Tri fusion modifier

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

Tri par tas modifier

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

Tri comptage modifier

// Code java :présenté par simoelma
// T.length:taille du tableau 

static void triparcomptage(int T[])	
{
	int i,s=0,k;
	int nb [] = new int [T.length];
	int res [] = new int [T.length];
	for(i=0;i<T.length;i++)
	{
		for(i=0;i<T.length;i++)
		{
			for(k=0;k<T.length;k++)
			{
				if(T[i]>T[k])
				{
					s++;
				}
				nb[i]=s;
			}
			res[nb[i]+1]=T[i];
			s=0;
		}	
		System.out.println("***tableau est trie***\n");
		for(i=0;i<T.length;i++)
		{
			System.out.println(res[i]+"");
		}	
	}	
}

Tri par comparaison modifier

Tri par dénombrement modifier

Tri par paquets modifier

Tri-paquet (A) :
n := longueur(A) ;
pour i de 1 à n
    faire insérer A[i] dans la liste B[ÎnA[i]°]
pour i de 0 à n-1
     faire trier la liste B[I] par le tri insertion
concaténer les listes B[0], B[1], …, B[n-1] dans l’ordre

Tri de Shell modifier

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 modifier

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

Ébauche (Liste complète des ébauches)

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 « modifier »).

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.

ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT : ELEMENT
FIN ENREGISTREMENT

LISTE : ENREGISTREMENT
   TETE : ELEMENT
FIN ENREGISTREMENT

Recherche dans une liste chaînée modifier

Recherche d'un élément ayant une clé CLEF dans une liste modifier

Complexité : O(N)

FONCTION SIMPLE_LISTE:RECHERCHER(LISTE, CLEF)
   ELEMENT = LISTE.TETE
   TANT QUE ELEMENT <> NIL ET ELEMENT.CLEF <> CLEF
      ELEMENT = ELEMENT.SUIVANT
   FIN TANT QUE'
   RETOURNER ELEMENT
FIN FONCTION

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

Complexité : O(1)

FONCTION SIMPLE_LISTE:SUIVANT(LISTE, ELEMENT)
   RETOURNER ELEMENT.SUIVANT
FIN FONCTION

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

Complexité : O(N)

FONCTION SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   ELEMENT_COURANT := LISTE.TETE
   TANT QUE ELEMENT_COURANT != NIL ET ELEMENT_COURANT.SUIVANT != ELEMENT
      ELEMENT_COURANT := ELEMENT_COURANT.SUIVANT
   FIN TANT QUE
   RETOURNER ELEMENT_COURANT
FIN FONCTION

Itération contre récursion modifier

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

Complexité en temps: O(N). Complexité en espace : O(N) ou O(1) selon le support d'exécution.

FONTION SIMPLE_LISTE: RECHERCHE(LISTE,CLEF)
  RETOURNER RECH_REC(LISTE.TETE)
FIN FONCTION

FONCTION SIMPLE_LISTE: RECH_REC(ELEMENT, CLEF)
  SI ELEMENT =  NIL OU ELEMENT.CLEF = CLEF 
    ALORS RETOURNER ELEMENT
    SINON RETOURNER RECH_REC(ELEMENT.SUIVANT)
FIN FONCTION

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 modifier

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

Complexité O(1)

FONCTION SIMPLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
    ELEMENT := LISTE.TETE
    LISTE.TETE := NOUVEL_ELEMENT
    NOUVEL_ELEMENT.SUIVANT = ELEMENT
FIN FONCTION

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

Complexité : O(1)

FONCTION SIMPLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT = NIL
   SINON
       NOUVEL_ELEMENT.SUIVANT := ELEMENT.SUIVANT
       ELEMENT.SUIVANT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

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

Complexité : O(N)

FONCTION SIMPLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)
   ELEMENT_PRECEDENT := SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   SI ELEMENT_PRECEDENT = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
   SINON
       ELEMENT_PRECEDENT.SUIVANT := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
   FIN SI
FIN FONCTION

Suppression modifier

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

Complexité : O(N)

FONCTION SIMPLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   ELEMENT_PRECEDENT := SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_PRECEDENT != NIL ALORS
      ELEMENT_PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI
FIN FONCTION

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.

ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT   : ELEMENT
   PRECEDENT : ELEMENT
FIN ENREGISTREMENT

LISTE : ENREGISTREMENT
   TETE  : ELEMENT
   QUEUE : ELEMENT
FIN ENREGISTREMENT

Recherche dans une liste chaînée modifier

Recherche d'un élément ayant une clé CLEF dans une liste modifier

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

FONCTION DOUBLE_LISTE:RECHERCHER(LISTE, CLEF)
   ELEMENT := LISTE.TETE
   TANT QUE ELEMENT != NIL ET ELEMENT.CLEF != CLEF
      ELEMENT := ELEMENT.SUIVANT
   FIN TANT QUE'
   RETOURNER ELEMENT
FIN FONCTION

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

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

FONCTION DOUBLE_LISTE:SUIVANT(LISTE, ELEMENT)
   RETOURNER ELEMENT.SUIVANT
FIN FONCTION

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   RETOURNER ELEMENT.PRECEDENT
FIN FONCTION

Insertion modifier

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

Complexité O(1)

FONCTION DOUBLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
   ELEMENT := LISTE.TETE
   LISTE.TETE := NOUVEL_ELEMENT
   NOUVEL_ELEMENT.SUIVANT = ELEMENT
   NOUVEL_ELEMENT.PRECEDENT = NIL
   SI LISTE.QUEUE = NIL ALORS
      LISTE.QUEUE := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := NIL
       NOUVEL_ELEMENT.SUIVANT = NIL
   SINON
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT.SUIVANT
       SI ELEMENT.SUIVANT != NIL ALORS
         ELEMENT.SUIVANT.PRECEDENT := NOUVEL_ELEMENT
       SINON
         LISTE.QUEUE := NOUVEL_ELEMENT
       FIN SI
       ELEMENT.SUIVANT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := NIL
       NOUVEL_ELEMENT.PRECEDENT := NIL
   SINON
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT.PRECEDENT
       SI ELEMENT.PRECEDENT != NIL ALORS
          ELEMENT.PRECEDENT.SUIVANT := NOUVEL_ELEMENT
       SINON
          LISTE.TETE := NOUVEL_ELEMENT
       FIN SI
       ELEMENT.PRECEDENT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

Suppression modifier

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_SUPPRIME.PRECEDENT != NULL ALORS
      ELEMENT_SUPPRIME.PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI

   SI ELEMENT_SUPPRIME.SUIVANT != NIL ALORS
      ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT
   SINON
      LISTE.QUEUE := ELEMENT_SUPPRIME.PRECEDENT
   FIN SI
FIN FONCTION

Arbres

Ébauche (Liste complète des ébauches)

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 « modifier »).

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 modifier

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

Intérêt modifier

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 :

1^er niveau = 1 nœud racine
2^e niveau = 2 nœuds
3^e niveau = 4 nœuds
…
6^e 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 modifier

Arbres binaires quelconques modifier

Parcours en profondeur modifier

Parcours préfixe modifier

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

Parcours infixe modifier

Parcours en largeur modifier

Arbres de recherche (triés) modifier

Arbres de recherche équilibrés modifier

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.

Programmation algorithmique/Version imprimable

Introduction

Introduction modifier

Algorithme modifier

Analyse algorithmique et complexité modifier

Complexité d'un algorithme modifier

Efficacité asymptotique modifier

Complexité d'un problème modifier

Notation modifier

Notation des types de données modifier

Types de données simples modifier

Tableaux modifier

Types de données composés modifier

Notation des instructions et structures de contrôle modifier

Affectations modifier

Structure alternative Si modifier

Structure alternative Suivant modifier

Structure itérative Pour modifier

Structure itérative Tant que modifier

Structure itérative Jusqu'à modifier

Nombre d'opérations optimal

Comparaison de quelques algorithmes modifier

Calcul de np modifier

Algorithme simple modifier

Algorithme plus compliqué modifier

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

Maths 1

Calcul de suites modifier

Suite récurrente niveau 1 modifier

Suite récurrence niveau 2 modifier

Suite récurrence niveau 3 modifier

Suite récurrence niveau 4 modifier

Calcul de somme modifier

Somme des N premiers entiers modifier

Calcul polynomial modifier

Évaluation d'un polynôme par l'algorithme de Horner modifier

Tableaux

Algorithmes sur les tableaux modifier

Recherche du plus petit élément d'un tableau modifier

Recherche d'une valeur dans un tableau modifier

Somme des éléments d'un tableau modifier

Recherche du nombre d'occurrences modifier

Algorithme Recherche Dichotomique modifier

Algorithme d'échange modifier

Algorithmes de tri à Bulles modifier

Tris

Les algorithmes de tri modifier

Tri par sélection modifier

Tri bulle modifier

Tri bulle bidirectionnel modifier

Tri linéaire modifier

Tri par insertion modifier

Tri rapide modifier

Tri par base modifier

Tri fusion modifier

Tri par tas modifier

Tri comptage modifier

Tri par comparaison modifier

Tri par dénombrement modifier

Tri par paquets modifier

Tri de Shell modifier

Tri de fichiers en mémoire externe modifier

Les structures de données

Listes simplement chaînées

Recherche dans une liste chaînée modifier

Recherche d'un élément ayant une clé CLEF dans une liste modifier

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

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

Itération contre récursion modifier

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

Insertion modifier

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

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

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

Suppression modifier

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

Listes doublement chaînées

Recherche dans une liste chaînée modifier

Recherche d'un élément ayant une clé CLEF dans une liste modifier

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

Calcul de n^p modifier