{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Texte d'oral de modélisation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2016-17
1.2  À propos de ce document
1.3  Question de programmation
1.4  Réponse à l'exercice requis
1.4.1  Rapide vérification du dénombrement annoncé
1.4.2  Q.II.1) Décodage d'un symbole
1.4.2.1  Structures et types de données
1.4.2.2  Exemples
1.4.2.3  Algorithme de décodage d'une séquence de caractères
1.4.2.4  Terminaison
1.4.2.5  Correction ?
1.4.2.6  Complexité en temps (et espace)
1.4.2.7  La sous-fonction est_issue_de
1.4.2.8  Fonction finale decodage_une_sequence
1.4.3  Q.II.2) Décodage d'une suite de symboles
1.4.3.1  1. Extraire la taille des séquence du codage de Hamming
1.4.3.2  2. Extraire les sous-séquences
1.4.3.3  3. et 4. Rassembler les morceaux
1.4.3.4  Exemple
1.5  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Préparation à l'agrégation - ENS de Rennes, 2016-17" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- *Date* : 7 avril 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Pour la Science, N°=319 mai 2014, par Jean-Paul Delahaye, \"Couleurs des chapeaux et codes correcteurs d'erreurs\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 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/).\n", "- 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.\n", "- L'implémentation sera faite en OCaml, version 4+ :" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.04.2\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> 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.\n", "> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question de programmation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La question de programmation pour ce texte était donnée en question II.1 et II.2 en page 7 :\n", "\n", "> - \"II.1) Écrire un programme de décodage, qui prend en entrée une suite de caractère codant un symbole (avec une erreur possible), et qui renvoie ce symbole.\"\n", "\n", "> - \"II.2) Écrire un programme qui décode une suite de symboles.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Réponse à l'exercice requis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Rapide vérification du dénombrement annoncé\n", "On veut vérifier, numériquement, que le nombre de stratégies pour le jeu à $n$ joueurs, annoncé à $3^{(n 2^{n-1})}$, vaut bien $531441$ pour $n=3$, et de l'ordre de $1.853 \\; 10^{15}$ pour $n=4$." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val denombrement_regles : float -> float = \n" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let denombrement_regles n =\n", " 3. ** (n *. (2. ** (n -. 1.)));;" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : float = 531441.\n" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "denombrement_regles 3.;;" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : float = 1853020188851841.\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "denombrement_regles 4.;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est bon. C'était inutile, mais autant s'échauffer sur un petit truc rapide et facile." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Q.II.1) Décodage d'un symbole" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Structures et types de données\n", "Comme toujours, on commence par proposer des structures de données (et déclarer des types) adaptés au problème.\n", "\n", "Ici, il nous faut un type de donnée pour les caractères (`0` ou `1`), les suites de caractères (e.g., `0011`), et les symboles (e.g., `'A'`)." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type caractere = int\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type suite_caracteres = caractere array\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type symbole = string\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type caractere = int;;\n", "\n", "type suite_caracteres = caractere array;;\n", "\n", "type symbole = string;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On préfère utiliser des *tableaux* plutôt que des listes puisque leur taille sera fixe, et qu'aucune récursion ne semble utile ici.\n", "\n", "Plutôt que de restreindre les symboles à être des `char` (une seule lettre), on autorise directement des chaînes entières." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ensuite, il faut une structure de données qui représente le *codage de Hamming*, c'est-à-dire la liste des suites de caractère associé à un symbole.\n", "\n", "- Une façon élégante serait d'utiliser des tables d'associations (avec le module `Map`), mais c'est un peu trop compliqué pour l'utilisation simple qu'on va en faire.\n", "- On choisit donc d'utiliser de simples listes de paires `(suite, symbole)`, et l'association d'une suite de caractère à son symbole utilisera `List.assoc`." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type codage = suite_caracteres * symbole\n" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type codage_hamming = codage list\n" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type codage = (suite_caracteres * symbole);;\n", "\n", "type codage_hamming = codage list;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exemples\n", "On peut commencer par définir les exemples du textes (page 5)." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n : int = 7\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite1 : suite_caracteres = [|0; 0; 0; 0; 0; 0; 0|]\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite2 : suite_caracteres = [|1; 1; 1; 1; 1; 1; 1|]\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite3 : suite_caracteres = [|0; 1; 0; 1; 0; 1; 0|]\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite4 : suite_caracteres = [|1; 0; 1; 0; 1; 0; 1|]\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n = 7 ;;\n", "\n", "let suite1 : suite_caracteres = [| 0;0;0;0;0;0;0 |];;\n", "let suite2 : suite_caracteres = [| 1;1;1;1;1;1;1 |];;\n", "let suite3 : suite_caracteres = [| 0;1;0;1;0;1;0 |];;\n", "let suite4 : suite_caracteres = [| 1;0;1;0;1;0;1 |];;" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val codage_ex1 : codage_hamming =\n", " [([|0; 0; 0; 0; 0; 0; 0|], \"A\"); ([|1; 1; 1; 1; 1; 1; 1|], \"B\");\n", " ([|0; 1; 0; 1; 0; 1; 0|], \"C\"); ([|1; 0; 1; 0; 1; 0; 1|], \"D\")]\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let codage_ex1 : codage_hamming = [\n", " (suite1, \"A\");\n", " (suite2, \"B\");\n", " (suite3, \"C\");\n", " (suite4, \"D\")\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'association se fait facilement :" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val quel_symbole : codage_hamming -> suite_caracteres -> symbole = \n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let quel_symbole (code : codage_hamming) (suite : suite_caracteres) : symbole =\n", " List.assoc suite code\n", ";;" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : symbole = \"C\"\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quel_symbole codage_ex1 suite3;; (* = \"C\" *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Algorithme de décodage d'une séquence de caractères\n", "Pourquoi a-t-on besoin de définir un codage (liste des séquences et de leur symbole associé) ?\n", "\n", "Et bien tout simplement parce que l'algorithme de décodage demandé en Q.II.2) nécessite de connaître le codage, pour savoir quelle séquence doit être associé à une séquence donnée (quelle erreur a été commise).\n", "\n", "L'algorithme en question est assez simple à concevoir :\n", "\n", "- Il prendra en entrée : un codage `code` (supposé de Hamming), et une séquence de caractère `seq`.\n", "- Il devra renvoyer un et un seul symbole, associé à la séquence `seq` par le codage de Hamming `code`.\n", "\n", "Il fonctionnera comme ça :\n", "\n", "- Pour chaque séquence `seq_i` du codage, vérifie si `seq` a été obtenue depuis `seq_i` par *une et une seule* modification d'un caractère (fonction `est_issue`),\n", "- si une unique séquence `seq_i` valide a été trouvée, alors le symbole associé par `code` à `seq_i` est celui associé à `seq`,\n", "- par contre, si aucune séquence ou si au moins deux séquences ont été trouvées, alors l'algorithme échouée (avec `Assert_failure`)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Terminaison\n", "L'algorithme décrit ci-dessus ne fait que des boucles `for` sur l'ensemble des séquences du codage de Hamming, et sur les caractères, donc termine (évidemment)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Correction ?\n", "Si la séquence d'entrée a effectivement été obtenue par une modification d'un *seul* caractère d'une des séquence du codage d'entrée, l'hypothèse de Hamming impose que l'algorithme va la trouver, et qu'il n'en existe qu'une.\n", "Donc le symbole renvoyé par l'algorithme décrit ci-dessus est correct." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Complexité en temps (et espace)\n", "- En mémoire, il n'utilise qu'au maximum une mémoire égale à celle de son entrée, donc l'algorithme de décodage d'*une* séquence est linéaire en mémoire.\n", "\n", "- En temps, les deux boucles `for` imbriquées sont en $\\mathcal{O}(N)$ pour la boucle sur les `N` séquences de caractères du codage, et en $\\mathcal{O}(n)$ pour chaque caractère des séquences, soit en $\\mathcal{O}(N n)$ finalement, ce qui est de l'ordre de la taille du codage, donc l'algorithme de décodage d'*une* séquence est aussi linéaire en temps." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### La sous-fonction `est_issue_de`\n", "On écrit chaque morceau, un par un." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a besoin de pouvoir extraire un sous-tableau en enlevant juste une case." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sans_j : 'a array -> int -> 'a array = \n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sans_j tab j =\n", " let n = Array.length tab in\n", " let indice i =\n", " if i < j then i else i + 1\n", " in Array.init (n - 1) (fun i -> tab.(indice i))\n", " (* Autre approche :\n", " let gauche = j\n", " and droite = n - j - 1\n", " in\n", " Array.append\n", " (Array.init gauche (fun i -> tab.(i)))\n", " (Array.init droite (fun i -> tab.(j + i + 1)))\n", " *)\n", "\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Note* : Ici, j'ai préféré utiliser une fonction qui renvoie `tab.(i)` ou bien `tab.(i + 1)` selon que `i < j` ou `j < i`, mais on pourrait aussi faire deux tableaux, et les concaténer avec `Array.append`." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int array = [|1; 2; 3|]\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int array = [|0; 2; 3|]\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int array = [|0; 1; 3|]\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int array = [|0; 1; 2|]\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sans_j [|0;1;2;3|] 0;;\n", "sans_j [|0;1;2;3|] 1;;\n", "sans_j [|0;1;2;3|] 2;;\n", "sans_j [|0;1;2;3|] 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ensuite, il nous faut pouvoir établir que deux tableaux sont égaux (case par case).\n", "C'est déjà le cas, via le test `=` en Caml :" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[|1;2;3|] = [|3;4;1|];;\n", "[|1;2;3|] = [|1;2;3|]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Donc on peut facilement vérifier si une séquence `seq` a été issue depuis `seq_i` par une modification de la case numéro `j` :" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_issue_de_en_j : suite_caracteres -> suite_caracteres -> int -> bool =\n", " \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_issue_de_en_j (seq_i : suite_caracteres) (seq : suite_caracteres) (j : int) =\n", " let seq_i_sansj = sans_j seq_i j in\n", " let seq_sansj = sans_j seq j in\n", " seq_i_sansj = seq_sansj\n", ";;" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres = [|0; 0; 0; 0; 0; 0; 0|]\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite1_delta0 : int array = [|1; 0; 0; 0; 0; 0; 0|]\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite1_delta5 : int array = [|0; 0; 0; 0; 0; 1; 0|]\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite1;;\n", "est_issue_de_en_j suite1 suite1 0;;\n", "\n", "let suite1_delta0 = [|1; 0; 0; 0; 0; 0; 0|];;\n", "\n", "est_issue_de_en_j suite1 suite1_delta0 0;;\n", "est_issue_de_en_j suite1 suite1_delta0 1;;\n", "est_issue_de_en_j suite1 suite1_delta0 4;;\n", "est_issue_de_en_j suite1 suite1_delta0 6;;\n", "\n", "let suite1_delta5 = [|0; 0; 0; 0; 0; 1; 0|];;\n", "\n", "est_issue_de_en_j suite1 suite1_delta5 3;;\n", "est_issue_de_en_j suite1 suite1_delta5 4;;\n", "est_issue_de_en_j suite1 suite1_delta5 5;;\n", "est_issue_de_en_j suite1 suite1_delta5 6;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour finir, il faut vérifier qu'*un et un seul* indice `j` est valide." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_issue_de : suite_caracteres -> suite_caracteres -> bool = \n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_issue_de (seq_i : suite_caracteres) (seq : suite_caracteres) =\n", " let taille = Array.length seq_i in\n", " let bon_j = ref (-1) in\n", " let nb_bon_j = ref 0 in\n", " (* Pour chaque *)\n", " for j = 0 to taille - 1 do\n", " if est_issue_de_en_j seq_i seq j\n", " then begin\n", " bon_j := j;\n", " (* s'ils diffèrent en cette case, ie si une vraie modification était nécessaire *)\n", " if seq_i.(j) != seq.(j) then\n", " incr nb_bon_j;\n", " end;\n", " done;\n", " (* Vérifie qu'au maximum une vraie modification a été utilisée *)\n", " assert (!nb_bon_j <= 1);\n", " (* 0 <= !bon_j, !bon_j, !nb_bon_j *) (* pour tester *)\n", " 0 <= !bon_j\n", ";;" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite1_4delta : int array = [|1; 1; 0; 1; 0; 1; 0|]\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_issue_de suite1 suite1;;\n", "est_issue_de suite1 suite1_delta0;;\n", "est_issue_de suite1 suite1_delta5;;\n", "\n", "let suite1_4delta = [|1; 1; 0; 1; 0; 1; 0|];;\n", "est_issue_de suite1 suite1_4delta;; (* false *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Fonction finale `decodage_une_sequence`\n", "\n", "La même architecture peut-être utilisée :" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val decodage_une_sequence : codage_hamming -> suite_caracteres -> symbole =\n", " \n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let decodage_une_sequence (code : codage_hamming) (seq : suite_caracteres) : symbole =\n", " let bon_indice = ref (-1) in\n", " let nb_bonne_seqi = ref 0 in\n", " (* Pour chaque seq_i du codage de Hamming *)\n", " List.iteri (\n", " fun i (seq_i, _) -> (\n", " if est_issue_de seq_i seq\n", " then begin\n", " bon_indice := i;\n", " incr nb_bonne_seqi;\n", " end;\n", " )\n", " ) code;\n", " (* Vérifie qu'une seule séquence du codage soit valide *)\n", " assert (!nb_bonne_seqi = 1);\n", " (* Associe le symbole de la seule séquence du codage qui soit valide *)\n", " let bonne_seqi = fst (List.nth code !bon_indice) in\n", " quel_symbole code bonne_seqi\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va faire quelques essais, avec le codage de Hamming suivant, défini plus haut :" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : codage_hamming =\n", "[([|0; 0; 0; 0; 0; 0; 0|], \"A\"); ([|1; 1; 1; 1; 1; 1; 1|], \"B\");\n", " ([|0; 1; 0; 1; 0; 1; 0|], \"C\"); ([|1; 0; 1; 0; 1; 0; 1|], \"D\")]\n" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "codage_ex1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va vérifier que pour chacun des 4 séquences, elles sont bien décodées si aucune ou si exactement une case a été changée, mais que le décodage échoue si plus de deux changements ont eu lieu :" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres = [|0; 0; 0; 0; 0; 0; 0|]\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"A\"\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int array = [|1; 0; 0; 0; 0; 0; 0|]\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"A\"\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int array = [|0; 0; 0; 0; 0; 1; 0|]\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"A\"\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite1;;\n", "decodage_une_sequence codage_ex1 suite1;;\n", "\n", "suite1_delta0;;\n", "decodage_une_sequence codage_ex1 suite1_delta0;;\n", "\n", "suite1_delta5;;\n", "decodage_une_sequence codage_ex1 suite1_delta5;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Jusqu'ici tout va bien, et sur un exemple avec quatre modifications, la séquence a été trop modifiée pour être encore identifiée comme `\"A\"` :" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int array = [|1; 1; 0; 1; 0; 1; 0|]\n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"C\"\n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite1_4delta;;\n", "decodage_une_sequence codage_ex1 suite1_4delta;; (* va trouver \"C\" *)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres = [|1; 1; 1; 1; 1; 1; 1|]\n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"B\"\n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite2_delta6 : int array = [|1; 1; 1; 1; 1; 1; 0|]\n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"B\"\n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite2;;\n", "decodage_une_sequence codage_ex1 suite2;;\n", "\n", "let suite2_delta6 = [|1; 1; 1; 1; 1; 1; 0|];;\n", "decodage_une_sequence codage_ex1 suite2_delta6;;" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres = [|0; 1; 0; 1; 0; 1; 0|]\n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"C\"\n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite3_delta3 : int array = [|0; 1; 0; 0; 0; 1; 0|]\n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"C\"\n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite3;;\n", "decodage_une_sequence codage_ex1 suite3;;\n", "\n", "let suite3_delta3 = [|0; 1; 0; 0; 0; 1; 0|];;\n", "decodage_une_sequence codage_ex1 suite3_delta3;;" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres = [|1; 0; 1; 0; 1; 0; 1|]\n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"D\"\n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val suite4_delta1 : int array = [|1; 1; 1; 0; 1; 0; 1|]\n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : symbole = \"D\"\n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suite4;;\n", "decodage_une_sequence codage_ex1 suite4;;\n", "\n", "let suite4_delta1 = [|1; 1; 1; 0; 1; 0; 1|];;\n", "decodage_une_sequence codage_ex1 suite4_delta1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Tout ça semble bien marcher !\n", "\n", "On va rapidement réussir à décoder le message bruité donné en exemple dans le texte." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Q.II.2) Décodage d'une suite de symboles" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cette deuxième étape ne va pas être très compliquée, il s'agit essentiellement d'appliquer l'algorithme précédent à chaque sous-séquence de la séquence donnée.\n", "\n", "Ces sous-séquences sont faciles à extraire depuis la séquence entière, puisque le texte supposait (implicitement) que toutes les séquences d'un codage de Hamming ont la même taille !\n", "\n", "1. on commence par extraire la taille `n` ($n \\geq 1$) des séquences du codage de Hamming,\n", "2. et ensuite on découpe la séquence d'entrée, de taille $n \\times k$, en une *liste* de $k \\geq 1$ sous-séquences, toutes de taille `n`,\n", "3. pour chaque sous-séquence on utilise la fonction `decodage_une_sequence` précédente,\n", "4. on reconstruit une liste de symboles, qu'on renvoie." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1. Extraire la taille des séquence du codage de Hamming" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val taille_sequences_codage : codage_hamming -> int = \n" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let taille_sequences_codage (code : codage_hamming) =\n", " let tailles = List.map (fun (seq, _) -> Array.length seq) code in\n", " let taille = List.hd tailles in\n", " (* On vérifie que toutes les séquence du codage aient cette même taille ! *)\n", " assert (List.for_all (( = ) taille) tailles);\n", " taille\n", ";;" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n1 : int = 7\n" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n1 = taille_sequences_codage codage_ex1 ;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ça marche comme voulu !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 2. Extraire les sous-séquences\n", "On commence par définir l'exemple d'une séquence longue de 4 sous-séquences de tailles $n = 7$, venant de la page 5." ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val seq_ex1 : suite_caracteres =\n", " [|1; 1; 0; 1; 0; 1; 0; 1; 0; 1; 1; 1; 0; 1; 1; 0; 0; 0; 0; 0; 0; 0; 1; 1;\n", " 1; 1; 1; 1|]\n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let seq_ex1 : suite_caracteres = [|\n", " 1;1;0;1;0;1;0;\n", " 1;0;1;1;1;0;1;\n", " 1;0;0;0;0;0;0;\n", " 0;1;1;1;1;1;1\n", "|];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va être malin, et découper en utilisant une combinaison des deux fonctions `Array.init` et `Array.sub`.\n", "\n", "> *Note* : Le second argument de `Array.sub` est la longueur, pas l'indice de fin." ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a array -> int -> int -> 'a array = \n" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int -> (int -> 'a) -> 'a array = \n" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Array.sub;;\n", "Array.init;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Astuce* : Si vous êtes en galère le jour de l'oral, rappelez vous qu'il existe deux modules [`ListLabels`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/ListLabels.html) et [`ArrayLabels`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/ArrayLabels.html) dans la bibliothèque standard, qui sont comme [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html), sauf que les signatures de chaque fonction contiennent des arguments *nommés* :" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a array -> pos:int -> len:int -> 'a array = \n" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int -> f:(int -> 'a) -> 'a array = \n" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ArrayLabels.sub;;\n", "ArrayLabels.init;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`Array.sub tab i n` revient à extraire `tab[i],...,tab[i+n-1]`.\n", "Par exemple, la deuxième sous-séquence de taille `n = 7` du tableau défini ci-dessus est extraite comme ça :" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : caractere array = [|1; 0; 1; 1; 1; 0; 1|]\n" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : caractere array = [|1; 0; 1; 1; 1; 0; 1|]\n" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Array.sub seq_ex1 ((2 - 1) * 7) 7;;\n", "\n", "ArrayLabels.sub seq_ex1 ~pos:((2 - 1) * 7) ~len:7;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est ensuite assez facile. On rajoute un test pour être sûr de ne pas rater des caractères." ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val decoupe_sequence : suite_caracteres -> int -> suite_caracteres list =\n", " \n" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let decoupe_sequence (seq : suite_caracteres) (n : int) : suite_caracteres list =\n", " let len = Array.length seq in\n", " let k = len / n in\n", " assert (len = (k * n)); (* Test, bonus *)\n", " Array.to_list (\n", " Array.init k (fun i ->\n", " Array.sub seq (i * n) n\n", " )\n", " )\n", ";;" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : suite_caracteres list =\n", "[[|1; 1; 0; 1; 0; 1; 0|]; [|1; 0; 1; 1; 1; 0; 1|]; [|1; 0; 0; 0; 0; 0; 0|];\n", " [|0; 1; 1; 1; 1; 1; 1|]]\n" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "decoupe_sequence seq_ex1 n1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ça marche comme voulu." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3. et 4. Rassembler les morceaux" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val decodage_sequences : codage_hamming -> suite_caracteres -> symbole list =\n", " \n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let decodage_sequences (code : codage_hamming) (seq : suite_caracteres) : symbole list =\n", " let n = taille_sequences_codage code in\n", " let seqs = decoupe_sequence seq n in\n", " List.map (decodage_une_sequence code) seqs\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exemple" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : symbole list = [\"C\"; \"D\"; \"A\"; \"B\"]\n" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "decodage_sequences codage_ex1 seq_ex1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a bien retrouvé l'exemple de l'énoncé. Et voilà." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conclusion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voilà pour les deux questions obligatoires de programmation :\n", "\n", "- on a décomposé le problème en sous-fonctions,\n", "- on a essayé d'être fainéant, en réutilisant les sous-fonctions,\n", "- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n", "- on a testé la fonction exigée sur un exemple venant du texte,\n", "- mais on a pas vraiment essayé d'en faire plus (à part le calcul au début).\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml 4.04.2", "language": "OCaml", "name": "ocaml-jupyter" }, "language_info": { "codemirror_mode": "text/x-ocaml", "file_extension": ".ml", "mimetype": "text/x-ocaml", "name": "OCaml", "nbconverter_exporter": null, "pygments_lexer": "OCaml", "version": "4.04.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "610px", "left": "0px", "right": "1223px", "top": "124px", "width": "249px" }, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }