Précédent Index Suivant

Exercices

Listes doublement chaînées

La programmation fonctionnelle se prête bien à la manipulation de structures de données non circulaires, comme par exemple les listes. Par contre pour les structures circulaires, il y a de réelles difficultés d'implantation. On se propose ici de définir des listes doublement chaînées, c'est-à-dire que chaque élément d'une liste connaît son successeur et son prédécesseur.
  1. Définir un type pour des listes doublement chaînées paramétré, en utilisant au moins un enregistrement avec champs mutables. Une cellule est un enregistrement contenant une valeur, la liste des cellules suivantes et la liste des cellules précédantes. 

    # type 'a cell = { 
         info : 'a ;
         mutable prev : 'a dlist ;
         mutable next : 'a dlist }


    Une liste est soit vide, soit une cellule. 

     and 'a dlist = Empty | Cell of 'a cell ;;
    type 'a cell = { info: 'a; mutable prev: 'a dlist; mutable next: 'a dlist }
    type 'a dlist = | Empty | Cell of 'a cell


  2. Écrire les fonctions add et remove qui ajoute et enlève un élément dans une liste doublement chaînée. Ajouter une cellule contenant x en l'intercalant entre la cellule désignée par dl et sa cellule précédante. 

    # let add x = function 
         Empty -> Cell { info=x ; prev=Empty ; next=Empty }
       | Cell c as l -> 
           let new_cell = { info=x ; prev=c.prev ; next=l } in
           let new_dlist = Cell new_cell in 
           c.prev <- new_dlist ;
           ( match new_cell.prev with 
                 Empty -> ()
               | Cell pl -> pl.next <- new_dlist ) ;
           new_dlist ;;
    val add : 'a -> 'a dlist -> 'a dlist = <fun>
    Supprimer la cellule désignée par dl en "recollant" la cellule précédante avec la suivante. 

    # let remove_cell = function 
         Empty -> failwith "enleve"
       | Cell c -> match (c.prev , c.next) with 
             Empty , Empty -> Empty 
           | Cell c1 as l , Empty -> c1.next <- Empty ; l
           | Empty , ((Cell c2) as l) -> c2.prev <- Empty ; l 
           | Cell c1 as l1 , (Cell c2 as l2) -> c1.next <- l2; c2.prev <- l1; l1  ;;
    val remove_cell : 'a dlist -> 'a dlist = <fun>


    Supprimer toutes les cellules contenant x. 

    # let rec remove x l = 
       let rec remove_left = function 
           Empty -> ()
         | Cell c as l -> let pl = c.prev in
                          if c.info = x then ignore (remove_cell l) ;
                             remove_left pl 
       and remove_right = function 
           Empty -> () 
         | Cell c as l -> let nl = c.next in 
                          if c.info = x then ignore (remove_cell l) ;
                          remove_right nl 
       in match l with 
              Empty -> Empty 
            | Cell c as l -> if c.info = x then remove x (remove_cell l) 
                             else (remove_left c.prev ; remove_right c.next ; l) ;;
    val remove : 'a -> 'a dlist -> 'a dlist = <fun>

Résolution de systèmes linéaires

Cet exercice porte sur le calcul matriciel. Il résoud un système d'équations selon la méthode de Gauss (dite du pivot). On note le système d'équation A   X = Y avec A une matrice carrée de dimension n, Y un vecteur de données de dimension n et X un vecteur inconnu de même dimension.

Cette méthode consiste à transformer le système A   X = Y en un système équivalent C   X = Z tel que la matrice C soit triangulaire supérieure. On diagonalise C pour obtenir la solution.
  1. Définir un type vect, un type mat et un type syst . 

    # type vect = float array ;;
    type vect = float array
    # type mat = vect array ;;
    type mat = vect array
    # type syst = { m:mat ; v:vect } ;; 
    type syst = { m: mat; v: vect }


  2. Écrire les fonctions utilitaires de manipulation de vecteurs : affichage à l'écran d'un système, addition de deux vecteurs, multiplication d'un vecteur par un scalaire. Écrire un flottant sur cinq caractères. 

    # let my_print_float s = 
       let x = string_of_float s 
       in let y = match String.length x with 
                      5 -> x 
                    | n when n<5 -> (String.make (5-n) ' ') ^ x 
                    | n -> String.sub x 0 5 
       in print_string y  ;;
    val my_print_float : float -> unit = <fun>


    Afficher un système. 

    # let print_syst s = 
       let l = Array.length s.m
       in for i=0 to l-1 do 
            print_string "  | " ;
            for j=0 to l-1 do 
              my_print_float s.m.(i).(j) ;
              print_string "  " 
            done ;
            if i=l/2 then print_string "  |  *  | x" 
                     else print_string "  |     | x" ;
            print_int (i+1) ;
            if i=l/2 then print_string "  |  =  | " 
                     else print_string "  |     | " ;
            my_print_float s.v.(i) ;
            print_string " |" ;
            print_newline ()
         done ;;
    val print_syst : syst -> unit = <fun>
    



    # let add_vect v1 v2 = 
       let l = Array.length v1 
       in let res = Array.create l 0.0 
       in for i=0 to l-1 do res.(i) <- v1.(i) +. v2.(i) done ;
          res ;;
    val add_vect : float array -> float array -> float array = <fun>
    



    # let mult_scal_vect x v = 
       let l = Array.length v
       in let res = Array.create l 0.0 
       in for i=0 to l-1 do res.(i) <- v.(i) *. x done ;
          res ;;
    val mult_scal_vect : float -> float array -> float array = <fun>


  3. Écrire les fonctions utilitaires de calcul sur les matrices : multiplication de deux matrices, produit d'une matrice par un vecteur. 

    # let mult_mat m1 m2 = 
       let l1 = Array.length m1 and l2 = Array.length m2.(0)
       and l3 = Array.length m2
       in let res = Array.create_matrix l1 l2 0.0 
       in for i=0 to l1-1 do 
            for j=0 to l2-1 do 
              for k=0 to l3-1 do 
                res.(i).(j) <- res.(i).(j) +. m1.(i).(k) *. m2.(k).(j)
              done done done ;
          res  ;;
    val mult_mat : float array array -> float array array -> float array array =
      <fun>
    



    # let mult_mat_vect m v = 
       let l1 = Array.length m and l2 = Array.length v
       in let res = Array.create l1 0.0
       in for i=0 to l1-1 do
            for j=0 to l2-1 do 
              res.(i) <- res.(i) +. m.(i).(j) *. v.(j)
            done done ;
          res ;;
    val mult_mat_vect : float array array -> float array -> float array = <fun>


  4. Écrire les fonctions utilitaires de manipulation de systèmes : division d'une ligne d'un système par un pivot (Aii), permutation de deux lignes. 

    # let div_syst s i = 
       let p = s.m.(i).(i) 
       in  s.m.(i).(i) <- 1.0 ;
           for j=i+1 to (Array.length s.m.(0)) - 1 do 
             s.m.(i).(j) <- s.m.(i).(j) /. p 
           done ;
           s.v.(i) <- s.v.(i) /. p ;;
    val div_syst : syst -> int -> unit = <fun>
    



    # let permut_syst s i j = 
       let aux1 = s.m.(i) and aux2 = s.v.(i) 
       in s.m.(i) <- s.m.(j)  ;  
          s.v.(i) <- s.v.(j) ;
          s.m.(j) <- aux1 ;  
          s.v.(j) <- aux2 ;;
    val permut_syst : syst -> int -> int -> unit = <fun>


  5. Écrire la diagonalisation d'un système. En déduire une fonction résolvant un système linéaire. 

    # exception Not_linear ;;
    exception Not_linear

    # let trigonalize s = 
       if s.m=[| |] || s.v=[| |] then raise Not_linear ;
       let l = Array.length s.m 
       in if l<>Array.length s.m.(0) || l<>Array.length s.v then raise Not_linear ;
          for i=0 to l-1 do 
            if s.m.(i).(i)=0.0 then 
              begin 
                let j = ref (i+1)
                in while !j<l && s.m.(!j).(i)=0.0 do incr j done ;
                   if !j=l then raise Not_linear ;
                   permut_syst s i !j 
              end ;
            div_syst s i ;
            for j=i+1 to l-1 do
              s.v.(j) <- s.v.(j) -.  s.m.(j).(i) *. s.v.(i) ;
              s.m.(j) <- add_vect s.m.(j) (mult_scal_vect (-. s.m.(j).(i)) s.m.(i))
            done
          done  ;;
    val trigonalize : syst -> unit = <fun>
    



    # let solve s =
       trigonalize s ;
       let l = Array.length s.v
       in let res = Array.copy s.v 
       in for i = l-1 downto 0 do 
            let x = ref res.(i)
            in for j=i+1 to l-1 do x := !x -. s.m.(i).(j) *. res.(j) done ;
               res.(i) <- !x 
          done ;
          res ;;
    val solve : syst -> float array = <fun>


  6. Tester vos fonctions sur les systèmes suivants :

    AX = æ
    ç
    ç
    ç
    è
    10 7 8 7
    7 5 6 5
    8 6 10 9
    7 5 9 10
    		ö
    ÷
    ÷
    ÷
    ø    		 * æ
    ç
    ç
    ç
    è
    x1
    x2
    x3
    x4
    		ö
    ÷
    ÷
    ÷
    ø    		 = æ
    ç
    ç
    ç
    è
    32
    23
    33
    31
    		ö
    ÷
    ÷
    ÷
    ø    		 = Y

    AX = æ
    ç
    ç
    ç
    è
    10 7 8 7
    7 5 6 5
    8 6 10 9
    7 5 9 10
    		ö
    ÷
    ÷
    ÷
    ø    		 * æ
    ç
    ç
    ç
    è
    x1
    x2
    x3
    x4
    		ö
    ÷
    ÷
    ÷
    ø    		 = æ
    ç
    ç
    ç
    è
    32.1
    22.9
    33.1
    30.9
    		ö
    ÷
    ÷
    ÷
    ø    		 = Y

    AX = æ
    ç
    ç
    ç
    è
    10 7 8.1 7.2
    7.08 5.04 6 5
    8 5.98 9.89 9
    6.99 4.99 9 9.98
    		ö
    ÷
    ÷
    ÷
    ø    		 * æ
    ç
    ç
    ç
    è
    x1
    x2
    x3
    x4
    		ö
    ÷
    ÷
    ÷
    ø    		 = æ
    ç
    ç
    ç
    è
    32
    23
    33
    31
    		ö
    ÷
    ÷
    ÷
    ø    		 = Y 

    # let ax1 = { m = [| [| 10.0 ;  7.0 ;  8.0 ;  7.0 |] 
                      ; [|  7.0 ;  5.0 ;  6.0 ;  5.0 |]
                      ; [|  8.0 ;  6.0 ; 10.0 ;  9.0 |]
                      ; [|  7.0 ;  5.0 ;  9.0 ; 10.0 |] |] ;
                 v =    [| 32.0 ; 23.0 ; 33.0 ; 31.0 |]   } ;;
    val ax1 : syst =
      {m=[|[|10; 7; 8; 7|]; [|7; 5; 6; 5|]; [|8; 6; 10; ...|]; ...|]; v=...}

    # let r1 = solve ax1 ;;
    val r1 : float array = [|1; 1; 1; 1|]
    



    # let ax2 = { m = [| [| 10.0 ;  7.0 ;  8.0 ;  7.0 |] 
                      ; [|  7.0 ;  5.0 ;  6.0 ;  5.0 |]
                      ; [|  8.0 ;  6.0 ; 10.0 ;  9.0 |]
                      ; [|  7.0 ;  5.0 ;  9.0 ; 10.0 |] |] ;
                 v =    [| 32.1 ; 22.9 ; 33.1 ; 30.9 |]   } ;;
    val ax2 : syst =
      {m=[|[|10; 7; 8; 7|]; [|7; 5; 6; 5|]; [|8; 6; 10; ...|]; ...|]; v=...}

    # let r2 = solve ax2 ;;
    val r2 : float array = [|9.2; -12.6; 4.5; -1.1|]
    



    # let ax3 = { m = [| [| 10.0  ;  7.0  ;  8.1  ;  7.2  |] 
                      ; [|  7.08 ;  5.04 ;  6.0  ;  5.0  |]
                      ; [|  8.0  ;  5.98 ;  9.89 ;  9.0  |]
                      ; [|  6.99 ;  4.99 ;  9.0  ;  9.98 |] |] ;
                 v =    [| 32.0  ; 23.0  ; 33.0 ; 31.0 |]   } ;;
    val ax3 : syst =
      {m=
        [|[|10; 7; 8.1; 7.2|]; [|7.08; 5.04; 6; 5|]; [|8; 5.98; 9.89; ...|];
          ...|];
       v=...}

    # let r3 = solve ax3 ;;
    val r3 : float array = [|-80.9999999999; 137; -33.9999999999; 22|]


  7. Que peut-on dire des résultats obtenus? Il ne faut jamais négliger les erreurs d'arrondis. Une petite différence dans les données de départ peuvent provoquer de grandes erreurs à l'arrivé.
Précédent Index Suivant