« INFO401 corr TD TP » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
mAucun résumé des modifications
 
(39 versions intermédiaires par 9 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | le TD1 et TP0]].


Vous pouvez aller discuter des corrections dans les sujets de discussions associes...


==Le TD1 et le TP0==

Pour vous montrer un exemple de ce que j'attends, voila la correction de la fonction factorielle. (C'était facile...) J'ai volontairement mis beaucoup de commentaires...


<u>La fonction factorielle (TD1, exercice 2, question 2)</u>

Le but est de calculer la fonction <math>!n = 1\times2\times \cdots \times n</math> par récurrence. La version typée est verbeuse de la fonction correspondante en Caml donne :

<source lang="ocaml">
(* fonction factorielle : c'est la factorielle habituelle des mathématiciens... *)
let rec fact (n:int) : int =
if (n>1)
then n * (fact (n-1))
else 1 (* rq : pour que le programme ne boucle pas sur les valeurs négatives, on renvoie 1 dés que n<1 *)
</source>

Comme la fonction est récursive, il ne faut pas oublier le <tt>rec</tt> au début de la définition.


On aurait pu faire une autre version, qui fonctionne différemment sur les nombres négatifs :

<source lang="ocaml">
let rec fact' = function
n when (n>0) -> n * fact' (n-1)
| n when (n<0) -> n * fact' (n+1)
| _ -> 1 (* si n n'est ni plus petit que 0 ni plus grand que 0, n est égal à 0, et on renvoie donc 1 *)
</source>

J'ai volontairement mis une version qui contient plusieurs choses que nous n'avons pas encore vues en cours :
* utilisation de "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

Vous devriez pouvoir comprendre ce que fait la fonction. Sinon, voici une version que vous auriez pu écrire :

<source lang="ocaml">
let rec fact_bis = fun n ->
if (n=0)
then 1
else begin
if (n>0)
then n*fact_bis (n-1)
else n*fact_bis (n+1) (* dans ce cas, n est forcement négatif *)
end
</source>


<u> Les fonctions sommes </u>

Il s'agit ici d'écrire la fonction qui va additionner les carrés des entiers de 1 jusqu'à un nombre donné.

Cela donne :
<source lang="ocaml">
let rec somme_carre b =
if (b=0) then 0
else (b*b) + somme_carre (b-1);;
</source>

Ensuite on nous demande de calculer la somme des cubes des entiers de 1 jusqu'à un nombre donné. On pourrait faire le même programme en remplaçant b*b par b*b*b, mais on va définir une fonction puissance (car elle n'existe pas d'origine sous Caml), qui nous servira aussi pour la suite... :

<source lang="ocaml">
let rec puissance x a =
if (a = 0) then 1
else x * puissance x (a-1);;
</source>

On doit maintenant calculer la somme des <math>i^i</math>, i variant de 1 à un nombre donné :

<source lang="ocaml">
let rec somme_puissance b =
if (b=0) then 0
else (puissance b b) + somme_puissance (b-1);;
</source>

On peut définir une unique fonction qui permettrait de faire toutes ces sommes, celle-ci aura pour argument une fonction quelconque :

<source lang="ocaml">
let rec somme_fonction n f = (* f étant une fonction *)
if (n=0) then f 0
else f n + somme_fonction (n-1) f;;
</source>

cette fonction est de type "<tt>int -> fun -> int</tt>"

<u> Nombres pairs et impairs (TP0 Partie 2 Question 2) </u>

Il faut écrire les fonctions récursives pairs et impairs, qui renvoient vrai si le nombre est pair (respectivement impair) et faux si le nombre est impair (respectivement pair);
Ici nous devons déclarer simultanément les deux fonctions, car chacune fait appel à l'autre lors de son exécution.

Cela donne :

<source lang="ocaml">
let rec pair n =
if (n=0) then true
else impair (n-1)
and impair n =
if (n=0) then false
else pair (n-1);;
</source>


<u> Suite de Fibonacci </u>

La suite de fibonacci est tel que u<sub>0</sub>=0 u<sub>1</sub>=1 et u<sub>n+2</sub>=u<sub>n+1</sub>+u<sub>n</sub>.

<source lang="ocaml">
let rec fib n =
if (n=0) then 0
else if (n=1) then 1
else fib (n-1) + fib (n-2);;
</source>

La plus grande valeur que l'on peut obtenir sans que cela soit trop long est 24157817, ce qui correspond à fib 37.
Nous trouvons qu'il faut déjà 88 additions pour calculer fib 10.

:'''Rq :''' fib de 37 prend effectivement beaucoup de temps. Il faut 39088168 additions avant d'en arriver à bout. Il est possible de faire une version de Fibonacci qui va très vite et qui calcule <tt>fib 37</tt> en seulement 36 additions...
: Comment ?

<u> Dragon ! </u>

<i> Le dragon est une créature mythique, présente dans de nombreuses cultures.
On peut déterminer deux grands types de dragons : le dragon occidental et le dragon oriental</i>

La fonction dragon a pour but de dessiner un dragon, pour cela on utilise une fonction récursive qui admet pour argument le nombre n d'itération de la fonction, et les coordonnées de 2 points. A chaque itération, la fonction calcule pour chaque segment, un nouveau point et le relie ensuite aux deux autres.

On obtient en tout 2<sup>n</sup> segments entremêlés, qui forment un dragon.

Let's go !

<source lang="ocaml">
let rec dragon (n:int) (a:int) (b:int) (c:int) (d:int) : unit =
if (n = 0) then (moveto a b ; lineto c d)
else begin
let x = (a+c+d-b)/2 in
let y = (b+d+a-c)/2 in
dragon (n-1) a b x y ;
dragon (n-1) c d x y
end ;;
</source>

:'''Rq : ''' votre version du dragon est bien, mais pas très précises. (Je chipote un peu...) Pour les paramètres (<tt>dragon 11 100 100 400 400</tt>), de nombreux carrés ne sont pas bien tracés.
:Comment expliquez-vous cela, et comment pouvez-vous le corriger ?

::Pour améliorer la précision je suggère de passer les coordonnées en type Float. --[[Utilisateur:Nicolas|Nicolas]] 31 janvier 2009 à 11:42 (CET)


==Le TD2==

'''Exercice 1 : Tuples'''<br />
'''Question 4 :'''

On définit la fonction curry par:

<source lang="ocaml">
Let curry (f: 'a * 'b -> 'c) : 'a -> 'b -> 'c
= fun x y -> f(x,y);;
</source>

Ou encore en simplifiant:

<source lang="ocaml">
Let curry f x y = f(x,y);;
</source>


On définit ensuite la fonction uncurry par:

<source lang="ocaml">
Let uncurry (f: 'a -> 'b -> 'c) : 'a * 'b -> 'c
= fun x -> f (fst x) (snd x);;
</source>

Ou encore de trois autres manières plus simplifiées:

<source lang="ocaml">
Let uncurry f = fun x -> f (fst x) (snd x);;
</source>

<source lang="ocaml">
Let uncurry f = fun x -> match x with (a,b) -> f a b;;
</source>

<source lang="ocaml">
Let uncurry f = function (a,b) -> f a b;;
</source>


Avantage de la première forme (à plusieurs arguments): Elle permet une application partielle: on peut appliquer cette fonction à une seule partie des arguments.

Inconvénients de la seconde forme (à un argument):
*il faut faire appel à fst, snd;
*Caml doit séparer les paires: c'est une perte de temps


'''Question 5 :'''

D'après la fonction récursive Fibonacci définit par <br />
f(0)=0 <br />
f(1)=1 <br />
f(n+2)=f(n+1)+f(n), <br />
comment compter le nombre d'appels récursifs en Caml? <br />
<source lang="ocaml">
let rec fib n =
if (n<2) then (n,0)
else let t = fib (n-1) in
let s = fib (n-2) in
(fst t + fst s , snd t + snd s + 1)
</source>
''exemple : ''fib 10 = (55, 88) pour exécuter la fonction Fibonacci(10), il y a 88 appels récursifs nécessaires...<br />

'''Exercice 2 : Listes'''<br />
'''Question 5 :'''<br /><br />
suite à l'étude des fonctions
*longueur
<source lang="ocaml">
let rec longueur l=
match l with
[] ->0
| _ :: l -> 1+longueur l
</source>
*applique
<source lang="ocaml">
let rec app f p =
match p with
[] -> []
| a :: p -> f(a) :: app f p
</source>
*concatene
<source lang="ocaml">
let rec cat l1 l2 =
match l1 with
[] -> l2
| a :: l -> a :: (cat l l2)
</source>
*renverse,
<source lang="ocaml">
let rec renverse l =
match l with
[] -> []
| a :: l -> (renverse l)@[a]
</source>
on remarque des similitudes. Ces fonctions ont le même schéma de base ( celui de la fonction reduit)
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> f a (reduit l o f)
</source>
''NB :'' val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun>

'''Question 6 :'''<br/>
Reprogrammons les fonctions précédentes à partir de la fonction reduit ! <br/>
<source lang="ocaml">
let longueur l =
let f _ r = 1 + r in
reduit l o f
</source>

<source lang="ocaml">
let app g l =
let f
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

<source lang="ocaml">
let renverse l =
let f r a = [r]@[a]
reduit l [] f
</source>

==Le TP1 - début==

--- à venir ---

Dernière version du 11 janvier 2010 à 10:13

Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO401_corr_TD_TP&oldid=4642 »