Sujet

Corrigé d'un sujet du concours CCINP donné en DS 6 de MPI. L'énoncé n'est pas reproduit ici : seules les réponses sont données, dans l'ordre des questions du sujet.

Logique¶

Oh chouette, du foot...

Question 1.

Corrigé

Quatre variables :

\(F\) : faire la fête
\(G\) : mon équipe gagne
\(M\) : je marque
\(C\) : je suis content, et quand je suis content je...

Question 2.

Corrigé

\(P_1 = M \rightarrow C \land F\)
\(P_2 = G \rightarrow C \lor F\)
\(P_3 = \lnot G \rightarrow \lnot C \lor M\)
\(P_4 = \lnot M \land F \rightarrow C\)
\(P_5 = \lnot C\)

Question 3.

Corrigé

\(P_1 \equiv \lnot M \lor (C \land F) \equiv (\lnot M \lor C) \land (\lnot M \lor F)\)
\(P_2 \equiv \lnot G \lor C \lor F\) (une seule clause)
\(P_3 \equiv G \lor \lnot C \lor M\)
\(P_4 \equiv \lnot (\lnot M \land F) \lor C \equiv M \lor \lnot F \lor C\)
\(P_5 = \lnot C\)

Question 4.

Corrigé

\[ \begin{array}{rcl} F &=& P_1 \land P_2 \land P_3 \land P_4 \land P_5 \\ &\equiv& (\lnot M \lor C) \land (\lnot M \lor F) \land (\lnot G \lor C \lor F) \land (G \lor \lnot C \lor M) \land (M \lor \lnot F \lor C) \land \lnot C \end{array} \]

qui est une formule en forme normale conjonctive dont chaque clause a au plus trois littéraux : c'est une instance de 3-SAT.

Question 5.

Corrigé

On commence par remplacer \(C \leftarrow \bot\) dans \(F\) et on appelle ainsi Quine sur \(\lnot M \land (\lnot M \lor F) \land (\lnot G \lor F) \land (M \lor \lnot F)\).
- On effectue alors le remplacement \(M \leftarrow \bot\) et on appelle ainsi Quine sur \((\lnot G \lor F) \land \lnot F\).
  - On remplace \(F \leftarrow \bot\) et on appelle Quine sur \(\lnot G\).
    - On remplace \(G \leftarrow \bot\) et on obtient l'ensemble vide de clauses, donc l'appel renvoie vrai.
  - On renvoie vrai.
- On renvoie vrai.
On renvoie vrai.

La formule est donc satisfiable. On note que la valuation qui la satisfait est : \(F = C = M = G = \bot\) (c'est d'ailleurs la seule, comme on le vérifie sur la table de vérité). Il ne fait pas la fête, il n'est pas content, il n'a pas marqué et il a perdu. Youpi.

Dominos¶

Remarque

Attention : le typedef sur une structure anonyme est hors programme. Aussi, Domino mais element, c'est horrible.

Question 1.

Corrigé

struct element {
    Domino *valeur;
    struct element *suivant;
};
typedef struct element element;

Question 2.

Corrigé

Je ne comprends pas bien la question, vu qu'on ne demande rien de plus, il suffirait de dire typedef element chaine. Pourtant, la question suivante incite à avoir un pointeur sur le dernier maillon :

struct chaine {
    element *debut;
    element *fin;
};
typedef struct chaine chaine;

Question 3.

Corrigé

J'imagine qu'il faut parcourir l ici. On renvoie le maillon ajouté, qui est aussi la nouvelle liste si l était vide.

element *ajouteElement(element *l, Domino *d)
{
    element *e = malloc(sizeof(element));
    e->valeur = d;
    e->suivant = NULL;
    if (l == NULL)
        return e;
    while (l->suivant != NULL)
        l = l->suivant;
    l->suivant = e;
    return e;
}

Question 4.

Corrigé

En C, on ne peut pas comparer deux structures avec == ou != : on compare ici les pointeurs, c'est-à-dire qu'on cherche ce domino précis. On renvoie la tête de la liste, qui change si on retire le premier maillon. Le domino lui-même n'est pas libéré : il appartient à l'appelant.

element *retireElement(element *l, Domino *d)
{
    if (l == NULL)
        return NULL;
    if (l->valeur == d)
    {
        element *suite = l->suivant;
        free(l);
        return suite;
    }
    element *prec = l;
    while (prec->suivant != NULL && prec->suivant->valeur != d)
        prec = prec->suivant;
    if (prec->suivant != NULL)
    {
        element *e = prec->suivant;
        prec->suivant = e->suivant;
        free(e);
    }
    return l;
}

Question 5.

Corrigé

bool rechercheElement(element *l, Domino *d)
{
    while (l != NULL)
    {
        if (l->valeur == d)
            return true;
        l = l->suivant;
    }
    return false;
}