# Sujet Mines 2019
En faisant le sujet, j'ai aussi parcouru la correction, j'ai ici noté quelques petits points mineurs.

Sur le site math-concours-CPGE, vous avez laissé "D.S. Révisions 1" dans le titre, et "D.S. Révisions 1" et "Option info MP1" sur chaque page.

## Coquilles du corrigé / Remarques
- Question 5 : ~~Il manque un `|]`. De plus, OCaml ne permet par de créer une variable commençant par une majuscule (réservé à d'autres usages). Cela devrait plutôt être `let q = (2, [|(0, 1); (1, 0)|], [|false; true|]);;`~~ Maintenant, c'est l'inverse, il y a 2 `|]` et plus de parenthèse fermante.
<!-- - Question 7, avant-dernière ligne de la fonction : il y a un paramètre en trop à `aux 0 [];`, il faut juste `aux 0;` -->
<!-- - Question 8, ligne 12 : il est écrit `term1.(s) <- term.(t);`, or `term` n'existe pas, il faut plutôt `term1.(s) <- f.(t);` -->
<!-- - Question 12, vous avez écrit $\mathcal{A}_2$ vers $\mathcal{A}_2$, au lieu de $\mathcal{A}_5$ vers $\mathcal{A}_2$, tel que vous l'avez écrit juste après. -->
<!-- - Question 16 : $\delta^*_\mathcal{B}(\varphi(i_\mathcal{A},u))$ : le $u$ ne devrait pas être dans la parenthèse, c'est plutôt $\delta^*_\mathcal{B}(\varphi(i_\mathcal{A}),u)$ -->
<!-- - Question 17 : faux dans certains cas, voir ci-dessous. `ssi` est-elle indispenssable ? La comparaison fonctionne aussi sur les booléens, on peut écrire `if f1.(s) = f2.(t)`. -->
<!-- - Question 21, 2em ligne du 1), une parenthèse fermante en trop au début de la ligne. -->
<!-- - Question 28, deuxième code, ligne 9 : cela devrait plutôt être `then union uf i j done done;`, la ligne actuelle n'a pas trop de sens. -->
<!-- - Questions 33, 35 : ce ne sont pas E et H, mais O et P -->
<!-- - Question 36, 3em code, l'avant-dernière ligne devrait être `then visiter (p, q) done done;` car il faut donner un tuple à la fonction. -->

## Erreurs

### Question 17

Le code ne fonctionne pas dans certains cas : la vérification de `traiter` n'est faite que si un arc pointe vers le noeud. Or même si les automates sont accessibles, l'état initial n'a pas forcément d'arc pointant vers lui, ce qui fait que les automates suivants sont considérés comme équivalents par cette fonction :

let auto0 = (1, [| (0, 0) |], [|true|]);;
let auto00 = (1, [| (0, 0) |], [|false|]);;

Alors que le premier reconnait n'importe quel mot, le second aucun. La version du code que j'ai codée, dans la section suivante, plus courte, palie aussi ce problème (paliable également en remplaçant la ligne 6 par
`let existe = ref (f1.(0) = f2.(0)) in`)

### Question 27

Pour la fonction maxi_tableau, ligne 5, vous avez écrit `:!` au lieu de `:=`.

Pour la seconde fonction, vous utilisez `None`, donc le type option, mais vous n'utilisez pas `Some <something>` lorsque vous assignez une valeur, cela provoque des erreurs. De plus, vous ne mettez pas `!` devant `subs` à 2 lignes différentes, provoquant ainsi une erreur. Je ne conaissait pas `incr`, par contre, c'est sympa comme fonction ! (Mais peut-on l'utiliser au concours ?). Et à la dernière ligne, il y a un `!` alors que ce n'est pas une ref. Voici donc une version qui fonctionne :

let renomme_d13 t =
    let n = Array.length t in
    let maxi = maxi_tableau t in
    let code = Array.make (maxi + 1) None in
    let out = Array.make n (-1) in
    let subs = ref 0 in
    for i = 0 to (n-1) do
        let k = t.(i) in
        match code.(k) with
        | None -> code.(k) <- Some !subs;
            out.(i) <- !subs;
            incr subs
        | Some p -> out.(i) <- p done;
    out;;

La même avec des fonctions plus "basiques", mais certes moins jolie. J'ai aussi quelques questions sur cette question et la solution, posée dans la section suivante.

let renomme_d13_2 t =
    let n = Array.length t in
    let maxi = maxi_tableau t in
    let code = Array.make (maxi + 1) (-1) in
    let out = Array.make n (-1) in
    let subs = ref 0 in
    for i = 0 to (n-1) do
        let k = t.(i) in
        match code.(k) with
        | p when p = -1 -> code.(k) <- !subs;
            out.(i) <- !subs;
            subs := !subs + 1
        | p -> out.(i) <- p done;
    out;;

<!-- ### Question 34

Votre solution n'est, a moins erreur de ma part, pas juste car Q et R ne sont pas finaux, ni l'un ni l'autre. On le voit d'ailleurs sur votre schéma au dessus. Mais on peut proposer :

Si un tel morphisme $\psi$ existe, on a une absurdité car le mot 'bab' est reconnu par le second automate uniquement. En effet, dans un tel cas, $S=\delta_1^*(P, bab)$. Donc $\psi(S)=\delta_2^*(\psi(P), bab)=\delta_2^*(\psi(R), b)=\delta_2^*(\psi(Q), b)=\psi(O)$. On a maintenant bien un état final dont l'image ne serait pas un état final. -->

## Solutions alternatives

<!-- ### Question 13
Pour la quesiton 13, j'ai raisonné sur un mot, je ne sais pas si c'est un plus simple ou juste exactement pareil, car au final c'est le même raisonnement. Ça évite juste d'avoir à poser les ensemble de tous les mots de longeur $n$, alors j'ai mis ça là.

---

On considère un morphisme $\varphi$ de l'automate $\mathcal{A}$ vers l'automate $\mathcal{B}$, et $u\in(a+b)*=x_1\dots x_n$.

On définit $e_0=i_\mathcal{A}$, et $e_{i}=\delta_\mathcal{A}(e_{i-1},x_{i})$ pour $0<i\leqslant n$, qui est le chemin de $\mathcal{A}$ correspondant au mot $u$. On pose de même $e'_0=i_\mathcal{B}$, et $e'_{i}=\delta_\mathcal{B}(e'_{i-1},x_{i})$. Alors :

- $\varphi(e_0)=e'_0$ selon **(2)**.
- Pour $i>1$, avec **(3)**, $e'_{i-1}=\varphi(e_{i-1})\implies e'_i=\delta_\mathcal{B}(\varphi(e_{i-1}),x_{i})=\varphi(\delta_\mathcal{A}(e_{i-1},x_{i}))=\varphi(e_i)=e_i$
- On a donc par récurrence que $e'_n=\varphi(e_n)$

Alors $u\in \mathcal{L}[\mathcal{A}]\iff e_n\in F_\mathcal{A} \iff \varphi(e_n)\in F_\mathcal{B}\ \ \ \ \ \ \ \ \ \ \text{Selon (4)}\\
\iff e'_n\in F_\mathcal{B} \iff u\in \mathcal{L}[\mathcal{B}]$
D'où $\mathcal{L}[\mathcal{A}]=\mathcal{L}[\mathcal{B}]$ -->

### Question 17

Une solution plus légère permet de se passer de la fonction `traiter` :

let existe_morphisme aut1 aut2 =
    let (n1, delta1, f1) = aut1 in
    let (n2, delta2, f2) = aut2 in
    let phi = Array.make n1 (-1) in
    let rec build i j =
        if phi.(i) = -1 then (
            phi.(i) <- j;
            let a1, b1 = delta1.(i) in
            let a2, b2 = delta2.(j) in
            ( f1.(i) = f2.(j) && (build a1 a2) && (build b1 b2) )
        ) else (phi.(i) = j)
    in (build 0 0), phi;;

Elle fonctionne sur le même principe, mais effectue les vérifications au moment de l'accès au noeud, et non pas de la part du parent sur les fils directement, ce qui élimine le problème de la racine, et simplifie le code, tout en permettant de se débarasser des références.

### Question 24

Il est tout aussi simple de rédiger par équivalence directement avec la propriété **(3)**:
$s_i\in F_\mathcal{B} \iff \varphi(s_i)\in F_\mathcal{A} \iff \varphi(s_{i+1})\in F_\mathcal{A} \iff s_{i+1}\in F_\mathcal{B}$

### Question 27

Pour cette question, vous parlez de temps linéaire. Or la question ne suppose pas *a priori* que la valeur maximale serait linéaire par rapport à la taille du tableau. Si ce n'est pas le cas, cela ferait exploser la complexité pour par exemple `[| 1000000000 |]`. Bien sûr, c'est pour des cas où cette fonction est linéaire que le sujet demande de la construire. Ainsi, peut-on dans ce sujet simplement assumer que ça sera le cas ? Ou préciser que c'est linéaire *dans le contexte du sujet*, sur notre copie quand on le fait ?

Autrement, on peut garentir $O(nl)$ facilement, avec une liste des valeurs déjà rencontrées, et faire un $O(n)$ (envirion) avec une hasmap. Mais cette deuxième solution est bien sûr plus complexe que ce qui est attendu, j'imagine.

### Question 28

La solution que vous proposez est en $O(n^2\ln(n))$, mais il existe une solution tout aussi simple, reposant aussi sur l'union-find, en $O(n\ln(n))$, simplement en remarquant que pour chaque noeud, il suffit de le fusionner avec ceux ayant la même image par phi, et ceux ayant la même image par psi, ayant déjà été rencontrés, ce que l'on peut faire avec une table d'occurence. Les deux tableaux `phi_roots` et `psi_roots` de ma solution marquent un noeud de la composante déjà vu (ou -1) ayant la même image par phi, ou psi. Cela donne ce code :

let rec uf_find i neta =
    if neta.(i) <> i then neta.(i) <- uf_find neta.(i) neta;
    neta.(i);;

let union_group i f f_roots neta =
    if f_roots.(f.(i)) = -1 then 
        f_roots.(f.(i)) <- i
    else neta.(uf_find i neta) <- uf_find f_roots.(f.(i)) neta;;

let relation phi psi =
    let n = Array.length phi in
    let neta = Array.init n (fun i -> i) in
    let phi_roots = Array.make n (-1) in
    let psi_roots = Array.make n (-1) in
    for i=0 to (n-1) do
        union_group i phi phi_roots neta;
        union_group i psi psi_roots neta
    done;
    renomme (Array.init n (fun i -> uf_find i neta));;

### Question 36

On peut rendre plus simple et lisible le premier code en remplaçant, à la fin `if f.(p) && (not f.(q)) || (not f.(p)) && f.(q)` par `if f.(p) <> f.(q)`. Pareil pour le 3em.

### Question 37

En réutilisant les fontions `renomme` et `maxi_tableau` précédentes, et en faisant simplement deux boucles imbriquées, ont peut construire plus simplement les classes d'équivalence. Tous les éléments vont pointer vers le dernier de leur classe d'équivalence dans l'ordre des éléments :

let reduit aut =
    let aut = partie_accessible aut in
    let (n, delta, f) = aut in
    let relations = table_de_predecesseurs aut in
    let numero = Array.make n 0 in
    for i=0 to (n-1) do
        for j=0 to (n-1) do
            if not relations.(i).(j) then numero.(i) <- j
    done done; print_int_tab numero;
    let numero = renomme numero in
    let n2 = (maxi_tableau numero)+1 in
    let delta2 = Array.make n2 (-1, -1) in
    let f2 = Array.make n2 false in
    for i=0 to (n-1) do
        let a, b = delta.(i) in
        delta2.(numero.(i)) <- (numero.(a), numero.(b));
        f2.(numero.(i)) <- f.(i)
    done;
    (n2, delta2, f2);;

De plus, dans la question il n'est pas précisé que l'automate est accessible, et on a déjà codé une fonction pour le rendre accessible. Vous avez suposé qu'il l'était, doit-on supposer qu'il l'est nécessairement ? Dans le doute, j'ai mis au début `let aut = partie_accessible aut in`, de sorte que la fonction marche avec n'importe quel automate et retourne le minimal.