Algorithmique & Complexité

Cours Complet avec Corrigés d'Examens

Licence Professionnelle GL / SIAD  20182019

Contenu du document
➤ Chapitre 1 : Le pseudocode LDA complet
➤ Chapitre 2 : Rappels mathématiques et logiques
➤ Chapitre 3 : Évaluation de la complexité algorithmique
➤ Chapitre 4 : Algorithmes de recherche et de tri
➤ Chapitre 5 : Structures de données linéaires
➤ Chapitre 6 : Arbres (ABR, Tas, 2-3, AVL)
➤ Chapitre 7 : Graphes et algorithmes sur graphes
➤ Chapitre 8 : Techniques de programmation avancées
➤ Examens S1S7 : Corrigés complets pas à pas

Ce document est conçu pour des étudiants reprenant leurs études. Chaque notion est
construite depuis les bases.
Contents
1 Le Pseudocode  Langage de Description d'Algorithmes (LDA) 5
1.1 Qu'est-ce que le pseudocode LDA ? . . . . . . . . . . . . . . . . . . . . 5

1.2 Structure générale d'un algorithme LDA . . . . . . . . . . . . . . . . . 5

1.3 Les types de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 L'aectation et les opérateurs . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 L'aectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.2 Les opérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Les structures de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5.1 La structure conditionnelle SI . . . . . . . . . . . . . . . . . . . 8

1.5.2 La boucle TANT QUE (while) . . . . . . . . . . . . . . . . . . . 9

1.5.3 La boucle RÉPÉTER ... JUSQU'À (do while) . . . . . . . . . . 9

1.5.4 La boucle POUR (for) . . . . . . . . . . . . . . . . . . . . . . . 10

1.6 Les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.7 Les structures (enregistrements) . . . . . . . . . . . . . . . . . . . . . . 12

1.8 Les pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.9 Passage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.10 La récursivité en LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.11 Synthèse  Squelette complet LDA . . . . . . . . . . . . . . . . . . . . 14

2 Rappels Mathématiques et Logiques 16

2.1 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.1 Tables de vérité . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Sommes et séries usuelles . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Logarithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 Divisions entières et modulo . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Évaluation de la Complexité Algorithmique 19

2
CONTENTS Algorithmique & Complexité  GL/SIAD
3.1 Pourquoi mesurer la complexité ? . . . . . . . . . . . . . . . . . . . . . 19

3.2 Notation Grand O, Omega, Thêta . . . . . . . . . . . . . . . . . . . . . 19

3.3 Complexité des structures de contrôle . . . . . . . . . . . . . . . . . . . 20

3.3.1 Méthode de comptage par imbrication . . . . . . . . . . . . . . 20

3.4 Récurrences et Théorème Maître . . . . . . . . . . . . . . . . . . . . . . 20

3.4.1 Identier une récurrence . . . . . . . . . . . . . . . . . . . . . . 21

3.4.2 Le Théorème Maître . . . . . . . . . . . . . . . . . . . . . . . . 21

3.5 Cas de récurrence sans Théorème Maître . . . . . . . . . . . . . . . . . 21

3.5.1 Récurrence linéaire simple : déroulement . . . . . . . . . . . . . 21

4 Algorithmes de Recherche et de Tri 23

4.1 Recherche séquentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Recherche dichotomique (binaire) . . . . . . . . . . . . . . . . . . . . . 23

4.3 Tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.4 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.5 Tri à bulles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.6 Tri fusion (Merge Sort) . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.7 Tri par tas (Heap Sort) . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Structures de Données Linéaires 30

5.1 Tableaux dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2 Listes chaînées simples . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.1 Dénition et représentation . . . . . . . . . . . . . . . . . . . . 31

5.2.2 Opérations fondamentales . . . . . . . . . . . . . . . . . . . . . 31

5.2.3 Listes doublement chaînées . . . . . . . . . . . . . . . . . . . . . 33

5.3 Piles (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.4 Files (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6 Arbres 37
6.1 Concepts fondamentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.2 Arbres Binaires de Recherche (ABR) . . . . . . . . . . . . . . . . . . . 38

6.2.1 Les trois parcours . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.2.2 Recherche, insertion, suppression . . . . . . . . . . . . . . . . . 39

6.3 Tas (Heap) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.4 Arbres 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Graphes et Algorithmes sur Graphes 43

7.1 Dénitions fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . 43

3
Algorithmique & Complexité  GL/SIAD CONTENTS
7.2 Représentation d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . 43

7.2.1 Matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . 43

7.2.2 Liste d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.3 Parcours en largeur (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.4 Parcours en profondeur (DFS) . . . . . . . . . . . . . . . . . . . . . . . 45

7.5 Algorithme de Dijkstra  Plus court chemin . . . . . . . . . . . . . . . 46

8 Techniques de Programmation 48
8.1 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

8.2 Diviser pour Régner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.3 Programmation Dynamique . . . . . . . . . . . . . . . . . . . . . . . . 49

8.4 Algorithmes Gloutons (Greedy) . . . . . . . . . . . . . . . . . . . . . . 50

PARTIE III  Corrigés des Examens S1 à S7 52

S1  Rattrapage Semestre 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

S2  Listes & Toeplitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

S3  Crible, ABR et Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 57

S4  Reconstruction d'Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . 59

S5  Grandeurs, Carré Magique, Tas . . . . . . . . . . . . . . . . . . . . . . 60

S6  Preuves, Arbres 2-3, Fusion . . . . . . . . . . . . . . . . . . . . . . . . 61

S7  Tris et Listes de Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4
Chapitre 1
Le Pseudocode  Langage de Descrip-
tion d'Algorithmes (LDA)
1.1 Qu'est-ce que le pseudocode LDA ?
■ Dénition : Algorithme
Unalgorithme est une suite nie et non ambiguë d'instructions permettant de

Analogie
résoudre un problème.
: une recette de cuisine est un algorithme  elle décrit des étapes
précises pour produire un résultat à partir d'ingrédients.

Le LDA (Langage de Description d'Algorithmes) est un pseudocode en français

pont entre la pensée humaine et le code informa-

utilisé pour décrire des algorithmes de façon claire et indépendante de tout langage de

tique
programmation. Il sert de
.

Pourquoi utiliser le LDA ?

ˆ lisible
Il est par n'importe qui, même sans connaissance d'un langage de pro-

rééchir
grammation.
ˆ Il force à à la logique avant de coder.
ˆ Il est utilisé dans les examens pour écrire et évaluer des algorithmes.

1.2 Structure générale d'un algorithme LDA

LDA  Structure d'un algorithme complet
1 algorithme NomDeLAlgorithme
2

3 // Section des constantes ( optionnel )

4 constante MAX : entier <- 100
5

6 // Section des variables

7 variable n , i : entier

5
 CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
Algorithmique & Complexité  GL/SIAD D'ALGORITHMES (LDA)
8 variable x : reel
9 variable trouve : booleen
10 variable nom : chaine [50]
11

12 debut
13

14 // Corps de l ' algorithme : les instructions

15

16 fin

LDA  Structure d'une procédure

1 procedure NomProcedure ( param1 : type1 , param2 : type2 )
2 // Une proc é dure ne retourne rien
3 variable locale : entier
4 debut
5 // Instructions
6 fin
7

8 // Appel d ' une proc é dure :

9 NomProcedure ( valeur1 , valeur2 )

LDA  Structure d'une fonction

1 fonction NomFonction ( param1 : type1 ) : typeRetour
2 // Une fonction retourne une valeur
3 variable resultat : typeRetour
4 debut
5 // Instructions
6 retourner resultat
7 fin
8

9 // Appel d ' une fonction :

10 x <- NomFonction ( valeur1 )

✘ Attention
Diérence procédure / fonction : procédure
fonction
Une eectue des actions mais
aucune
ne retourne valeur. Une retourne
calcule et une valeur. En LDA,
on écrit retourner uniquement dans une fonction.

6
CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
D'ALGORITHMES (LDA) Algorithmique & Complexité  GL/SIAD
1.3 Les types de données
Type LDA Exemples de valeurs Description
entier −5, 0, 42, 1000 Nombres entiers (positifs ou né-
gatifs)
reel 3.14, −2.7, 0.0 Nombres à virgule ottante
booleen vrai, faux Valeur logique
caractere 'a', 'Z', '5' Un seul caractère (entre apostro-
phes)
chaine[n] "bonjour" Chaîne de caractères de longueur
max n
tableau[n] de type Tableau de n éléments d'un type
donné
pointeur vers type Référence vers une cellule d'un
type donné

1.4 L'aectation et les opérateurs

1.4.1 L'aectation
LDA  Aectation  la èche ←
1 // Syntaxe : variable <- expression
2 x <- 5 // x re ç oit la valeur 5
3 y <- x + 3 // y re ç oit la valeur de x +3 , soit 8
4 nom <- " Alice " // nom re ç oit la cha î ne " Alice "
5 ok <- vrai // ok re ç oit la valeur bool é enne vrai
6 tab [0] <- 10 // premier é lé ment du tableau re ç oit 10

✘ Attention
n'est pas = x ← 5 est
peut changer
← . En mathématiques, x = 5 est une équation. En LDA,
une action : on place la valeur 5 dans la variable x. La variable x
à tout moment.

7
 CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
Algorithmique & Complexité  GL/SIAD D'ALGORITHMES (LDA)
1.4.2 Les opérateurs
Catégorie Opérateur Signication Exemple
+ Addition a + b
- Soustraction a - b
Arithmétique * Multiplication a * b
/ Division réelle a / b
div Division entière 10 div 3 = 3
mod Modulo (reste) 10 mod 3 = 1
= Égal a = b
<> ou != Diérent a <> b
Comparaison
<, <= Inférieur, inf. ou égal a < b
>, >= Supérieur, sup. ou égal a > b
et ET logique a > 0 et b > 0
Logique ou OU logique a = 0 ou b = 0
non NON logique (négation) non trouve

1.5 Les structures de contrôle

1.5.1 La structure conditionnelle SI
LDA  Structure Si  3 formes
1 // Forme 1 : Si simple
2 si condition alors
3 // instructions si condition est vraie
4 fin_si
5

6 // Forme 2 : Si / Sinon
7 si condition alors
8 // instructions si vrai
9 sinon
10 // instructions si faux
11 fin_si
12

13 // Forme 3 : Si / Sinon Si / Sinon ( cha în é)

14 si x > 0 alors
15 afficher " positif "
16 sinon_si x < 0 alors
17 afficher " né gatif "
18 sinon
19 afficher " nul "
20 fin_si

8
CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
D'ALGORITHMES (LDA) Algorithmique & Complexité  GL/SIAD
✰ Exemple
Algorithme qui indique si un entier est pair ou impair :

1 algorithme PariteEntier
2 variable n : entier
3 debut
4 afficher " Entrez un entier : "
5 lire n
6 si n mod 2 = 0 alors
7 afficher n , " est pair "
8 sinon
9 afficher n , " est impair "
10 fin_si
11 fin

1.5.2 La boucle TANT QUE (while)

LDA  Boucle Tant Que  condition testée AVANT l'exécution
1 tant_que condition faire
2 // instructions r épé té es tant que condition est vraie
3 fin_tq
4

5 // Exemple : lire des entiers jusqu 'à 0

6 tant_que n <> 0 faire
7 afficher " Lu : ", n
8 lire n
9 fin_tq

✘ Attention
fausse dès le départ jamais
exécuté vraie
Si la condition est , le corps de la boucle n'est
. Assurez-vous que la condition est initialement si vous voulez
entrer dans la boucle.

1.5.3 La boucle RÉPÉTER ... JUSQU'À (do while)

LDA  Boucle Répéter  condition testée APRÈS au moins UNE exécu-
tion
1 repeter
2 // instructions ex é cut é es au moins une fois
3 jusqu_a condition_d_arret
4

5 // Exemple : saisie s é curis ée d ' un entier positif

6 repeter
7 afficher " Entrez un entier positif : "

9
 CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
Algorithmique & Complexité  GL/SIAD D'ALGORITHMES (LDA)
8 lire n
9 jusqu_a n > 0

1.5.4 La boucle POUR (for)

LDA  Boucle Pour  nombre d'itérations connu à l'avance
1 // Forme standard
2 pour i de valeur_debut a valeur_fin faire
3 // instructions
4 fin_pour
5

6 // Avec pas personnalis é

7 pour i de 0 a 100 par_pas_de 5 faire
8 afficher i // 0, 5, 10 , ... , 100
9 fin_pour
10

11 // Boucle d é croissante
12 pour i de n a 1 par_pas_de -1 faire
13 afficher i // n , n -1 , ... , 1
14 fin_pour

✰ Exemple
Calcul de la factorielle n! :

1 fonction factorielle (n : entier ) : entier

2 variable fact : entier
3 variable i : entier
4 debut
5 fact <- 1
6 pour i de 2 a n faire
7 fact <- fact * i
8 fin_pour
9 retourner fact
10 fin
11 // factorielle (5) retourne 1*2*3*4*5 = 120

10
CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
D'ALGORITHMES (LDA) Algorithmique & Complexité  GL/SIAD
1.6 Les tableaux
LDA  Déclaration et utilisation d'un tableau
1 // D é claration
2 variable tab : tableau [10] de entier // 10 cases ,
indices 0..9
3 variable mat : tableau [5][5] de reel // matrice 5 x5
4

5 // Acc è s aux é lé ments ( indices commen ç ant à 0)

6 tab [0] <- 42 // premi è re case
7 tab [9] <- -7 // derni è re case
8 mat [2][3] <- 3.14 // ligne 2, colonne 3
9

10 // Parcours complet d ' un tableau

11 pour i de 0 a 9 faire
12 afficher tab [ i]
13 fin_pour
14

15 // Exemple : remplissage et affichage d ' un tableau

16 algorithme ExempleTableau
17 variable notes : tableau [5] de reel
18 variable i : entier
19 debut
20 pour i de 0 a 4 faire
21 afficher " Note " , i +1 , " : "
22 lire notes [i ]
23 fin_pour
24 pour i de 0 a 4 faire
25 afficher " Note [" , i , "] = ", notes [ i]
26 fin_pour
27 fin

❖ P.S.  Pour approfondir

Convention d'indices : En LDA, les tableaux peuvent commencer à l'indice 0
(comme en C/Java) ou à 1 (comme en Pascal/algorithmique française classique).
Dans ce cours, on indiquera toujours explicitement la plage d'indices utilisée (ex:
tab[1..n] ou tab[0..n-1]).

11
 CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
Algorithmique & Complexité  GL/SIAD D'ALGORITHMES (LDA)
1.7 Les structures (enregistrements)
LDA  Dénition et utilisation d'une structure
1 // D é finition d ' une structure
2 structure Etudiant
3 numero : entier
4 nom : chaine [50]
5 prenom : chaine [50]
6 moyenne : reel
7 fin_structure
8

9 // D é claration d ' une variable de type structure

10 variable e1 : Etudiant
11

12 // Acc è s aux champs ( op é rateur ".")

13 e1 . numero <- 12345
14 e1 . nom <- " Dupont "
15 e1 . prenom <- " Alice "
16 e1 . moyenne <- 14.5
17

18 afficher e1 . nom , " " , e1 . prenom , " : ", e1 . moyenne

1.8 Les pointeurs

Les pointeurs sont essentiels pour implémenter des structures chaînées (listes, ar-
bres, graphes).

LDA  Pointeurs et allocation dynamique

1 // Un pointeur contient l ' adresse mé moire d ' une cellule
2 structure Noeud
3 valeur : entier
4 suivant : pointeur vers Noeud // pointe vers le noeud
suivant
5 fin_structure
6

7 variable p : pointeur vers Noeud

8 variable nul : pointeur = NULL // pointeur " vide " (
nil / null )
9

10 // Cr é er une nouvelle cellule dynamiquement

11 allouer (p) // ré serve de la m é moire , p pointe
vers la nouvelle cellule
12 p. valeur <- 42 // acc ès au champ via le pointeur
13 p. suivant <- NULL // le champ suivant pointe vers
rien

12
CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
D'ALGORITHMES (LDA) Algorithmique & Complexité  GL/SIAD
14

15 // V é rifier si un pointeur est vide

16 si p = NULL alors
17 afficher " pointeur vide !"
18 fin_si
19

20 // Lib é rer la mé moire allou ée

21 liberer (p) // rend la mé moire au syst è me

cellule allouée

p 42 ∅

valeur suivant

1.9 Passage de paramètres

LDA  Passage par valeur vs par référence
1 // Passage PAR VALEUR : la fonction travaille sur une COPIE
2 // Les modifications n ' affectent PAS la variable originale
3 fonction doubler_val (n : entier ) : entier
4 debut
5 n <- n * 2 // ne modifie que la copie locale
6 retourner n
7 fin
8

9 // Passage PAR RÉ FÉ RENCE ( mot - cl é " ref " ou "&")

10 // Les modifications affectent la variable originale
11 procedure echanger ( ref a : entier , ref b : entier )
12 variable temp : entier
13 debut
14 temp <- a
15 a <- b
16 b <- temp
17 fin // a et b sont vraiment é chang és apr è s l ' appel !
18

19 // Exemple d ' appel :

20 variable x , y : entier
21 x <- 5 ; y <- 10
22 echanger (x , y )
23 // maintenant x = 10 et y = 5

13
 CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
Algorithmique & Complexité  GL/SIAD D'ALGORITHMES (LDA)
1.10 La récursivité en LDA
LDA  Fonction récursive : la factorielle
1 // Une fonction r é cursive s ' appelle elle - mê me
2 fonction factorielle_rec ( n : entier ) : entier
3 debut
4 si n = 0 ou n = 1 alors // cas de base ( arr êt )
5 retourner 1
6 sinon // cas r é cursif
7 retourner n * factorielle_rec ( n - 1)
8 fin_si
9 fin
10

11 // Trace d ' ex é cution pour n =4 :

12 // factorielle_rec (4)
13 // = 4 * factorielle_rec (3)
14 // = 4 * (3 * factorielle_rec (2) )
15 // = 4 * (3 * (2 * factorielle_rec (1) ))
16 // = 4 * (3 * (2 * 1) )
17 // = 4 * (3 * 2) = 4 * 6 = 24

★ Règles d'or de la récursivité

1. Il doit exister au moins un cas de base (condition d'arrêt) sans appel récur-
sif.

diminue
2. Chaque appel récursif doit se rapprocher du cas de base (le problème

récursion innie
).
3. Sans ces deux règles ⇒ (plantage du programme).

1.11 Synthèse  Squelette complet LDA

LDA  Exemple complet : tri d'un tableau par insertion
1 // Proc é dure de tri par insertion
2 // Trie le tableau tab [0.. n -1] dans l ' ordre croissant
3 procedure tri_insertion ( ref tab : tableau [..] de entier , n
: entier )
4 variable i , j , cle : entier
5 debut
6 pour i de 1 a n -1 faire
7 cle <- tab [i ] // on " saisit " l 'é lé ment i
8 j <- i - 1
9 // on d é cale vers la droite les élé ments plus grands
que cle
10 tant_que j >= 0 et tab [j] > cle faire
11 tab [j +1] <- tab [j]

14
CHAPTER 1. LE PSEUDOCODE  LANGAGE DE DESCRIPTION
D'ALGORITHMES (LDA) Algorithmique & Complexité  GL/SIAD
12 j <- j - 1
13 fin_tq
14 tab [j +1] <- cle // on ins è re cle à sa bonne place
15 fin_pour
16 fin
17

18 // Programme principal qui utilise la proc é dure

19 algorithme TriTableau
20 variable notes : tableau [5] de entier
21 variable i : entier
22 debut
23 // Remplissage
24 pour i de 0 a 4 faire
25 lire notes [i ]
26 fin_pour
27 // Tri
28 tri_insertion ( notes , 5)
29 // Affichage tri é
30 pour i de 0 a 4 faire
31 afficher notes [i ], " "
32 fin_pour
33 fin

15
Chapitre 2
Rappels Mathématiques et Logiques
2.1 Logique propositionnelle
2.1.1 Tables de vérité
P Q P ∧Q (ET) P ∨Q (OU) ¬P (NON) P ⇒Q (implication)
V V V V F V
V F F V F F
F V F V V V
F F F F V V

★ Lois de De Morgan
¬(P ∧ Q) ≡ (¬P ) ∨ (¬Q)
¬(P ∨ Q) ≡ (¬P ) ∧ (¬Q)
En LDA : non(a et b) ≡ (non a) ou (non b)

2.2 Sommes et séries usuelles

Ces formules apparaissent fréquemment dans le calcul de complexité.

16
CHAPTER 2. RAPPELS MATHÉMATIQUES ET
Algorithmique
LOGIQUES& Complexité  GL/SIAD
★ Sommes à connaître par c÷ur
n
X
1=n (n termes égaux à 1) (2.1)
i=1
n
X n(n + 1) n2
i= ≈ (somme des n premiers entiers) (2.2)
i=1
2 2
n−1
X n(n − 1)
i= (variante courante) (2.3)
i=0
2
k
X
2i = 2k+1 − 1 (suite géométrique de raison 2) (2.4)
i=0
k
X rk+1 − 1
ri = (r ̸= 1) (suite géométrique générale) (2.5)
i=0
r−1

log2 (n!) ≈ n log2 n − n log2 e (approximation de Stirling) (2.6)

2.3 Logarithmes
★ Propriétés des logarithmes
logb (xy) = logb x + logb y (2.7)
 
logb xy = logb x − logb y (2.8)

logb (xk ) = k logb x (2.9)

loga x
logb x = (changement de base) (2.10)
loga b
ln n
log2 n = ≈ 1.443 ln n (2.11)
ln 2

✰ Exemple
Calculer log2 (32) = log2 (25 ) = 5. En général, log2 (2k ) = k .
log2 (1024) = log2 (210 ) = 10. Donc un tableau de 1024 = 210 éléments se parcourt
en dichotomie en 10 étapes.

17
Algorithmique & ComplexitéCHAPTER
 GL/SIAD
2. RAPPELS MATHÉMATIQUES ET LOGIQUES
2.4 Raisonnement par récurrence
■ Dénition : Récurrence (principe)
Pour démontrer qu'une propriété P (n) est vraie pour tout n ≥ n0 :

Base :
Hérédité :
1. Vérier P (n0 ).
2. Supposer P (k) vraie (hypothèse de récurrence), et montrer que
P (k + 1) est vraie.

✰ Exemple
Preuve : P n
i = n(n+1)
Base n = 1 i=1 P .
2
1 1×2

Hérédité : i=1 i = 1 = 2 ✓
( ) :
Pk k(k+1)
Supposons i=1 i = 2
. Alors :

k+1 k
X X k(k + 1) k(k + 1) + 2(k + 1) (k + 1)(k + 2)
i= i+(k+1) = +(k+1) = = ✓
i=1 i=1
2 2 2

2.5 Divisions entières et modulo

Opération Notation LDA Formule Exemple
Division entière div ⌊a/b⌋ 17 div 5 = 3
Reste (modulo) mod a − b⌊a/b⌋ 17 mod 5 = 2
Relation a = b × (a div b) + (a mod b) 17 = 5 × 3 + 2
Parité n mod 2 = 0 ⇔ n pair 8 mod 2 = 0
k
Puissance de 2 n = 2 ⇔ n mod 2 = 0 tant que n > 1

18
Chapitre 3
Évaluation de la Complexité Algorith-
mique
3.1 Pourquoi mesurer la complexité ?
Deux algorithmes résolvant le même problème peuvent avoir des performances radi-
calement diérentes lorsque la taille des données augmente.

Complexité n = 10 n = 100 n = 1000 n = 106

O(1) 1 1 1 1
O(log n) 3 7 10 20
O(n) 10 100 1 000 106
O(n log n) 33 664 9 966 2 × 107
O(n2 ) 100 104
106
1012
O(n3 ) 103
106 109 1018
O(2n ) 1 024 1030 ≫ ≫≫

En supposant 109 opérations/seconde : O(n2 ) pour n = 106 prendrait ≈ 11 jours !

3.2 Notation Grand O, Omega, Thêta

■ Dénition : Notations asymptotiques
f (n) = O(g(n)) ⇔ ∃c > 0, n0 : ∀n ≥ n0 , f (n) ≤ c · g(n) (majorant)
f (n) = Ω(g(n)) ⇔ ∃c > 0, n0 : ∀n ≥ n0 , f (n) ≥ c · g(n) (minorant)
f (n) = Θ(g(n)) ⇔ f (n) = O(g(n)) et f (n) = Ω(g(n)) (équivalent)

★ Règles de simplication Grand O

Constantes multiplicatives : O(7n ) = O(n )
Terme dominant : O(3n + 5n + 12) = O(n )
2 2
1.

Logarithmes : O(n log(5n )) = O(n log n)

3 2 3
2.
2 4 2
3. (car log(5n4 ) = log 5 +
4 log n ∼ 4 log n)

19
Algorithmique CHAPTER
& Complexité3. ÉVALUATION
GL/SIAD DE LA COMPLEXITÉ ALGORITHMIQUE
Constante : O(c) = O(1)
Somme : O(f ) + O(g) = O(max(f, g))
4. pour toute constante c>0

Produit : O(f ) × O(g) = O(f × g)

5.
6.

3.3 Complexité des structures de contrôle

Structure Complexité Explication
Instruction simple O(1) Une seule opération, temps
constant
Séquence S1 ; S2 O(max(T1 , T2 )) Le plus lent domine
Si-Sinon O(max(Talors , Tsinon )) Pire des deux branches
Boucle Pour i de 1 à n O(n × Tcorps ) n répétitions
Double boucle imbriquée O(n2 × Tcorps ) n × n répétitions
Boucle i ← i * 2 O(log n) Division par 2 de l'espace
Récursion sur n/2 O(log n) Si Tcorps = O(1)

3.3.1 Méthode de comptage par imbrication

✰ Double boucle  Comment compter
1 pour i de 1 a n faire // n it é rations
2 pour j de 1 a n faire // n it é rations pour
chaque i
3 afficher i * j // O (1)
4 fin_pour
5 fin_pour

Nombre d'opérations = n × n × O(1) = O(n2 ).

✰ Boucle en O(log n)
1 i <- n
2 tant_que i > 1 faire // combien de fois ?
3 afficher i
4 i <- i div 2 // i est divis é par 2 à chaque tour
5 fin_tq

La valeur de i n, n/2, n/4, . . . , 1. Après k itérations, i = n/2k . La boucle

suit :
s'arrête quand n/2 ≤ 1, soit 2k ≥ n, soit k ≥ log2 n. Complexité : O(log n).
k

3.4 Récurrences et Théorème Maître

20
CHAPTER 3. ÉVALUATION DE LA COMPLEXITÉ
Algorithmique
ALGORITHMIQUE
& Complexité  GL/SIAD
3.4.1 Identier une récurrence
Quand un algorithme se décompose récursivement :

n
T (n) = a · T + f (n)
b

ˆ a ≥ 1 : nombre de sous-problèmes à chaque niveau

ˆ b > 1 : facteur par lequel on réduit la taille
ˆ f (n) : coût de la décomposition + recombinaison

3.4.2 Le Théorème Maître

● Théorème : Théorème Maître (version simpliée)
Pour T (n) = a T (n/b) + f (n), poser p = logb a :

Cas Condition Solution

Cas 1 f (n) = O(n )
Cas 2 f (n) = Θ(n )
p−ε
pour un ε>0 T (n) = Θ(np )

Cas 3 f (n) = Ω(n )

p
T (n) = Θ(np log n)
p+ε
et cond. de régularité T (n) = Θ(f (n))

★ Méthode en 4 étapes pour appliquer le Théorème Maître

Identier a b f (n)
Calculer p = log a
1. , , et dans la récurrence.

Comparer f (n) n
2. b .

Appliquer
p
3. avec .
4. le cas correspondant.

Récurrence a b p = logb a f (n) vs np Résultat

T (n) = 2T (n/2) + n 2 2 1 n = n1 : Cas 2 O(n log n)
T (n) = T (n/2) + O(1) 1 2 0 1 = n0 : Cas 2 O(log n)
T (n) = 4T (n/2) + n 4 2 2 n ≺ n2 : Cas 1 O(n2 )
T (n) = 2T (n/2) + n2 2 2 1 n2 ≻ n1 : Cas 3 O(n2 )
T (n) = 7T (n/2) + n2 7 2 2.807 n2 ≺ n2.807 : Cas 1 O(nlog2 7 )

3.5 Cas de récurrence sans Théorème Maître

3.5.1 Récurrence linéaire simple : déroulement
✰ Exemple
T (n) = T (n − 1) + O(1) (ex: recherche séquentielle)
En déroulant : T (n) = T (n − 1) + c = T (n − 2) + 2c = . . . = T (0) + nc = O(n).

21
Algorithmique CHAPTER
& Complexité3. ÉVALUATION
GL/SIAD DE LA COMPLEXITÉ ALGORITHMIQUE
✰ Exemple
T (n) = T (n − 1) + n (ex: tri par sélection)
T (n) = n + (n − 1) + (n − 2) + . . . + 1 = n(n+1)
2
= O(n2 ).

22
Chapitre 4
Algorithmes de Recherche et de Tri
4.1 Recherche séquentielle
LDA  Recherche séquentielle dans un tableau non trié
1 // Retourne l ' indice de val dans tab , ou -1 si absent
2 fonction recherche_seq ( tab : tableau [n] de entier ,
3 n : entier , val : entier ) : entier
4 variable i : entier
5 debut
6 pour i de 0 a n -1 faire
7 si tab [i] = val alors
8 retourner i // trouv é à l ' indice i
9 fin_si
10 fin_pour
11 retourner -1 // non trouv é
12 fin

Complexité : Meilleur cas O(1) (premier élément), pire cas O(n) (absent ou dernier).

4.2 Recherche dichotomique (binaire)

Prérequis : Le tableau doit être trié .

Principe : Comparer l'élément cherché avec l'élément du milieu, et éliminer la moitié

du tableau à chaque étape.

milieu=3 chercher ici si val>7

1 3 5 7 9 11 13 15
0 1 2 3 4 5 6 7

LDA  Recherche dichotomique itérative

1 // Tableau tri é tab [0.. n -1] , recherche de val
2 // Retourne l ' indice ou -1

23
Algorithmique & Complexité
CHAPTER
 GL/SIAD
4. ALGORITHMES DE RECHERCHE ET DE TRI
3 fonction dichotomie ( tab : tableau [n] de entier ,
4 n : entier , val : entier ) : entier
5 variable bas , haut , milieu : entier
6 debut
7 bas <- 0
8 haut <- n - 1
9 tant_que bas <= haut faire
10 milieu <- ( bas + haut ) div 2
11 si tab [ milieu ] = val alors
12 retourner milieu // trouv é !
13 sinon_si tab [ milieu ] < val alors
14 bas <- milieu + 1 // chercher à droite
15 sinon
16 haut <- milieu - 1 // chercher à gauche
17 fin_si
18 fin_tq
19 retourner -1 // non trouv é
20 fin

Complexité : O(log n)  la taille de l'espace de recherche est divisée par 2 à chaque

étape.

❍ Comparaison recherche séquentielle vs dichotomique

Prérequis Complexité Pour n = 10 6

Séquentielle Aucun O(n) 1 000 000 étapes

Dichotomique Tableau trié O(log n) ≈ 20 étapes

4.3 Tri par sélection

Idée : À chaque tour i, trouver l'élément minimal dans tab[i..n-1] et le placer en
position i.

Initial : 5 3
min=1 (idx 3) 8 1 9 2
Tour 1 : 1 3 8 5
min=2 (idx 5) 9 2
Tour 2 : 1 2 8 5 9 3

LDA  Tri par sélection

1 procedure tri_selection ( ref tab : tableau [..] de entier , n
: entier )
2 variable i , j , idx_min , temp : entier
3 debut
4 pour i de 0 a n -2 faire // n -1 tours suffisent
5 idx_min <- i // supposer que le min
est en i

24
CHAPTER 4. ALGORITHMES DE RECHERCHE
Algorithmique
ET DE TRI& Complexité  GL/SIAD
6 pour j de i +1 a n -1 faire // chercher le vrai
minimum
7 si tab [ j] < tab [ idx_min ] alors
8 idx_min <- j
9 fin_si
10 fin_pour
11 // é changer tab [ i] et tab [ idx_min ]
12 si idx_min <> i alors
13 temp <- tab [i]
14 tab [i ] <- tab [ idx_min ]
15 tab [ idx_min ] <- temp
16 fin_si
17 fin_pour
18 fin

❍ Complexité du tri sélection

La boucle externe fait n − 1 tours. Pour le tour i, la boucle interne fait n − 1 − i
comparaisons.
n−2
n(n − 1)
Total =
X
(n − 1 − i) = (n − 1) + (n − 2) + . . . + 1 = = Θ(n2 )
2
i=0

Toujours O(n ), peu importe l'ordre initial du tableau.

2

4.4 Tri par insertion

Idée : Comme trier des cartes à jouer en main : on prend chaque carte et on l'insère
à sa bonne place dans la partie déjà triée.

LDA  Tri par insertion

1 procedure tri_insertion ( ref tab : tableau [..] de entier , n
: entier )
2 variable i , j , cle : entier
3 debut
4 pour i de 1 a n -1 faire
5 cle <- tab [i ] // on " saisit " la carte i
6 j <- i - 1
7 // dé caler vers la droite les él é ments plus grands que
cle
8 tant_que j >= 0 et tab [j] > cle faire
9 tab [j +1] <- tab [j] // dé caler
10 j <- j - 1
11 fin_tq
12 tab [j +1] <- cle // ins é rer cle à sa place
13 fin_pour
14 fin

25
Algorithmique & Complexité
CHAPTER
 GL/SIAD
4. ALGORITHMES DE RECHERCHE ET DE TRI
❍ Complexité du tri insertion
Cas Complexité Condition
Meilleur cas O(n) Tableau déjà trié (0 décalage par élément)
Pire cas O(n2 ) Tableau trié à l'envers (max décalages)
Cas moyen O(n2 ) Tableau aléatoire

4.5 Tri à bulles

Idée : Comparer des paires adjacentes (tab[j], tab[j + 1]) et les échanger si mal ordon-
nées. Les grandes valeurs remontent comme des bulles.

LDA  Tri à bulles avec optimisation

1 procedure tri_bulles ( ref tab : tableau [..] de entier , n :
entier )
2 variable i , j , temp : entier
3 variable echange_fait : booleen
4 debut
5 pour i de 0 a n -2 faire
6 echange_fait <- faux
7 pour j de 0 a n -2 - i faire // la derni è re bulle est d
éj à plac é e
8 si tab [ j] > tab [j +1] alors
9 // é changer tab [ j] et tab [j +1]
10 temp <- tab [j]
11 tab [j ] <- tab [ j +1]
12 tab [j +1] <- temp
13 echange_fait <- vrai
14 fin_si
15 fin_pour
16 si non echange_fait alors // optimisation : si
aucun é change ,
17 retourner // le tableau est d éjà
tri é !
18 fin_si
19 fin_pour
20 fin

Complexité : O(n ) 2
en général, O(n) meilleur cas (tableau déjà trié, avec l'optimisation).

4.6 Tri fusion (Merge Sort)

Idée (diviser pour régner) :
fusionner
Diviser le tableau en deux moitiés, trier chaque moitié
récursivement, puis les deux parties triées.

26
CHAPTER 4. ALGORITHMES DE RECHERCHE
Algorithmique
ET DE TRI& Complexité  GL/SIAD
5, 3, 8, 1, 9, 2
diviser diviser

5, 3, 8 1, 9, 2
trier trier

3, 5, 8 1, 2, 9
fusionner

1, 2, 3, 5, 8, 9

LDA  Tri fusion

1 procedure fusion ( ref tab : tableau [..] de entier ,
2 g , milieu , d : entier )
3 // Fusionne tab [g .. milieu ] et tab [ milieu +1.. d] ( deux
parties tri é es )
4 variable n1 , n2 , i , j , k : entier
5 variable G , D : tableau [..] de entier
6 debut
7 n1 <- milieu - g + 1 ; n2 <- d - milieu
8 // Copier dans des tableaux temporaires
9 pour i de 0 a n1 -1 faire G[i ] <- tab [g + i] fin_pour
10 pour j de 0 a n2 -1 faire D[j ] <- tab [ milieu +1+ j]
fin_pour
11 i <- 0 ; j <- 0 ; k <- g
12 tant_que i < n1 et j < n2 faire
13 si G[i ] <= D[j ] alors
14 tab [k ] <- G[ i] ; i <- i + 1
15 sinon
16 tab [k ] <- D[ j] ; j <- j + 1
17 fin_si
18 k <- k + 1
19 fin_tq
20 tant_que i < n1 faire tab [k] <- G[i ] ; i <- i +1 ; k
<- k +1 fin_tq
21 tant_que j < n2 faire tab [k] <- D[j ] ; j <- j +1 ; k
<- k +1 fin_tq
22 fin
23

24 procedure tri_fusion ( ref tab : tableau [..] de entier , g , d

: entier )
25 debut
26 si g < d alors
27 milieu <- (g + d) div 2
28 tri_fusion ( tab , g , milieu )
29 tri_fusion ( tab , milieu +1 , d)
30 fusion ( tab , g , milieu , d)
31 fin_si
32 fin
33 // Appel initial : tri_fusion ( tab , 0, n -1)

Récurrence : T (n) = 2T (n/2)+O(n) . Par le Théorème Maître (Cas 2) : T (n) = O(n log n) .

27
Algorithmique & Complexité
CHAPTER
 GL/SIAD
4. ALGORITHMES DE RECHERCHE ET DE TRI
4.7 Tri par tas (Heap Sort)
LDA  Tri par tas
1 // Phase 1 : Construire un tas max à partir du tableau
2 // Phase 2 : Extraire les élé ments un par un ( ordre
croissant )
3

4 procedure percole_bas ( ref tab : tableau [..] de entier ,

5 i , taille : entier )
6 // Ré tablit la propri été tas en descendant depuis l '
indice i
7 variable j , temp : entier
8 variable continuer : booleen
9 debut
10 continuer <- vrai
11 tant_que continuer faire
12 j <- i
13 si 2* i <= taille et tab [2* i] > tab [j ] alors j <- 2* i
fin_si
14 si 2* i +1 <= taille et tab [2* i +1] > tab [ j] alors j <-
2* i +1 fin_si
15 si j <> i alors
16 temp <- tab [i ] ; tab [i] <- tab [j] ; tab [j ] <-
temp
17 i <- j
18 sinon
19 continuer <- faux
20 fin_si
21 fin_tq
22 fin
23

24 procedure heap_sort ( ref tab : tableau [..] de entier , n :

entier )
25 variable i , temp : entier
26 debut
27 // Construction du tas en O( n)
28 pour i de n div 2 a 1 par_pas_de -1 faire
29 percole_bas ( tab , i , n)
30 fin_pour
31 // Extraction en O(n log n)
32 pour i de n a 2 par_pas_de -1 faire
33 temp <- tab [1] ; tab [1] <- tab [ i] ; tab [i ] <- temp
34 percole_bas ( tab , 1 , i -1)
35 fin_pour
36 fin

Complexité : Toujours O(n log n), même dans le pire cas.

28
CHAPTER 4. ALGORITHMES DE RECHERCHE
Algorithmique
ET DE TRI& Complexité  GL/SIAD
❍ Comparaison de tous les algorithmes de tri
Algorithme Meilleur Moyen Pire Stable ?
Sélection O(n2 ) O(n2 ) O(n2 ) Non
Insertion O(n) O(n2 ) O(n )2 Oui
Bulles (opt.) O(n) O(n2 ) O(n2 ) Oui
Fusion O(n log n) O(n log n) O(n log n) Oui
Tas O(n log n) O(n log n) O(n log n) Non
Rapide (Quicksort) O(n log n) O(n log n) O(n2 ) Non
Borne inférieure théorique des tris par comparaison : Ω(n log n)

29
Chapitre 5
Structures de Données Linéaires
5.1 Tableaux dynamiques
LDA  Tableau à taille variable  simulation
1 // On g è re un " vrai " tableau avec un compteur d 'él é ments
2 structure TableauDyn
3 donnees : tableau [ MAX ] de entier
4 nb_elems : entier // nombre d 'él é ments
actuellement stock és
5 fin_structure
6

7 // Ins é rer en fin

8 procedure inserer_fin ( ref t : TableauDyn , val : entier )
9 debut
10 si t. nb_elems < MAX alors
11 t. donnees [t. nb_elems ] <- val
12 t. nb_elems <- t. nb_elems + 1
13 sinon
14 afficher " Tableau plein !"
15 fin_si
16 fin
17

18 // Acc è s à l 'é lé ment i ( avec vé rification )

19 fonction get ( t : TableauDyn , i : entier ) : entier
20 debut
21 si i >= 0 et i < t. nb_elems alors
22 retourner t. donnees [ i]
23 sinon
24 erreur " Indice hors bornes "
25 fin_si
26 fin

5.2 Listes chaînées simples

30
CHAPTER 5. STRUCTURES DE DONNÉES LINÉAIRES
Algorithmique & Complexité  GL/SIAD
5.2.1 Dénition et représentation
■ Dénition : Liste simplement chaînée
Une liste simplement chaînée est une collection de n÷uds où chaque n÷ud contient
:

ˆ valeur
pointeur
Une (donnée)
ˆ Un vers le n÷ud suivant (∅ si dernier)

On accède à la liste via un pointeur tête .

tête 5 22 1 8∅
val|suiv

LDA  Structures de base

1 structure Noeud
2 valeur : entier
3 suivant : pointeur vers Noeud
4 fin_structure
5

6 // D é claration de la tê te de liste
7 variable tete : pointeur vers Noeud = NULL

5.2.2 Opérations fondamentales

LDA  Insertion en tête  O(1)
1 procedure inserer_tete ( ref tete : pointeur vers Noeud , val
: entier )
2 variable nouveau : pointeur vers Noeud
3 debut
4 allouer ( nouveau )
5 nouveau . valeur <- val
6 nouveau . suivant <- tete // lier au reste de la liste
7 tete <- nouveau // nouveau devient la tê te
8 fin

LDA  Insertion en queue  O(n) ou O(1) avec ptr n

1 procedure inserer_queue ( ref tete : pointeur vers Noeud , val
: entier )
2 variable nouveau , courant : pointeur vers Noeud
3 debut
4 allouer ( nouveau )
5 nouveau . valeur <- val

31
Algorithmique & Complexité CHAPTER
GL/SIAD 5. STRUCTURES DE DONNÉES LINÉAIRES
6 nouveau . suivant <- NULL
7 si tete = NULL alors
8 tete <- nouveau // liste é tait vide
9 sinon
10 courant <- tete
11 tant_que courant . suivant <> NULL faire
12 courant <- courant . suivant // aller jusqu ' au dernier
13 fin_tq
14 courant . suivant <- nouveau // attacher le nouveau
noeud
15 fin_si
16 fin

LDA  Recherche  O(n)

1 // Retourne le pointeur vers le noeud contenant val , ou
NULL
2 fonction rechercher ( tete : pointeur vers Noeud ,
3 val : entier ) : pointeur vers Noeud
4 variable courant : pointeur vers Noeud
5 debut
6 courant <- tete
7 tant_que courant <> NULL et courant . valeur <> val faire
8 courant <- courant . suivant
9 fin_tq
10 retourner courant // NULL si non trouv é
11 fin

LDA  Suppression d'un n÷ud par valeur  O(n)

1 procedure supprimer ( ref tete : pointeur vers Noeud , val :
entier )
2 variable courant , precedent : pointeur vers Noeud
3 debut
4 // Cas 1 : la valeur est en tê te
5 si tete <> NULL et tete . valeur = val alors
6 precedent <- tete
7 tete <- tete . suivant
8 liberer ( precedent )
9 retourner
10 fin_si
11 // Cas 2 : chercher la valeur dans le reste
12 courant <- tete
13 precedent <- NULL
14 tant_que courant <> NULL et courant . valeur <> val faire
15 precedent <- courant
16 courant <- courant . suivant
17 fin_tq

32
CHAPTER 5. STRUCTURES DE DONNÉES LINÉAIRES
Algorithmique & Complexité  GL/SIAD
18 si courant <> NULL alors // noeud trouv é
19 precedent . suivant <- courant . suivant
20 liberer ( courant )
21 fin_si
22 fin

5.2.3 Listes doublement chaînées

LDA  Structure doublement chaînée
1 structure NoeudDouble
2 valeur : entier
3 suivant : pointeur vers NoeudDouble
4 precedent : pointeur vers NoeudDouble
5 fin_structure
6

7 // Insertion en t ê te dans une liste doublement cha în ée

8 procedure inserer_double ( ref tete : pointeur vers
NoeudDouble ,
9 val : entier )
10 variable nouveau : pointeur vers NoeudDouble
11 debut
12 allouer ( nouveau )
13 nouveau . valeur <- val
14 nouveau . suivant <- tete
15 nouveau . precedent <- NULL
16 si tete <> NULL alors
17 tete . precedent <- nouveau
18 fin_si
19 tete <- nouveau
20 fin

❍ Comparaison listes vs tableaux

Opération Tableau Liste chaînée
Accès k-ième élément O(1) O(n)
Insertion en tête O(n) (décaler) O(1)
Insertion en queue O(1) O(n) ou O(1) avec ptr
Suppression connue O(n) (décaler) O(1) (si précédent connu)
Recherche O(n) O(n)
Mémoire Contiguë, xe Dispersée, dynamique

33
Algorithmique & Complexité CHAPTER
GL/SIAD 5. STRUCTURES DE DONNÉES LINÉAIRES
5.3 Piles (LIFO)
■ Dénition : Pile (Stack)
LIFO
Analogie :
Une pile est une structure (Last In, First Out) : le dernier élément inséré
est le premier retiré. une pile d'assiettes.

9 push(5)
push/pop
sommet

1
7
3

LDA  Pile  implémentation avec liste chaînée

1 // On r é utilise la structure Noeud
2 // tete de la liste = sommet de la pile
3

4 procedure empiler ( ref tete : pointeur vers Noeud , val :

entier )
5 // = inserer_tete (O (1) )
6 variable nouveau : pointeur vers Noeud
7 debut
8 allouer ( nouveau )
9 nouveau . valeur <- val
10 nouveau . suivant <- tete
11 tete <- nouveau
12 fin
13

14 fonction depiler ( ref tete : pointeur vers Noeud ) : entier

15 // Retire et retourne le sommet (O (1) )
16 variable temp : pointeur vers Noeud
17 variable val : entier
18 debut
19 si tete = NULL alors erreur " Pile vide !" fin_si
20 val <- tete . valeur
21 temp <- tete
22 tete <- tete . suivant
23 liberer ( temp )
24 retourner val
25 fin
26

27 fonction sommet ( tete : pointeur vers Noeud ) : entier

28 // Consulte sans retirer (O (1) )
29 debut
30 si tete = NULL alors erreur " Pile vide !" fin_si
31 retourner tete . valeur
32 fin
33

34 fonction est_vide ( tete : pointeur vers Noeud ) : booleen

34
CHAPTER 5. STRUCTURES DE DONNÉES LINÉAIRES
Algorithmique & Complexité  GL/SIAD
35 debut
36 retourner tete = NULL
37 fin

5.4 Files (FIFO)

■ Dénition : File (Queue)
FIFO
Analogie :
Une le est une structure (First In, First Out) : le premier élément inséré
est le premier retiré. une le d'attente à la caisse.

enfiler défiler
5 22 1 8
dernier premier (tête)

LDA  File  implémentation avec liste chaînée (deux pointeurs)

1 structure File
2 premier : pointeur vers Noeud // tê te ( on d é file ici )
3 dernier : pointeur vers Noeud // queue ( on enfile ici )
4 fin_structure
5

6 procedure enfiler ( ref f : File , val : entier )

7 // Ins è re à la fin --- O (1) gr â ce au pointeur dernier
8 variable nouveau : pointeur vers Noeud
9 debut
10 allouer ( nouveau )
11 nouveau . valeur <- val
12 nouveau . suivant <- NULL
13 si f. premier = NULL alors // file vide
14 f. premier <- nouveau
15 f. dernier <- nouveau
16 sinon
17 f. dernier . suivant <- nouveau // lier l ' ancien dernier
18 f. dernier <- nouveau // mettre à jour le ptr
fin
19 fin_si
20 fin
21

22 fonction defiler ( ref f : File ) : entier

23 // Retire la t ê te --- O (1)
24 variable temp : pointeur vers Noeud
25 variable val : entier
26 debut
27 si f. premier = NULL alors erreur " File vide !" fin_si
28 val <- f. premier . valeur
29 temp <- f. premier

35
Algorithmique & Complexité CHAPTER
GL/SIAD 5. STRUCTURES DE DONNÉES LINÉAIRES
30 f. premier <- f. premier . suivant
31 si f. premier = NULL alors f. dernier <- NULL fin_si //
file devenue vide
32 liberer ( temp )
33 retourner val
34 fin

36
Chapitre 6
Arbres
6.1 Concepts fondamentaux
■ Dénition : Arbre
Un arbre est une structure hiérarchique composée de n÷uds reliés par des arêtes ,
avec les propriétés suivantes :

ˆ racine
un parent
Un n÷ud spécial : la (sans parent).
ˆ
feuilles
Chaque n÷ud non-racine a exactement .
ˆ Les n÷uds sans enfant sont appelés .

10 racine, hauteur=3

n÷ud interne
5 15

2 7 12 20

1 3 6 9
Terme Dénition
Racine N÷ud sans parent (sommet de l'arbre)
Feuille N÷ud sans enfant
N÷ud interne N÷ud avec au moins un enfant
Hauteur Longueur du chemin le plus long de la racine à une feuille
Profondeur d'un n÷ud Longueur du chemin de la racine à ce n÷ud
Degré Nombre d'enfants d'un n÷ud
Sous-arbre Arbre enraciné en un n÷ud ls

37
Algorithmique & Complexité  GL/SIAD CHAPTER 6. ARBRES
6.2 Arbres Binaires de Recherche (ABR)
■ Dénition : ABR
Un arbre binaire de recherche est un arbre binaire où, pour tout n÷ud de clé k :

ˆ gauche
droit
Toutes les clés du sous-arbre sont< k.
ˆ Toutes les clés du sous-arbre sont > k.

LDA  Structure d'un n÷ud ABR

1 structure NoeudABR
2 cle : entier
3 gauche : pointeur vers NoeudABR // sous - arbre gauche
4 droit : pointeur vers NoeudABR // sous - arbre droit
5 fin_structure

6.2.1 Les trois parcours

LDA  Parcours inxe, préxe, postxe
1 // INFIXE : Gauche , Racine , Droite -> cl és en ordre
CROISSANT pour un ABR
2 procedure infixe (n : pointeur vers NoeudABR )
3 debut
4 si n <> NULL alors
5 infixe (n . gauche )
6 afficher n . cle
7 infixe (n . droit )
8 fin_si
9 fin
10

11 // PR É FIXE : Racine , Gauche , Droite -> racine toujours en

premier
12 procedure prefixe (n : pointeur vers NoeudABR )
13 debut
14 si n <> NULL alors
15 afficher n . cle
16 prefixe (n. gauche )
17 prefixe (n. droit )
18 fin_si
19 fin
20

21 // POSTFIXE : Gauche , Droite , Racine -> feuilles avant

racines
22 procedure postfixe ( n : pointeur vers NoeudABR )
23 debut
24 si n <> NULL alors

38
CHAPTER 6. ARBRES Algorithmique & Complexité  GL/SIAD
25 postfixe ( n. gauche )
26 postfixe ( n. droit )
27 afficher n . cle
28 fin_si
29 fin

6.2.2 Recherche, insertion, suppression

LDA  Recherche dans un ABR
1 // Retourne le noeud contenant k , ou NULL si absent --- O (
log n ) é quilibr é
2 fonction recherche_ABR (n : pointeur vers NoeudABR ,
3 k : entier ) : pointeur vers
NoeudABR
4 debut
5 si n = NULL ou n . cle = k alors
6 retourner n
7 sinon_si k < n . cle alors
8 retourner recherche_ABR (n. gauche , k)
9 sinon
10 retourner recherche_ABR (n. droit , k)
11 fin_si
12 fin

LDA  Insertion dans un ABR

1 // Retourne la nouvelle racine apr ès insertion
2 fonction inserer_ABR (n : pointeur vers NoeudABR ,
3 k : entier ) : pointeur vers NoeudABR
4 variable nouveau : pointeur vers NoeudABR
5 debut
6 si n = NULL alors // on a trouv é la bonne place
7 allouer ( nouveau )
8 nouveau . cle <- k
9 nouveau . gauche <- NULL
10 nouveau . droit <- NULL
11 retourner nouveau
12 sinon_si k < n . cle alors
13 n. gauche <- inserer_ABR (n . gauche , k )
14 sinon_si k > n . cle alors
15 n. droit <- inserer_ABR (n. droit , k)
16 fin_si // k = n. cle : doublon , on ne fait rien
17 retourner n
18 fin

39
Algorithmique & Complexité  GL/SIAD CHAPTER 6. ARBRES
LDA  Suppression dans un ABR  3 cas
1 // Cas 1 : feuille -> supprimer directement
2 // Cas 2 : un seul enfant -> remplacer par l ' enfant
3 // Cas 3 : deux enfants -> remplacer par le successeur
infixe
4

5 // Trouver le minimum ( successeur infixe )

6 fonction min_ABR (n : pointeur vers NoeudABR ) : pointeur
vers NoeudABR
7 debut
8 tant_que n . gauche <> NULL faire n <- n . gauche fin_tq
9 retourner n
10 fin
11

12 fonction supprimer_ABR (n : pointeur vers NoeudABR ,

13 k : entier ) : pointeur vers
NoeudABR
14 variable succ : pointeur vers NoeudABR
15 debut
16 si n = NULL alors retourner NULL fin_si
17 si k < n . cle alors
18 n. gauche <- supprimer_ABR (n. gauche , k)
19 sinon_si k > n . cle alors
20 n. droit <- supprimer_ABR ( n. droit , k )
21 sinon // n. cle = k : noeud
trouv é
22 si n. gauche = NULL alors // Cas 1 ou 2 ( sans
fils gauche )
23 retourner n. droit
24 sinon_si n . droit = NULL alors // Cas 2 ( sans fils
droit )
25 retourner n. gauche
26 sinon // Cas 3 : deux fils
27 succ <- min_ABR (n. droit ) // successeur infixe
28 n. cle <- succ . cle // copier la cl é du
successeur
29 n. droit <- supprimer_ABR ( n. droit , succ . cle ) //
supprimer le successeur
30 fin_si
31 fin_si
32 retourner n
33 fin

40
CHAPTER 6. ARBRES Algorithmique & Complexité  GL/SIAD
6.3 Tas (Heap)
■ Dénition : Tas max
Un tas max est un arbre binaire complet (tous les niveaux remplis, sauf éventuelle-

propriété de tas
ment le dernier qui se complète de gauche à droite) tel que la clé de chaque n÷ud
est ≥ à celles de ses enfants ( ).

70

65 60

25 50 55 35 Idx
Val
1 2 3 4 5 6
70 65 60 25 50 55

Représentation en tableau (indices 1..n)

★ Navigation dans le tableau

Pour un n÷ud à l'indice i (tableau indexé depuis 1) :

Parent= ⌊i/2⌋
Fils gauche = 2i

Fils droit = 2i + 1

LDA  Insertion dans un tas

1 procedure inserer_tas ( ref tas : tableau [..] de entier ,
2 ref taille : entier , val : entier )
3 variable i , temp : entier
4 debut
5 taille <- taille + 1
6 tas [ taille ] <- val // ins é rer en fin
7 i <- taille
8 // Percolation vers le haut : remonter si > parent
9 tant_que i > 1 et tas [ i] > tas [i div 2] faire
10 temp <- tas [i ]
11 tas [i ] <- tas [i div 2]
12 tas [i div 2] <- temp
13 i <- i div 2
14 fin_tq
15 fin

LDA  Suppression du maximum (racine)

1 fonction supprimer_max ( ref tas : tableau [..] de entier ,
2 ref taille : entier ) : entier

41
Algorithmique & Complexité  GL/SIAD CHAPTER 6. ARBRES
3 variable max , i , j , temp : entier
4 debut
5 si taille = 0 alors erreur " Tas vide " fin_si
6 max <- tas [1] // sauvegarder le maximum
7 tas [1] <- tas [ taille ] // mettre le dernier à la
racine
8 taille <- taille - 1
9 // Percolation vers le bas
10 i <- 1
11 tant_que vrai faire
12 j <- i
13 si 2* i <= taille et tas [2* i] > tas [j ] alors j <- 2* i
fin_si
14 si 2* i +1 <= taille et tas [2* i +1] > tas [ j] alors j <-
2* i +1 fin_si
15 si j = i alors retourner max fin_si // propri été ré
tablie
16 temp <- tas [i ] ; tas [i] <- tas [ j] ; tas [j ] <- temp
17 i <- j
18 fin_tq
19 fin

6.4 Arbres 2-3

■ Dénition : Arbre 2-3
Un arbre 2-3 est un arbre de recherche parfaitement équilibré :

ˆ 2 ou 3 ls
1 clé 2 clés
Chaque n÷ud interne a .
ˆ
feuilles sont à la même profondeur
Un n÷ud à 2 ls contient , un n÷ud à 3 ls contient .
ˆ Toutes les .

Avantage : toutes les opérations en O(log n) garanti (pas de pire cas comme
l'ABR).

12, 24

5, 9 18 30, 36

3, 4 7, 8 10,11 13, 15 21, 22 25, 27 32 40

Insertion : Descendre jusqu'à la feuille correcte, insérer, et si le n÷ud a 4 ls ( over-

ow split
), éclater ( ) en remontant la clé médiane au parent.

Suppression : Supprimer dans la feuille. Si sous-alimenté, emprunter une clé d'un

frère ou fusionner deux frères.

42
Chapitre 7
Graphes et Algorithmes sur Graphes
7.1 Dénitions fondamentales
■ Dénition : Graphe
Un graphe G = (V, E) est constitué de :

ˆ V sommets
arêtes
: un ensemble de (vertices) ou n÷uds.
ˆ E : un ensemble d' (edges) reliant des paires de sommets.

Type Arêtes Poids

Non orienté (u, v) bidirectionnel Non
Orienté (digraphe) (u → v) unidirectionnel Non
Pondéré avec poids w(u, v) Oui
w
Pondéré orienté u−→v Oui

7.2 Représentation d'un graphe

7.2.1 Matrice d'adjacence
LDA  Matrice d'adjacence
1 // M [i ][ j] = 1 ( ou poids ) si ar ê te (i ,j) existe , 0 sinon
2 variable M : tableau [n ][ n] de entier
3

4 // Exemple : graphe non orient é avec 4 sommets

5 // Ar ê tes : (1 ,2) :2 , (1 ,3) :4 , (2 ,3) :1 , (2 ,4) :3 , (3 ,4) :2
6 M = [[0 , 2 , 4, 0] ,
7 [2 , 0, 1 , 3] ,
8 [4 , 1, 0 , 2] ,
9 [0 , 3, 2 , 0]]
10 // Acc è s : tab [i ][ j] -> O (1) | M é moire : O( n$ ^2 $)

43
Algorithmique & Complexité
CHAPTER
 GL/SIAD
7. GRAPHES ET ALGORITHMES SUR GRAPHES
7.2.2 Liste d'adjacence
LDA  Liste d'adjacence
1 structure Arc
2 destination : entier // sommet de destination
3 poids : entier // poids de l ' ar ê te
4 suivant : pointeur vers Arc
5 fin_structure
6

7 // adj [ i] = liste des arcs partant du sommet i

8 variable adj : tableau [ n] de pointeur vers Arc
9

10 // Acc è s aux voisins du sommet i :

11 courant <- adj [ i]
12 tant_que courant <> NULL faire
13 afficher " Voisin : " , courant . destination , " poids : ",
courant . poids
14 courant <- courant . suivant
15 fin_tq
16 // M é moire : O (n + m) o ù m = nombre d ' ar ê tes

❍ Matrice vs Liste d'adjacence

Critère Matrice Liste d'adjacence
Mémoire O(n2 ) O(n + m)
Vérier arête (u, v) O(1) O(deg(u))
Lister voisins de u O(n) O(deg(u))
Graphe dense (m ≈ n2 ) Préférable Équivalent
Graphe creux (m ≪ n2 ) Gaspillage Préférable

7.3 Parcours en largeur (BFS)

Principe : Explorer les sommets niveau par niveau, en utilisant une le
.

LDA  BFS  Breadth-First Search

1 // Parcours en largeur depuis le sommet source s
2 procedure BFS ( adj : tableau de liste , n , s : entier )
3 variable visite : tableau [n ] de booleen
4 variable dist : tableau [n] de entier
5 variable file : File
6 variable u , v : entier
7 debut
8 pour i de 0 a n -1 faire visite [ i] <- faux ; dist [ i] <-
-1 fin_pour
9 visite [s ] <- vrai ; dist [s ] <- 0
10 enfiler ( file , s)

44
CHAPTER 7. GRAPHES ET ALGORITHMES Algorithmique
SUR GRAPHES & Complexité  GL/SIAD
11 tant_que non est_vide ( file ) faire
12 u <- defiler ( file )
13 afficher " Visite : " , u , " distance : " , dist [ u]
14 pour_chaque voisin v de u dans adj faire
15 si non visite [ v] alors
16 visite [v ] <- vrai
17 dist [ v] <- dist [u] + 1
18 enfiler ( file , v)
19 fin_si
20 fin_pour_chaque
21 fin_tq
22 fin
23 // Complexit é : O (n + m)

7.4 Parcours en profondeur (DFS)

Principe : Aller le plus loin possible avant de revenir en arrière, en utilisant une pile
(ou la récursion).

LDA  DFS  Depth-First Search (récursif)

1 variable visite : tableau [n ] de booleen
2

3 procedure DFS_rec ( adj : tableau de liste , u : entier )

4 debut
5 visite [u ] <- vrai
6 afficher " Visite : " , u
7 pour_chaque voisin v de u dans adj faire
8 si non visite [v] alors
9 DFS_rec ( adj , v)
10 fin_si
11 fin_pour_chaque
12 fin
13

14 // Initialisation et appel
15 procedure DFS ( adj : tableau de liste , n , s : entier )
16 debut
17 pour i de 0 a n -1 faire visite [ i] <- faux fin_pour
18 DFS_rec ( adj , s )
19 fin
20 // Complexit é : O (n + m)

45
Algorithmique & Complexité
CHAPTER
 GL/SIAD
7. GRAPHES ET ALGORITHMES SUR GRAPHES
7.5 Algorithme de Dijkstra  Plus court chemin
■ Dénition : Problème du plus court chemin
Étant donné un graphe pondéré (poids ≥ 0) et un sommet source s, trouver le
plus court chemin (de poids minimal) de s vers tous les autres sommets.

Principe de Dijkstra : Maintenir un ensemble S de sommets dont la distance

minimale est connue. À chaque étape, ajouter le sommet non visité le plus proche.

LDA  Algorithme de Dijkstra

1 procedure dijkstra ( M : tableau [n ][ n] de entier , n , s :
entier )
2 // M[i ][ j] = poids de l ' ar ê te i - >j , ou 0 si inexistante
3 variable dist : tableau [n ] de entier
4 variable visite : tableau [ n] de booleen
5 variable pred : tableau [n ] de entier // pr é dé
cesseurs
6 variable u , v , min_dist , i : entier
7 debut
8 // Initialisation
9 pour i de 0 a n -1 faire
10 dist [ i] <- + INFINI ; visite [ i] <- faux ; pred
[i ] <- -1
11 fin_pour
12 dist [ s] <- 0
13

14 // n it é rations
15 pour i de 0 a n -1 faire
16 // Choisir le sommet non visit é de distance minimale
17 u <- trouver_min ( dist , visite , n)
18 si u = -1 alors retourner fin_si // tous les
sommets accessibles trait és
19 visite [u ] <- vrai
20

21 // Mettre à jour les voisins de u

22 pour v de 0 a n -1 faire
23 si M[u ][ v] > 0 et non visite [ v] alors // ar ê te (u ,
v) existe
24 si dist [u] + M [u ][ v] < dist [ v] alors
25 dist [ v] <- dist [ u] + M[ u ][ v ]
26 pred [ v] <- u
27 fin_si
28 fin_si
29 fin_pour
30 fin_pour
31

32 // Affichage des ré sultats

33 pour i de 0 a n -1 faire

46
CHAPTER 7. GRAPHES ET ALGORITHMES Algorithmique
SUR GRAPHES & Complexité  GL/SIAD
34 afficher " dist [" , s , " - >" , i , "] = " , dist [i]
35 fin_pour
36 fin

✰ Application de Dijkstra sur G1

2
2 3

1 1 4 5 Étape
1

0 ∞
d[1] d[2] d[3] d[4] d[5]

3 2
4 2 Init. ∞ ∞ ∞

3
Visit. 1 0 4 ∞ ∞

5
Visit. 2 0 2 5 ∞

5
Visit. 3 0 2 3 5
Visit. 4 0 2 3 5

2 1 2
Chemin optimal 1→5 : 1→
− 2→
− 3→
− 5, longueur = 5.

Complexité : O(n ) 2
avec tableau simple, O((n + m) log n) avec tas min.

47
Chapitre 8
Techniques de Programmation
8.1 Récursivité
■ Dénition : Récursivité
Une fonction (ou procédure) est récursive si elle s'appelle elle-même pour résoudre
un sous-problème de taille réduite.

Structure obligatoire :
Cas de base
Cas récursif
1. : condition d'arrêt (résolu directement, sans appel récursif ).
2. : ramène au même problème de taille strictement inférieure.

LDA  Récursivité sur les listes : somme des éléments

1 // Somme ré cursive d ' une liste cha îné e
2 fonction somme_liste (n : pointeur vers Noeud ) : entier
3 debut
4 si n = NULL alors
5 retourner 0 // cas de base
6 sinon
7 retourner n. valeur + somme_liste ( n. suivant ) // cas ré
cursif
8 fin_si
9 fin
10

11 // Hauteur d ' un arbre binaire

12 fonction hauteur (n : pointeur vers NoeudABR ) : entier
13 debut
14 si n = NULL alors retourner 0 fin_si // cas de base
15 retourner 1 + max ( hauteur (n . gauche ) , hauteur (n . droit ) )
16 fin
17

18 // Nombres de Fibonacci (ré cursivit é NAIVE : O (2^ n) )

19 fonction fibonacci ( n : entier ) : entier
20 debut
21 si n <= 1 alors retourner n fin_si // F (0) =0 , F (1) =1
22 retourner fibonacci (n -1) + fibonacci (n -2)

48
CHAPTER 8. TECHNIQUES DE PROGRAMMATION
Algorithmique & Complexité  GL/SIAD
23 fin

8.2 Diviser pour Régner

■ Dénition : Diviser pour régner (Divide and Conquer)
Paradigme algorithmique en 3 phases :

Diviser
Régner
1. : découper le problème en sous-problèmes plus petits.

Combiner
2. : résoudre chaque sous-problème récursivement.
3. : fusionner les solutions partielles.

Exemples : Tri fusion O(n log n), Recherche dichotomique O(log n), multiplication
de matrices de Strassen O(n2.807 ).
LDA  Puissance rapide  diviser pour régner
1 // Calculer a^ n en O( log n) au lieu de O (n)
2 fonction puissance_rapide (a , n : entier ) : entier
3 debut
4 si n = 0 alors retourner 1 fin_si // cas de
base
5 si n mod 2 = 0 alors
6 // n est pair : a^n = ( a ^( n /2) ) ^2
7 variable demi : entier <- puissance_rapide (a , n div 2)
8 retourner demi * demi
9 sinon
10 // n est impair : a ^n = a * a ^( n -1)
11 retourner a * puissance_rapide (a , n -1)
12 fin_si
13 fin
14 // Trace pour puissance_rapide (2 , 10) :
15 // 2^10 = (2^5) ^2 = (2 * 2^4) ^2 = (2 * (2^2) ^2) ^2 = ...
16 // 4 appels ré cursifs seulement , au lieu de 10 !

8.3 Programmation Dynamique

■ Dénition : Programmation dynamique
mémorisant les résultats intermédiaires
sous-
Technique qui résout un problème en

problèmes chevauchants structure optimale sous-problème

pour éviter de les recalculer. Applicable quand le problème présente des
et une .

49
Algorithmique & Complexité  GL/SIAD
CHAPTER 8. TECHNIQUES DE PROGRAMMATION
LDA  Fibonacci par mémoïsation  O(n) au lieu de O(2 ) n

1 // Avec un tableau de mé mo ï sation

2 variable memo : tableau [ MAX ] de entier
3 // Initialiser memo à -1 ( non calcul é)
4

5 fonction fibonacci_dp ( n : entier ) : entier

6 debut
7 si n <= 1 alors retourner n fin_si
8 si memo [n] <> -1 alors retourner memo [ n] fin_si // d éj
à calcul é !
9 memo [ n] <- fibonacci_dp (n -1) + fibonacci_dp (n -2)
10 retourner memo [n ]
11 fin
12

13 // Version BOTTOM - UP ( ascendante , sans ré cursion ) :

14 fonction fibonacci_bu ( n : entier ) : entier
15 variable F : tableau [n +1] de entier
16 debut
17 F [0] <- 0 ; F [1] <- 1
18 pour i de 2 a n faire
19 F[ i] <- F[i -1] + F[i -2] // on r é utilise les r é
sultats calcul é s
20 fin_pour
21 retourner F[n ]
22 fin

8.4 Algorithmes Gloutons (Greedy)

■ Dénition : Algorithme glouton
Un algorithme glouton prend à chaque étape la décision localement optimale
sans revenir en arrière, dans l'espoir d'obtenir une solution globalement optimale.

LDA  Rendu de monnaie glouton

1 // Rendu de monnaie avec des pi è ces standard
2 // pi è ces tri é es en ordre DÉ CROISSANT ( ex : [200 , 100 , 50 ,
20 , 10 , 5, 2, 1])
3 procedure rendu_monnaie ( pieces : tableau de entier ,
4 n_pieces , montant : entier )
5 variable i , nb : entier
6 debut
7 pour i de 0 a n_pieces -1 faire
8 nb <- montant div pieces [i] // nombre de pi è ces de
cette valeur
9 si nb > 0 alors
10 afficher nb , " pi è ce (s) de " , pieces [i ]

50
CHAPTER 8. TECHNIQUES DE PROGRAMMATION
Algorithmique & Complexité  GL/SIAD
11 montant <- montant - nb * pieces [i ]
12 fin_si
13 fin_pour
14 si montant > 0 alors afficher " Rendu impossible
exactement " fin_si
15 fin
16 // Note : glouton est optimal pour les syst è mes de pi è ces
standard
17 // mais pas toujours pour des syst è mes arbitraires !

❍ Comparaison des paradigmes

Paradigme Idée clé Avantage Exemple
Récursivité S'appelle soi-même Code élégant Parcours d'arbre
Diviser/Régner Divise, résout, combine O(n log n) Tri fusion
Prog. Dyn. Mémorise les résultats Évite recalculs Fibonacci, sac à dos
Glouton Choix local optimal Simple, rapide Dijkstra, monnaie

51
PARTIE III  Corrigés Complets des
Examens S1 à S7
8.4 S1  Rattrapage Semestre 5
8.4.0 Exercice 1  Ordres de grandeur (5 pts)
Fonctions : f = 4n + 22 f = 4n + 12 f
1
1
3
, 2
2
, 3 = n2 log(5n4 ), f4 = 12 n2 − 10n − 60,
f =2−
Q1  Trouver les Grand O (3 pts)
5 n

➤ Réponse
ˆ f1 : terme dominant 4n3 ⇒ O(n3 )

ˆ f2 : terme dominant 4n2 ⇒ O(n2 )

ˆ f3 = n2 (log 5 + 4 log n), terme dominant 4n2 log n ⇒ O(n2 log n)

ˆ f4 : terme dominant
1 2
2
n ⇒ O(n2 )

ˆ f5 → 2 (constante bornée) ⇒ O(1)

Q2  Ordre croissant (2 pts)

➤ Réponse
O(1) ≺ O(n2 ) ≺ O(n2 log n) ≺ O(n3 )
| {z } | {z } | {z } | {z }
f5 f2 , f 4 f3 f1

8.4.0 Exercice 2  Somme Parallèle (10 pts)

Q1  Algorithme somParallele (2 pts)
52
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
➤ Réponse
Algorithm 1:
Entrées:
somParallele(tabReel, n)

Sortie:
tabReel[0..n-1] : tableau de réels, n = 2k

Tant que n > 1 faire

Somme de tous les éléments

Pour i ← 0 à n/2 − 1 faire

1
2
3 tabReel[i] ← tabReel[2i] + tabReel[2i + 1]
4 n←n÷2
retourner tabReel[0]
5

Q2  Algorithme principal (2 pts)

➤ Réponse
Algorithm 2:
Répéter
Programme principal

1
n jusqu'à
Pour i ← 0 à n − 1 faire
2 lire n =1 puis2( )
3
4 lire tabReel[i]

acher
5 S← somParallele(tabReel , n)
6 S
"Somme = "

Q3  Fonction puis2 (1 pt)

➤ Réponse
Algorithm 3:
Entrées:
puis2(n) : entier

Sortie: n = 2
n : entier

si n ≤ 0 alors
k
1 si , sinon 0

retourner
1
2 0

Tant que n > 1 faire

si n mod 2 ̸= 0 alors
3

retourner
4
5 0

6 n←n÷2
7retourner 1

8.4.0 Exercice 3  File FIFO (5 pts)

Q1  Dessin de la le [5, 22, 1, 8] (1 pt)
53
Algorithmique & Complexité  GL/SIAD PARTIE III  Corrigés
➤ Réponse
premier dernier

5 22 1 8 ∅

Q2  Primitive inserer (2 pts)

➤ Réponse
Algorithm 4:
Entrées:
inserer(f, val)

f : t_le, val : entier

si [Link] = ∅ alors
1n← [Link] ← val
allouer(t_element) ; ; [Link] ← ∅
2
3 [Link] ← n [Link] ← n
;

4sinon
5 [Link] ← n ; [Link] ← n

Q3  Primitive supprimer (2 pts)

➤ Réponse
Algorithm 5:
Entrées:
supprimer(f ) : entier

Sortie:
f : t_le

si [Link] = ∅ alors
val : entier
1
2 erreur "File vide"

si alors
3 temp ← [Link] ; val ← [Link] ; [Link] ← [Link]
4 [Link] = ∅
5 [Link] ← ∅
6 libérer(temp) ; retourner val

8.4 S2  Listes Chaînées & Matrice de Toeplitz

8.4.0 Exercice 1  Gestion des Notes (10 pts)
Q1  Structure de données (2 pts)
➤ Réponse
1 structure Note
2 valeur : reel
3 coeff : reel
4 suivant : pointeur vers Note
5 fin_structure
6

7 structure Etudiant

54
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
8 numero : entier
9 nom : chaine [50]
10 prenom : chaine [50]
11 moy : reel // à calculer
12 eval : pointeur vers Note // liste des notes
13 precedent : pointeur vers Etudiant
14 suivant : pointeur vers Etudiant
15 fin_structure

Q2  Supprimer un étudiant (2 pts)

➤ Réponse
Algorithm 6: supprimerEtudiant(tête, num, ok)

Tant que c ̸= ∅ et [Link] ̸= num faire

1c ← tete
2
3 c ← [Link]
si c = ∅ alors
retourner
4
5 ok ← FAUX ;

6si [Link] ̸= ∅ alors

7 [Link] ← [Link]
8sinon
9 tete ← [Link]
10 si [Link] ̸= ∅ alors
11 [Link] ← [Link]
12 libérer(c) ; ok ← VRAI

Q3  Insérer une note (2 pts)

➤ Réponse
Algorithm 7: insererNote(tête, num, val, coe )

si c ̸= ∅ alors
1 Trouverc tel que [Link] = num dans la liste depuis tete
2
3 n ← allouer(Note) ; [Link] ← val ; [Link] f ← coef f
4 [Link] ← [Link] ; [Link] ← n

Q4  Nombre de notes (2 pts)

55
Algorithmique & Complexité  GL/SIAD PARTIE III  Corrigés
➤ Réponse
Algorithm 8:
[Link] = num si c = ∅ alors
nbNotes(tête, num) : entier

retourner −1
1 c
Trouver tel que ;
2

Tant que note ̸= ∅ faire

3
nb ← 0 note ← [Link]
;
4
5 nb ← nb + 1 note ← [Link]
;

retourner nb
6

Q5  Procédure moyennesEtudiants (2 pts)

➤ Réponse
Algorithm 9: moyennesEtudiants(tête)

Tant que e ̸= ∅ faire

1e ← tete
2

Tant que n ̸= ∅ faire

3 sN C ← 0 sC ← 0 n ← [Link]
; ;
4
5 sN C ← sN C + [Link] × [Link] f ; sC ← sC + [Link] f ;
n ← [Link]
6 si sC > 0 alors
7 [Link] ← sN C/sC
8 e ← [Link]

8.4.0 Exercice 2  Matrice de Toeplitz (10 pts)

Q1  Somme de deux Toeplitz (2 pts)
➤ Réponse
Oui. Si A et B sont Toeplitz, alors (A + B)i,j = ai,j + bi,j = ai−1,j−1 + bi−1,j−1 =
(A + B)i−1,j−1 . La propriété est préservée. □

Q2  Additionner en O(n) (3 pts)

➤ Réponse
Une matrice Toeplitzn×n est entièrement déterminée par 2n−1 valeurs (1ère ligne
+ 1ère colonne). On stocke A et B comme des vecteurs a[1..2n − 1] et b[1..2n − 1].
La somme est c[k] = a[k] + b[k] pour k = 1 à 2n − 1. Complexité : O(n).

Q3 & Q4  Produit et complexité (5 pts)

56
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
➤ Réponse
Pn

complexité O(n )
Le produit y = Tx est une convolution : yi = j=1 ti−j+n · xj .
2
Méthode naïve : n produits scalaires de taille n⇒ .
Méthode optimisée via FFT ⇒ O(n log n).

8.4 S3  Crible, ABR et Graphes

8.4.0 Exercice 1  Crible d'Ératosthène (9 pts)
Q1  Illustration sur les 10 premiers entiers (3 pts)
➤ Réponse
1 2 3 4 5 6 7 8 9 10

1
Init. 0 0 0 0 0 0 0 0 0 0

1 1 1 1
Marquer 1 0 0 0 0 0 0 0 0 0

1
Multiples de 2 1 0 0 0 0 0

Résultat Ö ✓ ✓
Multiples de 3 1 0 0 1 0 1 0 1 1
Ö ✓ Ö ✓ Ö Ö Ö

Nombres premiers ≤ 10 : 2, 3, 5, 7
Q2  Algorithme (3 pts)
➤ Réponse
Algorithm 10: cribleEratosthene(n)

Pour i ← 2 à ⌊ n⌋ faire
1tab[1..n] ← 0 tab[1]
;
√ ←1
si tab[i] = 0 alors
2
3

Tant que j ≤ n faire

4 j ← 2i
5
6 tab[j] ← 1 ; j ← j + i

Pour i ← 2 à n faire
si tab[i] = 0 alors
7

acher i
8
9

Q3  Complexité (3 pts)
➤ Réponse
O(n log log n)  quasi-linéaire, car on ne traite que les multiples des premiers
√
≤ n.

57
Algorithmique & Complexité  GL/SIAD PARTIE III  Corrigés
8.4.0 Exercice 2  Opérations sur les Arbres (11 pts)
Q1 à Q3  Parcours, résultats et insertions
➤ Réponse
Inxe : 1, 2, 3, 5, 6, 7, 9, 10, 12, 15, 20 Préxe :
Postxe : 1, 3, 2, 6, 9, 7, 5, 12, 20, 15, 10
(croissant)

Insertions : →
10, 5, 2, 1, 3, 7, 6, 9, 15, 12, 20
8 →
ls gauche de 9 ; 6 →
déjà présent (doublon ignoré) ; 4 ls
droit de 3.

Q4  Suppression du n÷ud 2 (1 pt)

➤ Réponse
Le n÷ud 2 a deux ls (1 et 3). On le remplace par son successeur inxe : 3 .
L'arbre conserve 3 à la place de 2, avec 1 en ls gauche et 4 en ls droit de 3.

Q5  Complexité de recherche (1 pt)

➤ Réponse
Cas moyen : O(log n) (arbre équilibré). Pire cas : O(n) (arbre dégénéré  inser-
tions en ordre trié).

Q6  Structure pt_noeud (2 pts)

➤ Réponse
1 structure pt_noeud
2 cle : entier
3 gauche : pointeur vers pt_noeud
4 droit : pointeur vers pt_noeud
5 fin_structure

Plus court chemin  Q1 Dijkstra G1 : 1 → 5 (1 pt)

➤ Réponse
2 1 2
Chemin : 1→
− 2→
− 3→
− 5, longueur = 5. (Voir table Dijkstra dans le cours Ch.7.)

Q3  Matrice d'adjacence G1 (2 pts)

➤ Réponse
 
0 2 4 0 0
2 0 1 3 0
 
MG1 4
= 1 0 0 2
0 3 0 0 1
0 0 2 1 0

58
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
8.4 S4  Reconstruction d'Arbre & Magasin

8.4.0 Exercice 1  Arbres Binaires (10 pts)

Préxe : 3,6,8,13,12,5,21,20,28,25 Inxe : 8,6,3,12,13,5,20,21,25,28

Q1  Reconstruction (2 pts)
➤ Réponse
Méthode : racine = premier du préxe = 3 . Dans l'inxe, 3 est en position 3 : 2
n÷uds à gauche {8,6}, 7 n÷uds à droite {12,13,5,20,21,25,28}.

6 13

8 12 5

21

20 28

25

Q2  Structure (2 pts) : Voir structure NoeudABR dans le cours.

Q3  Fichier vers arbre (2 pts)

➤ Réponse
Algorithm 11: chierVersArbre(nomFichier)

Tant que non n_de_chier(f ) faire

1 f racine ← ∅
Ouvrir chier ;
2
3 val
lire f racine ←
dans ; inserer_ABR(racine, val)
4 f retourner racine
Fermer ;

Q4  Somme des feuilles (2 pts)

59
Algorithmique & Complexité  GL/SIAD PARTIE III  Corrigés
➤ Réponse
Algorithm 12: O(n)
si n = ∅ alors
sommeFeuilles(n) : entier 

retourner
1
2 0

si [Link] = ∅ et [Link] = ∅ alors

retourner [Link]
3
4
retourner
5 [Link]
sommeFeuilles( ) + sommeFeuilles([Link])

Q5  Hauteur (2 pts)
➤ Réponse
Algorithm 13: O(n)
si n = ∅ alors
hauteur(n) : entier 

retourner
1
2 0

3retourner 1 + max( hauteur([Link]), hauteur([Link]))

8.4 S5  Ordres de Grandeur, Carré Magique, Tas

8.4.0 Exercice 1  Ordres de Grandeur (6 pts)
Q1 & Q2 (4 pts)
➤ Réponse
f1 = 3n3 − 2n−2 ⇒ O(n3 ) f2 = n3 − 12 ⇒ O(n3 ) f3 ⇒ O(n2 log n) f4 ⇒
O(n2 ) f5 = 1/n ⇒ O(1)
2 2 3
Ordre : O(1) ≺ O(n ) ≺ O(n log n) ≺ O(n ), soit f5 ≺ f4 ≺ f3 ≺ f1 = f2 .

Q3  Complexité de l'algorithme donné (2 pts)

➤ Réponse
En supposant la boucle interne décrémentale (j ← j − 1, ce qui semble être
l'intention) et i partant de n, divisant par 2 :

ˆ Boucle externe : log2 n itérations (i = n, n/2, . . . , 1).

ˆ Pour chaque i, boucle interne : 2i itérations.

Plog n n
P∞ 1
T (n) = k=0 2· 2k
= 2n k=0 2k = 4n ⇒ O(n)

8.4.0 Exercice 2  Carré Magique (8 pts)

Q1  Algorithme (2 pts)
60
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
➤ Réponse
Algorithm
P
14: c−1
estCarreMagique(T, c) : booléen

Pour i ←P1 à c − 1 faire

1
ref ← T [0][j]
j=0

T [i][j] si s ̸= ref alors

2
c−1

retourner
3 s← j=0 ;
4 FAUX

Pour j ←P 0 à c − 1 faire
T [i][j] si s ̸= ref alors
5
c−1

retourner
6 s← i=0 ;
7 FAUX

retourner
8 VRAI

Q2 à Q5
➤ Réponse
n = c2 (taille des données). Complexité : O(c2 ) = O(n) (optimal car il faut lire
tous les éléments).
Pour vérier les valeurs 1 à c2 : utiliser un tableau de marques vu[1..c2 ]. Coût
supplémentaire O(n), total O(n).

8.4.0 Exercice 3  Tas (6 pts)

Tas construit depuis {25,60,35,10,5,20,65,45,70,40,50,55,30,15} :

➤ Réponse
Résultat après insertion de toutes les clés : [70, 65, 60, 25, 50, 55, 35, 10,
5, 40, 45, 20, 30, 15]
Q1 & Q2 : Voir algorithmes inserer_tas, supprimer_max et heap_sort dans le
Chapitre 6.

8.4 S6  Preuves, Arbres 2-3 et Fusion

8.4.0 Exercice 2  Arbres 2-3 (8 pts)
Q3  Insertion puis suppression de c redonne A (2 pts)
➤ Réponse
c est plus grand que toutes les clés de A⇒c va toujours à l'extrémité droite. Les
éclatements lors de l'insertion ne touchent que le chemin droit. La suppression
de c défait ces mêmes éclatements en fusionnant le chemin droit. On retrouve
exactement A. □

Q4  O(nh) rééquilibrages (2 pts)

61
Algorithmique & Complexité  GL/SIAD PARTIE III  Corrigés
➤ Réponse
Chaque insertion/suppression de c déclenche au plus h éclatements/fusions (un
par niveau). Pour n opérations : n × h = O(nh).

Q5  Coût amorti non constant (1 pt)

➤ Réponse
pas constant
Coût amorti = O(nh)/n = O(h) = O(log n) ̸= O(1). Le coût amorti du rééquili-
brage n'est . □

8.4.0 Exercice 3  Pile avec Files & Fusion (7 pts)

Q1  Pile avec deux les (4 pts)
➤ Réponse
Empiler( ) :
Deux les F1 (principale), F2 (auxiliaire).

Dépiler() :
x enler x dans F1 . ⇒ O(1).
transférer tous les éléments de F1 vers F2 sauf le dernier. Récupérer
ce dernier. Échanger F1 ↔ F2 . ⇒ O(n).

Q2  Fusion de listes triées (3 pts)

➤ Réponse
Algorithm 15: L L O(|L | + |L |)
fusion( 1, 2)  1 2

Tant que p ̸= ∅ et p ̸= ∅ faire

1p ← 1 L
tete( p ←
1) ; L 2L← tete( 2) ; liste vide

si p .val < p .val alors

2 1 2
3 1 2
4 L p .val p ← p .suiv
insererFin( , ) ;

sinon si p .val > p .val alors

1 1 1

5 1 2
6 L p .val p ← p .suiv
insererFin( , ) ;

sinon
2 2 2

7
8 insererFin(L, p1 .val) ; p1 ← p1 .suiv ; p2 ← p2 .suiv

retourner L
9 Vider la liste non épuisée dans L
10

Vérication : fusion((3,5,8,11),(2,3,5,14)) = (2,3,5,8,11,14) ✓

8.4 S7  Algorithmes de Tri et Listes de Notes

8.4.0 Exercice 1  Algorithmes de Tri (9 pts)
Q1  Comportement cas extrêmes (5 pts)
62
PARTIE III  Corrigés Algorithmique & Complexité  GL/SIAD
➤ Réponse
Algorithme Trié ↗ Trié ↘ Explication
Sélection O(n2 ) O(n2 ) Cherche toujours le min du reste
Insertion O(n) O(n2 ) Déjà trié ⇒ 0 décalage
Bulles (avec ag) O(n) O(n2 ) Flag détecte l'absence d'échanges

Conséquence : tri insertion/bulles idéal pour données quasi-triées ; sélection

invariant.

Q2  Récurrences (4 pts)
➤ Réponse
(a) T (n) = T (n/3) + O(1) : a = 1, b = 3, p = log3 1 = 0, f (n) = O(1) = Θ(n0 )
⇒ ⇒ O(log n)
(b) T (n) = 7T (n/2) + n
Cas 2
2
a = 7, b = 2, p = log2 7 ≈ 2.807, f (n) = n2 =
:

O(n2.807−ε ) ⇒ Cas 1 ⇒ O(nlog2 7 ) ≈ O(n2.81 )

8.4.0 Exercice 2  Gestion des Notes (11 pts)

Voir S2, Exercice 1  mêmes structures et mêmes algorithmes (liste doublement
chaînée d'étudiants, liste de notes, suppression, insertion, moyenne).

Q4  Calcul de la moyenne d'un étudiant (2 pts)

➤ Réponse
Algorithm 16: moyenneEtudiant(tête, num) : réel

si c = ∅ alors
1 c
Trouver [Link] = num
tel que

retourner −1
2
3

Tant que note ̸= ∅ faire

4sN C ← 0 sC ← 0 note ← [Link]
; ;
5
6 sN C ← sN C + [Link] × [Link] f ; sC ← sC + [Link] f ;
note ← [Link]
si sC = 0 alors
retourner
7
8 0

9 retourner sN C/sC

Bonne révision et bon courage pour l'examen !

Lisez attentivement chaque énoncé · Posez vos
hypothèses · Montrez chaque étape · Vériez vos
réponses
63