E3A Option Informatique MP 2018Sujet

CONCOURS ARTS ET MÉTIERS ParisTech - ESTP - POLYTECH

Épreuve d'Informatique MP

L'usage de calculatrices est interdit.

AVERTISSEMENT

Exercice 1 (Python)

1. Pour quelles valeurs de n dans ℤ la fonction fun2 termine-t-elle? Même question pour fun3.

def fun1 (n): def fun2 (n): def fun3 (n):
    while n != 10: if n % 2 == 0: S = 0
        n = n + 1 return 0 while n != 0 :
            else : S = S + n
                while True: n = n - 2
                    n = n + 1 return S

2. Détailler l'exécution de fun3(10).
3. Écrire en Python une fonction ForEver (n) qui ne termine jamais.

Problématique

Exercice 2 (Caml)

1. Expliquer succintement comment, à partir de l'écriture en base deux de n ∈ ℕ^⋆, on peut lire la valuation et le résidu de n.
2. L'entier 192 s'écrit en base deux 11000000 . Donner sa valuation et son résidu.
3. Écrire en Caml une fonction residu : int -> int qui prend en argument un entier positif ou nul et renvoie son résidu.

Exercice 3 (Caml)

1. Écrire la matrice d'adjacence du graphe ci-dessus.
2. Écrire en Caml une fonction chemin : int vect vect -> int list -> bool qui prend en entrée la matrice d'adjacence d'un graphe et un chemin (une liste de sommets du graphe) et qui vérifie si ce chemin est possible dans le graphe. Par exemple, sur le graphe ci-dessus, avec le chemin [ 2; 1; 0; 4 ] la fonction chemin doit renvoyer false car les sommets 1 et 0 ne sont pas connectés. Avec le chemin [ 1; 2; 3 ] la fonction chemin doit renvoyer true car les sommets 1 et 2 sont connectés, ainsi que les sommets 2 et 3.

Exercice 4 (SQL)

1. Écrire une requête SQL renvoyant la table des chamelles (chameaux femelles).

2. Écrire une requête SQL renvoyant la table des bonobos mâles vivant en Asie.

3. Écrire une requête renvoyant la liste des pays ayant des zoos sur plusieurs continents.

Exercice 5 (Caml)

1. Considérons la formule " X ∨ (Y ∧ Z) " et notons-la φ_0.
   (a) Dessiner l'arbre correspondant à φ_0.
   (b) Écrire φ_0 en Caml en utilisant le type fp.

• Si X est une variable propositionnelle, alors X est une DVP.
• Si φ et ψ sont des DVP alors φ ∨ ψ est aussi une DVP.

2. Écrire en Caml une fonction dvp : fp -> bool prenant en argument une formule positive f et renvoyant true si et seulement si f est une DVP.

• Si φ est une DVP alors φ est une FNCP.
• Si φ et ψ sont des FNCP, alors φ ∧ ψ aussi.

3. Écrire en Caml une fonction fncp de type fp -> bool prenant en argument une formule positive f et renvoyant true si et seulement si f est une FNCP.

let rec norm f = match f with 0
    VAR _ -> f
    1
    | OU ET (norm a, norm b) -> E)
    | | | | | | | | | | (a,c) ) ) , norm (OU }
    | OU (a,b) -> let c = OU( norm a, norm b) in 5
        if f=c

        else norm c;; 8

4. Expliquer brièvement pourquoi si f est une FNCP alors norm f termine et renvoie f.
5. Montrer que si norm f termine, alors elle renvoie une FNCP.
6. Exhiber, sans démonstration, une fonction simple λ de l'ensemble des formules dans ℕ telle que pour toutes formules a, b, c et d :

• λ(a ∨ b) = λ(a ∧ b) > max(λ(a), λ(b)),
• λ((a ∧ b) ∨ c) = λ(c ∨ (a ∧ b)) > max(λ(a ∨ c), λ(b ∨ c)),
• Si λ(a) ⩾ λ(c) et λ(b) ⩾ λ(d) alors λ(a ∨ b) ⩾ λ(c ∨ d).

• μ(X) = 0 si X est une variable propositionnelle,
• μ(φ ∧ ψ) = 1 pour toutes formules φ et ψ,
• μ(φ ∨ ψ) = min(μ(φ), μ(ψ)) pour toutes formules φ et ψ.

7. On considère une formule f telle que :

• f correspond au cas de filtrage (pattern matching en anglais) de la ligne 5 mais ne correspond à aucun des cas des lignes 1 à 4,
• Le calcul de c à la ligne 5 termine.
  (a) Montrer que si f ≠ c alors μ(f) > μ(c).
  (b) Montrer que λ(f) ⩾ λ(c).

8. Démontrer soigneusement que norm termine sur toutes les formules positives.