Algorithmique
Techniques fondamentales de programmation
Introduction
Chapitre 1
Introduction à l'algorithmique
1. Les fondements de l'informatique13
1.1 Architecture de Von Neumann13
1.2 La machine de Turing17
1.3 Représentation interne des instructions et des données19
1.3.1 Le binaire19
1.3.2 Les octets et les mots22
1.3.3 L'hexadécimal23
2. L'algorithmique24
2.1 Programmer, c'est un art24
2.2 Définition : l'algorithme est une recette26
2.3 Pourquoi utiliser un algorithme ?27
2.4 Le formalisme28
2.4.1 Les algorigrammes29
2.4.2 L'algorithme sous forme de texte30
2.5 La complexité32
2.6 Les structures algorithmiques35
3. Les langages d'implémentation35
3.1 Quel langage ?35
3.2 Classifications des langages39
3.2.1 Haut niveau, bas niveau39
3.2.2 Diverses classifications40
3.2.3 Compilé ou interprété41
3.3 La machine virtuelle42
3.4 C#44
3.4.1 Les avantages44
3.4.2 Un premier programme C#45
4. Exercices48
Chapitre 2
Les variables et opérateurs
1. Les variables51
1.1 Principe51
1.2 Déclaration54
1.3 Les types54
1.3.1 Les nombres55
1.3.2 Autres types numériques58
1.3.3 Les caractères59
1.3.4 Le type booléen61
1.4 Affectation63
1.4.1 Affectation de valeurs63
1.4.2 Affectation de variables67
1.5 Saisie et affichage68
1.6 Les constantes70
2. Opérateurs et calculs71
2.1 Les affectations71
2.2 Les opérateurs arithmétiques71
2.3 Les opérateurs booléens76
2.4 Les opérateurs de comparaison79
2.4.1 L'égalité80
2.4.2 La différence81
2.4.3 Inférieur, supérieur82
2.5 Le cas des chaînes de caractères83
2.6 La précédence des opérateurs84
3. Pour aller plus loin85
3.1 Les nombres négatifs85
3.2 La représentation des nombres réels87
3.3 Les dates92
3.4 Les caractères93
4. Types et langages95
4.1 Langages typés ou non95
4.2 La gestion de la mémoire96
5. Exercices97
Chapitre 3
Tests et logique booléenne
1. Les tests et conditions101
1.1 Principe101
1.2 Que tester ?103
1.3 Tests SI105
1.3.1 Forme simple105
1.3.2 Forme complexe107
1.4 Tests imbriqués110
1.5 Choix multiples114
1.6 Des exemples complets117
1.6.1 Le lendemain d'une date117
1.6.2 La validité d'une date121
1.6.3 L'heure dans n secondes123
2. L'algèbre booléen127
2.1 L'origine des tests127
2.2 Petites erreurs, grosses conséquences129
2.2.1 Ariane 5129
2.2.2 Mars Climate Orbiter130
2.3 George Boole130
2.4 L'algèbre131
2.4.1 Établir une communication131
2.4.2 La vérité133
2.4.3 La loi ET133
2.4.4 La loi OU134
2.4.5 Le contraire135
2.4.6 Les propriétés135
2.4.7 Quelques fonctions logiques139
2.4.8 Avec plus de deux variables142
2.5 Une dernière précision145
3. Exercices146
Chapitre 4
Les boucles
1. Les structures itératives149
1.1 Définition149
1.2 Quelques usages simples150
2. Tant Que151
2.1 Structure générale151
2.2 Boucles infinies et "break"153
2.3 Des exemples155
2.3.1 Une table de multiplication155
2.3.2 Une factorielle156
2.3.3 x à la puissance y157
2.3.4 Toutes les tables de multiplication159
2.3.5 Saisie de notes et calcul de moyennes161
2.3.6 Rendez la monnaie167
2.3.7 Trois boucles170
3. Répéter ... Jusqu'à172
3.1 Différences fondamentales172
3.2 Quelques exemples adaptés174
3.2.1 La factorielle174
3.2.2 Les trois boucles175
4. Pour ... Fin Pour176
4.1 Une structure pour compter...176
4.2 ... mais pas indispensable177
4.3 Quelle structure choisir ?177
4.4 Un piège à éviter178
4.5 Quelques exemples179
4.5.1 De nouveau trois boucles179
4.5.2 La factorielle180
4.5.3 Racine carrée avec précision181
4.5.4 Calcul du nombre PI184
5. Exercices186
Chapitre 5
Les tableaux et structures
1. Présentation189
1.1 Principe et définition189
1.1.1 Simplifier les variables189
1.1.2 Les dimensions191
1.1.3 Les types192
1.1.4 Déclaration193
1.1.5 Utilisation194
1.1.6 Les tableaux dynamiques194
1.2 C# et les tableaux196
1.2.1 Tableaux à une dimension196
1.2.2 Références de tableaux197
1.2.3 Tableaux à n dimensions199
1.3 Représentation en mémoire201
1.3.1 Représentation linéaire201
1.3.2 Représentation par référence203
2. Manipulations simples205
2.1 Recherche d'un élément205
2.2 Le plus grand/petit, la moyenne208
2.3 Le morpion209
3. Algorithmes avancés214
3.1 Les algorithmes de tri214
3.1.1 Principe214
3.1.2 Le tri par création215
3.1.3 Le tri par sélection215
3.1.4 Le tri à bulles217
3.1.5 Le tri par insertion221
3.1.6 Le tri Shell224
3.2 Recherche par dichotomie226
4. Structures et enregistrements229
4.1 Principe229
4.2 Déclaration230
4.2.1 Type structuré230
4.2.2 Enregistrement231
4.3 Utiliser les enregistrements232
4.3.1 Utiliser les champs232
4.3.2 Un enregistrement dans une structure234
4.3.3 Un tableau dans une structure235
4.4 Les tableaux d'enregistrements237
4.4.1 Les tables237
4.4.2 Une table comme champ238
4.5 Et C# ?239
5. Exercices241
Chapitre 6
Les sous-programmes
1. Présentation243
1.1 Principe243
1.2 Déclaration et définition245
1.2.1 Dans un algorithme245
1.2.2 En C#246
1.3 Appel247
1.4 Fonctions et procédures249
1.4.1 Les procédures249
1.4.2 Les fonctions250
1.5 Variables locales et globales252
1.5.1 Variables locales252
1.5.2 Variables globales253
1.5.3 Variables globales et C#255
1.6 Les paramètres256
1.6.1 Les procédures256
1.6.2 Les fonctions259
1.6.3 Paramètres et C#261
1.6.4 Petite application fonctionnelle263
1.7 Sous-programmes prédéfinis266
1.7.1 Un choix important266
1.7.2 Quelques exemples266
1.8 Dernier cas : les tableaux271
2. Les sous-programmes récursifs274
2.1 Principe274
2.2 Un premier exemple : la factorielle275
2.3 Un exemple pratique : les tours de Hanoï277
3. Exercices280
Chapitre 7
Les fichiers
1. Les différents fichiers281
1.1 Préambule281
1.2 Problématique282
1.3 Définition283
1.4 Les formats283
1.4.1 Types de contenus283
1.4.2 Le fichier binaire285
1.4.3 Le fichier texte286
1.4.4 Quel format utiliser ?288
1.5 Les accès aux fichiers289
1.5.1 Séquentiel289
1.5.2 Accès direct290
1.5.3 Indexé290
1.5.4 Autre ?290
2. Les enregistrements291
2.1 Les délimiteurs291
2.2 Largeur fixe294
2.3 Principes d'accès295
2.3.1 Étapes de base295
2.3.2 Identificateurs de fichiers et canaux296
2.3.3 Les modes d'ouverture298
3. Fichier texte séquentiel299
3.1 Ouvrir et fermer un fichier299
3.2 Lire et écrire des enregistrements300
3.2.1 Lecture300
3.2.2 Écriture302
3.3 Les enregistrements structurés306
3.4 Exemple en C#309
4. Les fichiers binaires311
4.1 Nouvelles instructions311
4.2 Exemple312
5. Exercices313
Chapitre 8
Notions avancées
1. Les pointeurs et références315
1.1 Rappels sur la mémoire et les données315
1.1.1 Structure de la mémoire315
1.1.2 C# : des limites qui n'en sont pas317
1.1.3 Brefs exemples en C317
1.2 Le pointeur318
1.2.1 Principe et définition318
1.2.2 Le C, roi des pointeurs319
1.2.3 Applications321
1.3 Notation algorithmique324
1.3.1 Déclarer et utiliser les pointeurs324
1.3.2 Allocation dynamique326
1.4 C#, les références et les pointeurs328
1.4.1 Différences et points communs entre C et C#328
1.4.2 Références sur les objets329
1.4.3 Les types primitifs331
1.4.4 Références sur les structures332
1.4.5 Le piège en C#333
1.4.6 La valeur null334
1.4.7 Structures et passage de paramètre par valeur335
2. Les listes chaînées337
2.1 Listes chaînées simples337
2.1.1 Principe337
2.1.2 Création340
2.1.3 Parcours de la liste342
2.1.4 Recherche343
2.1.5 Ajout d'un élément344
2.1.6 Suppression d'un élément348
2.1.7 Supprimer toute la liste351
2.1.8 Parcours récursif351
2.2 L'implémentation en C#352
2.3 Autres exemples de listes357
2.3.1 Listes circulaires357
2.3.2 Listes d'éléments triés357
2.3.3 Listes doublement chaînées357
2.3.4 Files et piles358
3. Les arbres359
3.1 Principe359
3.2 Définitions361
3.2.1 Base361
3.2.2 Terminologie361
3.2.3 Description horizontale362
3.2.4 Description verticale362
3.2.5 L'arbre binaire362
3.3 Parcours d'un arbre363
3.4 Arbre binaire ordonné366
3.4.1 Principe366
3.4.2 Recherche d'un élément366
3.4.3 Ajout d'un élément368
3.4.4 Suppression d'un noeud369
4. Exercices370
Chapitre 9
Une approche de l'objet
1. Principe de l'objet, une notion évidente371
1.1 Avant de continuer371
1.2 Rappels sur la programmation procédurale372
1.2.1 Les données372
1.2.2 Les traitements373
1.3 L'objet373
1.3.1 Dans la vie courante373
1.3.2 En informatique375
1.4 Classe, objets378
1.5 Déclaration et accès380
1.6 Les méthodes382
1.7 Portée des membres384
1.8 Encapsulation des données385
1.9 L'héritage387
1.9.1 Principe387
1.9.2 Commerce389
1.9.3 Hiérarchie390
1.9.4 Simple ou multiple391
1.10 Le polymorphisme392
1.10.1 Principe392
1.10.2 Le polymorphisme ad hoc392
1.10.3 Le polymorphisme d'héritage393
1.10.4 Le polymorphisme paramétrique395
2. Manipuler les objets396
2.1 Les constructeurs396
2.1.1 Déclaration396
2.1.2 Appel implicite397
2.1.3 L'héritage399
2.2 Les destructeurs401
2.3 Les membres statiques ou attributs402
2.4 Classes et méthodes abstraites404
2.5 Interfaces407
3. L'objet en C#409
3.1 Les langages objet409
3.2 Déclaration des classes et objets410
3.3 Héritage413
3.4 Interfaces416
4. Exercices418
Annexe
Corrigés des exercices
1. Introduction à l'algorithmique421
2. Les variables et opérateurs425
3. Tests et logique booléenne432
4. Les boucles440
5. Les tableaux et structures458
6. Les sous-programmes467
7. Les fichiers473
8. Notions avancées480
9. Une approche de l'objet484
Index493