Exercice 1 : Parcoursup.
On demande aux responsables du futur portail Descartes (remplaçant la L1 informatique) de l'UFR Sciences d'Aix-Marseille Université de classer les candidats ayant fait vœux d'y entrer. Les places disponibles seront alors proposées prioritairement aux candidats les mieux classés.
On connait pour chaque candidat son nom, sa date de naissance et ses notes au baccalauréat dans chaque matière (chaque matière est identifiée par une chaîne de caractères). Proposer un type dont les valeurs représentent les candidats.
On voudra enregistrer pour chaque candidat des informations diverses, comme par exemple son classement ou l'état de sa demande. Pour cela, nous devons disposer d'une structure de dictionnaire. Comment construire un type des dictionnaires de candidats (on pourra supposer que les candidats ont des noms distincts) ?
List.sort est la fonction de tri standard sur les listes. Implémenter une fonction de tri ayant le type suivant :
val sort :
by:('elt -> 'comparable)
-> cmp:('comparable -> 'comparable -> int)
-> 'elt list -> 'elt list
Il a été proposé de classer les étudiants selon une note calculée comme suit : trois fois la note de mathématiques plus deux fois celles de physique plus une fois celle de français. Écrire une fonction qui étant donnée une liste d'étudiants, produit la liste des étudiants classés. Pensez à découper votre solution en fonctions simples.
Exercice 2 : File de priorité.
Voici une interface possible de file de priorité.
module type S = sig
type priority
type 'elt t
val empty : 'elt t
val push : priority -> 'elt -> 'elt t -> 'elt t
val observe : 'elt t -> (priority * 'elt * 'elt t) option
val pop : 'elt t -> 'elt t
val merge : 'elt t -> 'elt t -> 'elt t
val size : 'elt t -> int
val to_list : 'elt t -> 'elt list
end
On souhaite l'implémenter en utilisant un tas maxiphobique. Ceux-ci s'implémente par un arbre binaire, tel que chaque nœud contient un élément et sa priorité, ainsi que le nombre d'éléments dans le sous-arbre ayant ce nœud pour racine.
Proposer une définition pour le type 'elt t.
Implémenter la fonction size.
On suppose maintenant le reste du module implémenté, sauf to_list. Écrire la fonction to_list, retournant la liste des éléments en ordre de priorité croissante.
Généraliser la fonction to_list en une fonction fold de type :
val fold : ('state -> 'elt -> 'state) -> 'state -> 'elt t -> 'state
Réécrire to_list en utilisant fold.
Nous souhaitons tester l'implémentation avec QuickCheck. Proposer trois propriétés (des fonctions prenant des arguments arbitraires et devant toujours s'évaluer à true), pour vérifier que size se comporte bien par rapport aux autres opérations. On supposera disposer de générateurs arbitraires d'éléments, de priorités et de files de priorités, de sorte que les arguments des propriétés peuvent être de chacun de ces types. (Ne donner que les propriétés, pas les tests)
Exercice 3 : APB.
L'an dernier, le système d'admission des étudiants, Admission Post-Bac, a été critiqué car les formations en manque de places ont procédé à une sélection par tirage au sort. On s'intéresse ici au problème de tirer au sort $k$ candidats parmi une liste de $n$ candidats.
On trouvera en fin de sujet l'interface d'un module d'aléa similaire à QuickCheck.Gen.
Créer un générateur de booléens paramétré par un flottant $p$ (avec
$0 \leq p \leq 1$), qui génère true avec probabilité
$p$. Pour cela, générer d'abord un flottant entre 0 et 1 .
val true_with_proba : float -> bool Random.gen
Programmer un générateur qui choisit aléatoirement un élément parmi une liste. Chaque élément doit avoir la même probabilité d'être choisi. (indice : tirer le rang de l'élement choisi).
val choose_one : 'elt list -> 'elt Random.gen
Écrire un générateur de sous-listes d'une liste, gardant chaque élément avec la même probabilité p donnée en argument.
val filter : p:float -> 'elt list -> 'elt list Random.gen
Lors du choix de $k$ éléments parmi $n$, chaque élément a la même probabilité $k/n$ d'être choisi. On propose donc d'utiliser la fonction précédente pour construire une sous-liste. Nous ne pouvons pas garantir que filter retournera une liste avec exactement $k$ éléments. Mais s'il y en a trop, il suffit d'en reprendre $k$ parmi ceux déjà filtrés, et s'il y en manque, il suffit d'en ajouter suffisamment provenant des éléments écartés (récursivement). Écrire les fonctions suivantes :
val bipartition : p:float -> 'elt list -> ('elt list * 'elt list) Random.gen
val choose_k : k:int -> 'elt list -> 'elt list Random.gen
Une autre possibilité est de mélanger les éléments aléatoirement, et de prendre les $k$ premiers. Pour les mélanger, on utilise une approche diviser-pour-régner : on coupe la liste en deux parties aléatoirement, on mélange chaque partie et on les concatène. Implémenter une deuxième version de choose_k.
val shuffle : 'elt list -> 'elt list Random.gen
val choose_k' : k:int -> 'elt list -> 'elt list Random.gen
Les deux précédentes solutions présuppose de connaître la liste par avance, ou au moins sa longueur. On aimerait écrire un algorithme qui reçoit les éléments au fur et à mesure, et peut être arrêté à tout moment pour qu'il donne une solution. (On appelle un tel algorithme online).
Pour cela on propose de garder une file de priorité contenant au plus
$k$ éléments. Chaque élément est inséré avec une priorité choisie aléatoirement. Si la file contient $k+1$ éléments, on supprime le minimum.
Utiliser la structure de données de l'exercice précédent pour donner une troisième implémentation de choose_k.
val choose_k'' : k:int -> 'elt list -> 'elt list Random.gen
Éléments de langage
Module Random :
type 'value gen
val bool : bool gen
val int : int -> int gen
val float : float -> float gen
val bits : int gen
val return : 'value -> 'value gen
val bind : 'value gen -> ('value -> 'res gen) -> 'res gen
val (>>=) : 'value gen -> ('value -> 'res gen) -> 'res gen
val map : 'value gen -> ('value -> 'res) -> 'res gen
val (>|=) : 'value gen -> ('value -> 'res) -> 'res gen
type seed
val init : seed
val run : 'value gen -> seed -> ('value * seed)
Fonctions utiles du module List :
val length : 'elt list -> int
val nth : int -> 'elt list -> 'elt
val rev : 'elt list -> 'elt list
val concat : 'elt list list -> 'elt list
val map : ('elt -> 'im) -> 'elt list -> 'im list
val fold_left : ('state -> 'elt -> 'state) -> 'state -> 'elt list -> 'state
val for_all : ('elt -> bool) -> 'elt list -> bool
val exists : ('elt -> bool) -> 'elt list -> bool
val mem : 'elt -> 'elt list -> bool
val filter : ('elt -> bool) -> 'elt list -> 'elt list
val sort : ('elt -> 'elt -> int) -> 'elt list -> 'elt list
Fonctions utiles de Map.S :
type key
type 'assoc t
val empty : 'assoc t
val add : key -> 'assoc -> 'assoc t -> 'assoc t
val mem : key -> 'assoc t -> bool
val find : key -> 'assoc t -> 'assoc
val map : ('assoc -> 'im) -> 'assoc t -> 'im t
val fold : ('key -> 'assoc -> 'state -> 'state) -> 'assoc t -> 'state -> state
val cardinal : 'assoc t -> int
Exemples de syntaxe :
type ratio = int * int
let rec euclid a b =
if b = 0 then a
else euclid b (a mod b)
let pgcd a b = euclid (abs a) (abs b)
let ratio p q =
let d = pgcd p q in
if q < 0 then (-p / d, q / d)
else (p/d, q/d)
let (+/) (a,b) (c,d) = ratio (a*d + b*c) (b*d)
let (++) (a,b) (c,d) = ratio (a+c) (b+d)
let rec bipartitions list =
let open Base.List in
match list with
| [] -> [([],[])]
| head::tail ->
bipartitions tail >>= fun (left,right) ->
[ (head::left,right); (left, head::right) ]
module Queue =
struct
type 'elt t =
Queue of ('elt list) * ('elt list)
exception Empty
let empty = Queue ([],[])
let is_empty = function
| Queue ([],[]) -> true
| _ -> false
let queue = function
| Queue ([],l) -> Queue(List.rev l,[])
| x -> x
let snoc (Queue (l1,l2)) ele =
queue (Queue (l1,ele::l2))
let head = function
| Queue ([],_) -> raise Empty
| Queue (l,_) -> List.hd l
let tail = function
| Queue ([],_) -> raise Empty
| Queue (l1,l2) -> queue (Queue (List.tl l1,l2))
end
