Aller au contenu

DS 4 — Logique et tas

MPSI option informatique, année scolaire 2021-2022 — durée totale 2h.

Consignes

Tout document et dispositif électronique interdit.

Corrigés

La source ne comporte pas de corrigé. Les corrigés des questions de programmation ci-dessous sont soit repris du fichier de code de l'auteur (DS_OI4.ml), soit des propositions (testées), à relire.

I. Logique

Vous participez à un concours de mathématiques comportant une partie de raisonnement logique. Plusieurs orateurs font des déclarations et vous devez répondre à des questions en vous appuyant sur des informations déduites de ces déclarations. La règle suivante s'applique : « Les orateurs sont de trois natures : les véridiques, les menteurs et les changeants. Les véridiques disent toujours la vérité, les menteurs mentent toujours, et les changeants disent en alternance une vérité et un mensonge (c'est-à-dire, soit une vérité, puis un mensonge, puis une vérité, etc. ; soit un mensonge, puis une vérité, puis un mensonge, etc.). Pendant tout le concours, les orateurs ne peuvent pas changer de nature. »

Les épreuves comportent deux phases :

  • Les différents orateurs font plusieurs déclarations dont l'analyse permet de déterminer la nature de chaque orateur (véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).
  • Les orateurs font une seconde série de déclarations. Puis, vous devez répondre à des questions en exploitant les informations contenues dans ces déclarations.

Question 1. Dans la première phase, quel est le nombre minimum de déclarations que doit faire chaque orateur pour qu'il soit possible de déterminer sa nature ? Justifier votre réponse.

Question 2. Soit un orateur A qui fait une suite de \(n\) déclarations \(A_i\). Proposer des formules du calcul des propositions \(A_V\), \(A_M\), \(A_{CV}\) et \(A_{CM}\) qui permettent de caractériser la nature de A (respectivement véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).

Vous participez à une première épreuve avec un orateur A qui fait les déclarations suivantes :

  • J'aime le rouge mais pas le bleu.
  • Soit j'aime le rouge, soit j'aime le vert.
  • Si j'aime le rouge et le vert, alors j'aime le bleu.

Nous noterons R, V et B les variables propositionnelles associées au fait que l'orateur aime le rouge, le vert ou le bleu. Nous noterons \(A_1\), \(A_2\) et \(A_3\) les formules propositionnelles associées aux déclarations de A.

Question 3. Représenter les déclarations de l'orateur sous la forme de formules du calcul des propositions \(A_1\), \(A_2\) et \(A_3\) dépendant des variables R, V et B.

Question 4. Appliquer les formules permettant de caractériser la nature des orateurs \(A_V\), \(A_M\), \(A_{CV}\) et \(A_{CM}\) que vous avez proposées pour la question 2 pour l'orateur A dépendant des variables \(A_1\), \(A_2\) et \(A_3\).

Question 5. En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer la nature de l'orateur A. Quelles sont les couleurs qu'aime A ?

II. Tas

Dans cette partie, on cherche à créer une structure de données immuable appelée un tas-max pouvant contenir des éléments d'un type 'a ordonné totalement et défini par le type 'a tas des tas et les opérations suivantes :

  • tas_vide : 'a tas une valeur représentant un tas vide ;
  • ajoute : 'a tas -> 'a -> 'a tas telle que ajoute t x ajoute l'élément x sur le tas t ;
  • retire : 'a tas -> 'a * 'a tas telle que retire t renvoie un couple (x, t') où x est un plus grand élément parmi les éléments de t et t' est un tas dans lequel on a retiré x.

Tri par tas

Sans même savoir implémenter un tas, on peut l'utiliser pour obtenir un algorithme de tri :

  • Étant donné des éléments à trier, on les ajoute tous dans un tas.
  • Tant que le tas est non vide, on retire un élément du tas et on le place dans la sortie.

Comme on a la garantie d'avoir un élément plus grand que ceux qui restent à chaque fois qu'on en retire un, on est certain que la sortie sera triée dans l'ordre décroissant.

Question 6. Écrire une fonction remplit : 'a list -> 'a tas -> 'a tas qui prend en entrée une liste l et un tas t et renvoie un tas t' obtenu en ajoutant tous les éléments de l au tas t.

Corrigé 
let rec remplit l t =
  match l with
  | [] -> t
  | x :: q -> remplit q (ajoute t x)

Question 7. Écrire une fonction vide : 'a tas -> 'a list qui vide un tas pour obtenir la liste de ses éléments dans l'ordre décroissant.

Corrigé

On compare au tas vide (avec l'implémentation par arbres de la suite, on peut aussi filtrer sur Nil) :

let rec vide t =
  if t = tas_vide then []
  else begin
    let x, t' = retire t in
    x :: vide t'
  end

Question 8. Écrire une fonction tri : 'a list -> 'a list qui renvoie une liste triée dans l'ordre décroissant à l'aide d'un tas.

Corrigé 
let tri l = vide (remplit l tas_vide)

Question 9. Si on considère que ajoute et retire sont en complexité temporelle \(f(n)\) où \(n\) est la taille du tas et où \(f\) est croissante, quelle est la complexité de ce tri ?

Implémentation naïve

Pour représenter un tas, on va ici choisir une implémentation naïve :

type 'a tas = 'a list

let tas_vide = []
let ajoute t x = x :: t

Pour retirer, il va donc être nécessaire de trouver le maximum et de l'extraire. On décompose cela en deux fonctions.

Question 10. Écrire une fonction maximum : 'a list -> 'a qui renvoie la plus grande valeur dans la liste donnée en entrée.

Corrigé 
let rec maximum l =
  match l with
  | [] -> failwith "liste vide"
  | [x] -> x
  | x :: q -> max x (maximum q)

Question 11. Écrire une fonction supprime : 'a list -> 'a -> 'a list qui supprime la première occurrence d'un élément dans une liste si elle le contient (sinon, on renvoie la liste inchangée).

Exemple : supprime [2;1;3;1] 1 renvoie [2;3;1].

Corrigé 
let rec supprime l x =
  match l with
  | [] -> []
  | y :: q -> if x = y then q else y :: supprime q x

Question 12. Écrire la fonction retire avec cette implémentation de tas à l'aide des deux fonctions précédentes.

Corrigé 
let retire t =
  let m = maximum t in
  m, supprime t m

Question 13. Quelle est la complexité de la fonction précédente ?

Question 14. Quelle est alors la complexité du tri par tas avec cette implémentation ?

Tas binaires

On va maintenant donner une implémentation des tas avec des arbres binaires.

On considère le type :

type 'a tas = Noeud of 'a tas * 'a * 'a tas | Nil

let tas_vide = Nil

Et on ne va considérer que des arbres dont l'étiquette de la racine est toujours la plus grande des étiquettes et dont les fils gauches et droits sont aussi des tas.

Si on note \(\eta(t)\) les étiquettes des nœuds de \(t\), on a donc la propriété \(tas\) définie ainsi :

\[ tas(t) := t = Nil \vee (t = Noeud(g,x,d) \wedge x = \max \eta(t) \wedge tas(g) \wedge tas(d)) \]

Ainsi l'arbre

est un tas mais

n'en est pas un.

Question 15. Écrire une fonction arbre_max : 'a tas -> 'a qui renvoie le plus grand élément d'un arbre non vide.

Attention : on ne suppose pas encore que l'arbre est un tas.

Corrigé 
let rec arbre_max t =
  match t with
  | Nil -> failwith "arbre vide"
  | Noeud (Nil, x, Nil) -> x
  | Noeud (Nil, x, d) -> max x (arbre_max d)
  | Noeud (g, x, Nil) -> max x (arbre_max g)
  | Noeud (g, x, d) -> max x (max (arbre_max g) (arbre_max d))

Question 16. En déduire une fonction est_un_tas : 'a tas -> bool qui indique si un arbre est bien un tas.

Corrigé 
let rec est_un_tas t =
  match t with
  | Nil -> true
  | Noeud (g, x, d) -> x = arbre_max t && est_un_tas g && est_un_tas d

Pour l'ajout et l'extraction de la racine, on va utiliser une même opération : la fusion de deux tas. Il s'agit d'une opération qui, étant donnés deux tas \(t_1\) et \(t_2\) va renvoyer un tas comportant tous les éléments de \(t_1\) et de \(t_2\).

Pour cela, on procède ainsi :

  • Si \(t_1\) est vide, on renvoie \(t_2\).
  • Si \(t_2\) est vide, on renvoie \(t_1\).
  • Si \(t_1 = Noeud(g_1,x,d_1)\) et \(t_2 = Noeud(g_2,y,d_2)\) et \(x > y\), on va fusionner \(d_1\) et \(t_2\) pour obtenir \(t'\) et on renvoie \(Noeud(g_1,x,t')\).
  • On procède symétriquement si \(x \le y\) en renvoyant \(Noeud(g_2,y,t')\).

Question 17. Réaliser la fusion des deux tas

et

Question 18. Écrire une fonction fusionne : 'a tas -> 'a tas -> 'a tas qui fusionne deux tas.

Corrigé 
let rec fusionne t1 t2 =
  match t1, t2 with
  | Nil, _ -> t2
  | _, Nil -> t1
  | Noeud (g1, x, d1), Noeud (g2, y, d2) ->
    if x > y
    then Noeud (g1, x, fusionne t2 d1)
    else Noeud (g2, y, fusionne t1 d2)

Question 19. Exprimer la complexité de cette fonction en fonction des deux arbres de tas fusionnés.

Pour ajouter un élément à un tas, on va fusionner le tas avec une feuille étiquetée par l'élément.

Question 20. Écrire une fonction ajoute : 'a tas -> 'a -> 'a tas.

Corrigé 
let ajoute t x = fusionne t (Noeud (Nil, x, Nil))

Pour retirer un élément d'un tas non vide, on renvoie l'étiquette de la racine et le tas obtenu par fusion de ses deux sous-arbres.

Question 21. Écrire une fonction retire : 'a tas -> 'a * 'a tas.

Corrigé 
let retire t =
  match t with
  | Nil -> failwith "vide"
  | Noeud (g, x, d) -> x, fusionne g d

Question 22. Exprimer la complexité de ajoute et retire.

Question 23. Détailler l'exécution du tri par tas avec la liste [1;6;2;4;3;7]. On donnera tous les tas apparaissant au cours du déroulement.