19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Programmation
algorithmique

Une version à jour et éditable de ce livre est disponible sur Wikilivres,

une bibliothèque de livres pédagogiques, à l'URL :
[Link]

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

[Link] 1/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 2/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Introduction
Introduction

«
I conjecture that there is no good algorithm for the traveling
salesman problem. My reasons are the same as for any
mathematical conjecture: (1) It is a legitimate mathematical
possibility, and (2) I do not know.

»
— Jack Edmonds

Tout comme l'homme, la machine calcule ! Si vous avez déjà ouvert un livre de recettes de cuisine
ou déchiffré un mode d'emploi traduit directement du coréen pour faire fonctionner un
magnétoscope ou un répondeur téléphonique réticent, sans le savoir, vous avez déjà exécuté des
algorithmes. Les algorithmes sont des outils pour la résolution de problèmes. Évaluer leur
efficacité permet de classer ces problèmes selon leur difficulté intrinsèque.

Nous allons dans un premier temps définir précisément ce qu'est un algorithme. Nous présentons
ensuite les outils mathématiques nécessaires à l'évaluation de leur efficacité. Nous proposons une
typologie des problèmes de décision qui s'appuie sur la difficulté calculatoire de leur résolution.
Nous proposons également ce même type de typologie pour les problèmes de recherche.

Algorithme
Un algorithme est une procédure de calcul constituée d'une suite d'instructions, qui prend en
entrée une valeur ou un ensemble de valeurs et qui une fois exécutée correctement, conduit à un
résultat donné : une valeur ou un ensemble de valeur appelé sortie. Un algorithme est un outil de
résolution d'un problème abstrait bien défini. Celui-ci doit énoncer la relation désirée entre
l'entrée et la sortie en des termes généraux mais non-ambigus. Si l'algorithme est correct, la
sortie correspond au résultat désiré. On dit alors que l'algorithme résout le problème posé. Un
algorithme décrit une procédure de calcul spécifique pour établir cette relation. Il peut exister
plusieurs algorithmes candidats pour un problème donné. Il est alors nécessaire de les évaluer.

L'objectif fondamental de l'algorithmique est de permettre la description d'un module de

traitement indépendamment du langage de codage. La phase de codage ne devant alors pas
remettre en cause l'algorithme initial.

Tout algorithme est descriptible à l'aide de trois structures de contrôle fondamentales : la

séquence, l'alternative (si/alors) et l'itération (boucle). Il existe d'autres structures de
contrôle, comme le branchement explicite (GOTO), mais nous ne les utiliserons pas. Le GOTO est
un peu tombé en désuétude car il est avantageusement remplacé dans les langages de
programmation par des appels de sous-programmes (procédures, fonctions) ou des
déclenchements d'exceptions.

[Link] 3/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

. Sur une matrice de taille , on calcule coefficients multipliés par le

nombre d'opérations pour le calcul du coefficient . On arrive donc à une complexité en .

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

[Link] 4/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Lorsque la complexité d'un algorithme, en temps ou en espace, est exprimée sous la forme d'un
polynôme où est la taille de l'entrée et les 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 et par abus de langage . Cette
notation est explicitée de manière plus formelle dans la définition suivante.

Complexité d'un problème

La complexité d'un algorithme destiné à résoudre un problème ne doit pas être confondue avec la
complexité intrinsèque de ce problème. En effet, on peut concevoir plusieurs algorithmes de
complexités différentes pour résoudre un même problème. Voir Théorie_de_la_complexité_ pour
plus d'information sur la notion de complexité intrinsèque d'un problème algorithmique.

Notation
Nous utiliserons dans la suite de ce livre un formalisme permettant l'abstraction des algorithmes
que nous décrirons, de telle sorte qu'ils soient utilisables quel que soit le langage utilisé. Nous
donnerons l'équivalence en langage C++, en Pascal et en langage assembleur Intel pour chaque
mot clef. Le but n'est pas ici d'apprendre, ou bien de comparer ces différents langages, mais de
fournir des repères, des illustrations au formalisme choisi.

Notation des types de données

Types de données simples

Nous utiliserons cinq types de données :

Entier
Réel
Pointeur
Booléen
Caractère

On peut déclarer des variables de ces types de la manière suivante :

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

Pendant l'exécution d'un programme, la valeur associée à chaque variable est stockée en mémoire.
La position de cette valeur dans la mémoire est appelée son adresse. Selon le langage de
programmation utilisé, les adresses peuvent être manipulées comme les autres données (cas de C
et C++), et on parle alors de pointeurs, ou bien les adresses ne sont pas directement manipulables
(cas de Java, de Python, et généralement des langages fonctionnels).
[Link] 5/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Pour accéder au contenu de la mémoire pointée par une variable de type Pointeur, nous utiliserons
le caractère «*». Ainsi pour accéder au contenu de la variable pointée par le pointeur unPointeur,
on procèdera de la manière suivante :

* unPointeur

Ces notations se déclinent différemment dans différents langages :

En langage C++

int unEntier;
double unRéel;
char unCaractère;
bool unBooléen;
void * unPointeur;

En Pascal

unEntier : INTEGER;
unRéel : REAL;
unCaractère : CHAR;
unBooléen : BOOLEAN;
unPointeur : ^VOID;

En Assembleur Intel

L'assembleur Intel ne prend pas en compte les types de données, mais la taille des données à
réserver dans la mémoire. Ainsi, sur les architectures Intel 32 bits, la taille des données est la
suivante :

Entier : 4 octets ;
Réel : 8 octets ;
Caractère : 1 octet ;
Pointeurs : 4 octets.

En assembleur, la notion de booléen est exprimée par un entier égal (faux) ou différent de zéro
(vrai).

La traduction des déclarations proposées donne donc :

unEntier DD ?
unRéel DQ ?
unPointeur DD ?

Tableaux

On déclarera un tableau de la manière suivante :

[Link] 6/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

t[N] : tableau d'Entier

t est la variable et N est la taille du tableau. Si i est un entier inférieur à la taille du tableau, t[i]
désigne la valeur de la case i du tableau.

Types de données composés

Les types de données composés permettent de rassembler plusieurs variables sous un même nom.
Les variables ainsi rassemblées sont appellées les champs de l'enregistrement. Ils sont définis de la
manière suivante :

unEnregistrement : Enregistrement
unPremierEntier : Entier
unDeuxièmeEntier : Entier
unRéel : Réel
Fin Enregistrement

On accède aux membres d'un enregistrement en utilisant un «.». Dans l'enregistrement

précédement défini, pour accéder au champs unPremierEntier, on procèdera donc de la manière
suivante :

unEnregistrementInstancié : unEnregistrement
unEnregistrementInstancié.unPremierEntier

Ce qui correspond

En langage C ou C++

typedef struct unEnregistrement

{
int unPremierEntier ;
int unDeuxiemeEntier ;
double unReel ;
} unEnregistrement ;

En Pascal

TYPE
unEnregistrement=RECORD
unPremierEntier :INTEGER ;
unDeuxiemeEntier :INTEGER ;
unReel :REAL ;
END ;

[Link] 7/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

En Assembleur Intel

unEnregistrement STRUC
unPremierEntier DD
unDeuxiemeEntier DD
unReel DQ
unEnregistrement ENDS

Notation des instructions et structures de contrôle

Affectations

Nous noterons les affectations de la manière suivante :

uneVariable := uneExpression

Ce qui correspond

En langage C ou C++

uneVariable = uneExpression

En Pascal

uneVariable := uneExpression

En Assembleur Intel

MOV AX, uneExpression

MOV uneVariable, AX

Structure alternative Si

Les structures alternatives correspondent à des branchements dans l'exécution du code du

programme, activés ou non en fonction d'une condition booléenne. La condition correspond à
l'évaluation d'une instruction dont la valeur finale est booléenne (vrai ou faux), comme par
exemple : un test d'égalité ou d'infériorité.

SI condition
// Faire quelque chose
FIN SI

[Link] 8/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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 :

[Link] 9/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

; Faire quelque chose

FIN_SI :

Structure alternative Suivant

La structure suivant permet d'éviter une suite de Si imbriqués dans le cas fréquent où l'on doit
réaliser des traitements différents en fonction des valeurs d'une variable énumérable (entier).

unEntier : Entier

SUIVANT unEntier
val1 : // faire une chose
val2 : // faire autre chose
val3, val4, val5 : // faire autre chose, ici une énumération de valeurs
val6..val7 : // faire autre chose, ici un intervalle de valeurs
FIN SUIVANT

Il est aussi possible de décrire le cas ou aucune valeurs n'est trouvée

unEntier : Entier

SUIVANT unEntier
val1 : // faire une chose
val2 : // faire autre chose
val3, val4, val5 : // faire autre chose, ici une énumération de valeurs
val6..val7 : // faire autre chose, ici un intervalle de valeurs
SINON
// encore autre chose
FIN SUIVANT

Par exemple :

choix : entier

afficher menu
lire choix
suivant choix
1 : ajouter
2 : supprimer
3,5,6 : insérer
4 : copier
7..10 : fin := VRAI
sinon:

[Link] 10/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

afficher 'Entrer un nombre valide'

finsuivant

Structure itérative Pour

Cette structure itérative permet de répéter de façon inconditionnelle un nombre de fois connu à
priori un ensemble d'actions (ou instructions).

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

unEntier : Entier

POUR unEntier DE début À fin PAS pas

// Faire quelque chose
FIN POUR

Par exemple :

i : Entier

POUR i DE 1 À 100 // la pas vaut 1 par défaut

afficher i
FIN POUR

Remarque : le pour incrémente automatiquement la variable unEntier d'un pas à chaque

itération, cette variable ne doit donc pas être modifiée par ailleurs !

Structure itérative Tant que

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

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

TANTQUE condition
// Faire quelque chose
FIN TANTQUE

Par exemple :

tab[MAX] : tableau d'entiers

élémentCherché : entier
i : entier

i := 1
TANTQUE i <= MAX ET tab[i] != élémentCherché

[Link] 11/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

i := i + 1
FIN TANTQUE

Remarque : si dès le début la condition est fausse, le bloc d'instruction du tant que n'est jamais
exécuté (test préventif de condition avant toute action).

Structure itérative Jusqu'à

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

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

RÉPÉTER
// Faire quelque chose
JUSQU'À condition

Par exemple :

tab[MAX] : tableau d'entiers

élémentCherché : entier
i : entier

trouvé := FAUX
i := 1
RÉPÉTER
SI tab[i] = élémentCherché ALORS
trouvé := vrai
SINON
i := i + 1
FIN SI
JUSQU'À i > MAX OU trouvé

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

[Link] 12/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 13/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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 np

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

Algorithme simple

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é

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
[Link] 14/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

La valeur de l'exposant p en binaire s'exprime de la façon suivante :

Chaque bit de p est testé, s'il vaut 1, il faut multiplier le résultat temporaire par . La
relation mathématique entre les puissances est utilisée. Par exemple : .
Donc pour tous les bits de , on a :

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
devient très grand, devient négligeable devant . Pour de petites valeurs de , 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 et valant 100, le nombre
d'opérations sur une machine séquentielle est de l'ordre de , tandis que sur une machine à 64
processeurs on peut espérer un ordre de soit ou 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 ) est
négligeable devant un carré ou une exponentielle quand la taille du problème devient grande.

[Link] 15/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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.

[Link] 16/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 17/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Maths 1
Calcul de suites

Suite récurrente niveau 1

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

U0=1
Un+1=[Link]+8
Paramètres en entrée : l'entier N
Paramètres en sortie : l'entier U
Spécifications : U doit être égal à UN.
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

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

U0=1
Un+1=[Link]+n+4
Paramètres en entrée : l'entier N
Paramètres en sortie : l'entier U
Spécifications : U doit être égal à UN.
Algorithme :

u,n,i : Entier

u := 1
pour i de 0 à n - 1

[Link] 18/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

u := 3*u + i + 4
fin Pour

Suite récurrence niveau 3

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

U0=1
U1=1
Un+2=Un+1+Un
Paramètres en entrée : l'entier N
Paramètres en sortie : l'entier U
Spécifications : U doit être égal à UN.
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

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

U0=1
U1=17
Un+2=(n+4)*Un+1+[Link]+n
Paramètres en entrée : l'entier N
Paramètres en sortie : l'entier U
Spécifications : U doit être égal à UN.
Algorithme :

[Link] 19/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

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 :

n,s,i : Entier

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

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 à

Algorithme :

[Link] 20/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

[Link] 21/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 22/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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 avec

Paramètres en sortie : l'entier min.

Spécifications : min doit contenir la valeur du plus petit élément du tableau. Formellement :
. Avec le co-domaine (range en
anglais)de t.
Algorithme :

Soit

t[N] : Tableau d'Entier

// Soit
min : Entier
// Soit
i : Entier
// Soit
min := t[1];
//
pour i de 2 à N
//
si t[i] < min alors
//
min := t[i]
//
finsi
//
finPour
//

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 :

[Link] 23/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

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

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
[Link] 24/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

finsi
fin pour

Algorithme Recherche Dichotomique

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
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]
[Link] 25/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

t[j] := pro

Fin

Algorithmes de tri à Bulles

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

[Link] 26/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 27/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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.

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:

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.

[Link] 28/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

Tri linéaire

Tri par insertion

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

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.

[Link] 29/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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 .
Complexité en temps : en moyenne, dans le pire cas.

[Link] 30/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Nom anglais : quicksort.

Tri par base

Tri fusion
Complexité en temps :
Nom anglais : merge sort.

Tri par tas

Complexité en temps :
Nom anglais : heapsort.

Tri comptage

// Code java :présenté par simoelma

// [Link]:taille du tableau

static void triparcomptage(int T[])

{
int i,s=0,k;
int nb [] = new int [[Link]];
int res [] = new int [[Link]];
for(i=0;i<[Link];i++)
{
for(i=0;i<[Link];i++)
{
for(k=0;k<[Link];k++)
{
if(T[i]>T[k])
{
s++;
}
nb[i]=s;
}
res[nb[i]+1]=T[i];
s=0;
}
[Link]("***tableau est trie***\n");
for(i=0;i<[Link];i++)
{
[Link](res[i]+"");
}

[Link] 31/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

}
}

Tri par comparaison

Tri par dénombrement

Tri par paquets

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
Complexité en temps : la complexité en temps de ce tri dépend de son paramétrage et,
selon les cas, on trouve , , ou 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).

[Link] 32/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 33/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Les structures de données

Une structure de données permet de rassembler et d'encapsuler plusieurs données en un seul type,
manipulé par des fonctions.

[Link] 34/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 35/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

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

Complexité : O(N)

FONCTION SIMPLE_LISTE:RECHERCHER(LISTE, CLEF)

ELEMENT = [Link]
TANT QUE ELEMENT <> NIL ET [Link] <> CLEF
ELEMENT = [Link]
FIN TANT QUE'
RETOURNER ELEMENT
FIN FONCTION

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

Complexité : O(1)

[Link] 36/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

FONCTION SIMPLE_LISTE:SUIVANT(LISTE, ELEMENT)

RETOURNER [Link]
FIN FONCTION

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

Complexité : O(N)

FONCTION SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)

ELEMENT_COURANT := [Link]
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

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.

FONTION SIMPLE_LISTE: RECHERCHE(LISTE,CLEF)

RETOURNER RECH_REC([Link])
FIN FONCTION

FONCTION SIMPLE_LISTE: RECH_REC(ELEMENT, CLEF)

SI ELEMENT = NIL OU [Link] = CLEF
ALORS RETOURNER ELEMENT
SINON RETOURNER RECH_REC([Link])
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.

[Link] 37/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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)

FONCTION SIMPLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)

ELEMENT := [Link]
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT = ELEMENT
FIN FONCTION

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

ELEMENT

Complexité : O(1)

FONCTION SIMPLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)

SI [Link] = NIL ALORS
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT = NIL
SINON
NOUVEL_ELEMENT.SUIVANT := [Link]
[Link] := NOUVEL_ELEMENT
FIN SI
FIN FONCTION

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

ELEMENT

Complexité : O(N)

[Link] 38/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

FONCTION SIMPLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)

ELEMENT_PRECEDENT := SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)
SI ELEMENT_PRECEDENT = NIL ALORS
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT := ELEMENT
SINON
ELEMENT_PRECEDENT.SUIVANT := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT := ELEMENT
FIN SI
FIN FONCTION

Suppression

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

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
[Link] := ELEMENT_SUPPRIME.SUIVANT
FIN SI
FIN FONCTION

[Link] 39/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 40/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

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

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

FONCTION DOUBLE_LISTE:RECHERCHER(LISTE, CLEF)

ELEMENT := [Link]
TANT QUE ELEMENT != NIL ET [Link] != CLEF
ELEMENT := [Link]
FIN TANT QUE'
RETOURNER ELEMENT
FIN FONCTION

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

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

FONCTION DOUBLE_LISTE:SUIVANT(LISTE, ELEMENT)

RETOURNER [Link]
FIN FONCTION

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

[Link] 41/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Complexité : O(1)

FONCTION DOUBLE_LISTE:PRECEDENT(LISTE, ELEMENT)

RETOURNER [Link]
FIN FONCTION

Insertion

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

Complexité O(1)

FONCTION DOUBLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)

ELEMENT := [Link]
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT = ELEMENT
NOUVEL_ELEMENT.PRECEDENT = NIL
SI [Link] = NIL ALORS
[Link] := NOUVEL_ELEMENT
FIN SI
FIN FONCTION

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

ELEMENT

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)

SI [Link] = NIL ALORS
[Link] := NOUVEL_ELEMENT
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.PRECEDENT := NIL
NOUVEL_ELEMENT.SUIVANT := NIL
SINON
NOUVEL_ELEMENT.PRECEDENT := ELEMENT
NOUVEL_ELEMENT.SUIVANT := [Link]
SI [Link] != NIL ALORS
[Link] := NOUVEL_ELEMENT
SINON
[Link] := NOUVEL_ELEMENT
FIN SI
[Link] := NOUVEL_ELEMENT

[Link] 42/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

FIN SI
FIN FONCTION

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

ELEMENT

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)

SI [Link] = NIL ALORS
[Link] := NOUVEL_ELEMENT
[Link] := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT := NIL
NOUVEL_ELEMENT.PRECEDENT := NIL
SINON
NOUVEL_ELEMENT.SUIVANT := ELEMENT
NOUVEL_ELEMENT.PRECEDENT := [Link]
SI [Link] != NIL ALORS
[Link] := NOUVEL_ELEMENT
SINON
[Link] := NOUVEL_ELEMENT
FIN SI
[Link] := NOUVEL_ELEMENT
FIN SI
FIN FONCTION

Suppression

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)

SI ELEMENT_SUPPRIME.PRECEDENT != NULL ALORS
ELEMENT_SUPPRIME.[Link] := ELEMENT_SUPPRIME.SUIVANT
SINON
[Link] := ELEMENT_SUPPRIME.SUIVANT
FIN SI

SI ELEMENT_SUPPRIME.SUIVANT != NIL ALORS

ELEMENT_SUPPRIME.[Link] := ELEMENT_SUPPRIME.PRECEDENT
SINON
[Link] := ELEMENT_SUPPRIME.PRECEDENT

[Link] 43/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

FIN SI
FIN FONCTION

[Link] 44/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

[Link] 45/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

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

[Link] 46/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

Une recherche d'un élément se fera donc bien en 6 tests, et

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 ([Link]) /* Parcours préfixe sur le sous arbre gauche */

préfixe ([Link]) /* Parcours préfixe sur le sous arbre droit */

fin si

fin

Parcours infixe

Parcours en largeur

Arbres de recherche (triés)

Arbres de recherche équilibrés

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
GFDL inaltérables, sans texte de première page de couverture et
sans texte de dernière page de couverture.

Récupérée de « [Link]
title=Programmation_algorithmique/Version_imprimable&oldid=639939 »

[Link] 47/48
19/09/2023 21:55 Programmation algorithmique/Version imprimable — Wikilivres

La dernière modification de cette page a été faite le 7 mai 2020 à 17:55.

Les textes sont disponibles sous licence Creative Commons attribution partage à l’identique ; d’autres termes peuvent
s’appliquer.
Voyez les termes d’utilisation pour plus de détails.

[Link] 48/48