Patrick Cousot.

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

Cours

Exemples de figures

 
liste circulaire foule
liste circulaire foule
surface 1 surface 2
surface (avec parties cachées) surface (sans parties cachées)
Escher structure gravure de Escher
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