Algorithmique
2e édition
Des bases à la Programmation Orientée Objet en Java (avec exercices et corrigés)
Éditions eni
Avant-propos
Chapitre 1
Introduction à l'algorithmique
1. Introduction19
2. Les algorithmes hors du domaine de l'informatique20
3. Les objectifs de l'algorithmique21
3.1 La conception21
3.2 La complexité21
3.3 La calculabilité21
3.4 La correction22
4. Les représentations possibles pour un algorithme informatique22
4.1 Les logigrammes22
4.2 Le pseudo-code25
Chapitre 2
Le pseudo-code
1. La structure de l'algorithme27
2. Les commentaires29
3. La déclaration de variables30
3.1 Qu'est-ce qu'une variable ?30
3.2 Les types30
3.3 La déclaration d'une variable32
4. L'affectation d'une valeur33
5. La déclaration d'une constante34
6. Les opérations36
6.1 Les opérations arithmétiques36
6.1.1 Les quatre opérations arithmétiques usuelles36
6.1.2 La division entière et son reste37
6.1.3 Les opérateurs d'affectation combinés à un opérateur arithmétique38
6.1.4 L'incrémentation et la décrémentation39
6.1.5 La priorité d'exécution des calculs41
6.2 Les opérateurs de comparaison42
6.2.1 L'égalité42
6.2.2 La différence43
6.2.3 La supériorité et l'infériorité43
6.3 Les opérateurs booléens45
6.3.1 L'opérateur et45
6.3.2 L'opérateur ou47
6.3.3 L'opérateur non48
7. La console48
7.1 L'écriture de messages à l'utilisateur50
7.2 L'affichage formaté en Java51
7.3 L'affichage standard et l'affichage des erreurs en Java53
7.4 La saisie de valeur par l'utilisateur54
8. La génération de nombres aléatoires56
9. Les outils pour écrire du pseudo-code et du Java59
9.1 L'utilisation de Notepad + + pour écrire du pseudo-code59
9.2 Les environnements de développement intégré62
10. Exercices63
10.1 Valeurs des variables63
10.2 Quels affichages ?63
10.3 II fait quoi ?64
10.4 Vitesse moyenne.64
11. Solutions des exercices65
11.1 Valeurs des variables65
11.2 Quels affichages ?65
11.3 II fait quoi ?66
11.4 Vitesse moyenne66
Chapitre 3
Les conditionnelles
1. Présentation67
2. La structure de contrôle Si (forme simple)67
3. La structure de contrôle Si (forme double)70
4. L'imbrication des structures de contrôle.71
5. La structure de contrôle Selon74
6. L'opérateur ternaire77
7. Exercices79
7.1 La météo79
7.2 La météo version 279
7.3 Le nom du mois80
7.4 Le temps de cuisson80
7.5 Le bulletin de paie80
8. Solutions des exercices82
8.1 La météo82
8.2 La météo version 283
8.3 Le nom du mois83
8.4 Le temps de cuisson84
8.5 Le bulletin de paie85
Chapitre 4
Les boucles
1. Présentation89
2. La structure de contrôle Pour89
3. La structure de contrôle TantQue94
4. La structure de contrôle Répéter98
5. Le choix de la boucle la plus adaptée102
6. Les boucles imbriquées103
7. Exercices104
7.1 La moyenne de notes (version 1)104
7.2 La moyenne de notes (version 2)104
7.3 La moyenne de notes (version 3)105
7.4 Devinez à quel nombre je pense106
7.5 À moi de trouver106
7.6 Que fait cet algorithme ?107
7.7 Affichage de répliques de films (version 1)108
7.8 Affichage de répliques de films (version 2)108
7.9 Saisie d'un multiple de trois109
7.10 ASCII Art !109
7.11 ASCII Art 2110
8. Solutions des exercices111
8.1 La moyenne de notes (version 1)111
8.2 La moyenne de notes (version 2)112
8.3 La moyenne de notes (version 3)112
8.4 Devinez à quel nombre je pense113
8.5 À moi de trouver113
8.6 Que fait cet algorithme ?114
8.7 Affichage de répliques de films (version 1)115
8.8 Affichage de répliques de films (version 2)116
8.9 Saisie d'un multiple de trois117
8.10 ASCII Art !117
8.11 ASCII Art 2117
Chapitre 5
Les tableaux
1. Présentation119
2. La déclaration d'un tableau120
3. L'utilisation d'un tableau123
4. Le parcours d'un tableau124
5. Les tableaux : un type référence129
6. Les tableaux multidimensionnels132
7. Exercices136
7.1 Décollage immédiats136
7.2 Nombres d'occurrences136
7.3 Moyenne de notes (version 4)137
7.4 Machine à voter138
7.5 Palindrome140
7.6 Que fait-il donc ?141
7.7 Matrix142
7.8. Micro bataille navale142
7.9 Morpion143
8. Solutions des exercices143
8.1 Décollage immédiat143
8.2 Nombres d'occurrences144
8.3 Moyenne de notes (version 4)145
8.4 Machine à voter146
8.5 Palindrome147
8.6 Que fait-il donc ?148
8.7 Matrix149
8.8 Micro bataille navale149
8.9 Morpion150
Chapitre 6
Les procédures et fonctions
1. Présentation153
2. La déclaration d'un sous-algorithme155
2.1 Déclaration d'une procédure155
2.2 Déclaration d'une fonction156
3. L'appel à un sous-algorithme158
3.1 L'appel à une procédure158
3.2 L'appel à une fonction160
4. La transmission d'informations entre un sous-algorithme et l'algorithme appelant161
4.1 Les constantes globales162
4.2 Le passage de paramètres163
4.2.1 Le passage en paramètres des types valeur164
4.2.2 Le passage en paramètre des types référence165
4.3 Le retour d'une fonction167
5. La récursivité170
6. Exercices175
6.1 C'est le plus grand175
6.2 Micro bataille navale (version 2)175
6.3 Un tableau et des fonctions176
6.4 Le jeu du saute-mouton176
6.5 ASCII Art Studio177
7. Solutions des exercices178
7.1 C'est le plus grand.178
7.2 Micro bataille navale (version 2)179
7.3 Un tableau et des fonctions181
7.4 Le jeu du saute-mouton182
7.5 ASCII Art Studio184
1. Présentation189
1.1 Qu'est-ce que la programmation orientée objet ?189
1.2 L'intérêt de la programmation orientée objet190
2. Les notions de classe et d'instance191
3. La déclaration d'une classe192
4. Les attributs d'instance194
5. Les constantes196
6. Les méthodes d'instance.197
6.1 La déclaration d'une méthode d'instance197
6.2 Les méthodes Getters et Setters.201
6.3 La surcharge de méthodes202
7. La création d'une instance206
7.1 La déclaration et l'instanciation d'une variable de type classe206
7.2 Les tableaux d'instances210
8. Les constructeurs212
8.1 Le constructeur par défaut212
8.2 Les constructeurs212
8.3 La surcharge de constructeurs216
9. Les attributs de classe219
10. Les méthodes de classe222
10.1 La déclaration d'une méthode de classe222
10.2 L'appel à une méthode de classe226
10.3 Récapitulatif des méthodes de classe par rapport aux méthodes d'instance228
11. Les instances : un type référence234
12. Exercices235
12.1 Les dés235
12.2 Les clients235
12.3 Micro bataille navale (version 3)237
12.4 Micro bataille navale (version 4)237
13. Solutions des exercices238
13.1 Les dés238
13.2 Les clients239
13.3 Micro bataille navale (version 3)240
13.4 Micro bataille navale (version 4)242
Chapitre 8
Les relations entre les classes
1. Présentation245
2. L'utilisation d'une classe par une autre245
3. Les associations248
4. L'héritage256
4.1 La notion d'héritage256
4.2 La déclaration de l'héritage257
4.3 Les constructeurs et l'héritage260
4.3.1 Le constructeur par défaut260
4.3.2 Définir un constructeur261
4.4 La substitution de méthodes263
4.5 Le transtypage269
4.5.1 Le transtypage ascendant269
4.5.2 Le transtypage descendant271
4.5.3 Le transtypage et les méthodes substituées273
5. Les classes internes en Java275
5.1 La définition275
5.2 L'accès aux attributs278
6. La création d'instances par méthode de classe en Java278
6.1 L'encapsulation des constructeurs279
6.2 Un nommage différent pour les créateurs d'instance281
6.3 Le renvoi d'un sous-type282
7. Exercices284
7.1 La bataille de dés284
7.2 Les clients (version 2)287
8. Solutions des exercices291
8.1 La bataille de dés291
8.2 Les clients (version 2)293
Chapitre 9
Les éléments abstraits
1. Les classes abstraites299
2. Les méthodes abstraites305
2.1 La déclaration de méthodes abstraites305
2.2 L'implémentation d'une méthode abstraite307
2.3 L'appel à des méthodes abstraites312
3. Les interfaces314
3.1 La déclaration d'une interface314
3.2 L'implémentation d'une interface316
3.3 Le transtypage et les interfaces318
3.4 Les méthodes par défaut en Java320
4. Exercices321
4.1 La location de cycles321
4.1.1 Les classes et leurs attributs321
4.1.2 Les méthodes322
4.1.3 Le code322
4.2 Vitesse moyenne version multilingue323
5. Solutions des exercices323
5.1 La location de cycles323
5.1.1 Les classes et leurs attributs323
5.1.2 Les méthodes324
5.1.3 Le code325
5.2 Vitesse moyenne version multilingue328
Chapitre 10
Les erreurs et les exceptions
1. Présentation333
2. Les erreurs détectées à la compilation333
3. Les erreurs détectées à l'exécution334
3.1 Les erreurs irrécupérables335
3.1.1 La saturation de la pile des appels de méthodes335
3.1.2 La saturation de la mémoire335
3.1.3 Solutions336
3.2 Les exceptions en algorithmique336
3.2.1 Le traitement d'une exception336
3.2.2 La levée d'une exception338
3.3 Les exceptions en Java339
3.3.1 La levée d'une exception340
3.3.2 Les catégories d'exceptions.340
3.3.3 La propagation d'une exception342
3.3.4 Le traitement d'une exception343
3.3.5 Les traitements à effectuer dans tous les cas346
3.4 Les exceptions personnalisées en Java348
4. Exercices350
4.1 Le calcul de la racine carrée350
4.2 La calculatrice en Java350
4.2.1 Création d'une classe DepassementCapaciteException351
4.2.2 Création de la classe utilitaire Operation351
4.2.3 Création de la calculatrice351
5. Solutions des exercices353
5.1 Le calcul de la racine carrée353
5.2 La calculatrice en Java353
5.2.1 Création d'une classe DepassementCapaciteException353
5.2.2 Création de la classe utilitaire Operation353
5.2.3 Création de la calculatrice355
Chapitre 11
La généricité
1. Présentation359
2. Les procédures et les fonctions génériques359
2.1 La déclaration359
2.2 L'appel361
2.3 L'utilisation du type générique dans la procédure ou la fonction362
2.4 Les contraintes sur un type générique363
2.4.1 Type avec des valeurs ordonnées363
2.4.2 Type implémentant une interface365
2.4.3 Type héritant d'une classe367
2.5 Plusieurs types génériques367
3. Les classes génériques368
3.1 La déclaration368
3.2 L'instanciation370
4. Les interfaces génériques370
4.1 La déclaration371
4.2 L'implémentation372
4.2.1 L'implémentation par une classe non générique372
4.2.2 L'implémentation par une classe générique373
5. La généricité en Java377
5.1 Les méthodes génériques377
5.1.1 La déclaration377
5.1.2 L'appel378
5.1.3 Les méthodes génériques de Java378
5.2 Les contraintes sur un type générique379
5.2.1 Type héritant d'une classe ou implémentant une interface379
5.2.2 Type de valeurs ordonnées381
5.3 Les classes génériques383
5.3.1 La déclaration383
5.3.2 L'instanciation384
5.3.3 Les classes génériques de Java384
5.4 Les interfaces génériques386
5.4.1 La déclaration386
5.4.2 L'implémentation386
5.4.3 Les interfaces génériques de Java388
5.5 Les types valeur et la généricité391
6. Exercices392
6.1 Tirage au sort392
6.2 À l'envers392
6.3 Se mélanger les pinceaux393
6.4 Le plus grand393
6.5 Procédures et fonctions génériques en Java393
6.6 Apprentissage liste de vocabulaire393
6.7 Le podium395
7. Correction des exercices396
7.1 Tirage au sort396
7.2 À l'envers396
7.3 Se mélanger les pinceaux397
7.4 Le plus grand398
7.5 Procédures et fonctions génériques en Java399
7.5.1 Tirage au sort399
7.5.2 À l'envers399
7.5.3 Se mélanger les pinceaux400
7.5.4 Le plus grand401
7.6 Apprentissage liste de vocabulaire402
7.7 Le podium404
Chapitre 12
La mémoire
1. Présentation407
2. Les bases408
2.1 Les nombres entiers408
2.1.1 Les bases utilisées en informatique408
2.1.2 Notation409
2.1.3 La conversion d'une base vers la base dix410
2.1.4 La conversion de la base dix vers une autre base411
2.2 Les nombres réels412
2.2.1 La conversion d'une base vers la base dix413
2.2.2 La conversion de la base dix vers une autre base413
3. Les nombres entiers415
3.1 Les octets415
3.1.1 Les bits et les octets415
3.1.2 Les multiples416
3.2 Les entiers naturels417
3.3 Les entiers relatifs418
4. Les nombres réels422
4.1 La forme normalisée423
4.2 La norme IEEE-754423
4.2.1 Le codage du signe424
4.2.2 Le codage de l'exposant425
4.2.3 Le codage de la mantisse425
4.2.4 L'assemblage426
4.2.5 Les valeurs particulières427
5. Les caractères429
5.1 Le code ASCII430
5.2 Les pages nationales ou ASCII étendu431
5.3 L'Unicode432
5.3.1 L'UTF-32432
5.3.2 L'UTF-16433
5.3.3 L'UTF-8434
5.4 Les opérations sur les caractères436
5.4.1 L'incrémentation et la décrémentation436
5.4.2 Le changement de type436
5.4.3 L'addition et la soustraction437
5.4.4 La comparaison438
6. Les différentes zones mémoire438
6.1 La pile438
6.2 Le tas :443
6.3 Les instances et les tableaux444
6.3.1 Les instances444
6.3.2 Les instances et l'héritage446
6.3.3 Les tableaux447
6.3.4 Les opérations sur les instances et les tableaux449
6.4 Le passage des paramètres450
6.4.1 Le passage en paramètre de types valeur450
6.4.2 Le passage en paramètre de types référence453
6.5 Le retour d'une fonction455
6.5.1 Le retour d'un type valeur456
6.5.2 Le retour d'un type référence459
6.6 Le ramasse-miettes462
7. Exercices463
7.1 Conversion d'une base à une autre463
7.1.1 Convertir les valeurs suivantes en base 10463
7.1.2 Convertir les valeurs suivantes en base 2 et en base 16463
7.1.3 Convertir les valeurs suivantes en base 16463
7.1.4 Convertir les valeurs suivantes en base 2464
7.1.5 Convertir les valeurs suivantes en base 10464
7.1.6 Convertir les valeurs suivantes en base 2464
7.2 Algorithme de conversion464
7.3 Codage de valeurs en byte, short et int465
7.3.1 Comment sont codées les valeurs suivantes en byte ?465
7.3.2 Comment sont codées les valeurs suivantes en short ?465
7.3.3 Comment sont codées les valeurs suivantes en int ?465
7.4 Codage de valeurs en float465
7.4.1 Quelles valeurs sont codées par les octets suivants ?465
7.4.2 Comment sont codées les valeurs suivantes en float ?465
7.5 Unicode466
8. Correction des exercices466
8.1 Conversion d'une base à une autre466
8.1.1 Convertir les valeurs suivantes en base 10466
8.1.2 Convertir les valeurs suivantes en base 2 et en base 16467
8.1.3 Convertir les valeurs suivantes en base 16467
8.1.4 Convertir les valeurs suivantes en base 2468
8.1.5 Convertir les valeurs suivantes en base 10468
8.1.6 Convertir les valeurs suivantes en base 2468
8.2 Algorithme de conversion469
8.3 Codage de valeurs en byte, short et int470
8.3.1 Comment sont codées les valeurs suivantes en byte ?470
8.3.2 Comment sont codées les valeurs suivantes en short ?471
8.3.3 Comment sont codées les valeurs suivantes en int ?472
8.4 Codage de valeurs en float473
8.4.1 Quelles valeurs sont codées par octets suivants ?473
8.4.2 Comment sont codées les valeurs suivantes en float ?473
8.5 Unicode474
8.5.1 UTF-8474
8.5.2 UTF-32476
8.5.3 UTF-16476
Chapitre 13
La complexité des algorithmes
1. Présentation477
2. L'ordre de grandeur de la complexité479
3. Les catégories de complexité481
4. Illustration avec les algorithmes de tri483
4.1 Le tri par sélection484
4.1.1 Le principe de fonctionnement484
4.1.2 L'algorithme485
4.1.3 Un exemple d'utilisation485
4.1.4 La complexité487
4.2 Le tri à bulles487
4.2.1 Le principe de fonctionnement487
4.2.2 L'algorithme487
4.2.3 Un exemple d'utilisation488
4.2.4 La complexité491
4.3 Le tri par insertion491
4.3.1 Le principe de fonctionnement491
4.3.2 L'algorithme492
4.3.3 Un exemple d'utilisation492
4.3.4 La complexité493
4.4 Le tri de Shell493
4.4.1 Le principe de fonctionnement493
4.4.2 L'algorithme494
4.4.3 Un exemple d'utilisation495
4.4.4 La complexité496
4.5 Le tri fusion497
4.5.1 Le principe de fonctionnement497
4.5.2 L'algorithme497
4.5.3 Un exemple d'utilisation499
4.5.4 La complexité500
4.6 Le tri rapide500
4.6.1 Le principe de fonctionnement500
4.6.2 L'algorithme501
4.6.3 Un exemple d'utilisation502
4.6.4 La complexité504
4.7 Le tri par tas505
4.7.1 Le principe de fonctionnement505
4.7.2 L'algorithme507
4.7.3 Un exemple d'utilisation509
4.7.4 La complexité516
4.8 Synthèse517
4.9 Les limites de la complexité517
5. Exercices520
5.1 L'ordre de grandeur520
5.2 L'implémentation des algorithmes de tri en Java520
6. Solutions des exercices520
6.1 L'ordre de grandeur520
6.2 L'implémentation des algorithmes de tri en Java522
Index533