Algorithmique et programmation en Pascal (exercices et corrigés).
Cours de l'École polytechnique.
Ellipses, Paris, France, 1992. 271 p.
ISBN : 2-7298-9208-7
Illustration de couverture: Gustav KLIMT,
Portrait de Fritza Riedler, 1906, Détail du fauteuil.
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.
Les exercices du cours sont regroupés avec leurs corrigés pour constituer ce deuxième
volume. Les exercices sont marqués d'une (*), deux (**) ou trois (***) étoiles selon leur degré de difficulté.
Polycopiés de travaux dirigés
Exemples de figures
 |
 |
| liste circulaire |
foule |
 |
 |
| surface (avec parties cachées) |
surface (sans parties cachées) |
 |
 |
| gravure de Escher |
structure récursive de la gravure de Escher |
Table des matières
Leçon 1 Exercice/Corrigé
1.1 Nombre de chiffres dans un suite de
caractères 9 17
1.2 Date du
lendemain 9 17
1.3 Calcul de 1/x 9 18
1.4 Calcul d'une valeur approchée de n!
1.5 Calculde Arc tg
x 10 19
1.6 Calcul de Arc sin
x 10 19
1.7 Débordements
arithmétiques 10 20
1.8 lecture d'un nombre sous forme d'une chaîne de
caractères et conversion
en entiers
(*) 11 20
1.9 Calcul de m^n en utilisant la représentation
binaire des entiers (*) 11 22
1.10 Comparaison de deux politiques de gestion de bus par
simulation (**) 12 23
1.11 jeu vidéo
(***) 14 26
Leçon 2 Exercice/Corrigé
2.1 Minimum et maximum d'un
tableau 31 37
2.2 Tri par insertion
incorrect 31 38
2.3 Plus long plateau d'un
tableau 32 39
2.4 Heapsort 32 40
2.5 Drapeau
hollandais 32 41
2.6 Transposée d'une matrice
compacte 32 43
2.7 Justification d'une ligne de texte
(*) 33 44
2.8 Files d'attente avec priorité
(*) 33 45
2.9 Programme en langage machine
(**) 34 49
2.10 Enveloppe convexe d'un ensemble de points dans le
plan (***) 35 49
2.11 Représentation d'une surface en perspective
(***) 36 53
Leçon 3 Exercice/Corrigé
3.1 Structure de bloc 61 73
3.2 Passage de paramètres par valeur et par
variable 61 73
3.3 Alias 62 74
3.4 Terminaison de la fonction
d'Ackermann 62 74
3.5 Fonction 91 de
McCarthy 62 74
3.6 Dessin récursif de carrés
emboîtés 62 75
3.7 Flocon de Von
Koch 63 75
3.8 Dessin récursif d'un arbre binaire
plein 63 76
3.9 Courbes de Hilbert
(*) 64 77
3.10 Représentation d'une surface par niveaux de gris
(*) 64 79
3.11 Dragon 65 81
3.12 Ordre de grandeur du coût minimal d'un produit de
matrices (*) 66 83
3.13 Quicksort
(*) 67 84
3.14 Sous-ensembles d'un ensemble
(**) 67 86
3.15 Analyse syntaxique de listes
parenthésées (**) 67 87
3.16 Procédures locales passées en
paramètres de procédures récursives
(**) 68 88
2.17 Analyse syntaxique d'expressions arithmétiques
(**) 68 88
3.18 Traduction d'une expression infixée en
postfixé 69 91
3.19 Calcul de point fixe
(**) 69 92
3.20 Interpréteur et compilateur d'un langage
graphique (***) 70 93
Leçon 4 Exercice/Corrigé
4.1 Date du
lendemain 101 115
4.2 Triangle
rectangle 101 116
4.3 Types d'objets
graphiques 101 117
4.4 Inversion d'une liste
linéaire 101 117
4.5 Longueur d'une liste
circulaire 101 118
4.6 Inversion d'une liste
circulaire 103 119
4.7 Insertion dans une liste
circulaire doublement chaînée avec tête de liste
(*) 103 120
4.9 Réseau de
neurones 104 122
4.9 Tracé d'un segment de droite
(*) 105 124
4.10 Tracé de la partie visible d'un segment de droite
dans un fenêtre (**) 105 126
4.11 Graphiqme à la Escher
(***) 106 128
Leçon 5 Exercice/Corrigé
5.1 Inversion constructive d'une liste
linéaire 137 161
5.2 Insertion dans une liste circulaire doublement
chaînée avec tête de
liste 13! 162
5.3 Égalité d'arbres
binaires 140 162
5.4 Évaluation d'une expression
arithmétique (*) 140 164
5.5 Représentation d'un arbre 2-3 par un arbre
binaire (*) 141 167
5.6 Arithmétique des grands
naturels (**) 142 171
5.7 Tri des mécanographes
(**) 142 174
5.8 Dérivation formelle
(**) 146 178
5.9 Gestion interactive d'un dictionnaire
(***) 146 183
5.10 Interpréteur du langage Lxp
(***) 151 185
Leçon 6 Exercice/Corrigé
6.1 Minimum et maximum d'un fichier de
réels 199 209
6.2 Fusion de fichiers séquentiels
ordonnés 200 211
6.3 Recherche d'un élément commun à
trois fichiers triés 200 212
6.4 Carré
magique 201 214
6.5 Compression d'un fichier de
texte 201 214
6.6 Tri d'un fichier par interclassement de monotonies
(*) 201 219
6.7 Coût de l'algorithme de tri d'un fichier par
interclassemant de monotonies
de mêmes
longueurs 202 219
6.8 Représentation d'un arbre binaire dans un
fichier (*) 202 220
6.9 Arbre 2-3 sur disquette
(**) 203 22
6.10 Mise à jour d'un fichier de stock en temps
différé (**) 203 227
6.11 Gestion d'un fichier de stock en temps réel
(**) 207 228
6.12 Simulation d'une mini-machine
(***) 207 245
Leçon 7 Exercice/Corrigé
7.1 Crible
d'Erathosthène 257 259
7.2 Cheminement dans un labyrinthe avec in fil
d'Ariane (*) 257 260
7.3 Composantes connexes d'un graphe
(**) 258 264
Retour à / back to:Index,
Institutions,
Enseignement
/ Teaching, Recherche
/ Research, Services
Email: cousot@di.ens.fr,
cousotp@acm.org
Dernière mise à jour / Last modified :Friday, 10-Feb-2006 12:22:00 CET