Topographie de fonctions

Exercice 41

Soit f une fonction de [0, n[ sur [0, n[, on souhaite analyser les trajectoires f^n(i) pour tout n et i et ainsi détecter les cycles et les branches menant à ces cycles. Lorsque la topographie est finie, on veut aussi compter le nombre de cycles différents et le nombre de branches différentes: en moyenne, ces deux nombres doivent être 1/2 Log n et $\pi n/2$.

Définir un générateur pseudo-aléatoire de fonctions de [0, n[ sur [0, n[. Une telle fonction sera représentée par une fonction Caml enclosant un vecteur caractérisant sa trace c'est-à-dire un vecteur v tel que v.(i) = f(i).

Solution 41

Voici tout d'abord un générateur aléatoire simple:

let engendre_alea a b =
  let seed = ref 0 in
   fun n -> seed := (b + a * !seed) mod 16384;
            !seed mod n;;
engendre_alea : int -> int -> int -> int = <fun>
let alea = engendre_alea 17 251;;
alea : int -> int = <fun>

On peut maintenant engendrer aléatoirement des fonctions comme suit:

let engendrer_fonction n =
  let mappe = make_vect n 0 in
   for i = 0 to n-1 do
     mappe.(i) <- alea(n)
   done;
   function i -> mappe.(i);;
engendrer_fonction : int -> int -> int = <fun>
let f0 = engendrer_fonction 10;;
f0 : int -> int = <fun>

On alloue un vecteur pour stocker la trace, puis on l'initialise et on retourne une fonction qui ne fait qu'exploiter ce vecteur. On peut même utiliser une curryfication et écrire directement pour faire plus intelligent:

let engendrer_fonction n =
  let mappe = make_vect n 0 in
   for i = 0 to n-1 do
     mappe.(i) <- alea(n)
     done;
   vect_item mappe;;
engendrer_fonction : int -> int -> int = <fun>

Notez qu'un vecteur est alloué par fonction engendrée. Il ne faut surtout pas partager ce vecteur.

Exercice 42

Définir une fonction imprimant la trace d'une fonction telle que précédemment engendrée. Par exemple:

voir_fonction (engendrer_fonction 10) 10;;
(0 -> 9) (1 -> 8) (2 -> 9) (3 -> 2) (4 -> 9) (5 -> 6) (6 -> 3) (7 -> 0) (8 -> 1) (9 -> 6) 

- : unit = ()

Solution 42

let voir_fonction f n =
  for i = 0 to n-1 do
    print_string "(";
    print_int i;
    print_string " -> ";
    print_int (f i);
    print_string ") "
    done;
  print_newline();;
voir_fonction : (int -> int) -> int -> unit = <fun>

Exercice 43

Comme il est enquiquinant de fournir n à voir_fonction, adopter un codage de la fonction contenant n c'est-à-dire tel que l'on puisse manipuler la fonction sous la forme d'une unique valeur. Pour cela prendre un enregistrement à deux champs (l'un pour n, l'autre pour la fonction proprement dite). Définir le type fonction et refaire alors les fonctions engendre_fonction et voir_fonction.

Solution 43

On notera la définition de l'abréviation point. Une abréviation ne définit pas de nouveau type.

type point == int;;
Type point defined.
type fonction = \camlbslash{}{
  n     : int;
  image : point -> point
\camlbslash{}};;
Type fonction defined.
let engendrer_fonction n =
  let mappe = make_vect n 0 in
   for i = 0 to n-1 do
     mappe.(i) <- alea(n)
     done;
   \camlbslash{}{n = n; image = vect_item mappe \camlbslash{}};;
engendrer_fonction : int -> fonction = <fun>
let voir_fonction f =
  for i = 0 to f.n-1 do
    print_string "(";
    print_int i;
    print_string " -> ";
    print_int (f.image i);
    print_string ") "
    done;
  print_newline();;
voir_fonction : fonction -> unit = <fun>
let f0 = engendrer_fonction 10;;
f0 : fonction = \camlbslash{}{n = 10; image = <fun>\camlbslash{}}
voir_fonction f0;;
(0 -> 7) (1 -> 0) (2 -> 1) (3 -> 2) (4 -> 1) (5 -> 0) (6 -> 3) (7 -> 4) (8 -> 5) (9 -> 8) 

- : unit = ()

Exercice 44

Définir un type topographie associant à chaque élément i de l'ensemble de départ, la branche et le cycle de sa trajectoire. Le branche est la partie initiale de la trajectoire menant au cycle, ce dernier exclus. On définira aussi le type chemin pour une suite d'éléments de [0, n[.

Solution 44

type chemin == point list
and  trajectoire = \camlbslash{}{
        branche : chemin;
        cycle : chemin 
     \camlbslash{}}
and  topographie == trajectoire vect;;
Type chemin defined.
Type trajectoire defined.
Type topographie defined.

Exercice 45

Définir une fonction imprimant bellement une topographie. Vous pouvez vous inspirer de ce qui suit mais vous aurez aussi intérêt à séparer les fonctionnalités et savoir indépendamment imprimer trajectoire, branche et cycle.

imprimer_topographie 
  [| \camlbslash{}{ branche = [1]; cycle = [5;6] \camlbslash{}};
     \camlbslash{}{ branche = [2;3]; cycle = [4] \camlbslash{}};
     \camlbslash{}{ branche = [3]; cycle = [4] \camlbslash{}};
     \camlbslash{}{ branche = []; cycle = [4] \camlbslash{}}
  |];;
0: 1 [5 6 ...]
1: 2 3 [4 ...]
2: 3 [4 ...]
3: [4 ...]
- : unit = ()

Solution 45

C'est assez simple mais utile pour ce qui suivra.

let rec imprimer_cycle cycle =
  print_string "[";
  do_list (function pt -> print_int pt; print_string " ") (rev cycle);
  print_string "...]"
and imprimer_branche branche =
  do_list (function pt -> print_int pt; print_string " ") (rev branche);;
imprimer_cycle : int list -> unit = <fun>
imprimer_branche : int list -> unit = <fun>
let imprimer_trajectoire trajectoire =
  imprimer_branche trajectoire.branche;
  imprimer_cycle trajectoire.cycle;;
imprimer_trajectoire : trajectoire -> unit = <fun>
let imprimer_topographie topographie_fonction =
  for i = 0 to vect_length topographie_fonction - 1 do
    print_int i;
    print_string ": ";
    imprimer_trajectoire topographie_fonction.(i);
    print_newline()
  done;;
imprimer_topographie : trajectoire vect -> unit = <fun>

Exercice 46

Calculer la topographie d'une fonction. Il faut pour cela, identifier la branche et le cycle. Tâchez de partager les représentations des trajectoires.

Pour vous faciliter la tâche, on pourra écrire la fonction extraire_branche_et_cycle i deja_vus où deja_vus est la suite des points [$fn(a)fn-1(a)$&ldots;f(a)a]. Si le nouveau point i appartient à deja_vus alors on identifie facilement le cycle de la branche.

On peut ensuite pour chaque point du domaine, enumérer les valeurs composant la trajectoire jusqu'à identifier branche et trajectoire. Si l'on souhaite partager les représentations c'est un peu plus complexe car on calcule en fait de multiples trajectoires en même temps. Si j=f(i) alors la trajectoire de i se déduit aisément de celle de j.

Solution 46

Les points dans deja_vus sont rangés en ordre inverse.

let etendre_trajectoire f i trajectoire =
  if mem i trajectoire.branche
  then \camlbslash{}{ branche = i :: trajectoire.branche; cycle = trajectoire.cycle \camlbslash{}}
  else let tete_de_cycle = hd trajectoire.cycle in
       let rec enum i =
         if i = tete_de_cycle then [] else i :: enum (f.image i) in
         \camlbslash{}{ branche = enum i; cycle = trajectoire.cycle \camlbslash{}};;
etendre_trajectoire : fonction -> point -> trajectoire -> trajectoire = <fun>
let extraire_branche_et_cycle i deja_vus =
  let rec enum cycle reste =
    if i=(hd reste)
    then \camlbslash{}{ branche = rev (tl reste); cycle = i :: cycle \camlbslash{}}
    else enum ((hd reste) :: cycle) (tl reste) in
  enum [] deja_vus;;
extraire_branche_et_cycle : point -> point list -> trajectoire = <fun>
let rec suivre_trajectoire topog f i deja_vus =
  if topog.(i).cycle <> [] 
  then () (* trajectoire de i est deja calculee *)
  else if mem i deja_vus
       then topog.(i) <- extraire_branche_et_cycle i deja_vus
       else let j = f.image i in
            suivre_trajectoire topog f j (i :: deja_vus);
            topog.(i) <- etendre_trajectoire f i topog.(j);;
suivre_trajectoire :
 trajectoire vect -> fonction -> point -> int list -> unit = <fun>
let topographier_fonction f =
  let topographie_fonction = make_vect f.n \camlbslash{}{ branche = []; cycle = [] \camlbslash{}} in
  for i = 0 to f.n-1 do 
    suivre_trajectoire topographie_fonction f i []
  done;
  topographie_fonction;;
topographier_fonction : fonction -> trajectoire vect = <fun>
imprimer_topographie (topographier_fonction f0);;
0: [1 4 7 0 ...]
1: 1 [1 4 7 0 ...]
2: 1 2 [1 4 7 0 ...]
3: 1 2 3 [1 4 7 0 ...]
4: 1 4 [1 4 7 0 ...]
5: 5 [1 4 7 0 ...]
6: 1 2 3 6 [1 4 7 0 ...]
7: 1 4 7 [1 4 7 0 ...]
8: 5 8 [1 4 7 0 ...]
9: 5 8 9 [1 4 7 0 ...]
- : unit = ()

Exercice 47

Écrire une fonction comparant deux cycles. Attention 4 5 ... est semblable à 5 4 ....

Solution 47

let comparer_cycles cycle1 cycle2 =
  mem (hd cycle1) cycle2;;
comparer_cycles : 'a list -> 'a list -> bool = <fun>
comparer_cycles [1;2] [2;1];;
- : bool = true
comparer_cycles [1;2] [3];;
- : bool = false

Exercice 48

Extraire les cycles différents présents dans une topographie afin de les compter ou les imprimer.

Solution 48

Notez l'utilisation du prédicat exists.

let extraire_cycles topographie_fonction =
  let rec cycle_deja_vu cycle cycles = 
    exists (comparer_cycles cycle) cycles
  and enum cycles i =
   if i = vect_length topographie_fonction
   then cycles
   else if cycle_deja_vu topographie_fonction.(i).cycle cycles
        then enum cycles (i+1)
        else enum (topographie_fonction.(i).cycle :: cycles) (i+1) in
  enum [] 0;;
extraire_cycles : trajectoire vect -> point list list = <fun>
let compter_cycles topographie_fonction =
  list_length (extraire_cycles topographie_fonction);;
compter_cycles : trajectoire vect -> int = <fun>
compter_cycles (topographier_fonction f0);;
- : int = 1
do_list (function cycle -> imprimer_cycle cycle; print_newline())
        (extraire_cycles (topographier_fonction f0));;
[1 4 7 0 ...]
- : unit = ()

Exercice 49

Écrire un prédicat comparant deux branches. Il répond vrai si la première est un tronc de la seconde ou récriproquement. Par exemple,

Solution 49

let rec est_contenue_dans branche1 branche2 =
  if branche1 = branche2 then true
  else if branche2 = [] then false
       else est_contenue_dans branche1 (tl branche2);;
est_contenue_dans : 'a list -> 'a list -> bool = <fun>
est_contenue_dans [2;3] [0;1;2;3];;
- : bool = true
est_contenue_dans [2;3] [0;1;2;3;4];;
- : bool = false

On peut aussi écrire plus légérement:

let rec est_contenue_dans branche1 branche2 =
  branche1 = branche2
  or (branche2 <> [] 
      & est_contenue_dans branche1 (tl branche2));;
est_contenue_dans : 'a list -> 'a list -> bool = <fun>
est_contenue_dans [2;3] [0;1;2;3];;
- : bool = true
est_contenue_dans [2;3] [0;1;2;3;4];;
- : bool = false

Exercice 50

Extraire les branches différentes dans une topographie afin de les compter ou de les imprimer.

Solution 50

let extraire_branches topographie_fonction =
  let rec traiter branche = function 
      [] -> [branche]
    | b :: autres_branches as branches -> 
        if est_contenue_dans branche b
        then branches
        else if est_contenue_dans b branche
             then branche :: autres_branches
             else b :: (traiter branche autres_branches)
  and enum branches i =
    if i = vect_length topographie_fonction 
    then branches
    else let branche = topographie_fonction.(i).branche in
         enum (traiter branche branches) (i+1) in
  enum [] 0;;
extraire_branches : trajectoire vect -> point list list = <fun>
let compter_branches topographie_fonction =
  list_length (extraire_branches topographie_fonction);;
compter_branches : trajectoire vect -> int = <fun>
compter_branches (topographier_fonction f0);;
- : int = 3
do_list (function branche -> imprimer_branche branche; print_newline())
        (extraire_branches (topographier_fonction f0));;
1 2 3 6 
1 4 7 
5 8 9 
- : unit = ()

Exercice 51

Cartographier les fonctions c'est-à-dire compter leur nombre de cycles et de branches. Pour ce faire, on engendrera des fonctions aléatoirement, on comptera leur cycles et branches et l'on maintiendra la moyenne de ces nombres jusqu'à ce que ces compteurs n'évoluent plus (à epsilon près).

Solution 51

Notez l'emploi d'opérations sur des nombres flottants: les opérateurs sont suffixés d'un point.

let cartographier n epsilon =
  let nombre_fonctions = ref 0
  and somme_branches = ref 0
  and somme_cycles = ref 0
  and nombre_moyen_branches = ref 0.0
  and nombre_moyen_cycles = ref 0.0 in
  let rec analyser () =
    let f = engendrer_fonction n in
    let topographie = topographier_fonction f in
    let b = compter_branches topographie
    and c = compter_cycles topographie in
      print_string "("; print_int b; print_string ",";
      print_int c; print_string ")"; 
      nombre_fonctions := !nombre_fonctions + 1;
      somme_branches := !somme_branches + b;
      somme_cycles := !somme_cycles + c;
      let nmb = float_of_int(!somme_branches) /. float_of_int(!nombre_fonctions)
      and nmc = float_of_int(!somme_cycles) /. float_of_int(!nombre_fonctions) in
      if ( (abs_float (nmb -. !nombre_moyen_branches)) <=. epsilon  &
           (abs_float (nmc -. !nombre_moyen_cycles)) <=. epsilon )
      then (nmb,nmc)
      else (nombre_moyen_branches := nmb;
            nombre_moyen_cycles := nmc;
            analyser () ) in
  analyser ();;
cartographier : int -> float -> float * float = <fun>
cartographier 2 0.1;;
(1,1)(1,1)- : float * float = 1.0, 1.0
cartographier 5 0.01;;
(1,3)(1,2)(2,2)(2,3)(3,2)(2,1)(2,1)(2,1)(2,2)(2,2)(3,2)(2,2)- : float * float = 2.0, 1.916
66666667