L'éditeur du cours est emacs, la méthode de compilation
recommandée est la compilation sous emacs. Son avantage est
le positionnement automatique sur les erreurs détectées lors de la
compilation.
Voici ce qu'il faut faire pour configurer Emacs pour travailler avec OCaml
(si vous ne l'avez pas déjà fait).
Dans un terminal :
mkdir ~/.elisp
cp -r /users/profs/info/filliatre/.elisp/tuareg-mode/ ~/.elisp/
cat /users/profs/info/filliatre/.emacs >> ~/.emacs
Ensuite, créer un répertoire pour les travaux dirigés d'aujourd'hui,
par exemple
mkdir inf549
cd inf549
Cet algorithme de calcul du PGCD de deux entiers naturels est bien
connu.
Il repose sur les deux identités :
| pgcd(u, v) |
= |
v |
si v divise u |
| pgcd(u, v) |
= |
pgcd(v, u mod v) |
sinon |
Écrire une fonction pgcd de type int -> int -> int qui
calcule le pgcd selon la méthode d'Euclide.
Pour cela, ouvrir un fichier pgcd.ml avec Emacs :
emacs pgcd.ml
On pourra partir du modèle suivant, à
copier-coller dans Emacs.
Pour compiler, utiliser la touche F5.
Emacs propose par défaut la commande de compilation make -k.
L'effacer et la remplacer par la commande ocamlc -o pgcd
pgcd.ml (si votre fichier s'appelle pgcd.ml).
Pour recompiler ultérieurement, utiliser la
touche F6. En cas d'erreur à la
compilation, utiliser la touche F7 pour se positionner sur l'erreur.
Une fois le programme compilé avec succès, vous pouvez tester dans le terminal :
% ./pgcd 1111 1234
1
% ./pgcd 1234 1111
1
| 2 |
Une autre technique pour le PGCD |
|
Au collège, on ne connaît pas encore l'algorithme d'Euclide, et
on calcule le PGCD différemment :
en décomposant les nombres u et v en facteurs
premiers, puis en identifiant les facteurs communs.
On s'inspire ici de cette technique.
Supposons connue la suite des nombres premiers
p1=2,
p2=3,
p3=5,
etc.
L'idée est d'essayer de diviser u par les nombres premiers pris dans
l'ordre :
| décompose(i, 1) |
= |
[] |
|
| décompose(i, u) |
= |
pi :: décompose(i, u/pi) |
|
si pi
divise u |
| décompose(i, u) |
= |
décompose(i+1, u) |
|
si pi ne divise
pas u |
En fait, l'algorithme fonctionne toujours si on remplace la suite des pi par
une suite croissante
(qi),
commençant à 2 et qui contient les nombres
premiers (les pi, donc).
En effet, par construction et à chaque étape, u n'est divisible par
aucun des qk avec k < j, et donc u n'est pas non plus divisible
par un nombre premier strictement inférieur à qj.
Donc, si qj est un diviseur de u, alors qj n'a pas de facteur
premier strictement plus petit
que qj,
c'est-à-dire qj est premier.
Si on veut optimiser un peu, on peut choisir la suite définie par
q1 = 2, q2 = 3, qj+1 = qj+2 (j ≥ 2)
afin d'éviter de tester les entiers pairs à partir de 4.
On peut aussi terminer plus rapidement.
Soit qj tel que v, résultat de la divison euclidienne de u par
qj, est strictement plus petit que qj, alors
u est premier.
En effet, d'une part, v < qj entraîne qj × qj > u
(u = qj × v + r avec r < qj et v < qj.
et donc u < qj × (v + 1) ≤ qj × qj), et
d'autre part, la définition de décompose entraîne que u n'est
divisible par aucun nombre pris dans [2…qj[.
Soit f tel que 2 ≤ f et f × f ≤ u, alors
on a nécessairement f < qj (sinon, f × f ≥ qj × qj
> u). Soit finalement f n'est pas un facteur de u.
Or, si u n'est pas premier, alors il existe deux
nombres f et g, avec 2 ≤ f ≤ g et u = f × g.
Et donc u possède un diviseur propre f, avec f × f ≤ u.
Bref, on peut ajouter la règle :
| décompose(i, u) |
= |
u |
|
si u/qj < qj |
| 2.1 |
Décomposer en facteurs premiers |
|
Écrire une fonction decompose de type
int -> int list qui prend un entier u en argument et renvoie
la liste de ses facteurs premiers.
Il est conseillé d'écrire une fonction auxiliaire préalable qui suit
la définition « théorique » décompose, mais prend
en argument qi et la valeur courante de u.
Dans un premier temps, on peut s'abstenir des optimisations signalées.
On pourra modifier le programme tous.ml qui affiche les
entiers de 2 à l'entier passé sur la ligne de commande.
Vous devriez obtenir par exemple :
% ./decompose 524287
524287
% ./decompose 1048575
3 5 5 11 31 41
% ./decompose 2097151
7 7 127 337
Il suffit maintenant d'identifier les facteurs communs à u et
v et de les multiplier entre eux pour retrouver le pgcd.
-
Écrire une fonction communs de type
int list -> int list -> int list qui prend en argument deux
listes d'entiers triées selon l'ordre croissant et qui renvoie
la liste des entiers communs aux deux listes.
Il convient de profiter de l'ordre des listes pour écrire une fonction
de coût linéaire en la somme des longueurs de ses arguments.
La bonne façon de décomposer les listes en Caml est
d'utiliser le filtrage, c'est-à-dire la construction match
with ou la construction function.
- Écrire une fonction produit de type
int list -> int qui renvoie le produit des éléments de la liste
passée en argument. Trouver une convention raisonnable pour le cas de
la liste vide.
- En déduire une fonction qui calcule le pgcd de deux entiers
selon la méthode apprise au collège.
Nous disposons maintenant de deux fonctions pour calculer le pgcd.
Écrire un programme qui prend deux arguments m et n
sur la ligne de commande.
Ce programme doit procéder à n essais, consistant en un tirage
pseudo-aléatoire de deux entiers u et v compris entre 1 et m
(voir Random.int), au calcul du pgcd selon les deux
méthodes et à leur comparaison.
En cas d'échec le programme doit afficher un message
explicatif.
La fonction Printf.printf permet de composer de beaux
messages.
Pour afficher un beau message donnant le contenu de la
variable i on procède ainsi :
Printf.printf "i=%d\n" i (* «\n» est le retour à la ligne *)
On aura ainsi par exemple :
% ./verification 10000000 10000
Vérification, 10000 essais, sur [1..10000000]
Que des succès
| 4 |
Le PPCM comme au collège |
|
Les décompositions en facteurs premiers de u et v permettent de
trouver la décomposition du ppcm (Plus Petit Commun Multiple) de u
et de v.
Modifier un peu votre programme pour qu'il trouve et affiche le PPCM.
Ce document a été traduit de LATEX par
HEVEA et HACHA.