<jupyter_start><jupyter_text>Table of Contents 1&nbsp;&nbsp;Texte d'oral de modélisation - Agrégation Option Informatique1.1&nbsp;&nbsp;Préparation à l'agrégation - ENS de Rennes, 2017-181.2&nbsp;&nbsp;À propos de ce document1.3&nbsp;&nbsp;Question de programmation1.3.1&nbsp;&nbsp;Modélisation1.3.2&nbsp;&nbsp;Exercice1.4&nbsp;&nbsp;Solution1.4.1&nbsp;&nbsp;Types et représentations1.4.2&nbsp;&nbsp;Calcul récursif du nombre &amp;x03C1;" role="presentation">ρρ\rho1.4.3&nbsp;&nbsp;Algorithme demandé pour décorer l'arbre1.5&nbsp;&nbsp;Complexités1.5.1&nbsp;&nbsp;En espace1.5.2&nbsp;&nbsp;En temps1.6&nbsp;&nbsp;Implémentations supplémentaires1.6.1&nbsp;&nbsp;Évaluation des expressions1.6.2&nbsp;&nbsp;Evaluation par lecture postfix et pile1.6.3&nbsp;&nbsp;Affichage dans ce langage de manipulation de registre1.6.4&nbsp;&nbsp;Méthode d'Ershov1.7&nbsp;&nbsp;Conclusion1.7.1&nbsp;&nbsp;Qualités1.7.2&nbsp;&nbsp;Bonus1.7.3&nbsp;&nbsp;Défauts  Texte d'oral de modélisation - Agrégation Option Informatique Préparation à l'agrégation - ENS de Rennes, 2017-18- *Date* : 6 décembre 2017- *Auteur* : [<NAME>](https://GitHub.com/Naereen/notebooks/)- *Texte*: Annale 2018, ["Expressions arithmétiques" (public2018-D1)](http://agreg.org/Textes/public2018-D1.pdf)  À propos de ce document- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.- L'implémentation sera faite en OCaml, version 4+ :<jupyter_code>Sys.command "ocaml -version";;
print_endline Sys.ocaml_version;;<jupyter_output>The OCaml toplevel, version 4.04.2<jupyter_text>---- Question de programmationLa question de programmation pour ce texte était donnée en fin de page 6 : ModélisationOn est libre de choisir l'implémentation qui nous convient pour les expressions arithmétiques sous forme arborescente.Je choisis de ne considérer que les variables et pas les valeurs (on aura des expressions en OCaml comme `F("x")` pour la variable $x$), et uniquement des arbres binaires.Les noeuds `N(t1, op, t2)` sont étiquetées par un opérateur binaire `op`, dont on fournit à l'avance une liste fixée et finie, et les feuilles `F(s)` sont étiquetées par une variable `s`. Exercice> « Écrire une fonction qui reçoit en argument une expression algébrique donnée sous formearborescente et décore cette expression en calculant pour chaque nœud interne quelle estla valeur du paramètre ρ et quelle branche doit être évaluée en premier selon l’algorithmed’Ershov. » ---- SolutionOn va essayer d'être rapide et de faire simple, donc on choisit une algèbre de termes particulière, mais l'algorithme d'Ershov sera implémenté de façon générique (polymorphique, peu importe la valeur de `op`).  Types et représentations<jupyter_code>type operateur = Plus | Moins | MoinsDroite | Mul | Div | DivDroite | Modulo | Expo ;;
(* On utilisera MoinsDroite et DivDroite pour la compilation avec la méthode d'Ershov *)
type ('a, 'b) arbre_binaire = N of (('a,'b) arbre_binaire) * 'b * (('a,'b) arbre_binaire) | F of 'a<jupyter_output><empty_output><jupyter_text>Par exemple pour l'expression $\frac{x - yz}{u - vw}$, c'est-à-dire `(x - y*z)/(u - v*w)` :<jupyter_code>(* exp1 = (x - y*z) *)
let exp1 =
N(
    F("x"),
    Moins,
    N(
        F("y"),
        Mul,
        F("z")
    )
)
;;
(* exp2 = (u - v*w) *)
let exp2 =
N(
    F("u"),
    Moins,
    N(
        F("v"),
        Mul,
        F("w")
    )
)
;;
(* exp3 = (x - y*z)/(u - v*w) *)
let exp3 =
N(
    exp1,
    Div,
    exp2
)<jupyter_output><empty_output><jupyter_text>Calcul récursif du nombre $\rho$C'est assez immédiat, en suivant la définition récursive :$\rho(F) = 0$ et $\rho(N(t_1, t_2)) = \rho(t_1) + 1$ si $\rho(t_1) = \rho(t_2)$ et $\max(\rho(t_1), \rho(t_2))$ si $\rho(t_1) \neq \rho(t_2)$.<jupyter_code>let rec nombre_rho (expr : ('a, 'b) arbre_binaire) : int =
    match expr with
    | F _ -> 0
    | N(t1, _, t2) ->
        let d1, d2 = nombre_rho t1, nombre_rho t2 in
        if d1 = d2 then
            d1 + 1
        else
            max d1 d2
;;<jupyter_output><empty_output><jupyter_text>Pour comparer avec le calcul, plus simple, de la hauteur de l'arbre :<jupyter_code>let rec hauteur (expr : ('a, 'b) arbre_binaire) : int =
    match expr with
    | F _ -> 0
    | N(t1, _, t2) ->
        let d1, d2 = hauteur t1, hauteur t2 in
        1 + (max d1 d2)
;;<jupyter_output><empty_output><jupyter_text>Exemples qui concordent avec le texte :<jupyter_code>let _ = hauteur exp1;;
let _ = nombre_rho exp1;;
let _ = hauteur exp2;;
let _ = nombre_rho exp2;;
let _ = hauteur exp3;;
let _ = nombre_rho exp3;;<jupyter_output><empty_output><jupyter_text>Algorithme demandé pour décorer l'arbre On choisit d'ajouter une *décoration* de type `'c` :<jupyter_code>type ('a, 'b, 'c) arbre_binaire_decore = N2 of ('c * (('a, 'b, 'c) arbre_binaire_decore) * 'b * (('a, 'b, 'c) arbre_binaire_decore)) | F2 of 'a<jupyter_output><empty_output><jupyter_text>On a besoin d'attacher à chaque noeud son paramètre $\rho$ et un drapeau binaire permettant de savoir si l'algorithme d'Ershov indique d'évaluer en premier le sous-arbre gauche (`premier_gauche = true`) ou droite (`= false`).<jupyter_code>type decoration = {
    rho : int;
    premier_gauche : bool;
};;
let rec decore (expr : (('a, 'b) arbre_binaire)) : (('a, 'b, decoration) arbre_binaire_decore) =
    match expr with
    | F v -> F2 v
    | N (t1, o, t2) ->
        let d1, d2 = nombre_rho t1, nombre_rho t2 in
        let d = if d1 = d2 then d1 + 1 else max d1 d2 in
        N2({rho = d; premier_gauche = (d2<= d1)}, (decore t1), o, (decore t2))
;;<jupyter_output><empty_output><jupyter_text>Dans nos exemples, on voit que l'évaluation favorise en premier (avec des `premier_gauche = false`) les expressions les plus profondes (à droite) au sens du paramètre $\rho$ :<jupyter_code>decore exp1;;
decore exp2;;
decore exp3;;<jupyter_output><empty_output><jupyter_text>Complexités  En espaceLes deux fonctions présentées ci-dessus n'utilisent pas d'autre espace que l'arbre décoré, et la pile d'appel récursif.- Le calcul récursif de $\rho(t)$ prend donc un espace proportionnel au nombre d'appel récursif imbriqué, qui est borné par la taille du terme $t$ (définie comme le nombre de noeuds et de feuilles), donc est **linéaire**,- Le calcul de la méthode d'Ershov est elle aussi **linéaire** puisque l'arbre décoré est de même taille que l'arbre initial.  En tempsLes deux fonctions présentées ci-dessus sont **linéaires** dans la taille de l'arbre.  Implémentations supplémentairesOn peut essayer d'implémenter une fonction qui afficherait ceci pour la méthode d'évaluation naturelle :Et ceci pour la méthode d'Ershov :Ce n'est pas trop difficile, mais ça prend un peu de temps :- on va d'abord montrer comment évaluer les expressions, en lisant l'arbre et en effectuant des appels récursifs,- puis on fera un parcours postfix de l'arbre afin d'utiliser l'évaluation avec une pile, avec la stratégie naïve,- et enfin la méthode d'Ershov permettra de réduire la hauteur maximale de la pile, en passant de $h(t)$ (hauteur de l'arbre) à $\rho(t)$,- en bonus, on affichera les instructions style "compilateur à registre", pour visualiser le gain apporté par la méthode d'Ershov.> Bien sûr, tout cela fait beaucoup trop pour être envisagé le jour de l'oral ! Mais un des points aurait pû être implémenté rapidement.  Évaluation des expressionsUn premier objectif plus simple est d'évaluer les expressions, en fournissant un *contexte* (table associant une valeur à chaque variable).<jupyter_code>type ('a, 'b) contexte = ('a * 'b) list;;
let valeur (ctx : ('a, 'b) contexte) (var : 'a) = List.assoc var ctx;;
(* une Hashtbl peut etre utilisee si besoin de bonnes performances *)
let contexte1 : (string, int) contexte = [
    ("x", 1); ("y", 2); ("z", 3);
    ("u", 4); ("v", 5); ("w", 6)
];;
let intop_of_op (op : operateur) : (int -> int -> int) =
    match op with
    | Plus -> ( + )
    | Moins -> ( - )
    | MoinsDroite -> (fun v1 -> fun v2 -> v2 - v1)
    | Mul -> ( * )
    | Div -> ( / )
    | DivDroite -> (fun v1 -> fun v2 -> v2 / v1)
    | Modulo -> ( mod )
    | Expo ->
        (fun v1 -> fun v2 -> int_of_float ((float_of_int v1) ** (float_of_int v2)))
;;
let rec eval_int (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
    match expr with
    | F(s) -> valeur ctx s
    | N(t1, op, t2) ->
        let v1, v2 = eval_int ctx t1, eval_int ctx t2 in
        (intop_of_op op) v1 v2
;;<jupyter_output><empty_output><jupyter_text>Par exemple, $x$ vaut $1$ dans le contexte d'exemple, et $x + y$ vaut $1 + 2 = 3$ :<jupyter_code>let _ = eval_int contexte1 (F("x"));;
let _ = eval_int contexte1 (N(F("x"), Plus, F("y")));;
let _ = eval_int contexte1 exp1;;
let _ = eval_int contexte1 exp2;;
let _ = eval_int contexte1 exp3;;<jupyter_output><empty_output><jupyter_text>On voit la faiblesse de l'interprétation avec des entiers, la division `/` est une division entière !On peut aussi interpréter avec des flottants :<jupyter_code>let contexte2 : (string, float) contexte = [
    ("x", 1.); ("y", 2.); ("z", 3.);
    ("u", 4.); ("v", 5.); ("w", 6.)
];;
let floatop_of_op (op : operateur) : (float -> float -> float) =
    match op with
    | Plus -> ( +. )
    | Moins -> ( -. )
    | MoinsDroite -> (fun v1 -> fun v2 -> v2 -. v1)
    | Mul -> ( *. )
    | Div -> ( /. )
    | DivDroite -> (fun v1 -> fun v2 -> v2 /. v1)
    | Modulo ->
        (fun v1 -> fun v2 -> float_of_int ((int_of_float v1) mod (int_of_float v2)))
    | Expo -> ( ** )
;;
let rec eval_float (ctx : (string, float) contexte) (expr : (string, operateur) arbre_binaire) : float =
    match expr with
    | F(s) -> valeur ctx s
    | N(t1, op, t2) ->
        let v1, v2 = eval_float ctx t1, eval_float ctx t2 in
        (floatop_of_op op) v1 v2
;;<jupyter_output><empty_output><jupyter_text>Par exemple, $x$ vaut $1$ dans le contexte d'exemple, et $x + y$ vaut $1 + 2 = 3$ :<jupyter_code>let _ = eval_float contexte2 (F("x"));;
let _ = eval_float contexte2 (N(F("x"), Plus, F("y")));;
let _ = eval_float contexte2 exp1;;
let _ = eval_float contexte2 exp2;;
let _ = eval_float contexte2 exp3;;<jupyter_output><empty_output><jupyter_text>Evaluation par lecture postfix et pileOn va commencer par lire l'arbre en parcours postfix (cf. [TP2 @ ENS Rennes 2017/18](https://nbviewer.jupyter.org/github/Naereen/notebooks/tree/master/agreg/TP_Programmation_2017-18/TP2__OCaml.ipynb)) et ensuite l'évaluer grâce à une pile.<jupyter_code>type ('a, 'b) lexem = O of 'b | V of 'a;;
type ('a, 'b) parcours = (('a, 'b) lexem) list;;
let parcours_postfix (expr : ('a, 'b) arbre_binaire) : (('a, 'b) parcours) =
    let rec parcours vus expr =
        match expr with
        | F(s) -> V(s) :: vus
        | N(t1, op, t2) -> O(op) :: (parcours (parcours vus t1) t2)
    in
    List.rev (parcours [] expr)
;;<jupyter_output><empty_output><jupyter_text>On le teste :<jupyter_code>parcours_postfix exp1;;
parcours_postfix exp3;;
let eval_int_2 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
    let vus = parcours_postfix expr in
    let pile = Stack.create () in
    let aux lex =
        match lex with
        | V(s) -> Stack.push (valeur ctx s) pile;
        | O(op) ->
            let v1, v2 = Stack.pop pile, Stack.pop pile in
            Stack.push ((intop_of_op op) v1 v2) pile;
    in
    List.iter aux vus;
    Stack.pop pile
;;<jupyter_output><empty_output><jupyter_text>Par exemple, $x - y*z$ avec $x = 1, y = 2, z = 3$ vaut $1 - 2 * 3 = -5$ :<jupyter_code>let _ = exp1 ;;
let _ = eval_int_2 contexte1 exp1;;
let _ = exp2;;
let _ = eval_int_2 contexte1 exp2;;<jupyter_output><empty_output><jupyter_text>On peut maintenant faire la même fonction mais qui va en plus afficher l'état successif de la pile (avec des valeurs uniquement).<jupyter_code>let print f =
    let r = Printf.printf f in
    flush_all();
    r
;;
let print_pile pile =
    print "\nPile : ";
    Stack.iter (print "%i; ") pile;
    print "."
;;
let eval_int_3 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
    let vus = parcours_postfix expr in
    let pile = Stack.create () in
    let aux lex =
        print_pile pile;
        match lex with
        | V(s) -> Stack.push (valeur ctx s) pile;
        | O(op) ->
            let v1, v2 = Stack.pop pile, Stack.pop pile in
            Stack.push ((intop_of_op op) v1 v2) pile;
    in
    List.iter aux vus;
    Stack.pop pile
;;
let _ = exp1 ;;
let _ = eval_int_3 contexte1 exp1;;
let _ = exp3;;
let _ = eval_int_3 contexte1 exp3;;<jupyter_output><empty_output><jupyter_text>> Il y a un soucis dans l'ordre d'affichage des lignes, dû à Jupyter et pas à notre fonction. On vérifie qu'on utilise au plus 4 valeurs sur la pile, comme représenté dans la figure de l'énoncé :  Affichage dans ce langage de manipulation de registreOn ne va pas trop formaliser ça, mais juste les afficher...<jupyter_code>let print_aff (line : int) (i : int) (s : string) : unit =
    print "\n%02i: R[%d] := %s ;" line i s;
;;
let string_of_op (op : operateur) : string =
    match op with
    | Plus -> "+"
    | Moins | MoinsDroite -> "-"
    | Mul -> "*"
    | Div | DivDroite -> "/"
    | Modulo -> "%"
    | Expo -> "^"
;;
let print_op (line : int) (i : int) (j : int) (k : int) (op : operateur) : unit =
    match op with
    | MoinsDroite | DivDroite -> (* on gère ici les opérateurs "inverses" *)
        print "\n%02i: R[%d] := R[%d] %s R[%d] ;" line i k (string_of_op op) j;
    | _ ->
        print "\n%02i: R[%d] := R[%d] %s R[%d] ;" line i j (string_of_op op) k;
;;
let eval_int_4 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
    let vus = parcours_postfix expr in
    let pile = Stack.create () in
    let ligne = ref 0 in
    let aux lex =
        incr ligne;
        match lex with
        | V(s) ->
            Stack.push (valeur ctx s) pile;
            print_aff !ligne ((Stack.length pile) - 1) s;
        | O(op) ->
            let v1, v2 = Stack.pop pile, Stack.pop pile in
            Stack.push ((intop_of_op op) v1 v2) pile;
            print_op !ligne ((Stack.length pile) - 1) ((Stack.length pile) - 1) (Stack.length pile) op;
    in
    List.iter aux vus;
    Stack.pop pile
;;<jupyter_output><empty_output><jupyter_text>Essayons ça :<jupyter_code>let _ = exp1 ;;
let _ = eval_int_4 contexte1 exp1;;
let _ = exp3;;
let _ = eval_int_4 contexte1 exp3;;<jupyter_output><empty_output><jupyter_text>Méthode d'ErshovEnfin, on va générer, en plus de l'évaluation, un affichage comme celui qu'on voulait, qui montre les affectations dans les registres, et permettra de visualiser que la méthode d'Ershov utilise un registre de moins sur le terme exemple qui calcule $(x - y*z)/(u - v*w)$. On rappelle qu'on a obtenu un arbre binaire décoré, représenté comme tel :<jupyter_code>decore exp1;;<jupyter_output><empty_output><jupyter_text>On modifie notre parcours postfix pour prendre en compte la décoration et savoir si on calcul d'abord le sous-arbre gauche ou droit.<jupyter_code>let parcours_postfix_decore (expr : ('a, 'b, decoration) arbre_binaire_decore) : (('a, 'b) parcours) =
    let rec parcours vus expr =
        match expr with
        | F2(s) -> V(s) :: vus
        | N2(dec, t1, Moins, t2) when dec.premier_gauche = false ->
            O(MoinsDroite) :: (parcours (parcours vus t2) t1)
        | N2(dec, t1, MoinsDroite, t2) when dec.premier_gauche = false ->
            O(Moins) :: (parcours (parcours vus t2) t1)
        | N2(dec, t1, Div, t2) when dec.premier_gauche = false ->
            O(DivDroite) :: (parcours (parcours vus t2) t1)
        | N2(dec, t1, DivDroite, t2) when dec.premier_gauche = false ->
            O(Div) :: (parcours (parcours vus t2) t1)
        | N2(dec, t1, op, t2) when dec.premier_gauche = false ->
            O(op) :: (parcours (parcours vus t2) t1)
        | N2(_, t1, op, t2) ->
            O(op) :: (parcours (parcours vus t1) t2)
    in
    List.rev (parcours [] expr)
;;
let eval_int_ershov (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
    let vus = parcours_postfix_decore (decore expr) in
    let pile = Stack.create () in
    let ligne = ref 0 in
    let aux lex =
        incr ligne;
        match lex with
        | V(s) ->
            Stack.push (valeur ctx s) pile;
            print_aff !ligne ((Stack.length pile) - 1) s;
        | O(op) ->
            let v1, v2 = Stack.pop pile, Stack.pop pile in
            Stack.push ((intop_of_op op) v1 v2) pile;
            print_op !ligne ((Stack.length pile) - 1) ((Stack.length pile) - 1) (Stack.length pile) op;
    in
    List.iter aux vus;
    Stack.pop pile
;;<jupyter_output><empty_output><jupyter_text>Essayons ça :<jupyter_code>let _ = exp1 ;;
let _ = eval_int_ershov contexte1 exp1;;
let _ = exp3;;
let _ = eval_int_ershov contexte1 exp3;;<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13221223543055957, 'fraction_numerical': 0.021513482168744564, 'mean_word_length': 3.4783173201765774, 'pattern_counts': {'":': 0, '<': 90, '<?xml version=': 0, '>': 160, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '464430', 'license': 'MIT', 'n_tokens_mistral': 6773, 'n_tokens_neox': 6671, 'n_words': 1988, 'path': 'agreg/public2018_D1.ipynb', 'repo_name': 'doc22940/notebooks-2', 'size': '17252'}