Cours 3

Plan

Tri Shell 1959

(* cf polycopié *) 

let tri_shell a =
 let h = ref 1 in
  while !h <= vect_length a - 1 do
   h := 3 * !h + 1
  done;
  while !h > 1 do
   h := !h / 3;
   for i = !h to vect_length a - 1 do
    if a.(i) < a.(i - !h) then begin
     let v = a.(i) in
     let j = ref i in
     while !j >= !h && a.(!j - !h) > v do
      a.(!j) <- a.(!j - !h);
      j := !j - !h
     done;
     a.(!j) <- v 
    end    
   done
  done;;

Nombre moyen et nombre pire de comparaisons? On peut montrer qu'il en fait moins que O(N^{3/2}). Pour les séquences 2^p3^q, Vaughan Pratt a montré que N (log N)^2 suffisent.

Mais on ne connait pas de borne inférieure. C'est un pb ouvert!

Pour trouver des bornes sup sur le coût, il suffit d'exhiber un algorithme. Pour trouver des bornes inf, il faut un argument principalement combinatoire. Pour trouver les coûts moyens, on passe souvent par l'analyse complexe, fonctions génératrices, etc (cf Analysis of Algorithms, Sedgewick et Flajolet; ou cours de DEA).

Autres tris

Il y a bien d'autres tris (cf Knuth, vol 3; Searching and Sorting). Si on connait la distribution des valeurs et qu'elles ne soient pas très grandes, on peut arriver à trier en temps linéaire.

(cf. le TD1 de Bruno Salvy en
http://www.polytechnique.fr/poly/~salvy)

Tri distribution, tri des mécanographes (Straight Radix Sort). Enfin, si toutes les données ne tiennent pas dans la mémoire vive d'un ordinateur (c'est de moins en moins le cas), il y a des méthodes sophistiquées de tri externe.

Tri distribution: 

let tri_distribution a =
  let count = make_vect max_value 0 
  and b = make_vect (vect_length a) 0 in
    begin
    for j = 0 to max_value -1 do count.(j) <- 0 done;
    for i = 0 to vect_length a - 1  do
        count.(a.(i)) <- count.(a.(i)) + 1
        done;
    for j = 1 to max_value -1 do 
        count.(j) <- count.(j-1) + count.(j)
        done;
    for i = vect_length a - 1 downto 0 do
        count.(a.(i)) <- count.(a.(i)) - 1;
        b.(count.(a.(i))) <- a.(i)
        done;
    for i = 0 to vect_length a - 1 do a.(i) <- b.(i) done;
    end ;;

Polymorphisme en ML

let f x = x ;;
let g (x, y) = x ;;
let nth (a, n) =  a.(n) ;;
donnent 
f : 'a -> 'a = 
g : 'a * 'b -> 'a = 
nth : 'a vect * int -> 'a =
'a (lire "alpha") est une variable de type. On peut donc utiliser f dans tout contexte où alpha peut être intancié. Par exemple, 
f 2 ;;
- : int = 2
ou 
f "aaaa" ;;
- : string = "aaaa"

Pb: quel est le type de := ?? 

prefix :=  ;;
donne la réponse...

Filtrage et let ... in ...

La construction let est en fait plus générale que déjà vu. On peut mettre un motif à gauche de =. Les 3 expressions suivantes qui sont équivalentes 

let pat_1 = e_1 and ... pat_n = e_n in e               
let (pat_1, ... pat_n) = (e_1, ... e_n) in e
(function (pat_1, ... pat_n) -> e) (e_1, ... e_n)
comportent des motifs patterns (linéaires), c'est à dire des expressions incomplètes avec des variables (de filtrage). Dans un motif, toute variable est considérée comme une variable de filtrage. Un motif est une expression de la forme suivante: 
constante
variable
(pat_1 | pat_2 ... pat_n)
(pat_1, pat_2 ... pat_n)
Il est interdit d'avoir une variable dans un motif de la 2ème sorte (dont nous verrons l'utilité dans un match). Une variable ne peut intervenir qu'une seule fois (linéarité).

Les variables des motifs sont des variables locales avec les mêmes lois de portée que dans le cas (déjà vu) du motif trivial: 

let x_1 = e_1 and ... x_n = e_n in e

Exemples: 

let x = 3;;
let (x, y, z) = (1, 2, 3) in x+y+z;;

Filtrage et match ... with ...

On passe de la conjonction à la disjonction de filtrages avec match 

match e with pat_1 -> e_1 | ... pat_n -> e_n
1- On évalue e qui donne une valeur v. On filtre v par pat_1.
2- Si succès, on lie temporairement les variables de pat_1 avec les valeurs filtrées dans v, et on évalue e_1 dans ce nouvel environnement. La valeur v_1 de e_1 sera le résultat de toute l'expression.
3- Sinon, on passe à pat_2, etc, jusqu'à pat_n.
4- Si échec global, on a une exception Match_failure.

De la même manière, on peut définir une fonction à l'aide d'un filtrage disjonctif 

function pat_1 -> e_1 | ... pat_n -> e_n
dont le sens est défini par l'équivalence des 2 instructions suivantes 
match e with pat_1 -> e_1 | ... pat_n -> e_n
(function pat_1 -> e_1 | ... pat_n -> e_n) e
Le système signale un filtrage non exhaustif, qui a oublié un cas. C'est un simple avertissement. La constante _ permet d'avoir un cas par défaut. Si plusieurs cas se recouvrent, c'est le premier dans l'ordre d'écriture du programme qui est pris.

Définitions récursives

let rec définit une variable récursive, ie qui utilise la (les) valeur(s) en cours de définition. Exemples: 

let rec f (x) = if x <= 1 then 1 else f(x-1) + f(x-2) ;;
let rec g (x) = if x = 0 then 1 else x * g (x-1) ;;
let rec h (x, y) = if x = 0 then 1 else h (x-1, h(x,y)) ;;
let rec m (x) = if x > 100 then x - 10 else m (m (x+11)) ;;
On peut imprimer leur valeurs pour qques valeurs 
begin 
for i = 1 to 15 do 
   printf "%d " (f (i)) done; 
   printf "\n" 
end ;;
f, g sont les fonctions de Fibonacci et factorielles. C'est la même notation que pour les suites récurrentes. Que valent h et m?

A nouveau, la valeur des arguments est calculée avant de calculer le corps de la fonction appel par valeur. C'est le seul mécanisme d'appel des fonctions. Si on veut modifier la valeur d'un argument, on passe par les références (comme en C):

Exemples: 

let incr x = 
   x := !x + 1
   ;;

Récursivité terminale

La récursion ne coute pas cher. Il faut l'utiliser, car souvent élégante. La récursion terminale est particulièrement optimisée. C'est lorsque le résultat d'une fonction est un appel récursif. (Caml transforme alors le programme en programme itératif). Exemple: 

let f (x) = if even x then
               x / 2
            else 
               f (3*x + 1) ;;
dont on conjecture que le résultat vaut toujours 1. Essayez de calculer qques valeurs!

La récursivité est très puissante. Invention de Kleene (1935). Théorie des fonctions récursives, comme moyen général de calcul. On peut montrer qu'il existe toujours des fonctions récursives partielles (qui ne terminent pas pour tte valeur de leurs arguments), si on veut un modèle général. La sous théorie des fonctions récursives primitives correspond aux programmes sans boucles, sans appels récursifs, et l'instruction for. Ces programmes terminent toujours. (cf Introduction to Metamathematics, S. Kleene; Recursive Functions Theory and Logic, A. Yasuhara).

Church et les autres logiciens des années 30 ont montré que systèmes de Post, les fonctions récursives de Kleene, les machines de Turing, sont tous équivalentes. Il a émis la thèse suivante: tous les modèles de la calculabilité sont équivalents.
(cf majeure math/info, cours de Stern pour avoir tous les détails)

Les tours de Hanoi

La récursivité (qui existe aussi en Pascal et C) est proche de l'induction mathématique. Elle ne se contente pas de calculer des suites récurrentes. Exemple des tours de Hanoi.

Transporter N rondelles de la pile i à la pile j en ne mettant jamais une petite sous une plus grosse, avec (i,j dans {1, 2, 3}).

Si N = 0, ne rien faire. Si N > 0, alors on résoud le pb avec N-1 rondelles de i à la troisième pile k=6-i-j. On prend la grosse rondelle en bas de i et on la met sur j (qui est alors vide). On met alors les N-1 rondelles de k sur i.

Ecrire donc le programme correspondant (en moins de 5 lignes). On réalise alors que la récursion est un mécanisme très général.

Bibliothèque graphique

Par le Web, on trouve la description complète ici. Sans le Web, on peut lire le fichier d'interface graphics.mli (ML interface) du module graphique de votre système. 

value open_graph: string -> unit
value close_graph: unit -> unit
value clear_graph : unit -> unit
value size_x : unit -> int
value size_y : unit -> int
value rgb: int -> int -> int -> color
value set_color : color -> unit
value black : c
value magenta : color
value plot : int -> int -> unit

value point_color : int -> int -> color
value moveto : int -> int -> unit
value current_point : unit -> int * int
value lineto : int -> int -> unit
value draw_arc : int -> int -> int -> int -> int -> int -> unit
value draw_ellipse : int -> int -> int -> int -> unit
value draw_circle : int -> int -> int -> unit
value set_line_width : int -> unit

value draw_char : char -> unit
value draw_string : string -> unit
value set_font : string -> unit
value set_text_size : int -> unit

value text_size : string -> int * int
value fill_rect : int -> int -> int -> int -> unit
Au début du programme, on déclare l'utilisation de la librairie graphique par la directive: 
#open "graphics" ;;

Récursivité graphique, courbes fractales

Gaston Julia et Benoît Mandelbrot (x56?, IBM) en sont les pères fondateurs.

Le flocon de von Koch [1]
La courbe du dragon [1, 2]
La courbe de Hilbert [1]
La courbe de Sierpinsky [1 2 3 4]
Les fougères de Barnsley [1]
Les systèmes de Lindenmayer (arbres) [1]

Exemple (le dragon) 

let rec dragon n x y z t =
 if n = 1 then begin
  moveto x y;
  lineto z t
 end else begin
  let u = (x + z + t - y) / 2
  and v = (y + t - z + x) / 2 in
  dragon (n - 1) x y u v;
  dragon_bis (n - 1) u v z t
 end

and dragon_bis n x y z t =
 if n = 1 then begin
  moveto x y;
  lineto z t
 end else begin
  let u = (x + z - t + y) / 2
  and v = (y + t + z - x) / 2 in
  dragon (n - 1) x y u v;
  dragon_bis (n - 1) u v z t
 end;;
Attention aux arrondis, entiers contre flottants.

Exercices en TD