Transparents INFOB233 Programmation 2ème partie http

1

Transparents

INFOB233

Programmation 2ème partiehttp ://www.info.fundp.ac.be/˜pys/cours/infob233/

Pierre-Yves SCHOBBENS

[email protected]

bureau 409

081/724990

31 janvier 2011

TABLE DES MATIÈRES 1-1

Table des matières

1 La récursion 4

1.1Récursion bien fondée 51.1.1Relation bien fondée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2Récursion bien fondée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.3Cas de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.4Preuves par induction générale . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.5Récursion croisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.6Fonctions récursives en Pascal . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1.7Récursion croisée en Pascal . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.1.8Procédure récursive : Exemple du labyrinthe . . . . . . . . . . . . . . . . . 13

1.1.8.1Exigences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2Structures de données récursives 171.2.1Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.2.2Codage en Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18


1.3Arbres binaires 191.3.1Arbres binaires en Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.3.2Construire un arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.3.3Observer un arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3.4Recherche dans un arbre binaire . . . . . . . . . . . . . . . . . . . . . . . 24

1.3.5Arbres binaires triés (abt) . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.3.6Recherche dans un arbre binaire trié . . . . . . . . . . . . . . . . . . . . . 26

1.3.6.1Recherche en Pascal . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.4Arbres ordonnés 281.4.1Arbres ordonnés en Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.4.2Représentation aîné/cadet . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2 Temps d’exécution 31

2.1Preuve de programmes 322.1.1Règles de style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.1.2Affaiblissement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.1.3Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35


2.1.3.1Affectation dans un tableau . . . . . . . . . . . . . . . . . . . . . . 36

2.1.3.2Pointeurs : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.1.4Séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.1.5Conditionnelle (if) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.1.6Boucle for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.1.7Boucle while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.1.8Appel de procédure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.1.9Appel de fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.2Ordre de grandeur 432.2.1Calcul avec O. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.2.1.1Théorèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.3Règles pour le temps d’exécution 462.3.1Séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.3.2Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.3.3Appel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.3.4Conditionnelle (if) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.3.5Boucle for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50


2.3.6Boucle while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.3.7Temps des sous-programmes récursifs . . . . . . . . . . . . . . . . . . . . 52

2.3.7.1Équations récurrentes . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.3.8Espace en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

2.3.9Exemple 1 : Primalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

2.3.10Exemple 2 : Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.3.10.1Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.3.10.2Définition récursive . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.3.10.3Programme récursif . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2.3.11Exemple 3 : PosMax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.3.11.1Version améliorée . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.3.12Exemple 4 : Tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.3.13Exemple 5 : Tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3 Introduction aux Types Abstraits 71

3.1Définition 723.1.1Exemple : Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3.1.2Exemple : Les listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74


3.2Avantages 75

3.3Syntaxe 76

3.4Comment donner les propriétés 793.4.1Par modèles [VDM, Z, B] . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.4.1.1Exemple : TA listes par modèle . . . . . . . . . . . . . . . . . . . . 81

3.4.2Par axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.5Complétude 853.5.1Méthode des constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.5.1.1Exemple : Listes : constructeurs . . . . . . . . . . . . . . . . . . . . 87

3.5.2Méthode des observateurs . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.6Le type abstrait “Pile” 903.6.1Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

3.6.2Implémentation : Tableau+pointeur . . . . . . . . . . . . . . . . . . . . . . 92

3.7Types Abstrait Ensemble fini 933.7.1Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94


3.8Dictionnaire 953.8.0.1Axiomes par Constructeurs . . . . . . . . . . . . . . . . . . . . . . 96

3.8.1Ensembles avec procédures . . . . . . . . . . . . . . . . . . . . . . . . . 97

4 Implémentation des ensembles 98

4.1Tableau de Booléens 1004.1.1Fonctions et procédures . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4.2Liste 1074.2.1union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.2.2intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.2.3Temps de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.2.4Place en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.2.4.1Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.3Liste sans doubles 1144.3.1Place en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

4.3.2Temps d’exécution [Liste chaînée] . . . . . . . . . . . . . . . . . . . . . . 115


4.4Listes triées 1174.4.1Place en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

4.4.2Temps d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

4.5Tables de hachage 1234.5.0.1Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

4.5.0.2Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

4.5.1Ensemble des collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

4.5.1.1Temps d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 130

4.5.1.2Place mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

4.5.1.3Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

4.5.2Représenter la liste des collisions dans la table . . . . . . . . . . . . . . . . 132

4.5.2.1Temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4.5.2.2Place . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4.5.3Eviter les collisions en agrandissant la table . . . . . . . . . . . . . . . . . 136

4.6Arbres binaires de recherche 1394.6.1Fonctions et Procédures . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.6.2Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146


4.6.2.1Elimination de la récursivité terminale . . . . . . . . . . . . . . . . . 147

4.6.3Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

4.6.4Supprimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

4.6.4.1Temps d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 153

4.7Arbres rouges/noirs 1544.7.1Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

4.7.1.1Déclaration Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . 155

4.7.1.2 Invariants de données . . . . . . . . . . . . . . . . . . . . . . . . . 156

4.7.2Fonctions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

4.7.3Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

4.7.4Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

4.7.5Supprimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

4.7.5.1Rétablir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

4.8B-Arbres 1814.8.1Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

4.8.1.1Déclaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

4.8.1.2 Invariant de données . . . . . . . . . . . . . . . . . . . . . . . . . 184


4.8.2Procédures et fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

4.8.2.1Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

4.8.2.2Ensemble vide . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

4.8.2.3Diviser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

4.8.2.4 Insérer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

4.8.2.5Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

4.8.2.6Supprimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

5 TA File de priorité 193

5.1Spécification par modèle 194

5.2Implémentation 1955.2.1Arbre binaire partiellement ordonné (APO) . . . . . . . . . . . . . . . . . . 195

5.2.2Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

5.2.3Procédures et fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

6 Diviser pour règner 211


6.1Idée 2116.1.1Cas de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

6.1.2Choix possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

6.2Exemple : le Spécification 2156.2.1Solution D1 : Tri par INSERTION . . . . . . . . . . . . . . . . . . . . . . . 216

6.2.2Solution D2 : Tri par FUSION . . . . . . . . . . . . . . . . . . . . . . . . . 217

6.2.3Solution C1 : Tri par SELECTION . . . . . . . . . . . . . . . . . . . . . . . 218

6.2.4Solution C2 : ≈ QUICKSORT . . . . . . . . . . . . . . . . . . . . . . . . 219

6.2.5Temps d’exécution minimal d’un tri . . . . . . . . . . . . . . . . . . . . . . 220

6.3 Multiplication 2226.3.1Méthode classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

6.3.2Diviser pour règner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

6.3.2.1Puissances rapides . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6.3.2.2Fibonacci par puissances rapides . . . . . . . . . . . . . . . . . . . 227

7 Programmation Dynamique 228


7.1Mémoïsation 2327.1.1Idée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

7.1.2Détail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

7.2Récursivité Ascendante 2357.2.1Idée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

7.2.2Avantages de la Récursivité Ascendante . . . . . . . . . . . . . . . . . . . 236

7.2.3Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

7.2.4Sous-problèmes inutiles : Exemple . . . . . . . . . . . . . . . . . . . . . . 237

7.2.4.1Récursivité ascendante naïve . . . . . . . . . . . . . . . . . . . . . 238

7.2.5Économie de mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

7.2.6Exemple : Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

7.2.6.1Exemple : Fibonacci : Économie de mémoire . . . . . . . . . . . . . 241

7.2.7Exemple : Combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

7.3Programmation dynamique 2477.3.1Exemple : sac à dos discret . . . . . . . . . . . . . . . . . . . . . . . . . 249

7.3.2Diviser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

7.3.2.1Division en un élément / le reste . . . . . . . . . . . . . . . . . . . . 252


7.3.2.2Choix de l’article . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

7.3.2.3Conséquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

7.3.2.4 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

7.3.3Améliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

7.3.3.1Correct ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

7.3.4Multiplication de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

7.3.4.1Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

8 Algorithmes gloutons 270

8.1Sac à dos 2738.1.1Continu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

8.1.2Continu borné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

8.2Exemple : Les pleins d’essence 2748.2.1 Si on s’arrête, autant faire le plein : . . . . . . . . . . . . . . . . . . . . . . 277

8.2.2 Si on a de quoi atteindre la prochaine station, pas d’arrêt : . . . . . . . . . . 278

8.2.3Variante avec prix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280


8.3Exemple : Salle de spectacle 282

8.4Codes de Huffman 2868.4.1Codages des caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.4.1.1Fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.4.1.2Morse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.4.2Calcul du code optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

8.4.2.1Sans préfixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

8.4.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

8.4.2.3Moins fréquents . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

8.4.2.4Récursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296

8.4.2.5Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

8.4.2.6 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

8.5Exposants 302

8.6Le voyageur de commerce 3048.6.0.7Plus proche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

8.6.0.8Plus proche avant/arrière . . . . . . . . . . . . . . . . . . . . . . . 309


8.6.0.9Par arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

9 Générer et tester 311

9.1Principe 312

9.2Génération 314

9.3Améliorations 316

9.4Branch-and-bound 318

9.5Exemple : voyageur de commerce 319

TABLE DES MATIÈRES 2

Références

– T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduction à l’algorithmique, 2ème

éd., Dunod, Paris, 2002 (ISBN 2-10-003922-9).

pages 1-70, 121-153, 195-287, 315-382, 425-442.

Vous pouvez aussi utiliser l’ancienne édition :

T. Cormen, C. Leiserson, R. Rivest, Introduction à l’algorithmique, Dunod, Paris,

1994 (ISBN 2-10-003128-7).

– P. Berlioux et Ph. Bizard : Algorithmique : construction, preuve et évaluation de

programmes de (ed. Dunod)

TABLE DES MATIÈRES 3

Ce cours (et le livre) présupposent la connaissance :

1. du langage de programmation Pascal ; Si vous voulez vous mettre à niveau,

vous pouvez lire :

(a) N. Wirth, K. Jensen. Pascal User Manual and Report, Springer Verlag

(b) http ://www-ipst.u-strasbg.fr/pat/program/pascal.htm

2. Pour les exercices, du Langage de programmation C

3. des preuves mathématiques par induction

4. la preuve de programmes par pre- et post-conditions, par invariants de boucle.

Vous pouvez lire :

D. Gries, The Science of Programming, Springer

R. Backhouse, Construction et vérification de programmes, Masson, Paris, 1989

W. Vanhoof, Syllabus Méthodes de Programmation (1) (disponible sur

WebCampus)

CHAPITRE 1. LA RÉCURSION 4

CHAPITRE 1

LA RÉCURSION

Une définition est (directement) récursive si la terme défini apparaît lui-même

dans la définition

1.1 RÉCURSION BIEN FONDÉE 5

1.1 Récursion bien fondée

Le plus souvent, de telles “définitions” sont circulaires : elles ne définissent rien du

tout.

Pour qu’une récursion définisse vraiment quelque chose, il faut qu’elle soit bien

fondée : en l’utilisant on se ramène à des cas plus simples.

Exemple : factorielle: N → N

factorielle(0) = 1

factorielle(n) = n * factorielle(n-1) si n>0


1.1.1 Relation bien fondée

Une relation binaire quelconque < “plus simple” est bien fondée ssi il ne peut y

avoir de suite infinie strictement décroissante : a1 > a2 > a3 > . . ..

Ceci dépend de l’ensemble dans lequel on travaille :

par exemple, < sur les nombres entiers naturels N est bien fondée

tandis que < sur les nombres entiers relatifs Z ne l’est pas.

Dans ce cours, on se ramène aux nombres naturels par une fonction de mesure

m : . . . → N (où . . . est le type avec lequel on travaille). On utilise souvent aussi

un variant : une expression à resultat dans N.


1.1.2 Récursion bien fondée

Une définition récursive est bien fondée ssi il existe une relation bien fondée entre

les occurrences du terme défini telle que les occurrences qui apparaissent dans la

définition sont plus simples que le terme défini.

Exemple :

factorielle(0) = 1

Il n’y a aucune occurrence dans la définition, donc elles sont toutes plus simples.

factorielle(n) = n * factorielle(n-1) si n>0

L’occurrence factorielle(n-1) est plus simple que factorielle(n)

si on utilise la valeur de l’argument comme mesure : n-1 < n .


1.1.3 Cas de base

Les éléments b qui n’ont pas d’élément “plus simple” sont appelés les “cas de base”.

Par exemple :

– comme la mesure d’une liste est sa longueur, le cas de base d’un algorithme sur

les listes est une liste de longueur 0, càd une liste vide.

– comme la mesure d’un arbre est sa hauteur, le cas de base d’un algorithme sur

les arbres est une arbre de hauteur 0, càd un arbre vide.


1.1.4 Preuves par induction générale

Si pour tout élément,

en supposant qu’une propriété est vraie pour tous les élements plus simples,

on peut prouver qu’elle est vraie pour cet élément

alors

elle est vraie pour tous les éléments.

∀x : N (∀y < xP (y)) =⇒ P (x)

∀x : N P (x)

où < est bien fondé dans N.

Pour les cas de base b, il faut en fait prouver P (b).

Pour les autres, dès qu’on tombe sur P (y) plus simple, c’est prouvé !


1.1.5 Récursion croisée

Une récursion est croisée (ou mutuelle ) si plusieurs termes définis forment un

cycle.

Exemple (extrait du Larousse) :

Balayage : action de balayer.

Balayer : procéder à un balayage.

(Cet exemple est une récursion mal fondée.)


1.1.6 Fonctions récursives en Pascal

Les procédures et les fonctions récursives sont admises en Pascal. Les définitions

par égalités (comme pour factorielle ) ne sont pas admises, mais on les

traduit par des if then else .

funct ion factorielle (n : in teger ) : in teger ;

{ pré : n ≥ 0 }

{ post : f a c t o r i e l l e = n ∗ ( n−1) ∗ . . . ∗ 2 ∗ 1 }

{ v a r i a n t : n }

begin

i f n = 0

then factorielle := 1

else factorielle := n ∗ factorielle (n−1)

end


1.1.7 Récursion croisée en Pascal

Les récursions croisées sont admises en Pascal. Il faut d’abord déclarer les

procédures et fonctions comme forward pour que le compilateur connaisse leur

type avant qu’elles ne soient utilisées :

funct ion p1 (n : in teger ) : in teger forward ;


1.1.8 Procédure récursive : Exemple du labyrinthe

1.1.8.1 Exigences

Supposons qu’on reçoive un labyrinthe codé dans un tableau à deux dimensions

dont les cases sont soit blanches (pour un couloir) ou ’X’ pour un mur.

XXXXXXXXXXXXX X X XX X XXX XX X X X XX X X XXXXXXXXXXXXX

On demande d’imprimer un chemin vers la sortie.


Les objets utilisés par la procédure sont :

type xdim , ydim { i n t e r v a l l e s } ;

direction = nord ,est ,sud ,ouest ;

labychar = char { ’X ’ , ’ ’ , ’ . ’ } ;

position = record x : xdim ; y : ydim end ;

var laby : array [xdim ,ydim ] of labychar ;


La recherche en profondeur nous trouve un chemin de sortie récursivement : Elle

marquera d’un ’.’ les cases blanches où on est déjà passé.

procedure sortir (pos : position ) ;

var d : direction ;

begin

marquer (pos ) ;

i f sortie (pos ) then sortietrouvée ;

else for d := nord to ouest

i f accessible (pas (pos ,d ) ) then sortir (pas (pos ,d ) ) ;

end

Où accessible teste que la position n’est pas un mur et n’est pas déjà

marquée ; pas (pos ,d) avance d’un pas dans la direction d.


Base de la preuve : Le programme termine car le nombre de cases blanches (non

marquées) diminue toujours. Il atteint toutes les cases accessibles car il essaie

toutes les directions possibles.

Le chemin vers la sortie est constitué par les arguments de sortir ; on peut les

conserver dans une liste pour les afficher.

1.2 STRUCTURES DE DONNÉES RÉCURSIVES 17

1.2 Structures de données récursives

1.2.1 Liste

De même, on peut définir des structures de données récursivement.

Par exemple, une liste peut être définie comme étant soit une liste vide, soit

composée d’un élément (la tête) et d’une liste (le reste).

Exemple : 1 — 3 — 7 — 5 — 3 est une liste ;

sa tête est 1 ; son reste est 3 — 7 — 5 — 3

1.2 STRUCTURES DE DONNÉES RÉCURSIVES 18

1.2.2 Codage en Pascal

Les structures de données récursives sont interdites en Pascal, sauf pour les

pointeurs. On les implémente donc par des pointeurs. Ce codage se dérive

automatiquement de la définition récursive. Exemple :

type liste = ^ cell ;

cell = record

tête : information ;

reste : liste

{ i nv : longueur ( l ^ . res te ) < longueur ( l ) } ;

end ;

Cette façon de coder les listes s’appelle les listes (simplement) chaînées .

Note : il faut ajouter l’invariant de données sur liste , car rien ne garantit en Pascal que les

pointeurs sont sans cycles (bien fondés).

1.3 ARBRES BINAIRES 19

1.3 Arbres binaires

Un arbre binaire est soit un arbre vide, soit composé d’une information et de deux

arbres (le fils gauche et le fils droit).

Une mesure bien fondée est la hauteur de l’arbre.


1.3.1 Arbres binaires en Pascal

type arbreBinaire = ^ cell ;

cell = record

tête : information ;

gauche : arbreBinaire

{ inv : hauteur ( a ^ . gauche ) < hauteur ( a ) } ;

droit : arbreBinaire

{ inv : hauteur ( a ^ . d r o i t ) < hauteur ( a ) } ;

end ;


1.3.2 Construire un arbre binaire

On peut construire n’importe quel arbre binaire au moyen de deux opérations :

funct ion arbreVide : arbreBinaire ;

begin

arbreVide := nil ;

end


funct ion cons3 (f : information ; g ,d : arbreBinaire ) : arbreBinaire ;

var r : arbreBinaire ;

begin

new r ;

r ^ .tête := f ;

r ^ .gauche := g ;

r ^ .droit := d ;

cons3 := r ;

end


1.3.3 Observer un arbre binaire

funct ion info (a : arbreBinaire ) : information ;

begin

info := a ^ .tête

end

function gauche (a : arbreBinaire ) : arbreBinaire ;

begin

gauche := a ^ .gauche

end

function droit (a : arbreBinaire ) : arbreBinaire ;

begin

droit := a ^ .droit

end


1.3.4 Recherche dans un arbre binaire

La fonction dans nous dit si une information se trouve dans l’arbre :

funct ion dans (e :information ; a : arbreBinaire ) : boolean ;

dans (e , arbreVide ) = fa lse

dans (e , cons3 (f ,g ,d ) ) = (e=f ) or dans (e ,g ) or dans (e ,d )


1.3.5 Arbres binaires triés (abt)

Un arbre binaire est trié ssi : il est vide ou son information est plus grande que

toutes les informations contenues dans le fils de gauche et plus petite que toutes les

informations contenues dans le fils de droite, et ses deux fils sont des arbres

binaires triés.

5

3

2 4

8

7

6

9


1.3.6 Recherche dans un arbre binaire trié

La fonction dans nous dit si une information se trouve dans l’ABT :

funct ion dans (e :information ; a : abt ) : boolean ;

dans(e, arbreVide) = false

dans(e, cons3(f,g,d)) =

true si e = f

dans(e,g) si e < f

dans(e,d) si e > f

On ne parcourt qu’une branche dans l’arbre.


1.3.6.1 Recherche en Pascal

funct ion dans (e :information ; a : abt ) : boolean ;

begin

i f a = arbreVide

then dans := fa lse

else i f e = info (a )

then dans := t rue

else i f e < info (a )

then dans := dans (e ,gauche (a ) )

else dans := dans (e ,droit (a ) )

end

1.4 ARBRES ORDONNÉS 28

1.4 Arbres ordonnés

un arbre ordonné est vide ou composé d’une information et d’une liste d’arbres

(ses fils).

Le premier fils est appelé l’aîné ; le dernier, le puîné. Le suivant dans l’ordre est

appelé le cadet.

racine

ainé cadet de l’ainé puiné

petit-fils


1.4.1 Arbres ordonnés en Pascal

La définition récursive se code automatiquement en Pascal comme :

type arbreOrd = ^ cell ;

listearbreOrd = ^ celliste ;

cell = record

e : information ;

fils : listearbreOrd ;

end ;

celliste = record

person : arbreOrd ;

reste : listearbreOrd ;

end ;


1.4.2 Représentation aîné/cadet

On identifie souvent le type des arbres et des listes d’arbres :

type listearbreOrd = ^ cell ;

arbreOrd = listearbreOrd ; { inv ( a ) : a <> n i l }

cell = record

e : information ;

aîné : listearbreOrd ;

cadet : listearbreOrd ;

end

Notons que l’aîné représente (un pointeur vers) la liste des fils, tandis le cadet est

l’habituel pointeur vers le reste de la liste.

Exercice : quel est l’invariant de représentation ?

CHAPITRE 2. TEMPS D’EXÉCUTION 31

CHAPITRE 2

TEMPS D’EXÉCUTION

2.1 PREUVE DE PROGRAMMES 32

2.1 Preuve de programmes

Pour calculer le temps d’un programme, on a bien sûr besoin de sa preuve.

Voici donc un bref rappel de la preuve de programmes dans la logique de Hoare

avec preuve de terminaison.

Ici, {pre}S{post} signifie : chaque fois que l’on lance le programme S dans un

état qui vérifie pre, le programme se termine, et dans un état qui vérifie post .

Pour chaque règle, il faut démontrer ce qui est au-dessus de la barre avant de

pouvoir affirmer ce qui est en-dessous.


2.1.1 Règles de style

Pour que les règles de preuve simplifiées ci-après soient correctes, il faut que :

1. une fonction n’a pas d’effet de bord : elle ne modifie ni ses variables

non-locales, ni ses paramètres par variable.a

2. une fonction est déterministe : son résultat ne dépend que de la valeur de ses

arguments.

3. il n’y a pas de variables synonymes : lors d’un appel de procédure, les

paramètres par variable et les variables globales doivent désigner des

emplacements distincts.

4. Chaque sous-programme p (fonction ou procédure) a sa pré- et post-condition,

notées pre(p), post(p) et son variant Vp si elle est récursive.

aElle peut modifier ses variables locales ou ses paramètres par valeur, mais ceci n’a pas d’effet visible.


2.1.2 Affaiblissement

P ⇒ Q {Q}S{R}{P}S{R}

Q ⇒ R {P}S{Q}{P}S{R}


2.1.3 Affectation

{R[e/x] et pre(e)} x := e {R}

– R[e/x] signifie “R où l’on a remplacé toutes les occurrences libres de x par e”.

– x est un identificateur (nom) de variable.

– e est une expression du même type que x.

– pre(e) est la précondition de e, définie ci-dessous :

pre(f(~e)) = pre(f )[~e/~x] et pre(~e)

pre(~e) = pre(e1) et . . . et pre(en)

pre(a[i]) = pre(i) et bi ≤ i ≤ bs

pre(a.c) = pre(a)

pre(a↑) = pre(a) et not(free[a])

pre(v) = init(v)


2.1.3.1 Affectation dans un tableau

:

{pre(a[i]) et pre(e) et R[a([i] → e)/a] } a[i] := e{R}

où a est un nom de tableau ;

a([i] → e) signifie "le tableau a dont la case i a reçu la valeur e".

On peut généraliser [i] à une suite d’indexations s. On peut simplifier par la règle :

a([i] s → e) [j] = if i=j then a[j]( s → e) else a[j]

Si s est vide, on simplifie en : a(s → e) = e

L’égalité entre tableaux est calculée par extensionalité :

a = b ssi ∀ i : index, a[i] = b[i]

Les records sont aussi traités ainsi, avec la sélection à la place de l’indexation.


2.1.3.2 Pointeurs :

– La mémoire est un tableau MTindicé par les pointeurs de type T ;

– Un tableau de booléens free initialisé à true dit si une adresse n’est pas

allouée. free[nil] restera toujours vrai.

– pre(p^ ) = not free[p]

– p^ abrège MT[p]

new choisit un pointeur p libre et le réserve :

new(p)

post : (free0[p] = true) and (free = free0([p] → false))

dispose(p)

pre : not free[p]

post : free = free0([p] → true)


2.1.4 Séquence

{P}S1{R} {R}S2{Q}{P}S1;S2{Q}

2.1.5 Conditionnelle (if)

{P et B}S1{Q} {P et non B}S2{Q}

{P } if B then S1 else S2 {Q}

{P et B}S1{Q} P et non B ⇒Q

{P } if B then S1 {Q}


2.1.6 Boucle for

{I et l ≤ i ≤ h} S {I [succ(i) /i]}

{I [l/i]} for i := l to h do S {I [max(succ(h),l)/i]}

on suppose que :

– la variable i et les bornes l, h ne sont pas modifiées par le corps de la boucle.

– les bornes l, h ne dépendent pas de i.


2.1.7 Boucle while

{I et B et V = v0} S {I et V < v0}

{I } while B do S {I et non B}

où

– v0 est une variable logique, qui n’apparaît pas dans S, et retient la valeur

précédente du variant.

– V (le variant de boucle) est une expression de type natural qui borne le

nombre d’itérations.

– I (l’invariant de boucle) décrit ce qui reste vrai à chaque itération.

– < est une relation bien fondée (ici, sur les nombres naturels).

Le programmeur doit donner V, I . Mais les méthodes de programmation (Chap 6 et

suivants) donneront cette information.


2.1.8 Appel de procédure

{I et pre[~a/~x] et pre(~a) et Vp(~a) < v0} p(~a) {I et post[~a/~x]}

– pre, post sont la pré- et post-condition de la procédure.

– ~x en sont les paramètres formels.

– ~a en sont les arguments effectifs.

– I (l’invariant de contexte) ne contient pas de variables modifiées par p.

– pour une procédure récursive :

le variant de chaque appel récursif Vp(~a) doit être plus petit que celui du

sous-programme q dans lequel il se trouve. v0 est la valeur initiale de Vq(~x).


2.1.9 Appel de fonction

pre(f(~a)) et Vp(~a) < v0 =⇒ post[f(~a)/f,~a/~x]

où

– pre, post sont la pré- et post-condition de la fonction.

– ~x en sont les paramètres formels.

– ~a en sont les arguments effectifs.

– pour une fonction récursive :

le variant de chaque appel récursif doit être plus petit que celui du

sous-programme q dans lequel il se trouve. v0 est la valeur initiale de Vq(~x).

– Cet axiome peut être utilisé n’importe où dans une preuve.

2.2 ORDRE DE GRANDEUR 43

2.2 Ordre de grandeur

1. Le temps d’exécution dépend de la taille des données :

Soit n cette taille,

on veut une expression TP (n) du temps d’exécution du programme P .

2. Le temps d’exécution varie d’un facteur plus ou moins constant d’un ordinateur

à un autre.

3. La temps d’exécution pour les petites données est négligeable

⇒ On calcule seulement l’ordre de grandeur O de T (n), à une constante

près, et pour les données assez grandes (asymptotique).

O(T (n)) ≤ O(f(n)) ⇐⇒ ∃c, n0 > 0 : ∀n > n0 : T (n) ≤ c ∗ f(n)


2.2.1 Calcul avec O.

O(f(n)) = O(g(n))

Signifie :

O(f(n)) ≤ O(g(n)) ∧ O(g(n)) ≤ O(f(n))

Note : La notation officielle est f(n) = Θ(g(n)).


2.2.1.1 Théorèmes

Si la variable n ≥ 0, les constantes k, l ≥ 0 et f(n) ≥ 0 :

O(k.f(n)) = O(f(n))

O(f(n) + g(n)) = O(f(n)) si O(g(n)) ≤ O(f(n))

O(f(n)k) ≤ O(f(n)l) si 0 ≤ k ≤ l

O(nl) ≤ O(kn) si k > 1

O(ln) ≤ O(kn) si k > l

O(f(n)) ∗ O(g(n)) = O(f(n) ∗ g(n))O(max(f(n), g(n))) = O(f(n)) si O(g(n)) ≤ O(f(n))

2.3 RÈGLES POUR LE TEMPS D’EXÉCUTION 46

2.3 Règles pour le temps d’exécution

Pour chaque forme de programme, on a une règle de calcul de son temps

d’exécution. On peut donc calculer mécaniquement le temps de tout programme

non récursif.

2.3.1 Séquence

TS1;S2= TS1

+ TS2

Le temps pour faire la séquence d’opérations S1 puis S2 est la somme des temps

d’exécution de S1 et de S2.


2.3.2 Affectation

Tx:=E = TE + TA

Le temps pour calculer une affectation simple est le temps d’évaluer l’expression

TE plus le temps constant TA de mettre le résultat dans la variable. C’est le

modèle RAM (random access memory), où on peut lire ou écrire un type simple

(p.ex. un entier) en mémoire en temps constant.


2.3.3 Appel

Tf(e1,...,en) =∑

i

Tei +O(1) + Tf (Vf (e1, . . . , en)))

Le temps d’évaluer un appel de sous-programme est le temps d’évaluer ses

arguments, d’appeler le sous-programme, d’exécuter le corps du sous-programme.

Vf est le variant de f : une fonction des paramètres de f qui en mesure la

complexité.

On suppose Tf = O(1) pour les opérations prédéfinies sur les types simples

(addition, etc.)


2.3.4 Conditionnelle (if)

Tif B then S1 else S2= TB + if B then TS1

else TS2

Pour faire le test, il faut :

1. évaluer B

2. suivant sa valeur, faire S1 ou S2.

En pratique il est plus facile d’employer la borne supérieure :

Tif B then S1 else S2≤ TB +max(TS1

, TS2)

Exemple :

Tif false then while . . . = O(1) par la règle exacte

≤ O(Twhile...) par la règle approchée.


2.3.5 Boucle for

T for i :=l to h do S = Tl + Th + if l ≤ h then (h− l + 1) ∗ (TS +O(1)) else 0

On calcule l et h au début, puis il faut faire (h− l + 1) fois le corps ainsi que le

test et l’incrément (O(1)).

NB : On a souvent :

1. TS ≥ O(1) et donc O(TS +O(1)) = O(TS).

2. Tl et Th ≤ O(h− l + 1) ∗ TS , on peut alors négliger ces termes.

3. l ≤ h

On emploie alors T for i :=l to h do S = O((h− l + 1) ∗ TS )


2.3.6 Boucle while

Comment savoir combien de fois la boucle est exécutée ?

on trouve un variant V qui diminue à chaque passage dans la boucle. Sa valeur

initiale est une borne supérieure du nombre d’itérations.

Twhile B do S ≤ (V0 + 1) ∗ TB + V0 ∗ TS

La formule devient une égalité si le variant diminue de 1 à chaque passage, et qu’on

sort de la boucle ssi le variant vaut 0.

Le plus souvent, TB ≤ O(TS), donc on emploie ≤ O(V0 ∗ TS), dite “nombre de

passages fois le temps d’un passage”.


2.3.7 Temps des sous-programmes récursifs

La règle générale s’applique mais donne une équation récurrente.

Attention O ne s’applique qu’à une fonction déjà définie.

Pour les appels récursifs, il ne faut pas employer O.

Ne pas supprimer les constantes

T1(n) = T1(n− 1) + k, T1(0) = k a comme solution T1(n) = k.(n+ 1)

(temps linéaire), tandis que T2(n) = 2.T2(n− 1) a comme solution

T2(n) = k.2n (temps exponentiel), même si O(f(n) + k) = O(2f(n)) pourrait

faire croire que ces deux équations donneraient le même ordre de grandeur.


T1(n) = T1(n− 1) + k T2(n) = 2.T2(n− 1)

k k

T1(1) = 2.k T2(1) = 2.k

T1(2) = 3.k T2(2) = 4.k

T1(3) = 4.k T2(3) = 8.k

... ...

T1(n) = (n+ 1).k T2(n) = 2n.k


Ne pas induire sur l’ordre de grandeur

T (n) = T (n− 1) +O(1)

T (0) = O(1)

On pourrait croire que

T (0) = O(1)

T (1) = O(1) +O(1) = O(1)

T (2) = O(1) +O(1) = O(1)

. . .

et que par “induction” :

T (n) = O(1), ce qui est évidemment faux puisque T (n) = O(n).


2.3.7.1 Équations récurrentes

équation récurrente où... T (n) = O(. . .)

T (n) = cT (n− 1) + bnk c = 1 nk+1

” c > 1 cn

T (n) = cT (n/d) + bnk c > dk nlogdc

” c = dk nk logn

” c < dk nk


2.3.8 Espace en mémoire

Comme pour le temps, on travaille en ordre de grandeur. L’espace dépend du type

de chaque variable :

– array : espace proportionnel au produit de ses tailles ;

– integer, real, boolean, record : espace constant ;

– file : calculer le nombre d’éléments ;

– set : dépend de l’implémentation, voir chapitre 4 ;

Pour les sous-programmes récursifs, on crée une copie des paramètres et variables

locales à chaque appel récursif : il faut donc multiplier l’espace de ceux-ci par la

profondeur d’appel, qui est bornée par la valeur initiale du variant.


2.3.9 Exemple 1 : Primalité

funct ion premier (n : in teger ) : boolean ;

{ Pré : n > 0

Post : premier = ∄ i : i d i v i s e n e t 1 < i < n }

var i : in teger ;

p : boolean ; { = premier }

begin

p := t rue ;

i := 2 ;

while sqr (i ) <= n and p do

{ inv : p = pour t o u t j . 1< j < i : j ne d i v i s e pas n }

variant : ⌊√n⌋ − i }

begin


p := (n mod i <> 0)

i := i + 1;

end ;

premier := p ;

end ;

Temps : Tpremier(n) = O(√n)

Espace : Epremier(n) = O(1)


2.3.10 Exemple 2 : Fibonacci

2.3.10.1 Définition

Fib(n) =1√5

((

1 +√5

2

)n

−(

1−√5

2

)n)

n ∈ N


2.3.10.2 Définition récursive

Fib(0) = 0

Fib(1) = 1

Fib(2) = 1

Fib(3) = 2

Fib(4) = 3

Fib(5) = 5

Fib(6) = 8

. . .

En général, pour n > 1 :

Fib(n) = Fib(n− 1) + Fib(n− 2)


Preuve En posant :

a = 1√5

O1 = 1+√5

2

O2 = 1−√5

2

Notons que O1, O2 sont les racines de x2 = x+ 1 (les nombres d’or).

On a :

Fib(n) = a(On1 −On

2 ) = a(On−11 −On−1

2 ) + a(On−21 −On−2

2 )

car

aOn1 = aOn−2

1 O21 = aOn−2

1 (O1 + 1)


2.3.10.3 Programme récursif

funct ion Fib (n : in teger ) : in teger ;

{ Pré : n ≥ 0 ;

Va r ian t : n }

begin

i f n < 2 then Fib := n

else Fib := Fib (n−1) + Fib (n−2)

end ;


Équation récurrente

T (0) = T (1) = c

T (n) = T (n− 1) + T (n− 2) + b, pour n > 1

Solution :

T (n) = c ∗ Fib(n+ 1) + b ∗ (Fib(n+ 1)− 1)

= O(On1 ) temps exponentiel

Espace : 1 argument * variant = O(n)


2.3.11 Exemple 3 : PosMax

Calculons le temps d’exécution de :

funct ion posMax ( var a : tableau ; bi , bs : in teger ) : in teger ;

{ Pré : b i ≤ bs

a [ b i . . bs ] d é f i n i

Post : pour t o u t i dans b i . . bs , a [ posMax ] >= a [ i ]

posMax dans b i . . bs }

begin

i f bi >= bs then posMax := bi

else i f a [bi ] < a [posMax (a ,bi +1 ,bs ) ]

then posMax := posMax (a ,bi +1 ,bs )

else posMax := bi

end ;


Soit n la taille du tableau : n = bs− bi+ 1. Pour n = 1, bs = bi, on exécute le

then du premier test. Pour n > 1, bs > bi, on exécute le else du premier test.

T (1) = O(1)

T (n) = O(1) + T (n− 1) + max(T (n− 1) +O(1),O(1))

= O(1) + 2T (n− 1) si n > 1

Et donc :

⇒ T (n) = O(2n)

Très inefficace !


2.3.11.1 Version améliorée

function posMax ( var a : tableau ; bi , bs : in teger ) : in teger ;

{ Pré , post : v o i r posMax }

var posReste : in teger ;

begin

i f bi ≥ bs then posMax := bi

else begin

posReste := posMax (a ,bi +1 ,bs ) ;

i f a [bi ]<a [posReste ]

then posMax := posReste

else posMax := bi

end

end ;


T (1) = O(1)

T (n) = O(1) + T (n− 1) + max(O(1),O(1)) (n > 1)

= T (n− 1) +O(1)

⇒ T (n) = O(n)


2.3.12 Exemple 4 : Tri par sélection

procedure tri ( var a : tableau ) ;

var i : in teger ;

begin

for i := n downto 1 do

echange (a [ i ] ,a [posMax (a , 1 ,i ) ] ) ;

end ;

T (n) = b.(n+ (n− 1) + . . .+ 2 + 1)

= b∑n

i=1 i

= bn(n+1)2

= O(n2)


2.3.13 Exemple 5 : Tri par fusion

Supposons que fusion (a,bi ,m,bs ) s’exécute en temps O(bs− bi) = O(n).

procedure tri ( var a : tableau ; bi ,bs : in teger ) ;

var c : in teger ; { cen t re du tab leau }

begin

i f bs > bi {O( 1 ) }

then begin

c := (bi +bs ) div 2; {O( 1 ) }

tri (a ,bi ,c ) ; {T ( n / 2 ) }

tri (a ,c+1 ,bs ) ; {T ( n / 2 ) }

fusion (a ,bi ,c ,bs ) ; {O( n ) }

end ;

end ;


Qui donne l’équation récurrente :

T (n) = 2T (n/2) + bn

⇒ T (n) = O(n logn) < O(n2)

Cet algorithme est beaucoup plus rapide !

CHAPITRE 3. INTRODUCTION AUX TYPES ABSTRAITS 71

CHAPITRE 3

INTRODUCTION AUX TYPES

ABSTRAITS

3.1 DÉFINITION 72

3.1 Définition

Type Abstrait =

– un type

– des sous-programmes (procédures et fonctions) qui utilisent ce type

– des propriétés de ces sous-programmes.

6=Type concret = un type défini par une combinaison de types de base.

3.1 DÉFINITION 73

3.1.1 Exemple : Pascal

Tous les types de base de Pascal peuvent être considérés commes de types

abstraits pourvu qu’on donne leurs propriétés.

type integer

funct ion + (x ,y : in teger ) : in teger

funct ion − (x ,y : in teger ) : in teger

funct ion ∗ (x ,y : in teger ) : in teger

funct ion div (x ,y : in teger ) : in teger

const 0 : in teger

. . .

Bien sûr, ceci n’est pas syntaxiquement correct en Pascal !

3.1 DÉFINITION 74

3.1.2 Exemple : Les listes

Une liste contient une suite finie d’éléments : le premier, le deuxième, . . . On se

donne des fonctions :

– listeVide construit une liste vide

– cons (x ,l ) construit une nouvelle liste en ajoutant x devant l

– head (l ) donne le premier élément de la liste

– nth (i ,l ) donne le i-ème élément de la liste

– tail (l ) donne le reste de la liste (le deuxième, . . . )

– append (l1 ,l2 ) donne une liste formée de l1 suivi de l2 , càd la

concaténation de l1 et l2 .

– length (l ) la longueur de la liste

3.2 AVANTAGES 75

3.2 Avantages

1. Abstraction : On peut construire un programme utilisant le type abstrait sans

connaître son implémentation.

2. Modifiabilité : On peut modifier l’implémentation du TA, pourvu que les

propriétés restent vraies, SANS devoir changer le programme utilisateur.

3. Encapsulation : Les données ne sont changées que par les sous-programmes

de l’interface, ce qui garantit un invariant des données

4. Réutilisation : Les types abstraits sont employés dans un grand nombre de

programmes.

3.3 SYNTAXE 76

3.3 Syntaxe

Il n’y a pas de syntaxe pour les Types Abstrait en Pascal standard, mais bien dans

ses extensions.

Abstrait Concret

Language Visible Caché

Turbo Pascal unité interface implémentation

Ada paquetage spécification corps

Modula-2 module définition implémentation

3.3 SYNTAXE 77

En Turbo Pascal

Une unité (unit ) consiste en

– une interface, qui déclare les constantes, les types, et les en-têtes de fonctions et

de procédures ;

– suivie d’une implémentation, qui contient le corps des fonctions et procédures.

Problème : une interface ne correspond pas exactement à un type abstrait : on y

trouve le définition concrète du type, qui est liée à l’implémentation.

Free Pascal et Delphi sont basés sur la même syntaxe.

3.3 SYNTAXE 78

Exemple en Turbo Pascal

Unit Ensemble

Interface

const ensVide = nil ; (∗ ! implémentat ion ∗)

type ensemble = ^cell ; (∗ ! implémentat ion ∗)

funct ion union (x ,y : ensemble ) : ensemble ;

Implementation

uses Listes ;

funct ion union (x ,y :ensemble ) : ensemble ;

begin

. . .

end ;

end .

3.4 COMMENT DONNER LES PROPRIÉTÉS 79

3.4 Comment donner les propriétés

3.4.1 Par modèles [VDM, Z, B]

1. On donne une “implémentation” abstraite basée sur les ensembles

2. Les sous programmes sont spécifiés par Pré/Post-conditions (sur

l’implémentation abstraite).

3. Pour prouver une implémentation concrète, on définit un invariant de

représentation (ou d’abstraction ou de collage ) A(a, c) entre le type abstrait

et le type concret telle que

∀a ∈ (type abstrait), ∃c ∈ (type concret) : A(a, c)

L’invariant de données décrit la partie des données concrètes utilisées


{1,2}{}

{1,3}

Type abstrait

Ex.: ensemble fini

Type concret

Ex. : Pointeurs1

Partie inutilisée

NIL2

1

1

2

A

Partie qui vérifie l'invariant de représentation


3.4.1.1 Exemple : TA listes par modèle

Les listes sont définies comme un ensemble de couples (indice dans la séquence,

valeur) avec les propriétés :

1. il n’y a pas de valeur à l’indice 0 (on commence à 1)

2. il ne peut y avoir deux valeurs au même indice

3. les indices vont de 1 à n

P.ex. la liste (5, 4, 3) est représentée par l’ensemble {(1, 5), (2, 4), (3, 3)}


Type liste = P(N × elem)

tel que ∄e : (0, e) ∈ l

∄i, e1, e2 : (i, e1) ∈ l et (i, e2) ∈ l et e1 6= e2

∀(i, e) ∈ l, i > 1 ⇒ ∃e2 : (i− 1, e2) ∈ l


function listeVide : liste

Post : listeVide = {}

function cons(x : elem ; l : liste) :liste

Post : cons(x, l) = {(1, x)}⋃{(i+ 1, y)|(i, y) ∈ l}

function head(l : liste) :elem

Pré : l 6= {} (ou ∃x : (1, x) ∈ l)

Post : head = x ⇐ (1, x) ∈ l

function tail(l : liste) : liste

Pré : l 6= {}

Post : tail = {(i, x)|(i+ 1, x) ∈ l et i ≥ 1}

function null(l : liste) : boolean

Post : null = (l = {})

function append(l1, l2 : liste) : liste

Post : append = l1⋃{(n+ i, x)|(i, x) ∈ l2, n = |l1|}


3.4.2 Par axiomes

On donne des propriétés en termes des sous-programmes déclarés dans l’interface.

Pour les fonctions (sans effet de bord) On emploie la logique du premier ordre.

Exemple : ∀x : integer;A,B : ensemble :

dans(x, union(A,B)) ⇐⇒ (dans(x,A) ou dans(x,B))

Pour les procédures On ajoute la logique dynamique :

[Prog]Formule signifie : Après toute exécution de Prog, la formule est vraie.

Exemple : [ajouter(x,A)]dans(x,A)

3.5 COMPLÉTUDE 85

3.5 Complétude

Comment être sûr d’avoir donné assez d’axiomes ? Lorsqu’il n’y a que des

fonctions : 2 méthodes :

3.5 COMPLÉTUDE 86

3.5.1 Méthode des constructeurs

1. Choisir un sous-ensemble des fonctions qui permet de construire toutes les

valeurs du TA ( les constructeurs).

2. Donner toutes les combinaisons de la forme

n(c1(. . .), c2(. . .)) = e

où

– n est une fonction, mais pas un constructeur

– c1, c2 sont des constructeurs.

– e est une expression plus simple (pour un ordre bien fondé).

3. Puis les “équations entre constructeurs” de la forme

c1(c2(. . .)) = e

3.5 COMPLÉTUDE 87

3.5.1.1 Exemple : Listes : constructeurs

Constructeurs : { listeVide, cons}

Exemple : (1,2) = cons(1,cons(2,listeVide)).

Axiomes par la méthode des constructeurs.

– head(listeVide) = indéfini.

– head(cons(x,l)) = x.

– tail(listeVide) = indéfini.

– tail(cons(x,l)) = l.

– null(listeVide) = true.

– null(cons(x,l)) = false.

– append(listeVide,l2) = l2.

– append(cons(x,l),l2) = cons(x,append(l,l2)).

3.5 COMPLÉTUDE 88

3.5.2 Méthode des observateurs

– Choisir un sous-ensemble de fonctions qui permet d’observer toute différence

entre 2 valeurs.

– Donner toutes les combinaisons de la forme

o(n(x)) = e . . . o(x) . . .

où

– o est un observateur.

– n est une fonction non observateur.

– e est une expression qui ne contient pas o(x).

3.5 COMPLÉTUDE 89

Observateurs : { head, tail, null}.

– head(listeVide) = indéfini.

– tail(listeVide) = indéfini.

– null(listeVide) = true.

– head(cons(x,l))= x.

– tail(cons(x,l)) = l.

– null(cons(x,l)) = false.

– head(append(l1,l2))= head(l1) si null(l1) = false.

= head(l2) si null(l1) = true.

– tail(append(l1,l2))= append(tail(l1),l2) si null(l1) = false.

= tail(l2) si null(l1) = true.

– null(append(l1,l2)) = null(l1) and null(l2).

3.5 COMPLÉTUDE 89-1

3.6 LE TYPE ABSTRAIT “PILE” 90

3.6 Le type abstrait “Pile”

Une pile est une collection d’éléments récupérée dans l’ordre inverse de celui où on

les a mises : en anglais “Last In, First Out” (LIFO)

Fonctions :

1. pileVide donne une pile vide

2. empile (ou push ) ajoute un élément en sommet de pile

3. dépile (ou pop ) retire le sommet de pile

4. sommet (ou top ) renvoie le sommet de pile


3.6.1 Axiomes

– sommet(pileVide) = indéfini.

– sommet(empile(x,l)) = x.

– dépile(pileVide) = indéfini.

– dépile(empile(x,l)) = l.


3.6.2 Implémentation : Tableau+pointeur

Implémentation classique des piles.

type pile = record

a : array [ 1 . .max] of elem ;

p : 0 . .max

end

a[p] contient le sommet de pile

– Cette implémentation convient mieux en procédural

– En Pascal, on doit borner le tableau : il faut donc ensuite démontrer que le

tableau ne déborde pas.

3.7 TYPES ABSTRAIT ENSEMBLE FINI 93

3.7 Types Abstrait Ensemble fini

NB : ce type fait partie du Pascal, mais il est souvent inefficace.

type ens { se t o f elem } ; { No ta t ion en Pascal }

funct ion singleton (e :elem ) : ens ; { [ e ] }

funct ion ensVide : ens ; { [ ] }

funct ion union (x ,y : ens ) : ens ; { [ x+y ] }

funct ion intersection (x ,y : ens ) : ens ; { [ x∗y ] }

funct ion ajout (e : elem ; x :ens ) : ens ; { [ [ e ]+ x ] }

funct ion dans (e : elem ; x :ens ) : boolean ; { e i n x }

3.7 TYPES ABSTRAIT ENSEMBLE FINI 94

3.7.1 Axiomes

Constructeurs : {ensVide, ajout}.

– singleton(e) = ajout(e, ensVide).

– union(ensVide,y) = y.

– union(ajout(e,x),y) = ajout(e,union(x,y)).

– intersection(ensVide,y) = ensVide.

– intersection(ajout(e,x),y) =intersection(x,y) si dans(e,y) = false.

ajout(e,intersection(x,y)) si dans(e,y)= true

– dans(e,ensVide) = false.

– dans(e, ajout(e,x))= true.

– dans(e,ajout(f,x)) = (e=f) ou dans(e,x).

{Equations entre constructeurs}

– ajout(e,ajout(e,x)) = ajout(e,x).

– ajout(e,ajout(f,x)) = ajout(f,ajout(e,x)).

3.8 DICTIONNAIRE 95

3.8 Dictionnaire

Ce TA permet de retrouver la “définition” d’un “mot”, aussi appelé “clé”.

On l’appelle aussi Mapen Java 2.

type dico

funct ion ajout (d : def ; m : mot ; di : dico ) : dico ;

dicoVide : dico ;

def_de (m : mot ; di : dico ) : def ;

défini (m : mot ; di : dico ) : boolean ;

après (di1 ,di2 :dico ) :dico ;

Toutes nos implémentation d’ensembles peuvent être adaptées pour le type

dictionnaire.

3.8 DICTIONNAIRE 96

3.8.0.1 Axiomes par Constructeurs

– défini(m, dicoVide) = false.

– défini(m, ajout(d, m, di)) = true.

– défini(m, ajout(d, n, di)) = défini(m, di) (pour n 6= m).

– def_de(m, dicoVide) = indéfini.

– def_de(m, ajout(d, m, di)) = d.

– def_de(m, ajout(d, n, di)) = def_de(m, di) (pour n 6= m).

– après(dicoVide, di2) = di2.

– après(ajout(d, m, di), di2) = ajout(d, m, après(di, di2)).

– ajout(d2, m, ajout(d1, m, di)) = ajout(d2, m, di).

– ajout(d2, m, ajout(d1, n, di)) = ajout(d1, n, ajout(d2, m ,di)) (pour n 6= m).

3.8 DICTIONNAIRE 97

3.8.1 Ensembles avec procédures

type ens = P(elem ) ;

procedure insérer (e : elem ; var x : ens ) ;

Post : x = x0 + [e ]

procedure supprimer (e : elem ; var x : ens ) ;

Post : x = x0 − [e ]

CHAPITRE 4. IMPLÉMENTATION DES ENSEMBLES 98

CHAPITRE 4

IMPLÉMENTATION DES

ENSEMBLES

CHAPITRE 4. IMPLÉMENTATION DES ENSEMBLES 99

Différentes structures vont être abordées :

1. Tableau de booléens.

2. Liste avec doubles.

3. Liste sans doubles.

4. Liste triée.

5. Table de hachage.

6. Arbre binaire de recherche.

7. Arbre rouge/noir.

8. B-Arbre.

4.1 TABLEAU DE BOOLÉENS 100

4.1 Tableau de Booléens

Cette implémentation, aussi appelée “vecteur de bits” est définie comme :

type ens = packed array [elem ] of boolean

invariant de représentation :

e ∈ E ⇐⇒ X [e] = true

Notes

– elem doit être un type discret.

– Pour les boucles for il faut disposer de son MIN et de son MAX (i.e.

type elem = MIN..MAX).

– le résultat d’une fonction (ici ens ) doit être un type non structuré en Pascal pur,

mais la plupart des Pascal admettent cette extension.


4.1.1 Fonctions et procédures

type elem = MIN. .MAX;

ens = packed array [elem ] of boolean ;

funct ion dans (e : elem ; x : ens ) : boolean ; { O( 1 ) }

begin

dans := x [e ] ;

end ;


funct ion ensVide : ens ; { O( | elem | ) }

var i : elem ;

res : ens ;

begin

for i := MIN to MAXdo res [ i ] := fa lse ;

ensVide := res ;

end ;


funct ion ajout (e : elem ; x : ens ) : ens ; { O( | elem | ) }

var res : ens ;

begin

res := x ;

res [e ] := t rue ;

ajout := res ;

end ;


funct ion singleton (e : elem ) : ens ; { O( | elem | ) }

var i : elem ;

var res : ens ;

begin

for i := MIN to MAXdo res [ i ] : = fa lse ;

res [e ] := t rue ;

singleton := res ;

end ;


funct ion union (x ,y :ens ) : ens ; { O( | elem | ) }

var i : elem ; res : ens ;

begin

for i := MIN to MAXdo res [ i ] := x [ i ] or y [ i ] ;

union := res ;

end ;

funct ion intersection (x ,y :ens ) : ens ; { O( | elem | ) }

var i : elem ; res : ens ;

begin

for i := MIN to MAXdo res [ i ] := x [ i ] and y [ i ] ;

intersection := res ;

end ;


procedure insérer (e : elem ; var x : ens ) ; { O( 1 ) }

begin

x [e ] := t rue ;

end ;

procedure supprimer (e : elem ; var x : ens ) ; { O( 1 ) }

begin

x [e ] := fa lse ;

end ;

4.2 LISTE 107

4.2 Liste

Le problème des vecteurs de bits est que l’on obtient une complexité en O(|elem|)(nombre de valeurs possibles) or on voudrait O(|x|) (nombre de valeurs utilisées).

Soit un TA liste, on peut s’en servir pour implémenter les ensembles.

idée

ajout → cons

ensV ide → listeV ide

Puisque ce sont des constructeurs similaires.

4.2 LISTE 108

L’implémentation de dans se déduit de ses équations :

funct ion dans (e : elem ; x : ens ) : boolean ;

begin

i f null (x ) then dans := fa lse

else i f head (x ) = e then dans := t rue

else dans := dans (e , tail (x ) ) ;

end ;

4.2 LISTE 109

On obtient de même intersection et union.

4.2.1 union

Exemple :

union(ajout(e, x), y) = ajout(e, union(x, y))

↓union(cons(e,x),y) = cons(e, union(x, y))

On remarque que les équations de union sont exactement celles de append !

Donc union → append.

4.2 LISTE 110

4.2.2 intersection

funct ion intersection (x ,y : ens ) : ens ;

var e : elem ;

begin

i f null (x ) then intersection := listeVide

else

begin

e := head (x ) ;

i f dans (e ,y )

then intersection := ajout (e , intersection (tail (x ) ,y )

else intersection := intersection (tail (x ) ,y ) ;

end

end ;

4.2 LISTE 111

4.2.3 Temps de calcul

Si les listes sont implémentées par des listes chaînées, on a :

f Tf =

listeVide O(1)

cons O(1)

append O(length (x))

head O(1)

tail O(1)

4.2 LISTE 112

Les fonctions sur les ensembles prennent donc :

f Tf =

ensVide O(1)

ajout O(1)

dans O(length (x))

singleton O(1)

union O(length (x))

intersection O(length (x)∗length (y)) ! ! !

4.2.4 Place en mémoire

De l’ordre de la longueur de la liste l.

4.2 LISTE 113

4.2.4.1 Problème

Exemple : l’ensemble x = {1, 2} peut être représenté par la liste

[1, 2, 1, 2, 1, 2, 1, 2].

Pour un ensemble x , la longueur de la liste n’est pas bornée !

4.3 LISTE SANS DOUBLES 114

4.3 Liste sans doubles

Pour que

length(x) ≤ O(|x|)on pose comme invariant “pas de doubles” :

∀i, j ∈ N+0 : i, j ≤ length(x) et i 6= j ⇒ nth(i, x) 6= nth(j, x)

Il faut garantir que chaque fonction respecte bien le nouvel invariant.

– ensVide : OK.

– singleton : OK.


ajout : tester qu’on ne crée pas de double :

funct ion ajout (e : elem ; x : ens ) : ens ;

begin

i f dans (e ,x ) then ajout := x

else ajout := cons (e ,x ) ;

end ;

Les autres fonctions se déduisent des axiomes.


de l’ordre du nombre d’éléments dans l’ensemble.


4.3.2 Temps d’exécution [Liste chaînée]

P TP =

ensVide O(1)

dans O(|x|)ajout O(|x|)singleton O(1)

union O(|x| ∗ |y|)intersection O(|x| ∗ |y|)

Attention Apparemment, le temps augmente, mais pour les listes avec doubles, l

n’est PAS bornée !

4.4 LISTES TRIÉES 117

4.4 Listes triées

But diminuer le temps de union, intersection.

Idée éviter dans⇒ invariant : La liste x est triée

∀i, j ∈ N : 0 < i < j < length(x) ⇒ nth(i, x) < nth(j, x)

Les anciennes opérations vérifient-elles le nouvel invariant ?

– ensVide : OK.

– singleton : OK.


ajout : insérer à la bonne place !


begin

i f null (x ) then ajout := cons (e , x )

else i f e < head (x )

then ajout := cons (e , x )

else i f e = head (x )

then ajout := x

else ajout := cons (head (x ) , ajout (e , tail (x ) ) ;

end ;


dans : OK mais peut aller plus vite :


begin

i f null (x ) then dans := fa lse

else i f e < head (x ) then dans := fa lse

else i f e = head (x ) then dans := t rue

else dans := dans (e , tail (x ) ) ;

end ;


union : OK mais peut aller plus vite :

funct ion union (x ,y : ens ) : ens ;

begin

i f null (x ) then union := y

else i f null (y ) then union := x

else i f head (x ) < head (y )

then union := cons (head (x ) ,union (tail (x ) ,y ) )

else i f head (x ) = head (y )

then union := cons (head (x ) ,union (tail (x ) ,tail (y ) ) )

else union := cons (head (y ) ,union (x , tail (y ) ) ) ;

end ;


Intersection : même principe :

funct ion intersection (x ,y : ens ) : ens ;

begin

i f null (x ) then intersection := listeVide

else i f null (y ) then intersection := listeVide

else i f head (x ) < head (y )

then intersection := intersection (tail (x ) ,y )

else i f head (x ) = head (y )

then intersection :=

cons (head (x ) ,

intersection (tail (x ) ,tail (y ) ) )

else intersection := intersection (x , tail (y ) ) ;

end ;



La même : de l’ordre du nombre d’éléments.

4.4.2 Temps d’exécution

T(ensVide) = O(1)

T(singleton) = O(1)

T(ajout) = O(|x|)T(dans) = O(|x|)T(union) = O(|x|+ |y|)T(intersection) = O(|x|+ |y|)

4.5 TABLES DE HACHAGE 123

4.5 Tables de hachage

Idée

– Variante du vecteur de bits (Celui-ci utilise un tableau trop grand.)

– On diminue le type elem par une fonction qui le “compresse”.

funct ion h (e : elem ) : indice

où elem est grand, mais indice est petit, par exemple 0..M

P.ex. on peut prendre le reste de la division par M + 1.


4.5.0.1 Problème

Lorsque deux éléments distincts ont le même indice, il y a COLLISION.

4.5.0.2 Solutions

1. Représenter l’ensemble des éléments de même indice (p.ex. par une liste triée).

2. Représenter la liste dans la table : Adressage ouvert .

3. Agrandir la table de hachage.


4.5.1 Ensemble des collisions

type indice = 0 . .M;

ens = array [indice ] of ens2 ;

{ ens2 = par ex . l i s t e chaînée }


begin

dans := dans2 (e , x [h (e ) ] )

end ;


procedure inserer (e : elem ; var x : ens ) ;

begin

inserer2 (e , x [h (e ) ] )

end ;

procedure supprimer (e : elem ; var x : ens ) ;

begin

supprimer2 (e ,x [h (e ) ] )

end ;


funct ion ensVide : ens ;

var i : indice ;

res : ens ;

begin

for i := 0 to M do res [ i ] := ensVide2 ;

ensVide := res ;

end ;



var i : indice ;

res : ens ;

begin

res := x ; { ! peut c réer du partage }

res [h (e ) ] := ajout2 (e , x [h (e ) ] ) ;

ajout := res ;

end ;


funct ion union (x ,y : ens ) : ens ;

var i : indice ;

res : ens ;

begin

for i := 0 to M do res [ i ] : = union2 (x [ i ] ,y [ i ] ) ;

union := res ;

end ;


4.5.1.1 Temps d’exécution

Opération Temps au pire : O(. . .) Temps moyen : O(. . .)

insérer Tinsérer2 (|x|) 1

dans Tdans2 (|x|) 1

supprimer Tsupprimer2 (|x|) 1

fusionner M * Tfusionner2 (|x|) M

union M * Tunion2 (|x|) M

intersection M * Tintersection2 (|x|) M

ensVide M * TensVide2 (|x|) M

h est supposée en O(1)


4.5.1.2 Place mémoire

O(M) = O(|x|) si M bien choisi.

4.5.1.3 Conclusion

– Améliore dans, insérer, supprimer .

– Dégrade ensVide, ajout .

⇒ Souvent employé car ensV ide, ajout sont rares.


4.5.2 Représenter la liste des collisions dans la table

On met les éléments en collision à d’autres places libres du tableau

Avantage : pas de pointeurs, d’où économie de place.

On pourrait les mettre à la place suivante (si elle est libre) mais risque de collision

en chaîne ou cluster .

double hachage : h1, h2 telle que h2(e) est premier par rapport à M+1 (ex. : M+1

= 2n, h2 impair). On suppose une valeur spéciale de elem : vide.

La suite des indices explorés est :

funct ion h (e : elem ; i : indice ) : indice ;

begin

h := (h1 (e ) + i ∗ h2 (e ) ) mod M+1

end ;

{ h ( e , 0 ) , . . . , h ( e ,M) est une permuta t ion de 0 . .M}


Hypothèse : supprimer n’est pas dans le TA.

Invariant :

∃j : e = X [j] ⇒ ∀i ∈ [0..k[ ou h(e, k) = j,X [h(e, i)] 6= vide


Pour insérer, on parcourt la séquence d’indices jusqu’à trouver une case vide. Pour

rechercher, on parcourt la liste d’indices jusqu’à trouver la clé ou tomber sur une

case vide.


4.5.2.1 Temps

– Dépend du risque de “collision en chaîne”.

– Si négligeable, même temps moyen.

4.5.2.2 Place

Economie qui ne change pas l’ordre de grandeur :

O(M) = O(|x|)


4.5.3 Eviter les collisions en agrandissant la table

– Pas possible en Pascal car la taille des tableaux est fixe.

– Possible en C/C++.

– Nécessite une série de fonctions de hachage ; on prend souvent :

h(e, n) ∈ 0..2n − 1 On suppose que pour n grand, h ne donne plus de

collisions.


type ens = record

n : in teger ; { >= n0 > 0 }

t : array [ 0 . . 2 ^n −1] of elem { pas du PASCAL}

end ;

procedure inserer (e : elem ; var x : ens ) ;

begin

j := h (e , x .n ) ;

i f x .t [ j ] = vide then x .t [ j ] := e

else i f x .t [ j ] <> e

then begin

dedoubler (x ) ;

insérer (e ,x ) ;

end


end ;

4.6 ARBRES BINAIRES DE RECHERCHE 139

4.6 Arbres binaires de recherche

Un arbre binaire est soit un arbre vide, soit constitué d’une valeur, et de deux

sous-arbres : le fils de gauche et le fils de droite.

type arbre = arbreVide | cons (e : elem ; g ,d : arbre )

e est appelé la valeur de la racine de l’arbre. g et d, les fils gauche et droit.


3

5

7

86


arbre { b i n a i r e } = ^noeud ;

noeud = record

e : elem ;

g : arbre ;

d : arbre ;

end ;

{ inv : x . g < x , x . d < x pour ‘ ‘ < ’ ’ b ien fondé

càd pas de cyc les }


Un arbre binaire est trié (ou de recherche) , si les valeurs du sous-arbre de gauche

sont plus petites que la racine, et celles du sous-arbre de droite sont plus grandes,

et récursivement. La recherche (dans ) y est plus efficace.

type abr { a rbre b i n a i r e de recherche }

= arbre

{ inv : s i x <> n i l :

pour t o u t e1 dans I n f o ( x ^ . g ) ,

pour t o u t e2 dans I n f o ( x ^ . d ) ,

e1 < x ^ . e < e2

x ^ . g e t x ^ . d sont des abr } ;


4.6.1 Fonctions et Procédures

funct ion cons (e : elem ; g ,d : arbre ) : arbre ;

var p : arbre ;

begin

new (p ) ;

p^ .e := e ;

p^ .g := g ;

p^ .d := d ;

cons := p ;

end ;


funct ion ensVide : abr ;

begin

ensVide := nil

end ;

funct ion singleton (e : elem ) :abr ;

begin

singleton := cons (e ,ensVide ,ensVide )

end ;


funct ion ajout (e : elem ; x : abr ) :abr ;

begin

i f x = nil then ajout := singleton (e )

else i f e < x ^ .e

then ajout := cons (x ^ .e , ajout (e , x ^ .g ) , x ^ .d )

else i f e > x ^ .e

then ajout := cons (x ^ .e , x ^ .g , ajout (e , x ^ .d ) )

else ajout := x

end ;


4.6.2 Recherche

funct ion dans (e : elem ; x : abr ) : boolean ;

begin

i f x = nil then dans := fa lse

else i f e < x ^ .e then dans := dans (e ,x ^ .g )

else i f e > x ^ .e then dans := dans (e , x ^ .d )

else dans := t rue

end ;


4.6.2.1 Elimination de la récursivité terminale

function dans2 (e : elem ; x : abr ) : boolean ;

var trouve : boolean ;

begin

trouve := fa lse ;

while (x <> nil ) and not trouve do

i f e < x ^ .e then x := x ^ .g

else i f e > x ^ .e then x := x ^ .d

else trouve := t rue ;

dans2 := trouve

end ;


4.6.3 Insertion

procedure inserer (e : elem ; var a : abr ) ;

begin

i f a = nil then a := singleton (e )

else i f e < a ^ .e then inserer (e , a ^ .g )

else i f e > a^ .e then inserer (e , a^ .d )

{ i f e = a ^ . e : i l s ’ y t rouve déjà , ne r i e n f a i r e }

end ;


4.6.4 Supprimer

1. Si le noeud à supprimer n’a pas de fils gauche, on peut l’enlever

2. Sinon, il nous manque une valeur pour séparer les deux sous-arbres : on

remonte le max du fils gauche.

On pourrait mettre un sous-arbre sous l’autre, mais ça déséquilibrerait l’arbre


procedure supprimer (e : elem ; var x : abr ) ;

begin

i f x <> nil then

i f e < x ^ .e then supprimer (e ,x ^ .g )

else i f e > x ^ .e then supprimer (e , x ^ .d )

else SupprimerRacine (x )

end ;


procedure SupprimerMax ( var a : abr ; var m: elem ) ;

(∗ Pré : a <> n i l

Post : m = Max( I n f o ( a0 ) ) e t I n f o ( a ) = I n f o ( a0 ) \ { e } ∗)

var p : abr ;

begin

i f a ^ .d = nil

then begin

m := a^ .e ;

p := a ;

a :=a^ .g ;

dispose (p ) ;

end

else SupprimerMax (a^ .d ,e )

end ;


procedure SupprimerRacine ( var a : abr ) ;

(∗ Pré : a <> n i l

Post : I n f o ( a ) = I n f o ( a0 ) \ { a0 ^ . e } ∗)

var p : abr ;

begin

p := a ;

i f a^ .g = nil

then begin

a := a^ .d ;

dispose (p ) ;

end

else SupprimerMax (a^ .g ,a ^ .e )

end ;


4.6.4.1 Temps d’exécution

Le temps est de l’ordre de la hauteur, mais au pire elle peut être n.

Opération Temps au pire : O(. . .) Temps moyen : O(. . .)

dans n log(n)

insérer n log(n)

supprimer n log(n)

ensVide 1 1

ajout n log(n)

Il faut équilibrer l’arbre.

4.7 ARBRES ROUGES/NOIRS 154

4.7 Arbres rouges/noirs

4.7.1 Définition

On ajoute une “couleur” binaire à chaque noeud, et surtout des invariants de

données pour que la hauteur soit logarithmique :

– le nombre de noeuds noirs est le même sur toute branche

– le fils d’un noeud rouge est noir.

Les noeuds rouges donnent un peu de souplesse à la contrainte d’équilibre.

Note : on pourrait aussi choisir la couleur de la racine.


4.7.1.1 Déclaration Pascal

rougenoir = ^noeud ;

noeud = record

e : elem ;

g : rougenoir ;

d : rougenoir ;

rouge : boolean ;

end ;


4.7.1.2 Invariants de données

– l’arbre est acyclique : h(x^.g) < h(x ) et h(x^.d) < h(x )

– l’arbre est trié : si x <> nil , pour tout e1 dans Info (x^.g), e1 < x^.e pour

tout e2 dans Info (x^.d), x^.e < e2

– le fils d’un rouge est noir : si rouge (x ) alors non rouge (x^.g) et non

rouge (x^.d)

– toute branche contient le même nombre de noeuds noirs : hn (x^.g) = hn (x^.d)

– l’invariant est récursif : x^.g et x^.d sont des rougenoir


La hauteur noire d’un arbre rouge/noir est le nombre de noeuds noirs rencontrés le

long d’une branche :

funct ion hn (a : rougenoir ) : in teger ;

begin

i f a=nil then hn :=0

else i f a^ .rouge then hn := hn (a ^ .d )

else hn := 1+hn (a ^ .d )

end

Note : dans la nouvelle édition de Cormen, hn est noté bh (black height)


Exercice : Démontrez que pour tout arbre rouge/noir :

1. hn ≤ h ≤ 2 ∗ hn+ 1

2. 2hn − 1 ≤ n ≤ 2h − 1

3. h = O(logn)


4.7.2 Fonctions de base

On adapte les fonctions des arbres binaires triés, pour qu’elles traitent les arbres

rouges/noirs :

cons doit recevoir la couleur. La précondition doit être plus forte :

– hn (g) = hn (d)

– c = noir ou (c = rouge et non rouge(g) et non rouge(d))

– ∀x ∈ Info(g).x < e

– ∀x ∈ Info(d).x > e


funct ion cons (e : elem ;g ,d : rougenoir ; c : boolean ) : rougenoir ;

var p : rougenoir ;

begin

new (p ) ;

p^ .e := e ;

p^ .g := g ;

p^ .d := d ;

p^ .rouge := c ;

cons := p ;

end ;


Sans aucun changement, la recherche s’exécute en temps logarithmique.

funct ion dans (e : elem ; x : rougenoir ) : boolean ;

begin

i f x = nil then dans := fa lse

else i f e < x ^ .e then dans := dans (e , x ^ .g )

else i f e > x ^ .e then dans := dans (e , x ^ .d )

else dans := t rue

end ;


4.7.3 Rotations

Nous voulons que Insérer et Supprimer s’exécutent en temps logn. Nous

recherchons donc des opérations pour rééquilibrer l’arbre à faible coût.

a b

c

P

Qa P

b Q

x

y

RotationGauchex


Une rotation gauche prend un temps constant ; elle raccourcit les branches de c et

rallonge celles de a.

L’arbre reste trié mais pas toujours rouge-noir.

procedure RotationGauche (x : abr ) ;

var y : abr ;

begin

y := x ^ .d ; { <> n i l }

echanger (x ^ .e ,y ^ .e ) ;

x ^ .d := y ^ .d ;

y ^ .d := y ^ .g ;

y ^ .g := x ^ .g ;

x ^ .g := y ;

end ;


Si c’est b qu’il faut raccourcir, on fait d’abord une rotation droite sur y .

!"

#"

$"

#"

$"

!"

%"

%" &'"

&("

&("

&'"

)")"


4.7.4 Insertion

1. On fait une insertion dans un ABR d’un noeud rouge

2. Si le père p est rouge : il faut rétablir l’invariant

Cas 1 : si l’oncle est rouge : le problème est remonté sur le grand-père.


!"

#"

$"

%

!"

#"

$"

%


Cas 3 : si l’oncle est noir et le fils est du même côté que son père : on fait une

rotation qui résoud le problème.


!"

#"

$"

!%&"'"

#"

$" !"


Cas 2 : si l’oncle est noir et le fils est de l’autre côté que son père : on fait d’abord

une rotation qui ramène au cas 3.


!"

#"

$"

!"

$"

#"

!%&"'"


procedure insererec (e : elem ; var a ,b ,c : rougenoir ) ;

{ cas généra l de i n s e r e r

Pré : a , b <> n i l

b est l e f i l s de a où e d o i t ê t re insé ré .

c est l e f i l s de b où e d o i t ê t re insé ré .

Post : a = a0

b = b0

I n f o ( c )= I n f o ( c0 ) u { e } }

var y : rougenoir ; { oncle }

begin

i f c = nil then c := singleton (e )

else i f e < c ^ .e then insererec (e ,b ,c ,c ^ .g )

else i f e > c ^ .e then insererec (e ,b ,c ,c ^ .d ) ;


i f b^ .rouge and c ^ .rouge then { n o i r ( a ) }

i f b = a ^ .g

then begin

y := a ^ .d ;

i f rouge (y )

then begin { Cas 1 }

b ^ .rouge := fa lse ;

y ^ .rouge := fa lse ; { <> n i l car rouge ( y ) }

a ^ .rouge := t rue ;

end

else begin { n o i r ( y ) }

i f c = b ^ .d then RotationGauche (b ) { Cas 2 } ;

RotationDroite (a ) {Cas 3 } ;

end


end

Plus les cas symétriques.


procedure inserer (e : elem ; var a : rougenoir ) ;

{ a lance r sur l a rac ine de l ’ arbre , c e t t e procedure t r a i t e

les cas de niveau < 2 et envoie l e res te à inse re rec }

begin

i f a = nil then a := singleton (e )

else begin

a ^ .rouge := fa lse ;

i f e < a ^ .e

then i f a^ .g = nil

then a ^ .g := singleton (e )

else i f e < a ^ .g ^ .e

then insererec (e ,a ,a^ .g ,a ^ .g ^ .g )

else i f e > a^ .g^ .e

then insererec (e ,a ,a ^ .g ,a^ .g^ .d )


else { r i e n à f a i r e }

else i f e > a^ .e

then i f a ^ .d = nil

then a^ .d := singleton (e )

else i f e < a^ .d^ .e

then insererec (e ,a ,a ^ .d ,a^ .d^ .g )

else i f e > a ^ .d ^ .e

then insererec (e ,a ,a^ .d ,a ^ .d ^ .d )

else { r i e n à f a i r e }

end

end ;


4.7.5 Supprimer

1. On retire comme dans un arbre binaire trié ;

2. Si le noeud retiré est rouge : OK ;

3. sinon on appele retablir(x) : il manque un noir sur tous les chemins qui

passent par x (bulle). x est le fils du noeud retiré, qui le remplace.


4.7.5.1 Rétablir

Si x est rouge, on le met à noir et la bulle est résolue. SI w, le frère de x, est rouge,

on fait une rotation : le nouveau frère est noir.

a b

x.e w.e

p.ep

noir

noir(2x)

rouge

noir

x

a

b

pw.e noir

rouge

noir(2x)

ex-w

p.e

noir

(nouveau w)

Rotation Gauche


Si les neveux de x sont noirs, on rougit w, ce qui remonte la bulle sur p : appel

récursif. (Si p était rouge, on rétablit l’invariant en le mettant à noir).

p ?

x

noir(2x)

w noir

noir noir

px

ex-x

noir

w

rouge


SINON SI le neveu de gauche est rouge et le neveu de droite est noir : On fait une

rotation, qui rend le neveu de droite rouge.

p ?

x w noir

noir

p

noir

ag

b c

rouge

RotationDroite(w)

x g.e

w

?

b

c a

rougew.e

noir


Enfin une rotation sur p élimine la bulle en x ; on rougit d.

p ?

x w noir

p

noir

a

?

d

rouge?

RotationGauche

x a

noir

noirw

p.e d

noir

w.e

4.8 B-ARBRES 181

4.8 B-Arbres

Les B-arbres utilisent la même idée que les arbres rouges-noirs. Ils regroupent un

paquet de noeuds bicolores dans un noeud de B-arbres.

1. Si on regroupe un noeud noir avec son éventuel fils rouge, et qu’on met la

racine à noir, on obtient un arbre où toutes les branches ont la même longueur

mais dont le nombre de fils varie.

2. On peut en regrouper plusieurs niveaux – pour obtenir un noeud de B-arbre qui

a la taille d’un bloc disque

3. Dans une feuille, tous les fils sont vides, on peut donc les supprimer et mettre

plus de valeurs.

4.8 B-ARBRES 182

4.8.1 Définition

On choisit

const { pour un noeud i n t é r i e u r , non f e u i l l e }

Minelems = . . . ; { > 0 : nombre min de c l e f s }

Maxelems = . . . ; { > 2∗Minelems : nombre max de c l e f s }

{ pour une f e u i l l e : }

Mindonnees = . . . ; { > 0 : nombre min d ’ éléments }

Maxdonnees = . . . ; { > 2∗Mindonnees : nombre max d ’ éléments }

Le nombre minimum de fils t est Minelems+1.

Soit Min = Mindonnees pour une feuille, Minelems sinon. La cellule racine peut aller

en dessous du Min, mais doit avoir au moins 1 clef et 2 fils.

4.8 B-ARBRES 183

4.8.1.1 Déclaration

Barbre = ^noeud ;

{ i n v a r i a n t : b <> n i l }

noeud = record

uti : in teger ; { nombre d ’ éléments u t i l i s é s }

case feuille : boolean of

true : (donnees : array [ 1 . .Maxdonnees ] of elem ) ;

fa lse : (elems : array [ 1 . .Maxelems ] of elem ;

fils : array [ 0 . .Maxelems ] of Barbre ) ;

end ;

end ;

4.8 B-ARBRES 184

4.8.1.2 Invariant de données

1. uti >= 0

2. uti > 0 si la racine n’est pas une feuille

3. uti <= Max

4. pour tout noeud sauf la racine, uti >= Min

5. pour tout i in 1..uti, e in Info(fils[i-1]), e < elems[i]

6. pour tout i in 1..uti, e in Info(fils[i]), elems[i] < e

7. tous les fils ont la même hauteur.

8. la partie utilisée de donnees et elems est triée

4.8 B-ARBRES 185

L’invariant nous donne une hauteur logarithmique : la racine a au min une clé et

deux fils, ses fils ont au minimum t fils, etc.

n ≥ 1 + (t− 1).h∑

i=1

2ti−1

h ≤ logt(n+ 1

2)

4.8 B-ARBRES 186

4.8.2 Procédures et fonctions

4.8.2.1 Recherche

On recherche la clef dans le tableau elems ; Soit on l’y trouve, sinon on trouve le

fils dans lequel il pourrait se trouver. Cette recherche peut être linéaire, ou

dichotomique si Max est grand.

4.8.2.2 Ensemble vide

L’ensemble vide est représenté par une feuille avec uti=0.

4.8.2.3 Diviser

Un noeud plein peut être divisé en deux noeuds, et la clé centrale est remontée

dans le père pour séparer ces deux noeuds.

4.8 B-ARBRES 187

1. Technique préventive : On met dans la précondition que le père n’est pas plein.

2. Technique corrective : On divise le père après si nécessaire par un appel

récursif.

4.8 B-ARBRES 188

4.8.2.4 Insérer

On voudrait insérer une nouvelle clef dans la feuille où on devrait la trouver, mais

ceci peut faire déborder la feuille si elle était pleine.

1. Technique préventive : on divise tous les noeuds pleins qu’on traverse

2. Technique corrective : on divise en remontant.

4.8 B-ARBRES 189

procedure inserec (e : elem ; var b : Barbre ) ;

{ Pré : b^ est non p l e i n

Post : b est un B−arbre ; e s ’ a jou te à son contenu }

var i : in teger ;

begin

i := rech (e ,b ) ;

i f b ^ .feuille

then i f absent (e , i ,b ) then insererpos ( i ,e ,b )

else i f absent (e , i ,b )

then i f plein (b ^ .fils [ i ] )

then begin

diviser (b , i ) ;

i f b ^ .elems [ i +1] <= e then i := i + 1;

i f b ^ .elems [ i ] <> e then inserec (e ,b ^ .fils [ i ] ) ;

4.8 B-ARBRES 190

end

else inserec (e ,b .fils [ i ] )

end ;

4.8 B-ARBRES 191

begin { de i n s e r e r }

i f plein (b )

then begin

new (p ) ;

p^ .feuille := fa lse ;

p^ .uti := 0 ;

p^ .fils [ 0 ] := b ;

b := p ;

diviser (p , 0 ) ;

end ;

inserec (e ,b ) ;

end ;

4.8 B-ARBRES 192

4.8.2.5 Fusion

Symétriquement, la fusion supprime une clef du père qui pourrait ainsi passer en

dessous du minimum.

4.8.2.6 Supprimer

Technique préventive : on ne descend dans un fils que s’il est au-dessus du min.

Pour garantir cela, soit on prend des fils d’un frère (s’il n’est pas au min), soit on

fusionne avec un frère.

De même lors de la suppression du minimum/maximum ci-dessous.

Si la valeur à supprimer est dans un noeud intérieur, il faut la remplacer soit :

1. par la valeur suivante : le minimum du fils de droite

2. par la valeur précédente : le maximum du fils de gauche

Si ces deux fils sont au min, on les fusionne avant.

CHAPITRE 5. TA FILE DE PRIORITÉ 193

CHAPITRE 5

TA FILE DE PRIORITÉ

5.1 SPÉCIFICATION PAR MODÈLE 194

5.1 Spécification par modèle

procedure inserer (E: ens ; x : elem )

Post : E = E0 ∪ {x}

procedure SupprimerMax (E: ens ; var m: elem )

Pré : E non vide .

Post : m = max(E0)

E = E0 \ {m}

5.2 IMPLÉMENTATION 195

5.2 Implémentation

1. B-Arbres : inserer se fait en logn et supprimermax en logn, il s’agit des temps

optimaux.

2. Il existe une implémentation plus simple : le TAS

3. Un tas implémente un APO.

5.2.1 Arbre binaire partiellement ordonné (APO)

Invariant Un père est plus grand que ses fils.


5.2.2 Tas

Invariant

De plus :

1. tous les niveaux, sauf le dernier, sont remplis.

càd : tous les chemins ont la même longeur à 1 près.

2. le dernier niveau est rempli d’abord à gauche.


11

10

8

6 4

3 5 1

7i

2*i 2*i + 1

1

2 3

4 5 6 7

8 9


5.2.3 Procédures et fonctions

L’insertion dans un tas.

procedure swap ( var A : INTARRAY; i , j : in teger ) ;

var temp : in teger ;

begin

temp := A[ i ] ;

A[ i ] := A[ j ] ;

A[ j ] := temp ;

end ;


procedure bubbleUp ( var A: INTARRAY; i : in teger ) ;

begin

i f i > 1

then i f A[ i ] > A[ i div 2]

then begin

swap (A, i , i div 2 ) ;

bubbleUp (A, i div 2)

end

end ;


procedure insert ( var A : INTARRAY; x : in teger ; var n : in teger ) ;

begin

n := n + 1;

A[n ] := x ;

bubbleUp (A, n ) ;

end ;


bubbleDown fait descendre un élément responsable de la violation de la propriété

APO jusqu’à ce qu’une feuille soit atteinte.

procedure bubbleDown ( var A : INTARRAY; i ,n : in teger ) ;

var child : in teger ;

begin

child := 2 ∗ i ;

i f child < n

then i f A[child + 1] > A[child ]

then child := child + 1;

i f child <= n

then i f A[ i ] < A[child ]

then begin

swap (A, i , child ) ;

bubbleDown (A, child , n ) ;


end

end ;


procedure deletemax ( var A: INTARRAY; var n : in teger ) ;

begin

swap (A[ 1 ] , x ) ;

n := n − 1;

bubbleDown (A, 1 , n ) ;

end ;


Transformer un tableau en tas.

procedure heapify ( var A : INTARRAY;n : in teger ) ;

var i : in teger ;

begin

for i := n div 2 downto 1 do

bubbleDown (A , i , n ) ;

end ;


Tri par tas dans un tableau.

procedure heapsort ( var A : INTARRAY; n : in teger ) ;

var i : in teger ;

begin

heapify (A,n ) ;

i := n ;

while i > 1 do deletemax (A, i )

end ;


Exemple un arbre partiellement ordonné avec 10 noeuds.


18

16

1 9

18

7

573

9


Qui est représenté par le tableau :

i : 1 2 3 4 5 6 7 8 9 10

A[i] : 18 18 16 9 7 1 9 3 7 5


Question de départ

Comment passer d’un problème décrit par une spécification

↓ Architecture + Conception d’algorithme

un algorithme = une idée de solution, indépendante du langage

↓ Codage

un programme

↓ Compilation

pour finalement obtenir un exécutable

Dans ce cours nous nous limitons à la conception d’algorithmes.


Méthodes Générales de Conception d’Algorithmes

1. Générer et tester

2. Diviser pour règner

3. Programmation dynamique

4. Algorithmes gloutons

5. . . .

CHAPITRE 6. DIVISER POUR RÈGNER 211

CHAPITRE 6

DIVISER POUR RÈGNER

6.1 IDÉE 212

6.1 Idée

Utiliser la récursion, ce qui implique de diviser un problème en sous-problèmes

similaires mais plus simples.

– Diviser le problème en n sous-problèmes similaires plus simples (typiquement :

n = 2).

– Ces sous-problèmes sont résolus récursivement jusqu’aux “cas de base”.

– Les solutions sont recombinées pour donner une solution du problème originel.

6.1 IDÉE 213

6.1.1 Cas de base

La notion de “plus simple” doit être une relation bien fondée.

Les cas de base sont les cas minimaux de cette relation ;

Pour < sur N, c’est le cas 0.

La fonction résoudre(d) est donc de la forme

Si cas de base(d) Alors r := résoudre-directement(d)

Sinon (d1, d2, . . . , dn) := diviser(d)

pour chaque i : ri := résoudre(di)

r := combiner(r1, r2, . . . , rn)

6.1 IDÉE 214

6.1.2 Choix possibles

On peut choisir diviser ou combiner d’où on déduit l’autre.

Par exemple, on peut diviser un problème :

1. Suivant la définition récursive des données.

Exemple : puisque liste = listevide | cons(elem,liste) ⇒ division en tête et reste.

Cette méthode à l’avantage d’être simple, même si elle est parfois déséquilibrée

et donc moins efficace.

2. Pour avoir des sous-problèmes de même taille (souvent plus efficace).

Exemple : deux listes ayant environ la même longueur.

Dans ce cas, on doit aussi traiter le cas 1 comme cas de base.

6.2 EXEMPLE : LE SPÉCIFICATION 215

6.2 Exemple : le Spécification

tri :

En entrée : d : liste

En sortie : o : liste

Postcondition : o est triée et d est une permutation de o.

Si on veut qu’une solution existe toujours, on suppose que l’ordre de tri est réflexif

ce qui permet les doublons.


6.2.1 Solution D1 : Tri par INSERTION

diviser(l) = (tête(l), reste(l))

⇒ case de base : l = nil.

On déduit combiner = insérer un élément dans une liste triée. (en O(n))

Le temps total d’exécution sera donc de l’ordre de O(n2).

ins(e,nil) = cons(e,nil)

ins(e,cons(t,r)) = if e leq t then cons(e,cons(t,r))

else cons(t, ins(e, r))


6.2.2 Solution D2 : Tri par FUSION

diviser(l) = (l1, l2) tel que l1 + l2 = l et |l1| = |l2| ± 1. (en O(logn))

⇒ case de base : |l| ≤ 1.

On déduit combiner = fusionner deux listes triées. (en O(n)).

Le temps total d’exécution sera donc de l’ordre de O(n logn).


6.2.3 Solution C1 : Tri par SELECTION

combiner = cons(e,l).

⇒ cas de base : l = nil.

On déduit diviser = trouver le minimum des éléments de l. (en O(n))

Le temps total d’exécution sera donc de l’ordre de O(n2), car on fait n appels à

diviser.


6.2.4 Solution C2 : ≈ QUICKSORT

combiner = append(l1, l2)

⇒ cas de base : |l| ≤ 1.

On déduit diviser = trouver la médiane de l, puis diviser en plus grand, plus petit

autour de cette valeur pivot.

(variante : prendre un élément au hasard → QUICKSORT (en O(n logn) si on ne

fait pas toujours le mauvais choix)).


6.2.5 Temps d’exécution minimal d’un tri

Si le tri se fait par comparaisons (≤), on peut représenter les éxecutions possibles

par un arbre de décisions binaires.

a[1] ≤ a[2]

a[2] ≤ a[3]

1 – 2 – 3 a[1] ≤ a[3]

1 – 3 – 2 3 – 1 – 2

a[3] ≤ a[2]

3 – 2 – 1 a[1] ≤ a[3]

2 – 1 – 3 2 – 3 – 1

Le nombre de feuilles est au moins n!, car il y a n! permutations possibles de la

liste d’entrée.


Le temps d’exécution au pire T (en ne comptant que les comparaisons) est la

hauteur de l’arbre d’exécutions.

Un arbre binaire de hauteur T a au plus 2T feuilles.

n! ≤ 2T ⇐⇒ log2(n!) ≤ T

Or log(n!) = O(n logn) par l’approximation de Stirling.

D’où T ≥ O(n logn)

O(n logn) = meilleur ordre de grandeur possible pour un tri par comparaisons.

6.3 MULTIPLICATION 222

6.3 Multiplication

6.3.1 Méthode classique

Cette méthode est dérivée du calcul écrit classique.

1101

× 101

=

1101

+11 01

=

100 0001

Soit n le nombre de bits : on obtient une complexité en O(n2) car on effectue n

additions de n bits.


6.3.2 Diviser pour règner

On peut toujours augmenter n à une puissance de 2. Coupons X, Y en 2 parties

égales :

X = A2n/2 + B (1)

Y = C2n/2 +D (2)

(3)

X ∗ Y = (A ∗ C)2n + (A ∗D + B ∗ C)2n/2 + (B ∗D)

qui est composé de 4 multiplications et dont le temps d’exécution suit


T (1) = 1

T (n) = 4T (n/2) + cn

⇒ T (n) = O(n2)

Même temps par diviser pour règner !


Ceci est dû aux 4 appels récursifs à la multiplication. La première et la dernière

multiplication calculent le début et la fin du résultat et sont donc inévitables : donc

on s’attaque au terme central, en supposant le premier et le dernier connus.

On obtient alors 3 multiplications par la décomposition

X ∗Y = (A ∗C)2n +((A−B) ∗ (D−C) +A ∗C +B ∗D)2n/2 +B ∗D

T (1) = 1

T (n) = 3T (n/2) + cn

⇒ T (n) ≤ O(nlog23)

Cette méthode a été trouvée par Karatsuba et Ofman.


6.3.2.1 Puissances rapides

La nième puissance d’un nombre r est rn = r.r.r. . . . .r. Une implémentation

évidente est de faire une boucle for , avec un temps O(n.m) où m est le temps

d’une multiplication.

Par diviser pour règner, on a l’idée de couper la liste de r en deux parties égales.

funct ion puissance (r : rea l ; n : natural ) : rea l ;

begin

i f n=0 then puissance := 1

else i f pair (n )

then puissance := sqr (puissance (r ,n div 2 ) )

else puissance := puissance (r ,n−1)∗rend

T = O(m.logn)


6.3.2.2 Fibonacci par puissances rapides

Fib(n)

Fib(n+ 1)

=

0 1

1 1

Fib(n− 1)

Fib(n)

Et donc

Fib(n)

Fib(n+ 1)

= Mn

0

1

On peut utiliser l’algorithme précédent aussi pour les puissances de matrices.

CHAPITRE 7. PROGRAMMATION DYNAMIQUE 228

CHAPITRE 7

PROGRAMMATION DYNAMIQUE

Principe : mise en mémoire pour éviter les recalculs


Nous présentons d’abord quelques variantes simplifiées :

1. Mémoïsation

2. Récursivité ascendante

3. Programmation dynamique


Exemple : Nombres de Fibonacci

Les nombres de Fibonacci sont définis de la façon suivante :

Fib(n) =1√5((1 +

√5

2)n − (

1−√5

2)n)

Ou bien récursivement :

Fib(0) = 0

Fib(1) = 1

Fib(n+2) = Fib(n+1) + Fib(n)


Le temps d’exécution est :

T (0) = O(1)

T (1) = O(1)

T (n+ 2) = T (n+ 1) + T (n) +O(1)

Il s’agit donc de la même récursion et donc d’un temps exponentiel :

T (n) = O((1 +

√5

2)n)

7.1 MÉMOÏSATION 232

7.1 Mémoïsation

7.1.1 Idée

Pour éviter les recalculs, on met les valeurs calculées dans un tableau.

7.1.2 Détail

En plus de la fonction de départ f , on introduit la fonction fmémo et on remplace

tous les appels de f par des appels de fmémo. Celle-ci vérifie d’abord si le résultat

ne se trouve pas dans son tableau ; sinon elle appelle f et met le résultat dans son

tableau.

const undef = { une va leu r constante jamais employée par ex −1 }

var FibTab : array [ 0 . .MAX] of integer ; { i n i t i a l i s é à undef }


funct ion Fibmémo (n : in teger ) : in teger ;

{ Pré : 0 ≤ n ≤ MAX }

begin

i f FibTab [n ] = undef

then FibTab [n ] := Fib (n ) ;

Fibmémo := FibTab [n ]

end ;

Donc dans la fonction Fib, les appels récursifs se font à travers Fibmémo.


Avantages de la mémoïsation

– Technique facile à programmer.

– La transformation peut être automatisée.

– L’ordre de grandeur du temps d’exécution décroît (d’exponentiel à linéaire pour

Fib) ou reste identique.

– Seuls les sous-problèmes utiles sont calculés

Inconvénients

– Il faut limiter le nombre de valeurs possibles des arguments pour avoir un tableau

de taille raisonnable.

7.2 RÉCURSIVITÉ ASCENDANTE 235

7.2 Récursivité Ascendante

7.2.1 Idée

Pour éviter les test ( ... = undef) on s’arrange pour que la valeur se trouve déjà dans

la tableau au moment où on en a besoin. Pour cela on calcule les appels en

montant dans le graphe d’appels.


7.2.2 Avantages de la Récursivité Ascendante

– Petit gain de temps : élimination du test

– L’analyse du graphe d’appels permet souvent d’économiser de la mémoire.

7.2.3 Inconvénients

– La forme du programme est complètement changée.

– Attention aux calculs inutiles !


7.2.4 Sous-problèmes inutiles : Exemple

Logarithme entier : ⌊logk(n)⌋ where n ≥ 1, n ∈ N.

Diviser pour régner donne :

ilog(n) = 0 si 1 ≤ n < k (4)

ilog(n) = ilog(n div k) + 1 si n ≥ k (5)

(6)

Le temps d’exécution est O(logn).


7.2.4.1 Récursivité ascendante naïve

On aurait tendance à calculer ilog pour tous les nombres jusque n :

for i := 1 to k−1 do

ilogTab [ i ] := 0 ;

for i := k to n do

ilogTab [ i ] := ilogTab [ i div k ] +1

Ce programme est plus lent O(n) et demande plus de mémoire O(n). En effet, il

calcule et retient des sous-problèmes inutiles (qui n’interviennent pas dans le

résultat final)

Les sous-problèmes utiles sont ceux qui ont un chemin d’appels depuis le problème

de départ.


7.2.5 Économie de mémoire

1. La taille du tableau dépend du nombre de valeurs possibles des paramètres. Il

faut donc réduire ceux-ci. Les paramètres qui ne changent pas (k pour ilog)

peuvent être passés comme variable globale ou constante.

2. Il n’est souvent pas nécessaire de garder tout le tableau, car il se peut que

certains éléments ne soient plus utilisés dans le futur. On peut les déterminer

graphiquement :

(a) On choisit un ordre de parcours

(b) On trace une ligne séparant les éléments du tableau déjà calculés de ceux

qui ne le sont pas encore

(c) Les éléments calculés à conserver sont ceux qui sont le départ d’une flèche

e qui traverse la ligne, autrement dit qui seront utilisés par la suite.


7.2.6 Exemple : Fibonacci

Graphe d’appel (ou de dépendances) : Fib(i) dépend de Fib(i-1) et Fib(i-2).

La récursivité ascendante appliquée à l’équation de Fibonacci donne :

var F : array [ 0 . .MAX] of natural ;

F [ 0 ] := 0 ;

F [ 1 ] := 1 ;

for i :=2 to n do

F [ i ] := F [ i −2] + F [ i −1];

Fib := F [n ]

Temps et mémoire : O(n), comme la version mémoïsée.


7.2.6.1 Exemple : Fibonacci : Économie de mémoire

Le graphe d’appel montre qu’il ne faut garder que les deux derniers éléments en

mémoire. Posons un nouveau tableau F avec l’invariant F [imod2] = Fib(i).

var F : array [ 0 . . 1 ] of natural ;

F [ 0 ] := 0 ;

F [ 1 ] := 1 ;

for i :=2 to n do

F [ i mod 2] := F [ 0 ] + F [ 1 ] ;

Fib := F [n mod 2]


7.2.7 Exemple : Combinaisons

Le nombre de combinaisons (ensembles) de m éléments choisis dans un ensemble

de taille n (avec m ≤ n) est noté ici Cmn .

Certains le notent

n

m

ou inversent m et n.

Pre : n ≥ m ≥ 0 Post : Cmn = #{s ⊆ {1..n}‖#s = m}


Diviser pour régner nous permet de trouver une définition récursive :

Cmn = 0 Si m > n ou m < 0 car il est impossible de prendre un nombre négatif

d’objets ainsi que d’en prendre plus de n.

C0n = 1 Car seul l’ensemble vide ne contient aucun élément.

Cnn = 1 Car seul l’ensemble plein contient tous les objets.

Cmn = Cm

n−1 + Cm−1n−1 Car, si on ajoute un élément supplémentaire (’n’) dans un

ensemble de n− 1 éléments,

1. Toutes les anciennes combinaisons Cmn−1 restent valables (ce sont les cas

où ’n’ n’est pas pris).

2. Les combinaisons qui contiennent ’n’ sont au nombre de Cm−1n−1 ( car on

prend n− 1 anciens).


Le temps d’exécution est :

O(1) pour les cas de base (7)

T (n) = 2T (n− 1) +O(1) (8)

temps exponentiel en n.

On peut constater des recalculs dans l’arbre d’appels. Pour bien voir cela, on

dessine le graphe d’appels où les mêmes appels sont fusionnés. Un noeud avec

plusieurs pères est un appel recalculé plusieurs fois. On présente ce graphe dans le

tableau de memoïsation.


Par récursivité ascendante, dans l’ordre des obliques :

funct ion comb(m, n : in teger ) : in teger ;

var C : array [ 0 . .MAX] of integer ; . . .

begin

i f m > n div 2 then m := n−m;

for j := 0 to m do C[ j ] : =1 ;

for i := 0 to n−m−1 do

for j := 1 to m do

C[ j ] := C[ j ] + C[ j −1]

comb := C[m] ;

end ;


Remarques

1. Le test if... a pour but de maintenir m plus petit, et donc d’économiser du

temps et de la place mémoire.

2. L’invariant de la boucle for imbriquée (donc celle en j) est

k < j ⇒ C[k] = Cki+k+1 (9)

k ≥ j ⇒ C[k] = Cki+k (10)

3. Le temps d’exécution est O(n ∗m) ≤ O(n2)

4. La place mémoire est O(m) (linéaire, au lieu de O(n2) pour une mémoïsation

simple).

Ceci est juste une illustration historique de la programmation dynamique : on peut

faire plus rapide (linéaire) et plus économe en mémoire (constante) en se ramenant

à la factorielle.

7.3 PROGRAMMATION DYNAMIQUE 247

7.3 Programmation dynamique

La programmation dynamique combine “diviser pour régner”, puis la récursivité

ascendante avec mise en mémoire.

On l’applique surtout sur des problèmes d’optimisation : trouver une solution

faisable de coût minimal (ou de gain maximal).

1. Trouver la récursion par « diviser pour régner ».

(a) Dans le cas d’un problème d’optimisation, on l’appelle propriété de

sous-solution optimale : montrer que le problème de départ peut se calculer

à partir des solutions optimales de sous-problèmes plus petits.

(b) Pour simplifier on ne renvoie que le coût optimal (au point 4 on reconstruira

la solution complète.)

(c) limiter les paramètres pour réduire la taille du tableau.


2. Récursivité ascendante : de la définition récursive, on déduit le graphe des

dépendances.

(a) Si plusieurs chemins partent du même appel, il y a des recalculs donc on

met en mémoire. Sinon, la récursivité simple suffit.

(b) On choisit un ordre de calcul compatible avec les dépendances.

(c) On minimise l’emploi de mémoire en supprimant la mémoire qui ne sera plus

utilisée, autrement dit on ne garde que les départs d’une flèche qui franchit

la frontière de calcul.

(d) On reconstruit la solution : Chaque choix est mémorisé dans un tableau ; à la

fin, on reconstruit en arrière une solution optimale grâce à ces choix.


7.3.1 Exemple : sac à dos discret

Un voleur pénètre par effraction dans un magasin. Il vous demande comment

remplir son sac à dos pour maximiser la valeur du contenu ?

Données

– Capacité du sac : C

– Pour chaque article du magasin i :

– Une valeur : vi ∈ N (nombre naturel)

– Un poids : ti ∈ N+ (nombre naturel positif)


Résultat

Donner un tableau qi ∈ N (quantités emportées) qui maximise la valeur V du

contenu :

V =∑

i

qi ∗ vi

sous la contrainte de ne pas dépasser le poids :

∑

i

qi ∗ ti ≤ C


Formalisation récursive

Induction sur les articles : on pose g(S, c) = gain maximum pour un ensemble

S ⊆ {1 . . . n} et une capacité c ≤ C

Cas de base :

– Si le sac n’a pas de capacité, on ne peut rien y mettre : g(S, 0) = 0

– Si le magasin est vide, on ne peut rien emporter : g(∅, c) = 0


7.3.2 Diviser

7.3.2.1 Division en un élément / le reste

Soit k ∈ S un article de S.

g(S, c) = SI c < tk ALORS g(S\{k}, c)SINON max{g(S\{k}, c), vk + g(S, c− tk)}

c

Solution optimale pour S ou bien Solution optimale pour S\{k}Capacité : c− tk

1 article k

(Il faut c ≥ tk)


7.3.2.2 Choix de l’article

On choisit de considérer les articles dans l’ordre de leur numéro, pour diminuer la

taille du tableau, donc on pose g(k, c) = g({1 . . . k}, c)


c 1 2 3 . . . C

n g(n, 1) g(n, 2) g(n, 3) g(n,C)

n− 1 g(n− 1, 1) g(n− 1, 2) g(n− 1, 3) g(n− 1, C)...

3 g(3, 1) g(3, 2) g(3, 3) g(3, C)

2 g(2, 1) g(2, 2) g(2, 3) g(2, C)

1 g(1, 1) g(1, 2) g(1, 3) g(1, C)


7.3.2.3 Conséquences

1. L’implémentation récursive implique des recalculs si il y a deux façons

différentes de diviser la même quantité.

2. Organisation des calculs :

– De gauche à droite ( ligne par ligne car par rapport aux colonnes, les lignes

sont de longueurs différentes).

– Une ligne suffit en mémoire.

var gain : array[0..C] of integer ;


7.3.2.4 Invariants

– de for k := 0 to n do ... (boucle extérieure → pour chaque ligne)

0 ≤ k ≤ n

∀j : 0 ≤ j ≤ C : gain[j] = g(k, j)

– de for j := 0 to C do ... (boucle intérieure → pour chaque élément de la ligne)

0 < k ≤ n

0 ≤ j ≤ C

partie traitée ∀i : 0 ≤ i < j ⇒ gain[i] = g(k, i)

partie non traitée ∀i : j ≤ i ≤ C : gain[i] = g(k − 1, i)


L’application des techniques de programmation dynamique dans ce cas précis

donnent donc

Espace mémoire : tableau de taille C → O(C).

Temps d’exécution : n passages → O(nC).

Ce qui est coûteux dans les cas où C est grand.


7.3.3 Améliorations

Si il y a un article i et un article j(i 6= j) tels que

∃q : q ∗ ti ≤ tj et q ∗ vi ≥ vj

Alors j ne sera jamais employéa. En généralisant cette constatation :

Si ∃qi, qj :qi ∗ ti ≤ qj ∗ tj [plus léger]

qi ∗ vi ≥ qj ∗ vj [plus cher]

Alors j sera employé moins de qj fois.

aCar j est moins cher et plus lourd que i


L’idée est donc de calculer le “rapport qualité/prix” vi/ti. Soit m l’article de meilleur

rapport ; tous les autres ont une borne qj telle que

qj ≤ tm car tj ∗ tm ≤ tm ∗ tjet tj ∗ vm ≥ tm ∗ vj

Par application des relations de la généralisation et car m est le meilleur rapport.

De même,

qj ≤ vm


Soit Cm =∑

j 6=m qj ∗ tj ; on ne calcule la table “bouche-trou” que jusque Cm.

Si C > Cm :- Prendre ⌈C−Cm

tm⌉ articles de type m.

- Regarder dans la table pour le reste.


7.3.3.1 Correct ?

1. Si C > Cm, la solution contient un article m (puisque les autres sont bornés).

2. g(S,C) = g(S,C − tm) + vm si C > Cm.


7.3.4 Multiplication de matrices

Deux matrices se multiplient “ligne par colonne”

SI A = (aij)i=1..n,j=1..m est de taille n×m

B = (bjk)j=1..m,k=1..p est de taille m× p

ALORS A ∗B = (∑m

j=1 aij ∗ bjk)i=1..n,k=1..p est de taille n× p

est calculé en n ∗m ∗ p multiplications.

La multiplication matricielle est associative : on peut choisir de mettre les

parenthèses comme on veut, mais elle n’est pas commutative.


La question ici est de minimiser ce nombre de multiplications dans le cas d’une

chaîne de matrices :

Chaîne : M1 ∗M2 ∗ . . . ∗Mn avec Mi : pi−1 × pi


Exemple

Données :

A : 10 × 1

B : 1 × 10

C : 10 × 10

D : 10 × 1

E : 1 × 10


par (((AB)C)D)E

AB : 100 mult. → 10 × 10

. . . C : 1000 mult. → 10 × 10

. . . D : 100 mult. → 10 × 1

. . . E : 100 mult. → 10 × 10

Total : 1300 Mult.


par A(((BC)D)E)

BC : 100 mult. → 1 × 10

. . . D : 10 mult. → 1 × 1

. . . E : 10 mult. → 1 × 10

A . . . : 100 mult. → 10 × 10

Total : 220 Mult.


Soit nmul(i, j) le nombre minimum de multiplications nécessaires pour calculer

MiMi+1 . . .Mj

Notre objectif de départ s’écrit alors nmul(1, n). La mesure bien fondée est j − i.

Cas de base : nmul(i, i) = 0.

Pour j > 1 on a la récurrence :

nmul(i, j) = mini≤k<j

{nmul(i, k) + nmul(k + 1, j) + pi−1 ∗ pk ∗ pj}



7.3.4.1 Programme

{ i n i t }

for i := 1 to n do m[ i , i ] := 0 ;

{ i n v a r i a n t : pour t o u t k ’ < k , m[ i , k ’ ] = nmul ( i , k ’ ) }

for l := 2 to n do

for i := 1 to n−l +1 do

m[ i , j ] := min1≤k≤j−1 (m[ i ,k ] + m[k+1 ,j ] + pi−1 ∗ pk ∗ pj ) ;

result := m[ 1 ,n ]

Qui s’exécute en un temps en O(n3). L’énumération de tous les parenthésages

demande un temps ≥ O(2n).

CHAPITRE 8. ALGORITHMES GLOUTONS 270

CHAPITRE 8

ALGORITHMES GLOUTONS

Trouver localement un choix qu’on peut toujours faire dans un optimum


Exemples

Sac à dos continu borné* Prendre d’abord les articles de meilleur rapport

valeur/poids.

Pleins* Faire le plein le plus tard possible

Salle de spectacle * Prendre l’activité qui se termine le plus tôt.

Codes de Huffman * Fusionner les sous-arbres de moindre fréquences.

Voyageur de commerce Commencer par la ville la plus proche.

Correct ?

Pour les problèmes marqués d’une ’*’ la solution est optimale (et sinon il donne une

solution faisable, mais pas optimale).


Preuve

Le schéma d’une preuve gloutonne a deux étapes ; on prouve que :

1. Il y a un optimum qui contient le premier choix fait. Pour cela, on suppose un

optimum, et on montre que “notre” solution a la même valeur d’objectif

2. L’optimum pour le reste peut se trouver récursivement

3. En le combinant avec le premier choix, on trouve l’optimum.

On voit que c’est une preuve de type C1 (trouver un élément du résultat, puis

trouver le reste du résultat) qui donnera donc une récursion terminale équivalente à

une boucle.

8.1 SAC À DOS 273

8.1 Sac à dos

8.1.1 Continu

Dans ce cas, les qi peuvent être fractionnaires.

⇒ prendre uniquement l’article de meilleur rapport ⇐⇒ qm = C/tm

8.1.2 Continu borné

On impose une limite sur la quantité présente dans le magasin : qi ≤ Qi

⇒ Prendre les articles selon les rapports décroissants jusqu’à remplir le sac ou

vider le magasin.

8.2 EXEMPLE : LES PLEINS D’ESSENCE 274

8.2 Exemple : Les pleins d’essence

Donald a planifié son intinéraire de vacances, le long duquel il a relevé le

kilométrage des stations d’essence. Il veut s’arrêter le moins possible, sans tomber

en panne sèche.


Données

– Un réservoir de capacité CM ≥ 0 (en kilomètres)

– La distance à parcourir L ≥ 0

– La position des n stations le long de la route : (Si)i=1..n où

0 ≤ Si < Si+1 < . . . < L

0 arrivée

S4S1 S2 S3

– Le contenu du réservoir au départ : C0, où 0 ≤ C0 ≤ CM .

– On pose S0 = 0.


Résultat

Un tableau q contenant les quantités achetées qi à chaque station i, avec

0 ≤ qi ≤ CM , ou signaler qu’il n’y a pas de solution faisable. La fonction C(l)

donne le contenu du réservoir en fonction du kilométrage :

C(l) = C0 +∑

Si<l qi − l. Si l est la position d’une station, il s’agit du contenu à

l’entrée de la station. Le contenu du réservoir en sortant de la station k est donc :

Ck = C(Sk) + qk . Les arrêts A sont alors les stations où on achète de

l’essence : A = {i ∈ 1..n|qi > 0}.

Le problème est de minimiser le nombre d’arrêts |A| sans tomber en panne avant

de rallier l’arrivée :

∀l, 0 ≤ l < L : C(l) ∈ [0..CM ]


8.2.1 Si on s’arrête, autant faire le plein :

Soit q un optimum. q′ modifie q en faisant le plein chaque fois que q s’arrête :

q′i = CM − C ′(Si) si qi > 0. Alors q′ est aussi optimale.

Preuve : A′ = A donc la valeur de l’objectif est la même ; q′ reste faisable (on ne

tombe pas en panne) car CM ≥ C ′(l) ≥ C(l) ≥ 0.


8.2.2 Si on a de quoi atteindre la prochaine station, pas d’ar rêt :

Soit q un optimum. Si C(l) ≥ (Sk+1 − Sk), alors soit q′ une solution où q′k = 0

(on ne s’arrête pas en k) et q′k+1 = qk + qk+1 (on achète à la station suivante).

La fonction C ′(l) est identique à C(l), sauf entre SketSk+1, où

C ′(l) = C(l)− qk , mais elle satisfait toujours la contrainte.


Etant donné le choix de la première station, on résoud récursivement avec une

station en moins avec le réservoir initial soit plein si on s’arrête, ou diminué du trajet

parcouru sinon.

for i := 1 to n do

i f Ci−1 < (Si − Si−1)

then panneDessence

else i f (Si+1 − Si−1) > Ci−1

then Ci := CM

else Ci := Ci−1 − (Si − Si−1)

Temps : O(n).


8.2.3 Variante avec prix

Données On ajoute le prix à chaque station pi > 0.

Résultat Le coût à minimiser est :∑

i∈1..n pi ∗ qiNote : cet objectif encourage à arriver avec un réservoir vide.


Choix glouton : remplir le plus possible à la station m la moins chère. On arrive à

vide (sauf si C0 permet d’atteindre m) et on fait le plein (sauf si on peut atteindre la

destination).

On fait deux appels récursifs, pour résoudre le trajet avant m et le trajet après m.

Temps : retrouver la station la moins chère est linéaire, ce qui mène a un coût

total quadratique.

Une solution : un arbre rouge-noir trié sur le kilométrage des stations et augmenté

par le prix minimum des sous-arbres permet de retrouver la station de prix minimum

entre Si et Sj en temps O(n logn).

8.3 EXEMPLE : SALLE DE SPECTACLE 282

8.3 Exemple : Salle de spectacle

Données

Une liste d’activités candidates avec pour chacune :

si : temps de début

fi : temps de fin (avec si ≤ fi)


Résultat

Un ensemble A ⊂ {1 . . . n} de taille maximale d’activités compatiblesa

⇐⇒ ∀i, j ∈ A : si ≥ fj ou sj ≥ fi

a i.e. chronologiquement disjointes


Idée d’algorithme

Idée de preuve

1. Une solution optimale contient l’activité qui se termine le plus tôt (notée activité

k).

Soit A une solution optimale et soit m sa première activité.

B = A \ {m} ∪ {k} est optimale.

2. Après avoir choisi k, on résoud pour les activités compatibles avec k.


Algorithme

– Trier les activités par temps de fin (O(n logn)).

– A := ∅; f := −∞Pour chaque activité i prise dans cet ordre (O(n))

if si ≥ f

then A := A⋃{i} et f := fi

On obtient donc un temps d’exécution total de l’ordre de O(n logn).

8.4 CODES DE HUFFMAN 286

8.4 Codes de Huffman

8.4.1 Codages des caractères

8.4.1.1 Fixe

p.ex. ISO-Latin-1 fixe 8 bits pour chaque caractère,

8.4.1.2 Morse

les caractères plus fréquents (par ex. ’E’) ont un code plus court.

Le problème du morse est de séparer deux caractères :


5

i e i

s i

h e


e t

ai n m

wrus d k g o

h v f l p j b x c y z q


8.4.2 Calcul du code optimal

Données

– Un alphabet, càd un ensemble de caractères C.

– Pour chacun, une fréquence f [c]

Résultat Un code pour chaque caractère tel que aucun code n’est préfixe d’un

autre et∑

c∈C d(c) ∗ f(c) ( = longueur du texte) est minimum où d(c) est la

longueur du code de c.


Exemple

C = {a, b, c, d, e, f}

f = 45, 13, 12, 16, 9, 5.

codage ISO-Latin-1 8 * 100 = 800 bits.

codage fixe sur 3 bits 3 * 100 = 300 bits.a

codage optimal 224 bits

a b c d e f

0 101 100 110 1111 1110

acar 3 = ⌈log26⌉


a

c b d

f e

0 1

1

1

10

0

0

0 1


Lemmes

8.4.2.1 Sans préfixe

Un code est sans préfixe ssi un caractère n’apparaît que sur une feuille de l’arbre.

8.4.2.2

Dans un code sans préfixe optimal un noeud a 0 ou 2 fils. En effet, dans le cas

contraire, on peut “raccourcir la branche”.



8.4.2.3 Moins fréquents

Si x, y sont les deux caractères les moins fréquents alors il existe une solution

optimale où x et y ont deux codes les plus longs et diffèrent seulement par le

dernier bit.

Preuve :

Soit b,c deux codes les plus longs qui ne diffèrent que par le dernier bit.


x

y

b c

T:

x y

b

c

T':

x

y

c

T'':

b

coût(T) - coût(T’) =∑

c f [c] ∗ d(c)−∑

c f [c] ∗ d′(c)= f [x] ∗ d(x) + f [b] ∗ d(b)− f [x] ∗ d′(x)− f [b] ∗ d′(b)Or d′(x) = d(b)

= (f [b]− f [x]) ∗ (d(b)− d(x))

= (≥ 0) ∗ (≥ 0) (car x moins fréquent et b plus profond)


8.4.2.4 Récursion

Après avoir regroupé les deux caractères les moins fréquents, peut-on se ramener à

un problèmes similaire ?

Soit T une solution, x,y deux caractères frères de T.

Alors T est optimal ssi T\{x, y}⋃{z} est optimal pour le problème avec

C ′ = C\{x, y}⋃{z} où z est un “nouveau” caractère de fréquence

f ′[z] = f [x] + f [y].


Preuve :

coût(T ) =∑

c∈C

f [c] ∗ d(c) (11)

= (∑

c∈C′

f [c] ∗ d(c)) + f [x] + f [y] (12)

car f [z] = f [x] + f [y] et d(z) + 1 = d(x) = d(y) (13)

= coût(T ′) + (f [x] + f [y]) (14)

La différence est donc une constante : minimiser l’un revient minimiser l’autre.


8.4.2.5 Algorithme

Tant qu’il reste au moins deux caractères :

1. Retirer les deux caractères les moins fréquents : x et y.

2. Insérer l’arbre z := cons (f (x )+f (y ), x , y )



f:5 e:9

c:12 b:13 d:16

a:45

f:5 e:9 c:12 b:13 d:16 a:45

f:5 e:9

c:12 b:13 d:16 a:4514

f:5 e:9 c:12 b:13

d:16 a:4514 25

f:5 e:9

c:12 b:13 d:16

a:4525 30

f:5 e:9

c:12 b:13 d:16

55a:45

100


8.4.2.6 Implémentation

Comment trouver efficacement les deux caractères les moins fréquents ?

Une solution est le TA file de priorité, en particulier l’implémentation en tas qui

permet une complexité en O(log(n)) pour l’ajout et le retrait et en temps constant

pour la recherche du minimum.

La complexité d’une telle implémentation sera donc de O(nlog(n)), car on passe

n fois dans la boucle.

8.5 EXPOSANTS 302

8.5 Exposants

Données Une constante entière N > 0 ;

Un tableau d’entiers positifs b (bases) indexé de 1..N ;

Un tableau d’entiers positifs e (exposants) indexé de 1..N .

Résultat Une permutation p de 1..N qui maximise le gain :

N∑

i=1

b[p[i]]e[i]

8.5 EXPOSANTS 303

Propriété En étendant les exposants, le gain s’écrit :

b[p[1]] ∗ b[p[1]] ∗ .... ∗ b[p[N ]] ∗ b[p[N ]].

le nombre total de facteurs est fixe, c’est∑N

i=1 e[i]. Etant donné b[p[i]] > b[p[j]]

avec e[i] < e[j], on voit qu’en échangeant i et j dans p, le gain augmente car on

remplace e[j]− e[i] facteurs b[p[j]] par b[p[i]] qui est plus grand. Donc une

permutation optimale respecte l’ordre croissant des b et des e. On peut la trouver en

triant b et e et en les faisant correspondre dans cet ordre.

8.6 LE VOYAGEUR DE COMMERCE 304

8.6 Le voyageur de commerce

L’idée d’algorithmes gloutons donne parfois des heuristiques (i.e. des solutions

bonnes mais non optimales)

Problème Un représentant de commerce doit visiter n clients puis rentrer chez lui,

par le plus court chemin possible.

Données Un ensemble de “villes” V = {1, . . . n} et leurs distances :

d : V × V → R+ .

Résultat Une permutation p des villes telle que

∑n−1i=0 d(pi, pi+1) + d(pn, p0) est minimal.


Exemple Numérique Considérons les villes suivantes, chacune munie de sa

position, le tout sous la distance euclidienne.

a(0,0) f(8,0)

e(15,4)

d(15,7)

b(4,3)

c(1,7)

Le résultat sera : [a, b, f, e, d, c] pour un coût (optimal) de 48.39.


a

b

f

e

dc


Heuristiques gloutonnes

8.6.0.7 Plus proche

Partant de son domicile, le représentant va toujours à la ville la plus proche non

encore visitée.

Exemple :


a

Dans cet exemple, le coût d’une telle technique est de 50 > coût optimal, car le

dernier trajet est souvent long.a. Le temps d’exécution est de l’ordre de O(n2)

aMais si on partait de b alors on obtiendrait la solution optimale


8.6.0.8 Plus proche avant/arrière

On agrandit aussi le trajet “en arrière” si c’est moins coûteux.

Sur l’exemple : le même résultat.


8.6.0.9 Par arcs

On prend les arcs dans l’ordre de longueur croissante , a condition que cela ne crée

pas de cycle ni de carrefour (degré > 2).

aa a

1 2 3

Si les arcs sont dans un tas, on trouve une complexité de O(n2 log(n)) car il y n2

arrêtes.

CHAPITRE 9. GÉNÉRER ET TESTER 311

CHAPITRE 9

GÉNÉRER ET TESTER

Idée : essayer toutes les solutions.

Pour un problème d’optimisation, on garde la meilleure.

9.1 PRINCIPE 312

9.1 Principe

On divise la spécification du problème en deux parties :

1. la structure d’une solution, qu’on va générer

(a) On la découpe en choix, pour lesquelles on a des alternatives

(b) Un ensemble d’alternatives est une solution partielle ou un état

2. Les contraintes, qu’on va tester.

9.1 PRINCIPE 313

Exemple : N reines

On veut trouver toutes les façons de placer N reines sur un échiquier N ×N sans

qu’elles ne puissent se prendre, càd. qu’elles ne peuvent être sur la même ligne,

colonne, ou diagonale.

Structure d’une solution :

1. tableau des positions des reines : donne N2N solutions

2. chaque reine étant identifiée par sa colonne, on choisit sa ligne : donne NN

solutions ; on ne doit plus vérifier la contrainte sur les colonnes

9.2 GÉNÉRATION 314

9.2 Génération

1. Un programme récursif permettra de générer toutes les solutions

2. chaque niveau de récursion reçoit une solution partielle (état) et essaie toutes

les alternatives d’un nouveau choix : La pile de récursion contient l’information

utile pour continuer la génération. Son exécution peut être représentée par un

arbre d’exploration. La récursion classique l’explore en profondeur (DFS).

3. Lorsque la solution courante est complète, il teste les contraintes

4. Pour un problème d’optimisation, on évalue la valeur de l’objectif et on

mémorise la solution courante si c’est la meilleure jusqu’ici.

9.2 GÉNÉRATION 315

Exemple : N reines

Structure d’une solution partielle : pour les k premières colonnes, on donne dans

quelle ligne se trouve la reine de cette colonne. On la représente par une liste en

ordre inverse. L’appel initial se fait avec la liste vide (nil).

Choix suivant : la ligne de la reine dans la colonne k + 1. Les alternatives sont les

nombres de 1 à N.

procedure sols (l : liste )

begin

i f length (l ) < N then for i := 1 to N do sols (cons ( i , l ) )

else i f test (l ) then printQueen (l )

end

9.3 AMÉLIORATIONS 316

9.3 Améliorations

Elagage : On a intérêt à évaluer les contraintes dès que possible sur une solution

partielle, soit pour éliminer toutes les solutions descendantes.

Propagation : Trouver des conséquences plus simples des contraintes permet de

les évaluer plus tôt.

Domaine : En particulier, on peut retenir les alternatives encore possibles pour un

choix. S’il n’y en a plus qu’une, on la prend.

9.3 AMÉLIORATIONS 317

Pour les 4 reines, supposons qu’on choisisse pour chaque colonne de gauche à

droite. La première solution générée est 1,1,1,1, ensuite 1,1,1,2, etc. mais on aurait

pu backtracker dès 1,1 (même ligne).

9.4 BRANCH-AND-BOUND 318

9.4 Branch-and-bound

Amélioration : on utiliser des bornes (bound) sur le coût de la solution optimale

parmi celles qu’on construira dans le sous-arbre d’exploration. Pour une

minimisation, lorsque la borne inférieure d’une branche est supérieure à une

solution déjà trouvée, ce n’est plus la peine de l’explorer : on l’élague (pruning).

On a donc intérêt à trouver rapidement une bonne solution.

9.5 EXEMPLE : VOYAGEUR DE COMMERCE 319

9.5 Exemple : voyageur de commerce

On représente l’exploration par des noeuds de choix : inclure ou non l’arc (i, j) .

(a,b) ?

oui nonnon

non

oui

oui

(a,c)? (a,c) ?


premier client ?

1 2 ... n......

2nd client ?

1 3 4 ... n...

Exploré Non-Exploré


Borne inférieure

– Arc inclus ⇒ coût connu.

– Chaque noeud doit avoir un arc entrant et un sortant : on complète avec les arc

minimaux

– La demi-somme de ces arcs est une borne inférieure


Algorithme A∗

– Un choix est dit “ouvert” si on ne l’a pas exploré mais bien son père ;

– Heuristique : explorer le choix ouvert de moindre borne inférieure

– On élague lorsqu’une borne inférieure dépasse la meilleure valeur trouvée.

Documents

Transparents INFOB233 Programmation 2ème partie http