Épreuve d'Informatique MP

L'usage de calculatrices est interdit.

AVERTISSEMENT

• L'épreuve est composée de 4 exercices, totalement indépendants. L'exercice 1, sur les bases de données, demande d'écrire des requêtes SQL. Les exercices suivants demandent d'écrire du code Caml.
• Un candidat pourra toujours admettre le résultat des questions qu'il n'a pas faites pour faire les questions suivantes.

Exercice 1

1. Écrire une requête donnant la table des prénoms féminins et le nombre de filles nées avec ce prénom. Écrire une requête donnant la table des prénoms masculins ainsi que le nombre de garçons nés avec ce prénom.

On supposera par la suite que cette requête est sauvegardé sous le nom epicene.
3. Écrire une requête renvoyant la table des prénoms exclusivement féminins. Écrire une requête renvoyant la table des prénoms exclusivement masculins.

Exercice 2

1. Quelle est la complexité en temps de pow?
2. Que dire de l'occupation de la mémoire lors de l'exécution de pow ? Estimer la complexité en mémoire (on dit aussi en espace) de pow.

Python

def f(n):
    k=0
    while 2**k<=n:
        k=k+1
    return k

let f n =
    let k=ref 0 in
    while pow 2 !k <= n do
        k:= !k+1 done;
    !k;;

4. Décrire l'exécution de f (3) en Python.
5. Que calcule la en Python pour un entier strictement positif?
6. Dans cette question, nous supposons que n prend des valeurs entières, strictement positives, et représentables en Caml.
   (a) Pour quelles valeurs de n les fonctions f en Python et en Caml renvoient le même résultat?
   (b) Que se passe-t-il, pour les autres valeurs de n , lors du calcul de f n en Caml?
7. Réécrire la fonction de Caml pour qu'elle renvoie le même résultat que la fonction Python sur tous les entiers strictement positifs représentables en Caml.

Exercice 3

• m.etats représente l'ensemble des états de m,
• m. init représente l'ensemble des états initiaux de m ;
• m.final l'ensemble de ses états finaux,
• m. trans sa fonction de transition qui à chaque couple associe l'ensemble des états accessibles à partir de l'état q en lisant le caractère x .

Par exemple, considérons l'automate suivant:

1. L'automate est-il déterministe?
2. Écrire une fonction max_card : ('a, set) dict int qui étant donné un dictionnaire d'ensembles, renvoie le cardinal maximal des ensembles stockés dans le dictionnaire.
3. Écrire une fonction est_deterministe : auto -> bool qui renvoie true si l'automate donné en argument est déterministe et false sinon.
4. Considérons le code incomplet suivant:

let etats_suivants m s x = 1
let rec parcours_clefs clefs acc = match clefs with 2
    | [] -> acc 3
    | (etat,y)::r -> if ................ 4
        then ............. 5
        else .............. 6
in parcours_clefs (keys m.trans) empty;; 7

Exercice 4

1. Écrire une fonction distance : int -> int -> float. distance i j calcule la distance entre les fromages de numéros i et j.
2. Définir en Caml une matrice globale dist, telle que, pour tous fromages i et j, dist. (i). (j) est égal à la distance entre les fromages i et j.
3. Écrire une fonction dist_arbr : arbre -> arbre -> float qui étant donné deux arbres de fromages, calcule la distance entre ces deux arbres.
4. La fusion de deux arbres et est un arbre de la forme ci-après où la racine est étiquetée par , la distance entre et .