<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, 2016-171.2&nbsp;&nbsp;À propos de ce document1.3&nbsp;&nbsp;Question de programmation1.4&nbsp;&nbsp;Réponse à l'exercice requis1.4.1&nbsp;&nbsp;Structure de données1.4.2&nbsp;&nbsp;Exemples1.4.3&nbsp;&nbsp;Fonctions intermédiaires1.4.4&nbsp;&nbsp;Résolution1.5&nbsp;&nbsp;Bonus ?1.6&nbsp;&nbsp;Conclusion  Texte d'oral de modélisation - Agrégation Option Informatique  Préparation à l'agrégation - ENS de Rennes, 2016-17 - *Date* : 29 mai 2017- *Auteur* : [<NAME>](https://GitHub.com/Naereen/notebooks/)- *Texte*: [Circuits (public2010-D1)](http://agreg.org/Textes/public2010-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";;<jupyter_output>The OCaml toplevel, version 4.04.2<jupyter_text>> Notez que certaines fonctions des modules usuels [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) ne sont pas disponibles en OCaml 3.12.> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers. ----  Question de programmation La question de programmation pour ce texte était donnée en page 6, et était assez courte :> "Écrire un programme prenant en entrée deux nombres $a$, $b$, représentés par des écritures en base $B$ avec des chiffres signés entre $-\beta$ et $\beta$, et retournant un résultat ternaire indiquant si $a  b$. On supposera que $\beta < B < 2 \beta$, et que les écritures de $a$ et $b$ ont même longueur." ----  Réponse à l'exercice requis  Structure de donnéesPour représenter ces entiers, on stocke leur base et le tableau de leur coefficients.<jupyter_code>type entier = {
    base : int;
    t : int array
}
;;<jupyter_output><empty_output><jupyter_text>Exemples<jupyter_code>let quatre = {
    base = 10;
    t = [| 4 |]
}<jupyter_output><empty_output><jupyter_text>Le "bit" de poids faible est, par convention du texte, à gauche au début du tableau :<jupyter_code>let quarantedeux = {
    base = 10;
    t = [| 2; 4 |]
}<jupyter_output><empty_output><jupyter_text>Avec l'exemple du texte :<jupyter_code>let n2006 = {
    base = 10;
    t = [| 6; 0; 0; 2 |]
}
let n2006 = {
    base = 10;
    t = [| 6; 0; 0; 2 |]
}
let n2006_2 = {
    base = 10;
    t = [| -4; 1; 0; 2 |]
}
let n2006_3 = {
    base = 10;
    t = [| 6; 0; 0; -8; 1 |]
}
let n2006_4 = {
    base = 10;
    t = [| -4; 1; 0; -8; 1 |]
}<jupyter_output><empty_output><jupyter_text>Fonctions intermédiaires Caml, dans sa toute beauté, ne permet pas de calculer $x^k$ facilement si $x$ est entier...<jupyter_code>let rec puissance x k = 
    match k with
    | 0 -> 1
    | 1 -> x
    | k when k mod 2 = 0 ->
        (* x^k = x^(k/2 * 2) = (x^2)^(k/2) *)
        puissance (x * x) (k / 2)
    | k ->
        (* x^k = x^((k-1)/2 * 2 + 1) = x * (x^2)^((k-1)/2) *)
        x * (puissance (x * x) ((k - 1) / 2))
;;
puissance 10 0;;
puissance 10 1;;
puissance 10 2;;
puissance 10 3;;
puissance 10 4;;<jupyter_output><empty_output><jupyter_text>On va convertir un entier représenté sous cette forme en un entier machine de Caml :<jupyter_code>let valeur {base=b; t=t} =
    let v = ref 0 in
    let n = Array.length t in
    for k = 0 to n - 1 do
        v := !v + (t.(k) * (puissance b k))
    done;
    !v
;;
valeur quatre;;
valeur quarantedeux;;
valeur n2006;;
valeur n2006_2;;
valeur n2006_3;;
valeur n2006_4;;<jupyter_output><empty_output><jupyter_text>Résolution Le texte ne demandait *pas* une approche particulièrement maligne, donc on va naïvement répondre à la question : on convertit les deux entiers en leur valeur, on les compare et VOILÀ.<jupyter_code>let compare_entiers (a : entier) (b : entier) : int =
    let va = valeur a in
    let vb = valeur b in
    compare va vb
;;
compare_entiers quatre quarantedeux;;
compare_entiers quarantedeux quatre;;
compare_entiers quatre quatre;;
compare_entiers quarantedeux quarantedeux;;
compare_entiers n2006 quarantedeux;;<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1317928968763372, 'fraction_numerical': 0.03958065896448438, 'mean_word_length': 4.0, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 40, 'https://': 4, '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': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '271811', 'license': 'MIT', 'n_tokens_mistral': 1911, 'n_tokens_neox': 1782, 'n_words': 525, 'path': 'agreg/Circuits.ipynb', 'repo_name': 'doc22940/notebooks-2', 'size': '4681'}