Cours d'informatique Caml
Table des matières
Avant de commencer 7
Introduction à l’option informatique 9
1. Objectifs de formation 9
2. Choisir concrètement l’option informatique 9
3. Bref aper¸cu du programme de SUP 10
4. FAQ 10
partie A. Programmation en Caml 11
Chapitre I. Introduction 13
1. Le langage Caml 13
2. Quelques conseils 15
Chapitre II. Programmation en Caml 17
1. Brève présentation de Caml light 17
2. Notion d’effet de bord 17
3. Identificateurs 18
4. Types élémentaires 20
5. Deux exemples de types non élémentaires 22
6. Programmation fonctionnelle 22
7. Introduction à la récursivité 27
8. Programmation impérative 27
9. Types prédéfinis en Caml 30
10. Bref retour sur le filtrage 34
11. Types définis par l’utilisateur 36
partie B. Méthodes de programmation 39
Chapitre III. Programmation impérative 41
1. Correction et terminaison 41
2. Notion d’invariant de boucle 41
Chapitre IV. Récursivité 45
1. Introduction 45
2. Compléments sur les relations d’ordre 45
3. Terminaison et correction des fonctions récursives 48
4. Récursivité croisée 52
5. Gestion d’une fonction récursive 52
6. Ensembles inductifs, induction structurelle 59
partie C. Analyse des algorithmes 61
Chapitre V. Complexité 63
1. Généralités 63
2. Un premier exemple 64
3. Diviser pour régner 64
Chapitre VI. Tris 69
1. Introduction 69
2. Utilité du tri : recherche dans un tableau trié 69
3. Insertion dans une liste triée 70
3
CHAPITRE . TABLE DES MATIERES`
4. Fusion de deux listes triées 70
5. Exemples de tris 71
partie D. Structures de données et algorithmes 83
Chapitre VII. Structures de données 85
1. Notion de structure de données 85
2. Listes 85
3. Piles 90
partie E. Logique 99
Chapitre VIII. Calcul propositionnel 101
1. Préliminaires sur les arbres binaires 101
2. Syntaxe 101
3. Sémantique 106
Chapitre IX. Circuits logiques 113
1. Circuits combinatoires 113
2. Tableaux de Karnaugh 114
3. Additionneurs 115
partie F. Exercices 117
Feuille de TD 1. Premiers pas en Caml 119
Feuille de TD 2. Premiers pas en récursivité et itération 121
Feuille de TD 3. Itération 123
Feuille de TD 4. Terminaison et correction des fonctions récursives 125
Feuille de TD 5. Récursivité terminale 127
Feuille de TD 6. Induction structurelle 129
Feuille de TD 7. Complexité 131
Feuille de TD 8. Diviser pour régner 133
Feuille de TD 9. Tris 135
Feuille de TD 10. Listes 137
Feuille de TD 11. Piles 139
Feuille de TD 12. Logique (syntaxe) 141
Feuille de TD 13. Logique (sémantique) 143
Feuille de TD 14. Logique (circuits) 145
partie G. Solution des exercices 147
Feuille de TD 1. Solution de premiers pas en Caml 149
Feuille de TD 2. Solution de premiers pas en récursivité et itération 151
Feuille de TD 3. Solution d’itération 155
Feuille de TD 4. Solution de terminaison et correction des fonctions récursives 159
Feuille de TD 5. Solution de récursivité terminale 161
Feuille de TD 6. Induction structurelle 163
Feuille de TD 7. Solution de complexité 165
4 Stephane FLON´
CHAPITRE . TABLE DES MATIERES`
Feuille de TD 8. Solution de diviser pour régner 167
Feuille de TD 9. Solution de tris 169
Feuille de TD 10. Solution de listes 171
Feuille de TD 11. Solution de piles 175
Feuille de TD 12. Solution de logique (syntaxe) 177 Feuille de TD 13. Solution de logique (sémantique) 179
Feuille de TD 14. Solution de logique (circuits) 181
5 Stephane FLON´
Avant de commencer
Introduction à l’option informatique
1. Objectifs de formation
L’informatique, telle qu’enseignée en option en MPSI, est envisagée comme une science, et non comme un amas de techniques ou de compétences : comme le dit le programme officiel, l’informatique est une science opérant sur des représentations rigoureuses de concepts bien définis .
Cela signifie notamment que l’enseignement de cette option ne consistera pas seulement à vous faire programmer : une grande part du travail s’effectuera loin de tout ordinateur. Bien entendu, et heureusement, l’enseignement ne sera pas purement théorique, et vous pourrez souvent confronter votre apprentissage à un principe de réalité, en l’implémentant en salle info.
Pour cela, nous utiliserons le langage Caml (light), tout à fait approprié à l’esprit de l’option info (beaucoup plus que Maple par exemple ).
Nous aurons souvent recours aux mathématiques, afin de poser les bases d’une programmation rigoureuse. Elles nous permettront notamment :
(1) de prouver un programme (comme on prouve un théorème mathématique).
(2) d’évaluer l’efficacité d’un programme, en particulier le temps qu’il met à s’exécuter (étude de la complexité d’un programme).
(3) de confronter des parti-pris de programmation, de choisir, parmi eux, le plus adapté à la situation rencontrée (récursif vs impératif, étude des structures de données).
Il s’agira donc, grâce à cette démarche rigoureuse, de réfléchir –en décortiquant ce que l’on veut faire, ce dont on dispose, et comment on va s’y prendre–, avant de se lancer dans la programmation proprement dite.
Dans le cadre de cette option, ce sont les mathématiques qui sont au service de l’informatique, et non l’inverse.
L’idée est, entre autres, d’éviter la technique de programmation suivante, si souvent rencontrée : écrire un programme au hasard qui, avec un peu de chance, va donner le bon résultat, puis on se rend compte qu’en fait non, puis on passe des heures à tenter de le corriger .
En cela, cette option est très utile à qui veut bien programmer plus tard, même si elle va sans doute trop loin pour un ingénieur dont la programmation serait une activité secondaire. Cependant, cette discipline, par la rigueur et la logique qu’elle requiert, reste toujours bénéfique, au même titre que les mathématiques : en tant qu’ingénieur, vous ne vérifierez pas la continuité d’une fonction avant d’appliquer le théorème des valeurs intermédiaires, mais votre formation vous permettra de prendre conscience d’un cas retors, voire de le résoudre (cf. le phénomène de Gibbs).
2. Choisir concretement l’option informatique`
2.1. Consequences sur l’orientation´
En choisissant l’option informatique, vous fermez la voie de la PSI : vous ne pourrez aller qu’en MP (ou MP*). Bien entendu, cela ne vous limitera pas plus tard à une carrière dans l’informatique, toutes les écoles restent accessibles avec cette option, et, au sein de ces écoles, toutes les voies sont possibles.
L’option informatique permet de passer tous les concours MP, indifféremment de l’option SI, à l’exception notable de Polytechnique, ou` les listes d’admis sont séparées selon l’option.
2.2. Organisation du travail
Vous aurez informatique le vendredi matin de 8h à 10h : une heure de cours, puis une heure de TD. L’heure de TD se fera parfois devant l’ordinateur mais pas systématiquement, loin de là.
Certaines de ces séances seront consacrées aux devoirs surveillés (deux par trimestre).
Vous aurez également quelques colles Caml au long de l’année (horaires à définir).
3. Bref aperc¸u du programme de SUP
– Initiation à Caml
On présente le langage Caml, ses qualités, sa philosophie, sa syntaxe.
– Méthodes de programmation
Programmation impérative (boucles for, while, conditionnelle if, etc.). Comment prouver un programme impératif.
Programmation récursive : une nouvelle philosophie de programmation (la fonction s’appelle ellemême dans sa définition). Compléments mathématiques (sur les relations d’ordre), ensembles inductifs. Comment prouver un programmer récursif.
– Analyse des algorithmes
Complexités spatiale et temporelle (performance théorique des algorithmes con¸cus).
Méthode diviser pour régner.
Algorithmes classiques de tri (comment ranger des valeurs selon un ordre donné).
– Structures de données et algorithmes
Notion de structure de données. Listes, piles. Comment choisir la structure de données adaptée à un problème, quelles conséquences cela a-t-il sur la programmation?
– Logique
Calcul propositionnel. Distinction entre syntaxe et sémantique. Circuits logiques.
– Et en Spé?
Bien suˆr, vous reprendrez en partie ce qui a été fait en Sup, mais vous étudierez également de nouveaux sujets, parfois très abstraits, comme les automates finis.
4. FAQ
4.1. Quelles sont les bonnes raisons de suivre l’option informatique?
On peut suivre l’option informatique
– par gouˆt de l’informatique, par exemple parce qu’on
– veut devenir informaticien, ou intégrer une école d’informatique (désolé pour l’évidence )
– l’a déjà pratiqué (C/C++, php, etc.)
– a apprécié la partie programmation de Maple.
– n’a pas apprécié la partie programmation de Maple, parce qu’on l’a trouvée trop peu rigoureuse. – voudrait commencer la programmation sur de bonnes bases.
– par gouˆt des (et facilités en) mathématiques, surtout algébriques : relations d’ordre, structures algébriques, récurrence, dénombrement.
– par gouˆt de l’abstraction, de la rigueur.
4.2. Quelles sont les bonnes raisons de ne pas suivre l’option informatique?
On a bien raison de ne pas suivre l’option informatique si :
– on surkiffe la SI.
– on veut aller en PSI (ou s’en garder la possibilité).
– veut intégrer une école spécialisée dans un domaine précis, relevant de la SI (cela dit, SI comme informatique sont certainements utiles, au moins comme bagage culturel, à tout ingénieur qui se respecte).
– on a toutes les difficultés du monde à programmer une boucle for en Maple, ou si on est exaspéré car Maple nous en veut de ne pas avoir mis ; .
Pour les écoles généralistes, les deux options se valent.
4.3. Quelles sont les mauvaises raisons de suivre, ou de ne pas suivre, l’option informatique
Il ne faut pas se déterminer à cause :
– des horaires.
– de la stratégie : choisissez votre option selon vos gouˆts, et non parce qu’untel est une méga-torche et prend telle option
– de l’élitisme : l’option info est ouverte à tous ceux qui sont motivés, même s’ils ne sont pas géniaux en maths (mais ils s’engagent en connaissance de cause).
Programmation en Caml
CHAPITRE I Introduction
1. Le langage Caml
Bien que l’enseignement de l’option informatique ne se résume pas à la programmation, il nous faut disposer d’un langage dans lequel travailler, afin de mettre en pratique la théorie et de se confronter à un certain principe de réalité. Cette année, nous utiliserons le langage Caml, et plus précisément Caml light, que vous pourrez trouver facilement (et gratuitement) sur le net.
Sans rentrer dans une analyse poussée de ce langage, on peut lui reconnaˆ?tre de nombreuses qualités pédagogiques, que nous passons brièvement en revue, et sur lesquelles nous reviendrons plus en détail au chapitre suivant :
1.1. Rigueur
En Caml, tous les objets (y compris les fonctions) ont un type, c’est-à-dire que chacun appartient à une catégorie bien précise. On dit que ce langage est fortement typé.
Par exemple, comme en mathématiques, toute fonction a une source (un ensemble de départ) et un but (un ensemble d’arrivée) déterminés.
Après chaque définition, Caml répond sous la forme
nom : |
type = valeur |
Après chaque expression, Caml répond sous la forme
? |
: |
type = valeur |
(la réponse étant parfois précédée d’effets de bord, voir plus loin). Dans l’exemple
# 2 + 2;;
? : int = 4
Caml nous informe que le résultat 4 de l’expression 2 + 2 est de type entier (int).
Ces contraintes de type confèrent à Caml une certaine rigidité : Caml n’aime pas mélanger les choux et les carottes . Par exemple, Caml n’accepte pas que nous additionnions un entier (type int) avec un nombre à virgule flottante (type float) :
# 2 + 2 .4 ;;
Toplevel input :
>2 + 2 .4 ;;
> ˆˆˆ
This expression has type float , but is used with type int .
Cette rigidité doit toutefois être mise au crédit de Caml, car elle permet d’éviter ou détecter de nombreuses erreurs de programmation.
1.2. Simplicite´
Les bases de ce langage – dont nous nous contenterons – sont assez réduites, et la plupart des programmes que nous écrirons ne prendront que quelques lignes. Pourtant, nous pourrons répondre à de nombreux problèmes relativement compliqués.
1. LE LANGAGE CAML CHAPITRE I. INTRODUCTION
Nous avons vu que chaque objet avait un type : faut-il pour autant déclarer le type de chaque objet en Caml? Non, car le typage est automatique : Caml devine, autant que possible, de quel type d’objet vous parlez.
# let f x = x + 2;; f : int ?> int = <fun>
J’ai ici défini la fonction f, dont Caml a automatiquement déterminé le type, à savoir une fonction qui à un entier associe un entier : il a deviné que l’argument x de f était entier, puisque je lui ai ajouté 2, et sait que le résultat obtenu est de type entier.
1.3. Fonctionnel
Nous venons de voir un exemple de fonction en Caml. En fait, un programme Caml n’est pour ainsi dire qu’une succession de fonctions, que nous nous contentons d’appliquer en fin de programme. Dans un programme Caml, il s’agit bien plus de décrire les fonctions que nous souhaitons employer (programmation fonctionnelle) que de donner des instructions de gestion des données ou de la mémoire de l’ordinateur (programmation impérative). Il impose donc une vision assez mathématique de la programmation.
Il faut bien comprendre que les fonctions en Caml sont des objets comme les autres, ce qui fait qu’on peut les prendre en argument, comme en mathématiques : ainsi,
est la fonction qui, à une fonction f de type int ?> int, associe la fonction de même type, qui à x (entier) associe f(x + 2) + 2. C’est donc, avec les notations usuelles, un élément de (NN)(NN).
1.4. Polyvalent
Caml n’est pas un langage purement fonctionnel, dans le sens ou` il a également des traits impératifs, comme les boucles for et while par exemple, que vous connaissez sans doute déjà :
12345678910? :
... ...
2. Quelques conseils
Donnons ici quelques recommandations de bon sens, afin de faciliter la programmation, et la compréhension de vos programmes par quelqu’un d’autre (moi, par exemple).
2.1. Refl´ echir avant de programmer´
Il est recommandé, avant de se lancer dans l’écriture d’un programme, de bien réfléchir à la structure que l’on veut lui donner, éventuellement par écrit, au brouillon. Plutôt que d’écrire un premier jet incorrect, puis de lui appliquer des rustines jusqu’à ce qu’il fonctionne (ou semble fonctionner), au risque de le rendre incompréhensible, essayez de savoir ou` vous allez.
Pour bien structurer votre programme, répondant à un problème précis, vous pouvez essayer de décomposer ce dernier en sous-problèmes, se décomposant éventuellement à leur tour en (sous-)sous-problèmes, jusqu’à tomber sur des briques élémentaires faciles à programmer et à assembler : il s’agit donc de programmer par raffinements successifs, ou encore par analyse descendante.
Un autre avantage d’avoir écrit des sous-programmes élémentaires consiste en leur possible réutilisation et partage.
2.2. Pratiquer
Un langage de programmation s’apprend en le pratiquant : il ne faut pas vous contenter de comprendre les programmes trouvés ici ou là, il vous faudra tester votre bonne assimilation en programmant, en les testant, en devinant ce qu’un programme va produire, etc.
Comme en mathématiques, il faudra travailler activement en TD, et non se contenter de lire un corrigé.
2.3. Rendre votre programme lisible
N’oubliez pas que le programme sera sans doute lu par quelqu’un d’autre, et que sa compréhension n’est pas forcément immédiate : il vous faut donc faire des efforts de lisibilité. D’ailleurs, même si votre programme est à usage personnel, il vaut mieux le clarifier, car vous pouvez avoir du mal à le comprendre une fois que vous l’avez laissé de côté pendant quelques temps.
N’hésitez pas à insérer des commentaires dans vos programmes (utiliser (? ?) en Caml), expliquant votre démarche, pourquoi votre algorithme fonctionne, les notations, etc.
On simplifie grandement la compréhension d’un programme en donnant des noms parlants aux objets introduits : de même qu’en mathématiques, il est possible mais malvenu de noter un certain nombre complexe x et z sa partie réelle (ou un entier naturel ?), il vaut mieux éviter en informatique de noter addition ou même k la loi de multiplication des entiers.
Pensez également à aérer et hiérarchiser le texte, notamment en utilisant les indentations.
Vous pouvez aussi rendre votre programmation plus abstraite, ce qui rend parfois le texte plus lisible. Attention cependant, dans certains cas, l’abstraction ne simplifie pas vraiment la compréhension.
Stephane FLON´
2. QUELQUES CONSEILS CHAPITRE I. INTRODUCTION
2.4. Laisser l’ordinateur travailler
La récursivité et l’aspect fonctionnel de Caml permettent d’écrire des programmes qui ne semblent être que des reformulations du problème posé. Ces programmes sont le plus souvent clairs, efficaces, élégants, et simples à écrire. Il est parfois possible, au prix d’un effort mathématique, d’enlaidir et compliquer lesdits programmes, mais on n’a pas grand chose à y gagner. Les intoxiqués de la programmation impérative doivent apprendre à laisser l’ordinateur faire le job!