Programmation algorithmique/Version imprimable
Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Programmation_algorithmique
Introduction
Introduction
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
modifierUn 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é
modifierAnalyser 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
modifierLa 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
modifierLorsque 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
modifierLa 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
modifierNous 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
modifierTypes de données simples
modifierNous 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
modifierOn 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
modifierLes 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
modifierAffectations
modifierNous 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
modifierLes 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
modifierLa 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
modifierCette 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
modifierCette 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'à
modifierCette 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
modifierCalcul de np
modifierBut: Élever un nombre entier n à la puissance p (entier également).
Algorithme simple
modifierL'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é
modifierCet 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 , , , , ... - 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
modifierToutes 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.
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
modifierSuite récurrente niveau 1
modifierOn veut évaluer le N-ième terme de la suite définie par :
- U0=1
- Un+1=3.Un+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
modifierOn veut évaluer le N-ième terme de la suite définie par :
- U0=1
- Un+1=3.Un+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 u := 3*u + i + 4 fin Pour
Suite récurrence niveau 3
modifierOn 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
modifierOn veut évaluer le N-ième terme de la suite définie par :
- U0=1
- U1=17
- Un+2=(n+4)*Un+1+2.Un+n
- 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 := 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
modifierSomme 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 à
- 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
modifierRecherche 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 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
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
modifierfonction 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
modifierAlgorithme 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
modifierAlgorithme 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
modifierTri 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:
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
modifierTri linéaire
modifierTri par insertion
modifierParamè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
modifierOn 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 .
- Complexité en temps : en moyenne, dans le pire cas.
- Nom anglais : quicksort.
Tri par base
modifierTri fusion
modifier- Complexité en temps :
- Nom anglais : merge sort.
Tri par tas
modifier- Complexité en temps :
- 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
modifierTri par dénombrement
modifierTri par paquets
modifierTri-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 , , 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
modifierCette 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
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
modifierRecherche d'un élément ayant une clé CLEF dans une liste
modifierComplexité : 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
modifierComplexité : 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
modifierComplexité : 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
modifierDe 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)
modifierComplexité 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
modifierInsertion d'un élément NOUVEL_ELEMENT en début de liste
modifierComplexité 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
modifierComplexité : 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
modifierComplexité : 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
modifierSuppression d'un élément ELEMENT_SUPPRIME d'une liste
modifierComplexité : 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
modifierRecherche 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
modifierComplexité : O(1)
FONCTION DOUBLE_LISTE:PRECEDENT(LISTE, ELEMENT) RETOURNER ELEMENT.PRECEDENT FIN FONCTION
Insertion
modifierInsertion d'un élément NOUVEL_ELEMENT en début de liste
modifierComplexité 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
modifierComplexité : 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
modifierComplexité : 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
modifierSuppression d'un élément ELEMENT_SUPPRIME d'une liste
modifierComplexité : 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
Un arbre est une structure de données hiérarchique sans cycle.
Principes
modifierUn arbre est constitué de nœuds. Chaque nœud contient lui-même un ensemble de nœuds "fils" (tableau ou liste selon l'implémentation).
Le premier nœud sans père, père de tous les autres est nommé "racine de l'arbre". Généralement, seul le nœud père est conservé dans une variable, car on peut obtenir les autres nœuds en parcourant l'arbre.
Il existe 2 méthodes classiques de parcours d'arbre :
- Parcours en Profondeur, on part de la racine et on descends jusqu'à une première feuille avant de passer aux nœuds suivants puis remonter. Dans cette représentation, les feuilles apparaissent aux côtés de leur arborescence.
- Parcours en Largeur, les élément du niveau courant sont traités puis on passe aux éléments du niveau suivant.
Les parcours en largeur sont plus difficiles à réaliser car, en l'absence de liens entre les nœuds d'un même niveau dans la structure de données, on utilise généralement une file pour stocker temporairement les nœuds à traiter dans l'ordre approprié. Cependant le parcours en profondeur peut avoir besoin d'une pile pour stocker les nœuds parents si le lien parent est absent de la structure de données des nœuds ; cette pile peut être implicite avec les algorithmes récursifs car il s'agit alors de la pile d'appel des fonctions.
Intérêt
modifierCertaines données présentent naturellement une structure d'arbre, par exemple les arbres de syntaxe dans un compilateur. Mais l'usage des arbres ne se limite pas à ces cas : ils sont notamment utilisés pour stocker des données de manière à accélérer leur temps d'accès par rapport au stockage dans un taleau ou dans une liste (complexité en temps logarithmique contre complexité en temps linéaire).
Le classement d'une série de données avec un arbre permet des recherches en log(N) si l'arbre est trié et « équilibré » (si dans tout l'arbre, pour 2 branches voisines, on a soit une longueur égale, soit une différence de longueur de 1 au maximum).
Il existe des algorithmes peu coûteux pour garder un arbre « équilibré » sur insertion ou suppression d'un élément.
Exemple :
Si chaque nœud a 2 fils, un arbre équilibré de 63 éléments aura une profondeur de seulement 6 :
- 1er niveau = 1 nœud racine
- 2e niveau = 2 nœuds
- 3e niveau = 4 nœuds
- …
- 6e niveau = 32 nœuds
Une recherche d'un élément se fera donc bien en 6 tests, et
- .
Algorithmes
modifierArbres binaires quelconques
modifierParcours en profondeur
modifierParcours préfixe
modifierfonction 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
modifierParcours en largeur
modifierArbres de recherche (triés)
modifierArbres de recherche équilibrés
modifierGFDL | 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. |