Cours 4

Plan

• tours de Hanoi
• problèmes indécidables
• 1er exemple de diviser pour régner
• 2ème exemple: QuickSort, Tri Fusion

• entrées graphiques
• 3ème exemple: cubiques de Bézier (spline)
• exercices

Les 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.

Problèmes indécidables

Qques exemples:

1- Faire un programme qui teste si un autre termine. Sinon on aboutit à une contradiction:

let test_terminaison (u) = 
    begin
    (* test_terminaison (u) = true si u() termine  *)
    (*                        false sinon          *)
    (* Source du programme brevete' par le vendeur *)
    end;;

let rec d () =
    while test_terminaison(d) do ()  
    done ;;

2- Considérer des dominos carré dont chacun des 4 cotés est coloré. On suppose qu'on peut prendre des dominos en nombre arbitraire dans un type fini donné à l'avance. Peut-on recouvrir toute surface avec des carrés compatibles, c'est a` dire dont les cote's qui se touchent sont de me^mes couleurs? Peut-on recouvrir le plan avec des carrés compatibles?

3- Problème de correspondance de Post. Soient 2 ensembles finis de mots avec des lettres de l'alphabet. Existe-t-il 2 chaines identiques formés uniquement avec un nombre arbitraire de mots de chacun des 2 types?

Ne pas confondre avec des problèmes décidables, mais de complexité très élevée.

Il existe aussi des pbs plus indécidables que les autres. Cf le livre de Rogers. (La récursivité sera vu dans le cours de Stern en majeure Math et Informatique, M1).

Premier exemple de diviser pour régner

Les éléments d'un tableau sont des nombre entiers relatifs. Trouver les sommes maximales de sous-séquences consécutives. (livre de Bentley, Programming Pearls)

let maximum a =
  let n = vect_length a in
  let res = ref 0 
  and s = ref 0 in
  begin
     for g = 0 to n-1 do 
        for d = g to n-1 do
           s := 0;
           for i = g to d do
               s := !s + a.(i);
           done;
           res := max (!res, !s)
        done
     done;
     !res
  end
;;

Minimum partiels (bis)

let maximum a =
  let n = vect_length a in
  let res = ref 0 
  and s = ref 0 in
  begin
     for g = 0 to n-1 do 
        s := 0;
        for d = g to n-1 do
               s := !s + a.(i);
               res := max (!res, !s)
           done
        done
     done;
     !res
  end
;;

Minimum partiels (ter)

let max (x, y) = if x < y then y else x ;;

let rec maximum a g d =
  let n = vect_length a in
  let res = ref 0  
  and s = ref 0 and maxG = ref 0 and maxD = ref 0 
  and maxACheval = ref 0 and maxAGauche = ref 0 and maxADroite = ref 0
  in
   if g > d then 0
   else 
   if g = d then max (0, a.(g))
   else 
   let m = (g + d) / 2 in
   begin
      s := 0; maxG := 0;
      for i = m downto g do
           s := !s + a.(i);
           maxG := max(!maxG, !s);
      done;
      s := 0; maxD := 0;
      for i = m+1 to d do
           s := !s + a.(i);
           maxD := max(!maxD, !s);
      done;
      let maxACheval = !maxG + !maxD  and
          maxAGauche = maximum a g m  and
          maxADroite = maximum a (m+1) d
      in
      max(maxACheval, max(maxAGauche, maxADroite))
   end ;;

Tri récursif -- Quicksort, Merge sort

Quicksort. On prend un élément au hasard, on le met en place avec à sa gauche des plus petits ou égal, et à sa droite des plus grands ou égal et on recommencre récursivement sur les 2 moitiés.

let rec quick_sort g d =
  if g < d then begin
    let v = a.(g)
    and m = ref g in
    for i = g + 1 to d do
       if a.(i) < v then begin
          m := !m + 1;
          let x = a.(!m) in
          a.(!m) <- a.(i); a.(i) <- x
       end
    done;
    let x = a.(!m) in
    a.(!m) <- a.(g); a.(g) <- x;
    quick_sort g (!m - 1);
    quick_sort (!m + 1) d
  end;;

Entrées graphiques

Pour lire des points à la souris, on peut faire de l'attente active (polling) avec des événements multiplexés clavier/souris:

 
let wait_button_down() =
   while not button_down() do () done;;

let wait_button_up() =
   while button_down() do () done;;

let get_next_point () =
   begin
   wait_button_down();
   wait_button_up();
   mouse_pos()
   end;;

   let e = wait_next_event [Button_down; Key_pressed] in
     if e.keypressed then begin
        match e.key with 
          'q' -> ....

     end else
     if e.button then begin

Courbes de Bézier

L'ingénieur Bézier de Renault a défini des courbes intéressantes pour la conception des carosseries de voitures. Ces courbes sont aussi utilisées en PostScript (pour les imprimantes laser) et dans MetaFont (pour générer les polices de caractères de TeX).

Les cubiques de Bézier (splines) sont données par 4 points, A, B, C, D. La cubique est tangente en A et D, les vecteurs {AB} et {CD} représentent les valeurs des dérivées en A et D. La cubique est tjrs inscrite dans le quadrilatère ABCD.

On peut les dessiner très facilement avec une méthode Diviser pour Régner. En effet, il existe une définition récursive simple. En posant A1=A et D2=D et en prenant les milieux:

I de [B,C],
B1 de [A,B],
C2 de [C,D],
C1 de [B1,I],
B2 de [I,C2],
D1=A2 de [B1,B2],

Un expert est Lyle Ramshaw (DEC/SRC Tech Report 19). On en parle au cours Graphique de Puech et Sillion dans la majeure Math et Info, M1.

Exercices en TD

• dessiner des splines en rentrant les (4 ou N) points de controle graphiquement.
• faire QuickSort ou Merge Sort (cf. polycopié).