DM de Pâques — Dessin de graphes, chasseurs de fantômes, expressions

MP2I, année scolaire 2021-2022 — devoir pour les vacances de Pâques.

Sources

La partie « Chasseurs de fantômes » est d'après le sujet d'informatique de Centrale 2009 (« La chasse aux fantômes »). La partie « Dessin de graphes » cite un extrait de l'article de P. Eades, A heuristic for graph drawing.

Dessin de graphes

Il s'agit ici de la partie bonus du TP19 avec plus d'explications.

On reproduit l'explication succincte mais complète de l'article de 1983 de Eades :

Implémenter cette stratégie pour afficher des graphes avec graphics. Testez-la sur des graphes variés en nombre de sommets et d'arêtes.

Chasseurs de fantômes

Un groupe de \(n\) chasseurs de fantômes combat un groupe de \(n\) fantômes. Chaque chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de rayon. Un rayon se propage en ligne droite et termine sa course en touchant le fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire d'éliminer tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre initial de \(n\) fantômes ; il est très dangereux que deux rayons se croisent, cela ne doit donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse, dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont possibles que sur un rebord confondu avec la circonférence, mais les tirs se font entre deux points de la circonférence, selon des cordes du cercle.

A

Les \(2n\) protagonistes sont représentés par des points distincts \(P_1, P_2, \dots, P_{2n}\) répartis dans l'ordre des indices croissants sur la circonférence d'un cercle parcouru dans le sens trigonométrique ; \(n\) sont des chasseurs, \(n\) des fantômes, mais, dans cette section, on cherche les liens possibles entre les \(P_i\) sans s'occuper de qui est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par une corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il faut donc respecter les deux conditions :

1. chaque point est une extrémité d'une et une seule corde,
2. les différentes cordes ne doivent pas se couper.

Dans toute la suite on fixe un entier \(n > 0\) et on appelle stratégie de taille \(n\) un \(2n\)-uplet \((c_1,c_2,\dots,c_{2n})\) tel que pour tout entier \(i\) vérifiant \(1 \le i \le 2n\) on ait :

\[ 1 \le c_i \le 2n, \qquad c_{c_i} = i, \qquad c_i \neq i. \]

Cette notation exprime bien le lien entre les points \(P_i\) et \(P_{c_i}\).

En C, on représente le \(2n\)-uplet avec un tableau de int. Les éléments seront donc numérotés de \(0\) à \(N-1\). Pour simplifier, on prendra des tableaux de taille \(2n+1\) et on ignorera la valeur à l'indice \(0\). Ainsi c[i] contiendra \(c_i\).

On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite « admissible » si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie.

Par exemple, pour les stratégies de taille 4, \(c_1\) et \(c_2\) données dans le tableau, on présente les figures correspondantes, \(c_1\) admissible à gauche, et \(c_2\) non admissible à droite :

Question 1. Dans le cas \(n = 3\), donner le nombre de stratégies possibles, admissibles ou non.

Question 2. Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure.

Question 3. Déterminer le nombre de stratégies de taille \(n\) entier positif (qu'elles soient ou non admissibles).

B

Soit \(i, j, k, l\) quatre entiers distincts tels que : \(1 \le i < j \le 2n\) et \(1 \le k < l \le 2n\).

Question 4. Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments \([P_i P_j]\) et \([P_k P_l]\) se croisent.

Question 5. Écrire une fonction croise prenant les quatre entiers pour paramètres et renvoyant un booléen dont le résultat est true si et seulement si les segments \([P_iP_j]\) et \([P_kP_l]\) se croisent. On suppose que les paramètres donnés à la fonction satisfont les conditions données en introduction de cette partie.

Corrigé

int croise(int i, int j, int k, int l)
{
    return (i < k && k < j && j < l)
        || (k < i && i < l && l < j);
}

Question 6. En utilisant la fonction croise, écrire une fonction estAdmissible qui prend en paramètre le tableau et le nombre \(n\) de chasseurs, et renvoie un booléen dont le résultat est true si la stratégie est admissible.

Corrigé

int estAdmissible(int *c, int n)
{
    int p = 2 * n + 1;
    for (int i = 1; i < p; i++)
    {
        for (int k = i+1; k < c[i]; k++)
        {
            if (k < c[k] && croise(i, c[i], k, c[k]))
                return false;
            if (k >= c[k] && croise(i, c[i], c[k], k))
                return false;
        }
    }

    return true;
}

Question 7. Donner, en la justifiant, la complexité de cette méthode, en terme de temps de calcul (on se contentera d'une évaluation du type \(O(n^\alpha)\), en précisant la valeur de \(\alpha\)).

C

On souhaite tester la stratégie de façon plus efficace. Pour cela on utilise une fonction evalue qui prend deux entiers \(i\) et \(j\) comme paramètres (\(i\) et \(j\) étant compris entre 1 et \(2n\)) et dont le résultat est true si et seulement si les deux propositions suivantes sont vraies :

• \((i\le k \le j) \Rightarrow (i \le c_k \le j)\)
• les segments ayant leurs extrémités dans l'arc (fermé) \([P_i P_j]\) ne se croisent pas.

Question 8. Donner la valeur de evalue(i,j) dans les trois cas particuliers \(a,b\) et \(c\) suivants :

\[a)\ j < i; \quad b)\ j\ge i \text{ et } c_i < i ; \quad c)\ j \ge i \text{ et } c_i > j\]

Question 9. Pour \(i < c_i < j\), montrer que evalue(i,j) se déduit de evalue(i+1,c[i]-1) et de evalue(c[i]+1,j).

Question 10. Écrire une fonction testStrategie qui prend en paramètre un tableau et le nombre \(n\) de chasseurs, et renvoie un booléen dont la valeur est true si la stratégie est admissible. Cette fonction devra être de complexité \(O(n)\).

Corrigé

bool evalue(int *c, int i, int j)
{
    if (j < i)
        return true;
    if (c[i] < i || c[i] > j)
        return false;
    return evalue(c, i+1, c[i]-1)
        && evalue(c, c[i]+1, j);
}

bool testStrategie(int *c, int n)
{
    return evalue(c, 1, 2*n);
}

Question 11. Démontrer avec soin que la fonction testStrategie est bien de complexité \(O(n)\).

D

La méthode précédente teste si une stratégie est admissible. On souhaite maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer directement une stratégie admissible, de façon également efficace.

Question 12. Montrer que si \(P_i\) est un chasseur (\(1 \le i \le 2n\)), alors il existe \(j \neq i\), avec \(1 \le j \le 2n\) tel que \(P_j\) est un fantôme et tel que le nombre de chasseurs soit égal au nombre de fantômes de chaque côté de l'axe \(P_i P_j\).

Question 13. En déduire un algorithme simple pour construire une stratégie admissible.

Question 14. On se propose d'évaluer la complexité de cette méthode.

1. Déterminer la complexité dans le pire des cas.
2. Évaluer, sans démonstration, la complexité moyenne.

Question 15. Un tableau \(p\) contient la nature des points \(P_i\) : p[i] vaut \(1\) pour un chasseur et \(-1\) pour un fantôme (\(1 \le i \le 2n\)). On a donc \(\sum_{i=1}^{2n} p[i] = 0\) puisqu'il y a autant de fantômes que de chasseurs. Écrire une fonction cibles qui prend en paramètre le tableau \(p\) et le nombre \(n\) de chasseurs, et renvoie un tableau \(T\) de \(2n+1\) valeurs représentant les couples d'une stratégie admissible où le chasseur \(T[2i+1]\) cible le fantôme \(T[2i+2]\) (on ignore ici aussi la première case du tableau).

Corrigé

// renvoie k tel qu'il y ait autant de fantômes que de chasseurs
// dans PiPk
int coupe(int *p, int n, int i)
{
    int k = i;
    int s = p[i];
    while (s != 0)
    {
        k++;
        s += p[k];
    }
    return k;
}

// Remplit récursivement le tableau t
void tir(int *p, int *t, int i, int j, int nbTir)
{
    if (p[i] == 1)
    {
        t[2*nbTir+1] = i;
        t[2*nbTir+2] = j;
    }
    else
    {
        t[2*nbTir+1] = j;
        t[2*nbTir+2] = i;
    }
}

int remplit(int *p, int n, int *t, int i, int j, int nbTir)
{
    if (j <= i)
        return nbTir;
    if (j == i+1)
    {
        tir(p, t, i, j, nbTir);
        return nbTir+1;
    }

    int k = coupe(p, n, i);
    nbTir = remplit(p, n, t, i+1, k-1, nbTir);
    nbTir = remplit(p, n, t, k+1, j, nbTir);
    tir(p, t, i, k, nbTir);

    return nbTir+1;
}

int *cibles(int *p, int n)
{
    int *t = malloc(sizeof(int) * (2*n+1));
    remplit(p, n, t, 1, 2*n, 0);
    return t;
}

Exemple d'utilisation :

int main(void)
{
    int p[] = { 0, 1, -1, 1, 1, -1, -1, 1, -1 };
    int n = 4;

    int *t = cibles(p, n);

    for (int i = 1; i <= n; i++)
    {
        printf("%d -> %d\n", t[2*i-1], t[2*i]);
    }
    free(t);
}

Manipulation d'expressions

L'objectif de ce devoir, à réaliser sur machine, est de manipuler informatiquement des expressions mathématiques. On a déjà vu cela avec l'évaluation d'expressions arithmétiques, on va ici prolonger ce qui a été fait en rajoutant :

• des variables
• des fonctions
• des simplifications
• des dérivées ou primitives formelles
• \(\dots\)

Pour cela, on va utiliser un type d'expression qui va changer à mesure qu'on progresse dans ce devoir.

Expressions avec variables libres

On va utiliser le type expr suivant :

type bin_op = Add | Mult | Minus | Div
type un_op = Neg | Inv
type expr =
  | Const of int
  | Var of string
  | BinOp of expr * bin_op * expr
  | UnOp of un_op * expr

Ainsi, l'expression \(-\frac{x+1}{2+x^2}\) sera représentée par :

UnOp(Neg, BinOp(BinOp(Var "x",Add,Const 1),
                Div, BinOp(Const 2, Add, BinOp(Var "x", Mult, Var "x"))))

Les variables ici sont nécessairement libres : elles ne peuvent être liées comme dans \(\forall x, P(x)\) ou \(x \mapsto x+1\).

Question 16. Écrire une fonction variables_libres : expr -> string list qui renvoie la liste des variables apparaissant dans l'expression.

Corrigé

let rec variables_libres e = match e with
  | Const _ -> []
  | Var x -> [x]
  | BinOp (e, _, e') -> variables_libres e @ variables_libres e'
  | UnOp (_, e) -> variables_libres e

Question 17. Écrire une fonction string_of_expr : expr -> string qui renvoie une expression sous la forme d'une chaîne de caractère lisible.

Dans l'exemple introductif, on renverra la chaîne : "-((x+1)/(2+(x*x)))".

Corrigé

let string_of_bin_op op = match op with
  | Add -> "+" | Mult -> "*" | Minus -> "-" | Div -> "/"

let string_of_un_op op = match op with
  | Neg -> "-" | Inv -> "1/"

let rec string_of_expr e =
  let protect e =
    let s = string_of_expr e in
    match e with
    | Const _ | Var _ -> s
    | _ -> "(" ^ s ^ ")"
  in
  match e with
  | Const n -> string_of_int n
  | Var x -> x
  | BinOp(e, op, e') ->
    protect e
    ^ string_of_bin_op op
    ^ protect e'
  | UnOp(op, e) -> string_of_un_op op ^ protect e

Pour évaluer une telle expression, il est nécessaire de connaitre la valeur de chaque variable. Une association de valeurs aux variables est appelé un environnement d'évaluation. Pour simplifier, on va supposer qu'un environnement est une liste de couples \((variable, valeur)\).

type env = (string * float) list

Attention : dans l'expression, les constantes sont uniquement entières mais en raison de la présence de la division, il est nécessaire que l'évaluation se fasse avec des flottants.

Question 18. Écrire une fonction eval : env -> expr -> float qui évalue l'expression étant donné un environnement associant une valeur à chacune des variables.

Corrigé

let rec eval env e =
  match e with
  | Const n -> float_of_int n
  | Var x -> List.assoc x env
  | BinOp(e, op, e') ->
    let v = eval env e in
    let v' = eval env e' in
    (match op with
     | Add -> v +. v'
     | Mult -> v *. v'
     | Minus -> v -. v'
     | Div -> v /. v')
  | UnOp(Neg, e) -> -. (eval env e)
  | UnOp(Inv, e) -> 1. /. (eval env e)

Si \(e, e'\) sont deux expressions et \(x\) est une variable, on note \(e[x \backslash e']\) l'expression déduite de \(e\) en substituant chaque occurrence libre (pour le moment elles le sont toutes) de \(x\) par l'expression \(e'\).

Exemple : si \(e = (2+x) - (x \times x)\) et \(e' = 4+y\) alors \(e[x \backslash e'] = (2+(4+y))-( (4+y) \times (4+y))\).

Si \(x\) n'est pas une variable libre de \(e\), alors \(e[x \backslash e'] = e\).

Question 19. Écrire une fonction subst : expr -> string -> expr -> expr telle que subst e x e' renvoie \(e[x \backslash e']\).

Corrigé

let rec subst e x e' =
  match e with
  | Var y when x = y -> e'
  | BinOp(e1, op, e2) ->
    BinOp(subst e1 x e', op, subst e2 x e')
  | UnOp(op, e) -> UnOp(op, subst e x e')
  | _ -> e

On va essayer de simplifier des expressions en appliquant les règles suivantes :

• \(e + 0 \rightarrow e\)
• \(0 + e \rightarrow e\)
• \(e - 0 \rightarrow e\)
• \(0 - e \rightarrow -e\)
• \(0 \times e \rightarrow 0\)
• \(e \times 0 \rightarrow 0\)
• \(1 \times e \rightarrow e\)
• \(e \times 1 \rightarrow e\)
• \(0 / e \rightarrow 0\)
• \(e / 1 \rightarrow e\)
• \(e \times (e'+e'') \rightarrow (e \times e')+(e \times e'')\)
• \((e+e') \times e'' \rightarrow (e \times e'')+(e' \times e'')\)

Question 20. Écrire une fonction simpl : expr -> expr appliquant ces règles.

Corrigé

let rec simpl e = match e with
  | BinOp(e, Add, Const 0)
  | BinOp(e, Mult, Const 1)
  | BinOp(e, Div, Const 1)
  | BinOp(Const 1, Mult, e)
  | BinOp(Const 0, Add, e) -> simpl e
  | BinOp(e, Minus, Const 0) -> simpl e
  | BinOp(Const 0, Minus, e) -> UnOp(Neg, simpl e)
  | BinOp(e, Mult, Const 0)
  | BinOp(Const 0, Mult, e)
  | BinOp(Const 0, Div, e) -> Const 0
  | BinOp(BinOp(e', Add, e''), Mult, e)
  | BinOp(e, Mult, BinOp(e', Add, e'')) ->
    let s_e = simpl e in
    simpl (BinOp(BinOp(s_e, Mult, simpl e'),
                 Add, BinOp(s_e, Mult, simpl e'')))
  | BinOp(e, op, e') ->
    let s_e = simpl e in
    let s_e' = simpl e' in
    let bin = BinOp(s_e, op, s_e') in
    if s_e <> e || s_e' <> e'
    then simpl bin (* pour propager *)
    else bin
  | UnOp(op, e) -> UnOp(op, simpl e)
  | _ -> e

Essayez d'améliorer au maximum votre fonction de simplification.

Dérivation formelle

Question 21. Écrire une fonction derive : string -> expr -> expr telle que derive x e renvoie l'expression correspondant à la dérivée de l'expression \(e\) par rapport à la variable \(x\).

Exemples :

• derive "x" (BinOp(Var "x",Add,Const 1)) va renvoyer Const 1

• derive "x" (BinOp(Var "x",Mult,Var "x")) va renvoyer

  BinOp(BinOp(Const 1,Mult,Var "x"),
        Add,BinOp(Var "x",Mult,Const 1))
  

• derive "y" (BinOp(Var "x",Mult,Var "x")) va renvoyer Const 0

Corrigé

let rec derive x e = match e with
  | Const _ -> Const 0
  | Var y -> Const (if x = y then 1 else 0)
  | BinOp(e, Mult, e') ->
    BinOp(BinOp(derive x e, Mult, e'), Add, BinOp(e, Mult, derive x e'))
  | BinOp(e, Div, e') ->
    BinOp(
      BinOp(BinOp(derive x e, Mult, e'), Minus, BinOp(e, Mult, derive x e')),
      Div, BinOp(e', Mult, e'))
  | BinOp(e, op, e') ->
    BinOp(derive x e, op, derive x e')
  | UnOp(Neg, e) -> UnOp(Neg, derive x e)
  | UnOp(Inv, e) -> UnOp(Neg, BinOp(derive x e, Div, BinOp(e, Mult, e)))

Sans simplification, le premier exemple donne BinOp(Const 1, Add, Const 0) ; on obtient Const 1 (et Const 0 pour le troisième) en appliquant simpl au résultat.

On peut rajouter des symboles de fonctions élémentaires comme \(\cos, \sin\dots\) et adapter la dérivation formelle.