Algorithmique et programmation en Pascal (cours).
Cours de l'École polytechnique.
Ellipses, Paris, France, 1992. 288 p.
ISBN 2-7298-9208-8
Illustration de couverture: Gustav KLIMT,
La Vie et la mort, 1908-1911, Détail de la robe.
Introduction
Nous avons enseigné ce cours en tronc commun à
l'École Polytechnique de 1985 à 1992. Il s'adresse à
des élèves ayant quelques connaissances rudimentaires de
programmation en Pascal et d'algorithmique numérique acquises en
classes préparatoire (voir l'ouvrage cité en référence
[1]
de la leçon 1).
L'objectif du cours est d'apprendre aux élèves
comment spécifier, concevoir, coder, mettre au point et documenter
des programmes performants, en utilisant un langage de haut niveau (pascal)
mis en úuvre sur des systèmes informatiques personnels (Macintohs
512K puis SE) et multi-utilisateurs (DEX VAX 8600 puis 9021-VP).
En même temps que ces concepts de programmation,
nous présentons les principales méthodes de conception d'algorithmes
qui sont illustrées par les algorithmes numériques, non numériques
(rechercher, interclassements, tris) et graphiques de base, ainsi que les
méthodes de spécification et représentation de structures
d'information (piles, files, listes, tables, arbres, graphes). Les notions
de spécification modulaire, preuve et analyse de complexité
abstraite et concrète sont abordées à propos d'exemples.
Le cours commence par une phase optionnelle de familiarisation
à l'usage de l'ordinateur (édition de texte et exécution
d'un programme sur le Macintosh, utilisation du Macintosh comme terminal
sous Unix, commandes élémentaires d'Unix, courrier électronique,
etc.). Pour ce faire, les élèves disposent d'un polycopié
de travaux dirigés qui n'a pas été inclus dans cet
ouvrage car il dépend de l'installation disponible.
Le cours proprement dit comporte une quarantaine d'heures
d'enseignement réparties en sept séances comportant un amphi
de présentation de la leçon suivi d'une petite classe consacrée
à des exercices qui doivent ensuite être programmés
sur ordinateur pendant les travaux dirigés.
À la suite du cours, les élèves doivent
faire un projet personnel assez conséquent qui permet d'aborder
la programmation en vraie grandeur.
Ce cours écrit est donc principalement un document de référence,
l'explication plus synthétique des enseignants étant en général
préalable à sa lecture.
Polycopiés de travaux dirigés
Exemples de figures
 |
 |
| diagramme syntaxique |
pile |
 |
 |
| liste |
table |
 |
 |
| arbre |
graphe |
Table des matières
Introduction 2
Leçon 1 9
1. Introduction 9
2. Description syntaxique et sémantique d'un langage de programmationv10
2.1 Spécification de la syntaxe de PASCAL 10
2.2 Spécification de la sémantique de PASCAL 12
3. Programmation en PASCAL 13
3.1 Structure générale des programmes PASCAL 13
3.2 Symboles et séparateurs 14
3.3 Identificateurs 14
3.4 Types et constantes de base 15
3.5 Constantes 22
3.6 Déclarations 23
3.7 Expressions 32
3.8 Instructions 37
Leçon 2 53
1. Introduction 53
2. Tableaux 53
2.1 Exemple introductif: tri par sélection 53
2.2 Type tableau 53
2.3 Variables tableaux 55
2.4 Types compatibles 55
2.5 Variables indicées 56
2.6 Tableaux à plusieurs dimensions et tableaux de tableaux (*) 57
2.7 Représentation d'un tableau en mémoire (**) 58
2.8 Exemple d'algorithme utilisant des tableaux: carré magique 59
3. Ensembles (**) 59
3.1 Type ensemble (**) 59
3.2 Représentation d'ensembles en mémoire (**) 61
3.3 Notation d'ensembles (**) 61
3.4 Expressions de type ensemble et opérations sur les ensembles (**) 61
3.5 Affectation à une variable de type ensemble (**) 62
3.6 Exemple: crible d'Eratosthène (**) 63
4. Types compacts (**) 65
5. Type des chaînes de caractères (*) 66
5.1 Chaînes de caractères de longueur fixe en PASCAL standard (*) 66
5.2 Chaînes de caractère en PASCAL VAX 8600 (*) 67
5.3 Chaînes de caractères de longueur variable en PASCAL Macintosh (**) 67
5.4 Transport d'un programme utilisant des chaînes de caractères entre le
Macintosh
et le VAX 8600 68
ALGORITHMIQUE ET STRUCTURES D'INFORMATION
6. Recherche en table 69
6.1 Définition de la notion de table et critères de comparaison des représentations
de tables en machine 70
6.2 Recherche directe 70
6.3 Recherche séquentielle 74
6.4 Recherche dichotomique 76
6.5 Recherche par hachage 78
7. Algorithmes de tri (en mémoire centrale) 82
7.1 Tri par remontée des bulles 83
7.2 Ordre de grandeur du temps optimum de tri 83
7.3 Heapsort 84
ARCHITECTURE DES ORDINATEURS
8. Principe simplifié de fonctionnement d'un ordinateur (**) 89
8.1 Architecture de la machine (**) 89
8.2 Unité de traitement (unité centrale) (**) 90
8.3 Mémoires centrales (**) 90
8.4 Bus de communication (**) 90
8.5 Séquencement de la machine (**) 90
8.6 Langage machine (**) 91
8.7 Exemples de programmes en langage machine (**) 93
Leçon 3 97
1. Introduction 97
2. Procédures sans paramètres 97
2.1 Déclaration de procédure 98
2.2 Appel de procédure 98
3. Procédures avec paramètres par valeur ou par variable 101
3.1 Paramètres formels 101
3.2 Paramètres effectifs 103
3.3 Passage de paramètres par valeur 104
3.4 Affinement de la notion de variable 105
3.5 Passage de paramètres par variable 106
3.6 Passage d'un élément de tableau en paramètre par variable (*) 108
4. Fonctions (*) 109
4.1 Déclaration de fonction (*) 109
4.2 Appel de fonction (*) 110
5. Visibilité des identificateurs: structure de bloc 111
5.1 Occurrences de définition et d'utilisation d'un identificateur 111
5.2 Identificateurs locaux et globaux 112
5.3 Visibilité et portée des identificateurs 114
5.4 Quelques avantages et inconvénients de la structure de bloc (**) 115
6. Effets de bord (*) 120
6.1 Effets de bord des procédures (*) 120
6.2 Effets de bord des fonctions (*) 120
7. Alias 121
8. Paramètres procéduraux et fonctionnels (**) 125
8.1 Passage de procédures en paramètres (**) 126
8.2 Passage de fonctions en paramètres (**) 126
8.3 Contexte d'exécution d'un sous-programme passé en paramètre (**) 126
9. Récursivité 127
9.1 Récursivité simple 127
9.2 Règle de recopie 130
9.3 Preuve de terminaison d'un sous-programme récursif (*) 131
9.4 Coût de la récursivité: exemple du calcul du nombre de combinaisons (*) 131
9.5 Elimination de la récursivité: exemple de la fonction d'Ackermann (**) 133
9.6 Récursivité croisée 136
9.7 Passage de sous-programmes en paramètres de sous-programmes
récursifs (**) 138
10. Compilation séparée en PASCAL sous UNIX (**) 140
10.1 Décomposition d'un programme en modules (**) 140
10.2 Compilations indépendantes et séparées (**) 140
10.3 Compilation séparée en PASCAL sous UNIX (**) 143
10.4 Automatisation des compilations après modification d'un module (**) 54
Leçon 4 150
1. Introduction 150
2. Enregistrements 150
2.1 Type enregistrement 150
2.2 Variables de type enregistrement 152
2.3 Champs de variables enregistrements 152
2.4 Enregistrements avec variantes (*) 154
2.5 Instruction "with" (**) 161
3. Structures d'informations élémentaires 162
3.1 Piles 163
3.2 Files 164
3.3 Tableaux flexibles 166
3.4 Listes linéaires 168
3.5 Tables 174
3.6 Arbres binaires 176
3.7 Graphes (*) 183
Leçon 5 192
1 Introduction 192
2. Pointeurs sur des enregistrements alloués dynamiquement 192
2.1 Exemple introductif 192
2.2 Rappels sur les variables statiques 196
2.3 Variables dynamiques et pointeurs 196
2.4 Déclaration du type des variables dynamiques et pointeurs 197
2.5 Création d'une variable dynamique repérée par un pointeur 197
2.6 Création d'une variable dynamique avec variantes (**) 197
2.7 Autres opérations sur les variables dynamiques 198
2.8 Opérations sur les pointeurs 198
2.9 Exemple: inversion destructive d'une liste linéaire 198
2.10 Ramassage de miettes (**) 201
3. Structures d'information 203
3.1 Arbres binaires 203
3.2 Représentation d'une table par arbre binaire ordonné aléatoire 205
3.3 Représentation d'une table par un arbre 2-3 ordonné 213
3.4 Comparaison des performances des représentations d'une table par une liste
linéaire, par un arbre 2-3 et par hachage (*) 231
3.5 Représentation d'une table par un arbre †n/2†-n ordonné (**) 239
Leçon 6 241
1. Introduction 241
2. Notion générale de fichier en PASCAL (et ses extensions) 242
2.1 Fichier à accès direct 242
2.2 Fichier séquentiel 243
3. Fichiers à accès direct 244
3.1 Disques magnétiques 244
3.2 Organisation des fichiers sur un disque (**) 245
3.3 Opérations sur les fichiers à accès direct en PASCAL (non standard) 247
3.4 Fichiers à accès direct sous Unix (**) 253
4. Fichiers séquentiels (*) 259
4.1 Bandes magnétiques (*) 259
4.2 Analogie entre les bandes magnétiques et les fichiers séquentiels en
PASCAL (*) 260
4.3 Fichiers séquentiels en PASCAL standard (*) 263
4.4 Fichiers de texte séquentiels (**) 265
5. Différences entre le PASCAL du Macintosh et le PASCAL standard
concernant les fichiers (***) 268
5.1 Liaison entre les variables de type fichier internes au programme et
les fichiers externes (***) 268
5.2 Entrées-sorties par nécessité (***) 269
6. Diagrammes de syntaxe 272
RÉFÉRENCES ET BIBLIOGRAPHIE 282
INDEX 284
(*) Les paragraphes marqués de (*) peuvent être lus en deuxième lecture.
(**) Les paragraphes marqués de (**) ou les textes écrits en petits caractères peuvent être réservés pour une lecture plus approfondie.
(***) Les paragraphes marqués de (***) sont à lire si le besoin s'en fait sentir pour les projets de programmation.
Retour à / back to:Index,
Institutions,
Enseignement
/ Teaching, Recherche
/ Research, Services
Email: cousot@di.ens.fr,
cousotp@acm.org
Dernière mise à jour / Last modified :Wednesday, 04-Jun-2003 12:29:52 CEST