Archives de l’auteur : pedago

Brouillon

Programmation logique et fonctionnelle – partie D

Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

La logique du premier ordre

Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.

Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.

Activité de découverte D.dec

Introduction

En logique propositionnelle (partie C), les formules sont constituées de variables, connecteurs logiques ($\vee$, $\wedge$, $\neg$, $\to$, $\leftrightarrow$), de parenthèses, et des constantes $\top$ et $\bot$. Lorsqu’on interprète ces formules, pour déterminer leur valeurs de vérités, on assigne des valeurs de vérité 0 ou 1 (vrai ou faux) à leurs variables.

En logique du premier ordre, les variables peuvent prendre des valeurs diverses et variées (par exemple des entiers naturels, des réels, des symboles) appartenant à un domaine d’interprétation. Ces variables peuvent être liées par des quantificateurs $\forall$ et $\exists$. En plus, un nombre illimité de nouveaux symboles apparaissent : les symboles fonctionnels et les symboles relationnels, aussi appelés symboles de prédicats.

Par convention, nous représenterons les variables du premier ordre par des lettres majuscules ou des mots commençant par une lettre majuscule, alors que les symboles fonctionnels et relationnels seront représentés par des lettres minuscules ou des mots commençant par une lettre minuscule.

Les formules de la logique du premier ordre sont donc beaucoup plus riches que celles de la logique propositionnelle, ce qui leur permet de modéliser beaucoup plus de choses. Mais il va falloir prendre le temps d’assimiler différents concepts avant de parvenir à saisir l’intérêt et la puissance de ce paradigme.

D.dec1 : Les termes fonctionnels

Les termes fonctionnels font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des symboles fonctionnels qui ont vocation à être interprétés comme des fonctions. Mais pour le moment nous les considérerons comme des objets purement syntaxiques.

Définition : Une signature fonctionnelle est un ensemble de symboles ayant chacun une arité, qui est un entier naturel.

Voici un exemple de signature fonctionnelle :

${\text{coul}/1, \text{mix}/2, \text{noir}/0}$

Le symbole $\text{coul}$ est d’arité 1, le symbole $\text{mix}$ est d’arité 2 et le symbole $\text{noir}$ est d’arité 0. Les symboles d’arité 0 sont appelé constantes fonctionnelles.

Définition : On appelle terme fonctionnel compatible avec une signature fonctionnelle $F$ tout terme pouvant être construit de manière inductive avec les règles suivantes :

Une variable est un terme fonctionnel.
Une constante fonctionnelle (i.e., un terme fonctionnel d’arité 0) appartenant à $F$ est un terme fonctionnel est un terme fonctionnel compatible avec $F$.
Si $\mathcal{T}_1, \dots, \mathcal{T}_n$ sont des termes fonctionnels compatibles avec $F$ et $\mathcal{S}$ un symbole fonctionnel d’arité $n$ appartenant à $F$, alors $\mathcal{S}(\mathcal{T}_1, \dots, \mathcal{T}_n)$ est un terme fonctionnel compatible avec $F$.

Voici quelques exemples de termes fonctionnels compatibles avec la signature fonctionnelle ${\text{coul}/1, \text{mix}/2, \text{noir}/0}$ :

$X, ~ \text{coul}(X), ~ \text{mix}(\text{noir}, \text{coul}(\text{coul}(Y)))$

Exercice de découverte D.dec.x1

Parmi les expressions suivantes, quel sont les termes fonctionnels compatibles avec la signature ${\text{coul}/1, \text{mix}/2, \text{noir}/0}$ ?

$\text{noir} $
$\text{coul}(\text{coul (Y)} ) $
$\text{coul}(\text{coul (noir)} ) $
$Y$
$\text{mix(X,Y)} $
$\text{mix}(\text{noir}, \text{noir}) $
$\text{mix}(\text{mix}(X,\text{noir} ) ) $
$X(\text{noir} )$

"Réponse"

Les termes fonctionnels compatibles avec la signature donnée sont :

$\text{noir} $
$\text{coul}(\text{coul (Y)} ) $
$\text{coul}(\text{coul (noir)} ) $
$Y$
$\text{mix(X,Y)} $
$\text{mix}(\text{noir}, \text{noir}) $

D.dec2 : Les atomes

Les atomes font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des symboles relationnels qui ont vocation à être interprétés comme des prédicats, c’est à dire des fonctions à valeurs dans ${\text{vrai},\text{faux}}$. Mais pour le moment nous les considérerons comme des objets purement syntaxiques.

Définition : Une signature relationnelle est un ensemble de symboles ayant chacun une arité, qui est un entier naturel.

Voici un exemple de signature relationnelle :

${\text{arc}/2, \text{source}/1}$

Les symboles $\text{arc}$ et $\text{source}$ sont d’arités respectives 2 et 1. Les symboles d’arité 0 sont appelés variables propositionnelles. Ce sont en fait les variables de la logique propositionnelles introduites dans la partie C.

Définition : On appelle signature tout couple $(F,R)$ où $F$ est une signature fonctionnelle et $R$ une signature relationnelle telles que $F \cap R$ est vide.

Définition : On appelle atome compatible avec une signature $S=(F,R)$ tout terme pouvant être construit de manière inductive avec les règles suivantes :

Un symbole relationnel d’arité 0 appartenant à la signature relationnelle $R$ est un atome compatible avec $S$.
Si $\mathcal{T}_1, \dots, \mathcal{T}_n$ sont des termes fonctionnels compatibles avec la signature fonctionnelle $F$ et si est $\mathcal{R}$ un symbole relationnel d’arité $n$ appartenant à la signature relationnelle $R$, alors $\mathcal{R}(\mathcal{T}_1, \dots, \mathcal{T}_n)$ est un atome compatible avec $S$.

Voici quelques exemples d’atomes compatibles avec la signature $({\text{coul}/1}, {\underline{\text{arc}}/2, \underline{\text{source}}/1})$ :

$\text{arc}(X,Y), ~ \text{source}(\text{coul}(X), ~ \text{arc}(\text{coul}(Y),Z) $

Exercice de découverte D.dec.x2

Parmi les expressions suivantes, quel sont les atomes compatibles avec la signature $({\text{coul}/1}, {\underline{\text{arc}}/2, \underline{\text{source}}/1})$ ? (Les symboles relationnels ont été soulignés.)

$\text{arc}(X) $
$\text{coul}(Y) $
$\text{coul}(\text{arc}(X,Y) ) $
$\text{arc}(X,\text{coul(X)} ) $
$\text{source}(\text{coul}(\text{coul}(X) ) ) $
$Z$

"Réponse"

$\underline{\text{arc}}(X,\text{coul(X)} ) $
$\underline{\text{source}}(\text{coul}(\text{coul}(X) ) ) $

D.dec3 : Interprétation d’une signature

Les symboles fonctionnels et relationnels ne sont… que des symboles tant qu’on ne leur donne pas une interprétation.

Une interprétation donne un sens à chaque symbole relationnel et chaque symbole fonctionnel d’une signature.

Une interprétation d’une signature $(F,R)$ est constituée :

D’un domaine d’interprétation qui est un ensemble non vide $D$.
Pour chaque chaque constante fonctionnelle $\mathcal{F}/0\in F $, d’une valeur de $D$.
Pour chaque symbole fonctionnel d’arité non nulle $\mathcal{F}/n \in F$, d’une application de $D^n$ dans $D$.
Pour chaque symbole relationnel $R/0 \in R$, d’une valeur de vérité 0 ou 1.
Pour chaque symbole relationnel d’arité non nulle $\mathcal{R}/n $, d’une application de $D^n$ dans ${\text{vrai},\text{faux}}$.

On associe donc à chaque constante fonctionnelle une valeur du domaine d’interprétation, à chaque symbole fonctionnel d’arité non nulle une fonction, à chaque symbole relationnel un prédicat (ou de manière équivalente, une relation) et à chaque symbole relationnel d’arité 0 une valeur de vérité.

Voici deux exemples concrets d’interprétations d’une même signature :

$S = ({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$

Interprétation 1 :

Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Interprétation 2 :

Le domaine d’interprétation est l’ensemble ${0,1,2}$.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.
Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Exercice de découverte D.dec.x3

Combien y a t-il d’interprétations différentes de la signature $S = ({\text{zero}/0 },{\underline{\text{egal}}/2 })$ ayant l’ensemble ${1,2}$ comme domaine d’interprétation ?

"Indice"

Le symbole $\text{zero} $ peut être interprété par 1 ou par 2.

Le symbole $\text{egal} $ peut représenter n’importe quelle relation (ou prédicat) d’arité 2. On peut voir chacune de ces interprétations comme une table de vérité. Voici un exemple d’une telle table de vérité :

$X$	$Y$	$\text{egal}(X,Y) $
1	1	$\text{faux} $
1	2	$\text{faux} $
2	1	$\text{faux} $
2	2	$\text{faux} $

Il y a autant d’interprétations différentes du symbole relationnel $\text{egal} $ qu’il y a de tables de vérité différentes.

"Réponse"

Avec le domaine d’interprétation ${1,2}$, il y a 2 interprétations différentes du symbole $\text{zero} $ et 16 interprétation différentes du symboles $\text{egal} $.

Il existe donc 32 interprétations différentes de la signature $({\text{zero}/0 },{\underline{\text{egal}}/2 })$.

D.dec4 : Interprétation des termes fonctionnels

On appelle valuation d’un ensemble $V$ de variables sur un domaine d’interprétation $D$ toute application de $V$ dans $D$. En d’autre termes, une valuation assigne à chaque variable un élément du domaine d’interprétation.

Étant donnés :

un terme fonctionnel $f$,
une interprétation $I$ des symboles fonctionnels apparaisant dans $f$,
une valuation $A$ des variables apparaissant dans le terme $f$,

L’interprétation de $f$ pour la valuation $A$ consiste à déterminer la valeur $\text{Val}(f,A)$ par induction d’après les règles suivantes :

La valeur d’une constante fonctionnelle est celle qui lui est assignée par l’interprétation $I$.
La valeur d’une variable est celle qui lui est assignée par la valuation $A$.
Pour tout symbole $\mathcal{F}/n$ ayant pour interprétation la fonction $\text{Val}_ \mathcal{F}$, $\text{Val}(\mathcal{F}(f_1,…,f_n),A)$ $=$ $\text{Val}_ \mathcal{F}(\text{Val}(f_1,A),…,\text{Val}(f_n,A))$.

Exemple :

On considère la signature fonctionnelle ${\text{zero}/0, \text{plus}/2 }$ et l’interprétation suivante de cette signature :

**Interprétation 1 ** :

Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.

Soit le terme fonctionnel $f = \text{plus}(\text{plus}(\text{zero},X),Y))$ et la valuation $A = {(X,1), (Y,2)}$.

L’interprétation de $f$ pour $A$ est 3 car :

$\text{Val}(\text{zero},A) = 0$,
$\text{Val}(X,A) = 1$
$\text{Val}(Y,A) = 2$
$\text{Val}(\text{plus}(\text{zero},X),A) = 1$

En termes informels, interpréter un terme fonctionnel consiste à déterminer sa valeur à partir des valeurs de ses variables et des fonctions assignées à ses symboles fonctionnels par leur interprétation.

Exercice de découverte D.dec.x4

Donnez la valeur du terme fonctionnel $f = \text{plus}(\text{plus}(\text{zero},X),Y)$ pour la valuation $A = {(X,1), (Y,2)}$ et l’interprétation suivante :

**Interprétation 2 ** :

Le domaine d’interprétation est l’ensemble ${0,1,2}$.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.

"Réponse"

$\text{plus}(\text{zero},X)$ s’interprète à 1, c’est à dire $(0 + 1) \mod 3$.
$f = \text{plus}(\text{plus}(\text{zero},X),Y)$ s’interprète à 0, c’est à dire $(2 + 1) \mod 3$

D.dec5 : Interprétation des atomes

Pour mémoire, la valuation d’un ensemble $V$ de variables sur un domaine d’interprétation $D$ est une application qui assigne à chaque variable de $V$ un élément de $D$.

Étant donnés :

un atome $t$,
une interprétation $I$ des symboles fonctionnels et du symbole relationnel apparaissant dans $t$,
une valuation $A$ des variables apparaissant dans $t$,

L’interprétation de $t$ pour la valuation $A$ consiste à déterminer la valeur $\text{Val}(t,A)$ par induction d’après les règles suivantes :

La valeur d’une constante relationnelle est celle qui lui est assignée par l’interprétation $I$ ($\text{vrai} $ ou $\text{faux}$).
Pour tout terme relationnel $\mathcal{T}/n$ ayant pour interprétation la fonction $\text{Val}_ \mathcal{T}$, $\text{Val}(\mathcal{T}(f_1,…,f_n),A)$ $=$ $\text{Val}_ \mathcal{T}(\text{Val}(f_1,A),…,\text{Val}(f_n,A))$.

Exemple :

On considère la signature fonctionnelle $S = ({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$ et l’interprétation suivante de cette signature :

**Interprétation 1 ** :

Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Soit l’atome $t =$ $\text{egal}(1, \text{plus}(\text{plus}(\text{zero},X),Y)) )$ et la valuation $A = {(X,1), (Y,2)}$.

L’interprétation de $f$ pour $A$ est $\text{faux} $ car :

$\text{plus}(\text{plus}(\text{zero},X),Y)) = 3$
et $\text{egal(3,0}) = \text{faux}$

En termes informels, interpréter un atome consiste à déterminer sa valeur à partir des valeurs de ses variables, des fonctions assignées à ses symboles fonctionnels et de la relation assignée à son symbole relationnel par leur interprétation.

Exercice de découverte D.dec.x5

Donnez la valeur de l’atome $t = \text{p}( \text{plus}(\text{plus}(\text{zero},X),Y))$ pour la valuation $A = {(X,1), (Y,2)}$ et l’interprétation suivante :

**Interprétation 2 ** :

Le domaine d’interprétation est l’ensemble ${0,1,2}$.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.
Le symbole $\text{p}$ représente la fonction telle que $\text{p}(0) = \text{p}(2) = \text{vrai}$ et $\text{p}(1) = \text{faux} $.

"Réponse"

$\text{plus}(\text{plus}(\text{zero},X),Y)$ s’interprète à 0 (vu dans l’exercice précédent).
donc $t$ s’interprète à $\text{vrai}$.

D.dec6 : Formules

Jusqu’à maintenant, nous n’avons vu que des parties de formules appelées termes fonctionnels et atomes. Ces expressions sont construites à partir de symboles fonctionnels, variables et symboles relationnels.

Une formule du premier ordre est constituée d’atomes, de connecteurs logiques, de parenthèses et de quantificateurs.

On appelle formule complètement parenthésée toute expression pouvant être construite par induction en utilisant les règles suivantes :

Tout atome est une formule.
Si $\sigma$ est une formule, alors $\neg \sigma$ en est une.
Si $\sigma_1$ et $\sigma_2$ sont des formules, alors $(\sigma_1 \vee \sigma_2)$, $(\sigma_1 \wedge \sigma_2)$, $(\sigma_1 \to \sigma_2)$ et $(\sigma_1 \leftrightarrow \sigma_2)$ sont des formules.
Si $\sigma$ est une formule et $X$ une variable, alors $(\exists X \sigma)$ et $(\forall X \sigma)$ sont des formules.

Voici un exemple de formule complètement parenthésée dans la quelle les atomes ont été soulignés :

$(\exists Y((\forall X \underline{\text{egal}(\text{plus}(X,Y),X)})$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)}))$

Attention, on ne s’intéresse pas, pour le moment, aux valeurs de vérité des formules, qui peuvent dépendre de l’interprétation de leurs symboles fonctionnels er relationnel, comme nous le verrons plus loin.

On peut supprimer certaines parenthèses en utilisant les mêmes règles d’associativité et priorités que pour la logique propositionnelle, auxquelles d’ajoutes les règles suivantes :

Les quantificateurs ont la même priorité que le connecteur $\neg$, donc une priorité plus élevée que les connecteurs $\vee, \wedge, \to, \leftrightarrow$.
Les quantificateurs sont associatifs à droite (donc par exemple $\exists X \forall Y \exists Z ~ \sigma$ se lit $\exists X (\forall Y (\exists Z ~ \sigma))$).

La formule donnée en exemple peut donc s’écrire :

$\exists Y(\forall X \underline{\text{egal}(\text{plus}(X,Y),X)}$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)})$

Mais pour améliorer la lisibilité, n’hésitez pas à mettre plus de parenthèses que ce qui est strictement nécessaire.

Exercice de découverte D.dec.x6

Voici une formule complètement parenthésée :

$(\exists X((\forall Y(\text{p}(X,Y) \wedge \text{q}(Y)))$ $\to$ $(\forall Y(\text{p}(Y,X) \vee \text{q}(X) ))))$

Supprimez les parenthèses qui ne sont pas strictement nécessaires.

"Réponse"

$\exists X(~ \forall Y(\text{p}(X,Y) \wedge \text{q}(Y))$ $\to$ $\forall Y(\text{p}(Y,X) \vee \text{q}(X) ) ~)$

Y-a-t-il des symboles relationnels dans cette formule ? Si oui lesquels ? Y-a-t-il des symboles fonctionnels ? Si oui lesquels. Soulignez tous les atomes.

"Réponse"

Les symboles relationnels sont $\text{p}$ et $\text{q}$. Il n’y a pas de symboles fonctionnels. En effet, des symboles fonctionnels ne peuvent se trouver que dans les atomes, qui sont définit à l’aide de symboles relationnels.

$\exists X(~ \forall Y(\underline{\text{p}(X,Y)} \wedge \underline{\text{q}(Y)})$ $\to$ $\forall Y(\underline{\text{p}(Y,X)} \vee \underline{\text{q}(X)} ) ~)$

D.dec7 : Formules closes

Les variables apparaissant dans une formule peuvent être liées ou libres.

Les variables liées sont introduites par les quantificateurs $\forall$ et $\exists$. Chaque quantificateur lie entre elle toutes les occurrence de la variables qu’il quantifie et qui se situent dans sa portée, c’est à dire entre les parenthèses associée à ce quantificateur dans la forme complètement parenthésée de la formule.

Voici un exemple de formule où les occurrences de variables liées par chaque quantificateur sont mises en évidence.

Les variables qui ne sont pas liées sont dites libres.

Toute formule dont toutes les variables sont liées est dite close.

Exercice de découverte D.dec.x7

Dans la formule suivante, soulignez les atomes, reliez par des flèches les occurrences de variables liées entre elles, et entourez les variables libres.

$\forall A ~ \text{p}(A,B)$ $\to$ $\exists A ~ (~ q(A,C) \vee \exists B ~ t(f(B))~) $

"Réponse"

Cette formule est-elle close ?

"Réponse"

Non, car elle contient une variable libre.

D.dec8 : Interprétation d’une formule close

Nous avons vu précédemment comment interpréter les termes fonctionnels et les atomes de formules en nous basant sur un domaine d’interprétation et en donnant un sens aux symboles fonctionnels et aux symboles relationnels.

Interpréter une formule close consiste à déterminer sa valeur de vérité pour une interprétation donnée de ses symboles fonctionnels et de ses symboles relationnels.

Pour une valuation $A$ donnée de ses variables, un atome s’interprète à $\text{vrai}$ ou $\text{faux}$. Une formule constituée uniquement d’atomes et de connecteurs logiques s’interprète selon les mêmes règles qu’en logique propositionnelle, basées sur les tables de vérités des connecteurs.

Toujours pour une valuation donnée, la valeur de vérité d’une formule est déterminée par induction d’après les règles suivantes :

La valeur de vérité d’un atome $t$ (qui est un cas particulier de formule) pour une valuation $A$ de ses variables est $\text{Val}(t,A)$. (Voir section D.dec5).
Si $\Sigma$ est une formule, alors $\text{Val}(\neg \Sigma,A)$ $=$ $\underline\neg \text{Val} (\Sigma, A)$
Si $\Sigma$ et $\Omega$ sont des formules, alors :
- $\text{Val}(\Sigma \vee \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\vee \text{Val}(\Omega,A)$
- $\text{Val}(\Sigma \wedge \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\wedge \text{Val}(\Omega,A)$
- $\text{Val}(\Sigma \to \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\to \text{Val}(\Omega,A)$
- $\text{Val}(\Sigma \leftrightarrow \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\leftrightarrow \text{Val}(\Omega,A)$
Si $\Sigma$ est une formule et $X$ une variable non assignées par $A$, alors $\text{Val}(\exists X ~ \Sigma,A) = \text{vrai}$ si et seulement si il existe au moins un élément $x$ du domaine d’interprétation tel que $\text{Val}(\Sigma, A\cup{X,x}) = \text{vrai}$.
Si $\Sigma$ est une formule et $X$ une variable non assignées par $A$, alors $\text{Val}(\forall X ~ \Sigma,A) = \text{vrai}$ si et seulement si pour tout élément $x$ du domaine d’interprétation, $\text{Val}(\Sigma, A\cup{X,x}) = \text{vrai}$.

Le sens des quantificateurs est donc celui usuellement utilisé en mathématique.

En résumé, pour attribuer une valeur de vérité à une formule $\Sigma$, il faut :

Une interprétation, incluant un domaine d’interprétation et une interprétation de tous les symboles fonctionnels et relationnels apparaissant dans $\Sigma$.
Une valuation des variables libres apparaissant dans $\Sigma$.

L’interprétation d’une formule close repose uniquement sur une interprétation de ses symboles fonctionnels et relationnels.

Considérons l’exemple suivant.

$\Sigma =$ $\exists Y(\forall X ~ \underline{\text{egal}(\text{plus}(X,Y),X)}$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)})$

Cette formule est close. Sa valeur de vérité dépend uniquement de l’interprétation de la signature $({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$, c’est à dire du domaine d’interprétation considéré et du sens donné aux symboles $\text{egal}$, $\text{plus}$ et $\text{zero}$.

Pour certaines interprétations, la formule a la valeur $\text{vrai}$ et pour d’autre elle a la valeur $\text{faux}$.

Prenons l’interprétation que nous avons déjà utilisée section D.dec5.

**Interprétation 1 ** :

Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Quelle est la valeur de vérité de $\Sigma$ pour cette interprétation ?

Pour le savoir, il nous faut déterminer s’il existe une valeur de $Y$ telle que…

$\Sigma =$ $\underbrace{\forall X ~ \text{egal}(\text{plus}(X,Y),X)}_ {\sigma_1}$ $\to$ $\neg \underbrace{\text{egal}(\text{zero},y)}_ {\sigma_2}$

… s’interprète à $\text{vrai}$.

Or pour $Y=1$, par exemple, $\sigma_1$ s’interprète à $\text{faux}$ (puisque cette valuation de $Y$, $\sigma_1$ dit que pour tout $X$, on a $X+1=X$) et $\sigma_2$ s’interprète à $\text{vrai}$, donc $\sigma_1 \to \sigma_2$ s’interprète à $\text{vrai}$ (d’après la table de vérité du connecteur $\to$).

On en conclu que notre interprétation donne la valeur $\text{vrai}$ à $\Sigma$.

Exercice de découverte D.dec.x8

On reprend la même interprétation, mais une formule différente :

$\Omega =$ $\forall X(\exists Y ~ \text{egal}(X,Y) \to \text{egal}(\text{zero},X))$

Donnez la valeur de vérité de $\Omega$.

"Réponse"

On décompose la formule comme ceci pour faciliter le raisonnement :

$\Omega =$ $\forall X(\underbrace{\exists Y ~ \text{egal}(X,Y)}_ {\omega_1}$ $\to$ $\underbrace{\text{egal}(\text{zero},X)}_ {\omega_2})$

Pour $X=1$, la formule $\omega_1$ s’interprète à $\text{vrai}$ puisqu’il existe une valeur de $Y$, en l’occurrence 1, qui satisfait l’atome $\text{egal}(X,Y)$, et $\omega_2$ s’interprète à $\text{faux}$, donc $\omega_1 \to \omega_2$ s’interprète à $\text{faux}$.

Puisqu’il existe au moins une valeur de $X$ qui falsifie $\omega_1 \to \omega_2$ , $\Omega$ s’interprète à $\text{vrai}$.

D.dec9 : Validité et cohérence

On s’intéresse uniquement aux formules closes de la logique du premier ordre.

On dit qu’une interprétation $I$ satisfait une formule $\Sigma$ si et seulement si elle donne à cette formule la valeur $\text{vrai}$. Dans le cas contraire, on dit que $I$ falsifie $\Sigma$. On appelle modèle d’une formule close $\Sigma$ toute interprétation qui satisfait $\Sigma$. Toute interprétation qui falsifie $\Sigma$ est appelée contre-modèle de $\Sigma$.

Une formule close est une tautologie, ou formule valide, si et seulement si elle n’admet aucun contre-modèle. Autrement dit, la formule s’interprète à $\text{vrai}$ quels que soient le domaine d’interprétation et le sens donné à ses symboles relationnels et à ses symboles fonctionnels. En quelque sorte, une telle formule est "toujours vraie".

Une formule close est cohérente si et seulement si elle admet au moins un modèle. Dans le cas contraire, elle est dite incohérente.

Prenons comme exemple la formule $\Sigma = \forall X~ \text{p}(X,X)$. Une interprétation de cette formule définit un domaine d’interprétation et donne un sens au symbole relationnel $\text{t}$. Considérons deux interprétations ayant pour domaine ${1,2}$. Ces deux interprétations se différencie donc uniquement par le sens donné au symbole $\text{p}$.

Interprétation $I_1$ :

Voici trois représentations de la première interprétation. Une seule est suffisante, mais c’est l’occasion de voir les différente manière de représenter l’interprétation d’un symbole relationnel d’arité 2 lorsque le domaine d’interprétation comporte relativement peu de valeurs.

La première représentation est dite sagittale. Elle marque par une flèche les couples $x,y$ pour lesquels $\text{p}(x,y) = \text{vrai}$. La deuxième représentation donne ces même couples sous la forme d’une matrice avec le premier argument en ligne et le deuxième en colonne. La troisième représentation est généralisable aux symboles relationnels d’arité quelconque.

Cette interprétation falsifie $\Sigma$ puisque par exemple pour $X=1$, $\text{p}(X,X)$ s’interprète à $\text{faux}$.

Interprétation $I_2$ :

Cette interprétation satisfait $\Sigma$ puisque pour toutes les valeurs de $X$, $\text{p}(X,X)$ s’interprète à $\text{vrai}$.

La formule $\Sigma$ est cohérente, puisqu’elle a au moins un modèle, mais ce n’est pas une tautologie car elle admet au moins un contre-modèle.

Exercice de découverte D.dec.x9

Donnez une interprétation qui falsifie et une qui satisfait la formule suivante :

$\Omega =$ $\underbrace{(\forall X \exists Y ~ \text{p}(X,Y))}_ {\omega_1}$ $\to$ $\underbrace{(\forall X \exists Y ~ \neg \text{p}(X,Y))}_ {\omega_2}$

Les deux interprétations doivent avoir pour domaine l’ensemble ${1,2}$. Commencez par rechercher un modèle (réponse 1), puis un contre-modèle (réponse 2).

"Réponse1"

Il existe plusieurs modèles. Par exemple, toute interprétation de $\text{p}$ qui falsifie $\omega_1$ est un modèle de $\Omega$ en vertu de la table de vérité du connecteur $\to$.

Les représentations sagittales de ces modèles se caractérisent par une ou deux valeurs d’où ne part aucune flèche. Voici trois exemples.

"Réponse2"

Un contre-modèle, en vertu de la table de vérité du connecteur $\to$ (qu’il vaut mieux avoir toujours à portée de main), doit satisfaire $\omega_1$ et falsifier $\omega_2$. Sa représentation sagittale se caractérise par le fait qu’exactement une flèche part de chaque valeur. Voici trois exemples.

D.dec10 : Conséquence logique

La conséquence logique et l’équivalence logique sont définie exactement de la même façon en logique propositionnelle et en logique du premier ordre.

Une formule $\Omega$ est conséquence logique d’une formule $\Sigma$, i.e., $\Sigma \models \Omega$ si et seulement si tout modèle de $\Sigma$ est un modèle de $\Omega$.

Deux formules sont logiquement équivalentes si et seulement si elles ont les même modèles.

La grosse différence entre la logique du premier ordre et la logique propositionnelle tient à la notion de modèle. En logique propositionnelle, un modèle est simplement une valuation des variables qui satisfait la formule. En logique du premier ordre, un modèle est une interprétation qui satisfait la formule. Une formule du premier ordre à une infinité d’interprétations différentes, chacune constituée d’un domaine (qui peut être fini ou infini) et de fonctions donnant un sens à chacun des symboles fonctionnel et relationnel utilisé.

En logique propositionnelle, comme en logique du premier ordre, déterminer si une logique est conséquence logique d’une autre est de même difficulté que déterminer si une formule est une tautologie ou que déterminer si une formule est cohérente.

En logique propositionnelle, déterminer si une formule est cohérente ou si elle est valide est un problème NP-complet, pour lequel aucun algorithme efficace, au sens d’une complexité en temps polynomiale, n’est connu.

En logique du premier ordre c’est encore pire : le problème est indécidable. Aucun algorithme ne peut, pour toute formule placée en entrée, déterminer en un temps fini si cette formule est une tautologie. Déterminer si une formule est cohérente est également indécidable.

En pratique, il est possible de déterminer et de prouver que certaines formules sont valides ou sont cohérentes en réalisant des déductions.

Par exemple, considérons la formule suivante :

$\Sigma =$ $\underbrace{\forall X ~ \text{p}(X)}_ {\sigma_1} \to \underbrace{ \exists X ~ \text{p}(X)}_ {\sigma_2}$

Il est évident que $\Sigma$ est une tautologie. En effet, si une interprétation $I$ est un modèle de $\sigma_1$, alors $\text{p}(X)$, tel que défint par $I$, est $\text{vrai}$ pour toute valeur $X$ du domaine d’interprétation de $I$. Donc $\text{p}(X)$ il est vrai pour au moins une valeur $X$ du domaine d’interprétation de $I$, donc $I$ est aussi un modèle de $\sigma_2$.

Il existe des algorithmes permettant de déterminer si certaines formules sont des tautologies en utilisant des ensembles de règles appelés systèmes de preuve. Cela relève d’un champ de l’intelligence artificielle appelé raisonnement automatique. Comme le problème sous-jacent est indécidable, de tels algorithmes ne s’arrêtent jamais et ne peuvent pas conclure pour certaines formules placées en entrée. Mais il peuvent traiter certaines autres formules. Ces algorithmes sont qualifiés de corrects parce que s’ils s’arrêtent et fournissent un résultat (par exemple : la formule d’entrée est une tautologie), alors ce résultat est correct. Par contre, pour certaines formules, il ne s’arrêtent jamais. Si le programme ne s’est pas arrêté après un certain temps, vous n’avez aucun moyen de savoir s’il va fournir une réponse ou si son exécution va se prolonger indéfiniment :slightly_smiling_face:. Et le problème, c’est que même dans les cas où si le programme va s’arrêter en théorie, en pratique l’exécution peut être d’une durée astronomique, sans vous laisser aucune chance d’avoir le résultat.

D.dec11 : Modélisation

La logique du premier ordre permet de formaliser des énoncés faisant intervenir des objets (les éléments du domaine d’interprétation) et des relations entre ces objets (les interprétations des symboles relationnels et des symboles fonctionnels).

On dit qu’une formule $\Sigma$ modélise une émoncé $E$ si et seulement si elle est satisfaite par les interprétations qui ne sont pas en contradiction avec $E$, et seulement pour ces interprétations.

Prenons pour exemple l’énoncé suivant :

Tout humain qui possède un chien est anglophone.

Cet énoncé est-il vrai ou faux ? Cela dépend, pour commencer, du sens donné aux mots chien, humain, possède et anglophone. Mais admettons que nous leur donnions leur sens usuel. La valeur de vérité de l’énoncé dépend du domaine d’interprétation. S’il s’agit des êtres vivants terrestre, alors clairement l’énoncé est faux. Mais si on réduit ce domaine aux êtres vivant situés dans le village de Capel, en Angleterre, il n’est pas impossible que l’énoncé soit vrai. Et si le domaine d’interprétation est l’ensemble des êtres vivant de l’ile de Achi Kochi au Japon, où il est interdit de posséder un chien, alors l’énoncé est… vrai ! En effet, si personne ne possède de chien, alors il est vrai que toute personne humaine en possédant un parle anglais.

Pour modéliser cet énoncé par une formule du premier ordre, il nous faut définit les symboles relationnels et symboles fonctionnels utilisés. Dans la suite, nous ne travaillerons qu’avec des symbole relationnel pour simplifier les exercices, compte tenu du faible nombre d’heures d’enseignement consacrées à la logique du premier ordre.

Ici, nous utiliserons les symboles relationnels suivants : $\text{hum}/1$, $\text{chien}/1$, $\text{angl}/1$ et $\text{poss}/2$.

L’énoncé peut alors être modélisé ainsi :

$\forall X$ $[\underbrace{(\text{hum}(X) \wedge \underbrace{\exists Y~(\text{chien}(Y) \wedge \text{poss}(X,Y)}_ {\mu})}_ {\sigma}$ $\to$ $\underbrace{\text{angl}(X)}_{\omega} ]$

La sous-formule $\omega$ modélise la propriété : $X$ est anglophone.

La sous formule $\mu$ modélise la propriété : $X$ possède un chien.

La sous-formule $\sigma$ modélise la propriété : $X$ est un humain qui possède un chien.

L’utilisation du symbole $\to$ traduit l’implication sous-jacente à l’énoncé : "Si $X$ est un humain qui possède un chien, alors $X$ est anglophone".

Le quantificateur $\forall$ traduit le fait que pour satisfaire l’énoncé, il faut que tout humain possédant un chien soit anglophone.

Le quantificateur $\exists$ traduit la condition "$X$ possède au moins un chien", i.e., il existe au moin un chien possédé par $X$.

Exercice de découverte D.dec.x9

Nous reprenons la formule…

$\forall X$ $[\underbrace{(\text{hum}(X) \wedge \underbrace{\exists Y~(\text{chien}(Y) \wedge \text{poss}(X,Y)}_ {\mu})}_ {\sigma}$ $\to$ $\underbrace{\text{angl}(X)}_{\omega} ]$

…qui modélise l’énoncé :

Tout humain qui possède un chien est anglophone.

Imaginons une planète où il n’y a aucun humain, où nul être vivant ne peut être à la fois une salade et un chien, et qui est peuplée uniquement :

d’un chien anglophone nommé $\alpha$, qui ne possède rien.
d’une salade nommée $\beta$ (son vrai nom est $\beta$via) qui ne parle pas anglais et possède le chien et rien d’autre.

La situation sur cette planète est-elle en contradiction avec l’énoncé $E$ ? (Réponse 1)

Donnez l’interprétation correspondante (dont le domaine d’interprétation est ${\alpha, \beta}$. (Réponse 2)

Cette interprétation est-elle un modèle de $\Sigma$ ? (Réponse 3)

"Réponse1"

Oui, la situation est compatible avec l’énoncé puisqu’il n’y a pas d’humain sur la planète.

"Réponse2"

Voici une représentation graphique de l’interprétation.

"Réponse3"

Quel que soit la valeur de $X$, la sous-formule $\sigma$ s’interprète à $\text{faux}$ donc $\sigma \to \omega$ s’interprète à $\text{vrai}$ (d’après la table de vérité du connecteur $\to$.

L’interprétation est bien un modèle de $\Sigma$.

Activité d’entraînement D.ent

Chacune des deux itération propose un panel d’exercices couvrant les compétences qui seront évaluées à l’examen.

Itération D.ent1

Exercice d’entrainement D.ent1.1

Soit la formule :

$\Sigma = \forall X \exists Y$ $\underbrace{[\underbrace{(p(X) \wedge p(Y))}_ {\sigma_1} \to \underbrace{(q(X) \vee q(Y))}_ {\sigma_2}]}_ {\sigma}$

L’interprétation suivante est-elle un modèle de $\Sigma$ ? (Les valeurs entourées sont celles qui satisfont l’interprétation du symbole relationnel d’arité 1 mentionné au dessus.)

"Indice"

Les questions auxquelles il faut répondre pour conclure sont :

Pour $X=1$, existe-t-il une valeur de $Y$ telle que $\sigma$ s’interprète à $\text{vrai}$ ?
Pour $X=2$, existe-t-il une valeur de $Y$ telle que $\sigma$ s’interprète à $\text{vrai}$ ?
Pour $X=3$, existe-t-il une valeur de $Y$ telle que $\sigma$ s’interprète à $\text{vrai}$ ?
Pour $X=4$, existe-t-il une valeur de $Y$ telle que $\sigma$ s’interprète à $\text{vrai}$ ?

Si la réponse à ces 4 questions est positive, alors l’interprétation satisfait $\Sigma$ (i.e., est un modèle de $\Sigma$.

"Réponse"

La valeur $Y=3$ permet de répondre positivement aux 4 questions. En effet, avec cette valeur de $Y$, $p(Y)$ est faux donc $\sigma_1$ est faux, donc $\sigma$ est vrai.

L’interprétation satisfait $\Sigma$.

Donnez un contre-modèle de $\Sigma$ ayant le même domaine mais une interprétation différente des symboles relationnels $p$ et $q$.

"Indice"

Il faut que pour au moins une valeur de $X$, par exemple $X=1$, $\sigma$ s’interprète à $\text{faux}$ pour toutes les valeurs possibles de $Y$.

"Réponse"

Voici une solution simple :

Comme $p$ est toujours interprété à $\text{vrai}$ et $q$ à $\text{faux}$, $\sigma$ s’interprète à $\text{faux}$ pour toute valeur de $X$ et toute valeur de $Y$, donc l’interprétation falsifie $\Sigma$.

Exercice d’entrainement D.ent1.2

Soit les formules suivantes :

$\Sigma_1 = \forall X ~ r(X,X)$
$\Sigma_2 =$ $\forall X \forall Y (r(X,Y) \to r(Y,X))$
$\Sigma_3$ $=$ $\forall X \forall Y \forall Z$ $(~[(r(X,Y) \wedge r(Y,Z)] \to r(X,Z)~)$

L’interprétation suivante est-elle un modèle de $\Sigma_1$ ? de $\Sigma_2$ ? de $\Sigma_3$ ?

"Réponse"

L’interprétation satisfait $\Sigma_1$ puisqu’une flèche relie chaque élément à lui même.

Elle ne satisfait pas $\Sigma_2$ car $r(d,e)$ est vrai alors que $r(e,d)$ est faux.

Elle ne satisfait pas non plus $\Sigma_3$ car $r(d,c)$ et $r(c,e)$ sont vrai alors que $r(e,d)$ est faux.

Proposez une modification minimale (en termes de nombre d’arcs ajoutés ou enlevés) pour que l’interprétation satisfasse les trois formules.

"Réponse"

Exercice d’entrainement D.ent1.3

Donnez une interprétation $I_1$ qui satisfait (Réponse 1) et une interprétation $I_2$ qui falsifie (Réponse 2) la formule suivante :

$\Omega = [\forall X \exists Y~ p(X,Y)]$ $\to$ $[\exists Y \forall X~ p(X,Y)]$

Ces deux interprétations doivent avoir pour domaine ${1,2}$.

"Réponse1"

Une interprétation dans laquelle $p$ est toujours vrai est un modèle de la formule.

$p(1,1) = p(1,2)$ $=$ $p(2,1) = p(2,2)$ $=$ $\text{vrai}$

Mais il y en a bien d’autres, comme par exemple celle où $p$ est toujours faux.

"IndiceRéponse2"

$\Omega = \underbrace{[\forall X \exists Y~ p(X,Y)]}_ {\omega_1}$ $\to$ $\underbrace{[\exists Y \forall X~ p(X,Y)]}_ {\omega_2}$

Pour falsifier $\Omega$, Il faut une interprétation qui satisfait $\omega_1$ et qui falsifie $\omega_2$. Pour que $\omega_1$ soit vrai, il faut, sur le diagramme sagittal représentant l’intreprétation de $p$, qu’au moins une flèche parte de chaque valeur du domaine d’interprétation. Et pour falsifier $\omega_2$ ?

"Réponse2"

Voici deux exemples de contre-modèles de $\Omega$. Il me semble que ce sont les deux seuls.

Exercice d’entrainement D.ent1.4

Soient les 2 formules suivantes :

$\Omega_1 = \exists Y \forall X~ p(X,Y)$
$\Omega_2 = \exists Y \forall X~ p(Y,X)$

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\Omega_1$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de flèches et avec le domaine ${1,2,3}$.

"Réponse"

Il doit y avoir une valeur recevant une flèche provenant de toutes les valeurs (y compris elle-même).

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\Omega_2$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de flèches et avec le domaine ${1,2,3}$.

"Réponse"

Il vaut au moins une valeur de laquelle partent des flèches allant vers toutes les autres valeurs, y compris elle-même.

La formule $\Omega_1 \leftrightarrow \Omega_2$ est-elle une tautologie ? Justifiez votre réponse.

"Réponse"

Non, ce n’est pas une tautologie car $\Omega_1$ et $\Omega_2$ n’ont pas les même modèles. Par exemple, les modèles de $\Omega_1$ donné en réponse à la première question ne sont pas des modèles de $\Omega_2$.

Exercice d’entrainement D.ent1.5

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Il existe au moins un plombier riche.

Les symboles relationnels sont $\text{plombier}/1$ et $\text{riche}/1$.

"Réponse"

$\Sigma = \exists X~ (\text{plombier}(X) \wedge \text{riche}(X))$

Pourquoi la formule suivante n’est-elle pas une modélisation correcte de la phrase ?

$\Omega =$ $\exists X$ $(\underbrace{\text{plombier}(X) \to \text{riche}(X)}_{\omega})$

"Réponse"

Il suffit qu’un élément du domaine d’interprétation ne soit pas plombier pour que $\Omega$ soit satisfaite, même si aucun plombier n’est riche.

Par exemple, considérons l’interprétation $I$ suivante :

Domaine : {donald, picsou}
riche(donald) = faux, riche(picsou) = vrai
plombier(donald) = vrai, plombier(picsou) = faux

Clairement, cette interprétation n’est pas compatible avec l’énoncé et elle falsifie $\Sigma$. Mais elle satisfait $\Omega$ car il existe une valeur du domaine, en l’occurrence picsou, qui satisfait $\omega$. ($\text{faux} \to \text{vrai}$ s’évalue à $\text{vrai} $ d’après le table de vérité du connecteur $\to$.)

Modélisez maintenant la phrase :

Tous les plombiers sont riches.

"Réponse"

$\Theta = \forall X~ (\text{plombier}(X) \to \text{riche}(X))$

Pourquoi la formule suivante n’est-elle pas une modélisation correcte de la phrase ?

$\Lambda = \forall X$ $(\underbrace{\text{plombier}(X) \wedge \text{riche}(X)}_{\omega})$

"Réponse"

La formule $\Lambda$ est satisfaite si et seulement si tous les élément du domaine d’interprétation sont plombiers et riches, ce qui n’est pas le cas de la formule $\Theta$.

Voici une interprétation qui satisfait $\Theta$ mais qui falsifie $\Lambda$.

Domaine : {donald, picsou}
riche(donald) = faux, riche(picsou) = vrai
plombier(donald) = faux, plombier(picsou) = vrai

Exercice d’entrainement D.ent1.6

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Nul n’a assassiné un souverain auquel il est fidèle.

Les symboles relationnels sont $\text{souv}/1$, $\text{ass}/2$ et $\text{fid}/2$.

"Indice"

Une solution a la structure suivante :

$\Omega = \neg \exists X[\underbrace{~\exists S(~~\sigma ~~)~}_{\omega}]$

Supposons, pour faciliter le raisonnement, que le domaine d’interprétation soit un ensemble de personnes. $\Omega$ se présente comme la négation d’une formule qui modélise "Au moins une personne personne a assassiné un souverain auquel elle est fidèle".

La sous-formule $\omega$ modélise : "Il existe un souverain auquel $X$ est fidèle et qui a été assassiné par $X$".

"Réponse"

$\neg \exists X$ $[~\exists S(\text{souv}(S) \wedge \text{fid}(X,S) \wedge \text{ass}(X,S))~]$

Exercice d’entrainement D.ent1.6

Soit la formule suivante :

$\Sigma = $ $\forall X$ $[\exists Y~p(X,Y) \to \exists Y~q(X,Y)]$

Parmi les interprétations suivantes ayant pour domaine ${1,2}$, lesquelles sont des modèles de $\Sigma$ ?

plfd18

"Réponse"

Pour que l’interprétation soit un modèle de $\Sigma$, il faut que pour toute valeur $X$ du domaine d’interprétation,

soit aucune flèche ne parte de $X$ dans la représentation sagittale de $p$,
soit une flèche parte de $X$ dans la représentation sagittale de $q$.

Les interprétations qui répondent à ce critère sont celles numérotées 1 et 3.

Exercice d’entrainement D.ent1.7

On définit une relation $r$ sur une ensemble $D$ par un ensembles de couples d’éléments de $D$ (flèches sur la représentation sagittale).

La relation complémentaire d’une relation $r$ est définie par l’ensemble :

{$(x,y) \in D \times D$, $(x,y) \notin r$}

Modélisez la propriété…

$q$ est la relation complémentaire de $r$

…en utilisant les symboles de prédicats $r/2$ et $q/2$.

"Réponse"

$\forall X \forall Y$ $[r(X,Y) \leftrightarrow \neg q(X,Y)]$

On peut aussi l’écrire avec deux implications :

$\forall X \forall Y$ $[r(X,Y) \to \neg q(X,Y)]$ $\wedge$ $[\neg r(X,Y) \to q(X,Y)]$

Ou encore :

$\forall X \forall Y$ $[r(X,Y) \to \neg q(X,Y)]$ $\wedge$ $[\neg q(X,Y) \to r(X,Y)]$

Toutes ces formules sont logiquement équivalentes.

Itération D.ent2

Exercice d’entrainement D.ent2.1

Soit la formule :

$\Sigma =$ $\exists Y \forall X$ $\underbrace{[\underbrace{(p(X) \wedge q(Y))}_ {\sigma_1} \to \underbrace{(p(X) \vee q(Y))}_ {\sigma_2}]} _{\sigma}$

L’interprétation suivante est-elle un modèle de $\Sigma$ ? (Les valeurs entourées sont celles qui satisfont l’interprétation du symbole relationnel d’arité 1 mentionné au dessus.)

"Indice"

Les questions auxquelles il faut répondre pour conclure sont :

Pour $Y=1$, $\sigma$ s’interprète-t-elle à $\text{vrai}$ pour toutes les valeurs de $X$ ?
Pour $Y=2$, $\sigma$ s’interprète-t-elle à $\text{vrai}$ pour toutes les valeurs de $X$ ?
Pour $Y=3$, $\sigma$ s’interprète-t-elle à $\text{vrai}$ pour toutes les valeurs de $X$ ?
Pour $Y=4$, $\sigma$ s’interprète-t-elle à $\text{vrai}$ pour toutes les valeurs de $X$ ?

Si la réponse à une de ces 4 questions est positive, alors l’interprétation satisfait $\Sigma$ (i.e., est un modèle de $\Sigma$).

"Réponse"

Par chance, on peut répondre oui à la question 1. Si $Y=1$ alors $q(Y)$ est vrai donc $\sigma_2$ est vraie, donc, d’après la table de vérité du connecteur $\to$, $\sigma$ est vraie. (La seule manière de rendre fausse une formule du type $\omega \to \mu$ est que $\omega$ soit vraie et $\mu$ soit fausse.)

L’interprétation satisfait $\Sigma$.

Exercice d’entrainement D.ent2.2

Soit la formule :

$\Sigma =$ $[\forall X(g(X) \vee h(X))]$ $\to$ $([\forall X ~ g(X)] \vee [\forall X ~ h(X)])$

Donnez une interprétation $I_1$ qui satisfait $\Sigma$ (Réponse 1) et une interprétation $I_2$ qui falsifie $\Sigma$ (Réponse 2). ces deux interprétations doivent avoir pour domaine ${1,2}$.

"Réponse1"

Pour $I_1$, on peut simplement prendre par exemple l’interprétation dans laquelle $g$ et $h$ sont toujours interprétés à $\text{vrai} $ :

Mais celle ou les deux symboles relationnels sont toujours interprétés à $\text{faux}$ convient aussi, et il y en a d’autres qui satisfont la formule, incluant toutes celles où $g$ est toujours vrai et celles ou $h$ est toujours vrai.

"Réponse1"

Voici un exemple d’interprétation qui falsifie $\Sigma$ :

En effet, cette interprétation satisfait la sous-formule de gauche $\forall X(g(X) \vee h(X))$, mais pas la sous formule de droite $[\forall X ~ g(X)] \vee [\forall X ~ h(X)]$.

Exercice d’entrainement D.ent2.3

Soit la formule suivante :

$\Omega =$ $\underbrace{[\exists X \forall Y~ p(X,Y)]}_ {\omega_1}$ $\to$ $\underbrace{[\forall Y \exists X~ p(X,Y)]}_ {\omega_2}$

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\omega_1$ soit satisfaite ?

"Réponse"

Il faut qu’il y ait au moins une valeur d’où partent des flèches vers toutes les autres valeurs.

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\omega_2$ soit satisfaite ?

"Réponse"

Il faut que chaque valeur soit la destination d’au moins une flèche (pouvant provenir d’une autre valeur ou d’elle même).

Existe-t-il une interprétation qui satisfait $\omega_1$ et falsifie $\omega_2$ ?

"Réponse"

Non, car s’il y a une valeur du domaine d’interprétation d’où part une flèche vers toutes les autres valeurs, alors au moins une flèche arrive à chaque valeur, donc tout modèle de $\omega_1$ satisfait aussi $\omega_2$.

$\Omega$ est-elle une tautologie ?

"Réponse"

Oui, car pour toute interprétation $I$,

soit $I$ est modèle de $\omega_1$, et donc aussi de $\omega_2$ (d’après les réponses aux questions précédentes), et donc est modèle de $\Omega$,
soit $I$ falsifie $\omega_1$ et donc (d’après la table de vérité du connecteur $\to$), satisfait $\Omega$.

Si on change le sens du connecteur $\to$, la formule devient :

$\Theta =$ $\underbrace{[\forall Y \exists X~ p(X,Y)]}_ {\omega_2}$ $\to$ $ \underbrace{[\exists X \forall Y~ p(X,Y)]}_ {\omega_1}$

Cette nouvelle formule est-elle une tautologie ? Autrement dit tout modèle de $\omega_2$ est-il un modèle de $\omega_1$ ?

"Réponse"

Non. Par exemple, les interprétations suivantes satisfont $\omega_2$ et falsifient $\omega_1$.

Exercice d’entrainement D.ent2.4

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Tous les humains qui possèdent une voiture ont un chien.

Les symboles relationnels sont $\text{hum}/1$ (pour humain), $\text{chien}/1$, $\text{voit}/1$ (pour voiture) et $\text{poss}/2$ (pour possède).

"Indice"

Voici un squelette de formule modélisant la phrase.

$\forall X[~(\text{hum}(X) \wedge (~ ~ \sigma_1 ~ ~)~ ) \to (~ ~ \sigma_2 ~ ~)~]$

La sous-formule $\sigma_1$ modélise "$X$ possède une voiture" et la sous-formule $\sigma_2$ modélise "$X$ possède un chien".

"Réponse"

$\forall X\left[\right.$ $(\text{hum}(X)$ $\wedge$ $\exists V( [\text{voit}(V) \wedge \text{poss}(X,V))] )$ $\to$ $[\exists C( \text{chien}(C) \wedge \text{poss}(X,C))]$ $\left. \right]$

Exercice d’entrainement D.ent2.5

Soit la formule suivante :

$\Sigma =$ $\forall X$ $\forall Y$ $[p(X,Y) \to (q(X) \wedge \neg q(Y))]$

On considère uniquement les interprétations ayant pour domaine ${1,2}$. Donnez deux modèles de $\Sigma$ pour lesquels la représentation sagittale de $p$ comporte exactement une flèche.

"Réponse"

Combien y a-t-il de modèles pour lesquels la représentation sagittale de $p$ comporte au moins deux flèches ?

"Réponse"

Aucune. Pour satisfaire $\Sigma$, il faut que si une flèche relie une valeur $X$ à une valeur $Y$, alors $q(X)=\text{vrai}$ et $q(Y)=\text{faux}$.

Si une flèche relie une valeur à elle-même, alors aucune interprétation de $q$ ne permet de satisfaire la formule car il faudrait que pour une telle valeur, $q$ soit à la foi vrai et faux. Il reste une seule autre possibilité, qui est l’interprétation dans laquelle $p(1,2) = \text{vrai}$, $p(2,1) = \text{vrai}$, $p(1,1) = \text{faux}$, $p(2,2) = \text{faux}$, mais aucune interprétation de $q$ ne permet de satisfaire $\Sigma$ avec cette interprétation de $p$.

Combien y a-t-il de modèles pour lesquels la représentation sagittale de $p$ ne comporte aucune flèche ?

"Réponse"

Il y en a 4. En effet, si $p$ est toujours faux alors la sous-formule entre crochet est satsifaite quelle que soit l’interprétation de $q$.

Exercice d’entrainement D.ent2.6

Modélisez l’énoncé suivant :

Tout nombre pair supérieur à 2 est la somme de 2 nombres premiers.

On appelle nombre toute valeur du domaine d’interprétation. Les symboles relationnels à utiliser sont les suivants :

$\text{pair}/1$ : $\text{pair}(X)$ modélise "$X$ est pair"
$\text{prem}/1$ : $\text{prem}(X)$ modélise "$X$ est premier"
$\text{sup2}/1$ : $\text{sup2}(X)$ modélise "$X$ est supérieur à 2"
$\text{add}/3$ : $\text{add}(X,Y,Z)$ modélise "$Z$ est la somme de $X$ et $Y$"

"Indice"

Une solution peut avoir la forme suivante, dans laquelle la sous-formule $\sigma$ modélise "$X$ est un nombre pair supérieur à 2" et la sous-formule $\omega$ modélise "$X$ est la somme de 2 nombre premiers", c’est à dire "Il existe deux nombres premier $A$ et $B$ tels que $X$ est la somme de $A$ et $B$.

$\forall X$ $[$ $(~ ~ \sigma ~ ~)$ $\to$ $(~ ~ \omega ~ ~)$ $]$

"Réponse"

$\forall X$ $[$ $(\text{pair}(X) \wedge \text{sup2}(X))$ $\to$ $($ $\exists A$ $\exists B $ $[$ $\text{prem}(A)$ $\wedge$ $\text{prem}(B)$ $\wedge$ $\text{add}(A,B,X)$ $]$ $)$ $]$

C et C++ TP2

—

Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

TP2

Le but de ce TP est de réaliser un simulateur de machine de Turing en langage C.

1. La machine de Turing à réaliser

La machine que nous allons simuler est constituée :

d’une bande comportant des cases contenant des symboles,
d’une variable d’état contenant un entier positif ou nul,
d’une tête de lecture / écriture qui se situe en face d’une des cases de la bande,
d’un programme.

La bande comporte 32 cases. Chaque case contient un symbole parmi trois possibles : #, 0 et 1. Le symbole # a pour rôle de délimiter les données placées sur la bande. Ces données sont codées avec les symboles 0 et 1.

La variable d’état peut prendre une valeur entre 0 et 7. L’état 0 est appelé état initial. C’est l’état de la machine au début de l’exécution d’un programme. L’état 7 est appelé état final. On le note STOP Il indique la fin de l’exécution du programme de la machine.

La tête est représentée par une variable dont la valeur, comprise entre 0 et 31, représente la position sur la bande.

Voici une représentation schématique de la machine juste avant l’exécution de son programme. Sa tête de lecture est en position 0 (visualisée par le point sous la première case). Son état est 0. Sa bande contient des valeurs qui représentent la donnée d’entrée du programme. Le programme n’apparait pas sur le dessin.

On appelle situation le couple $(v,e)$ où $v$ est la valeur de la case désignée par la tête et $e$ l’état courant de la machine. La machine représentée ci-dessus est dans la situation (valeur : #, état : 0).

Le programme associe une action à chaque situation. Une action indique ce que doit faire la machine à la prochaine étape d’exécution du programme. Elle consiste en trois ordres :

Une valeur à écrire sur la bande à l’emplacement actuel de la tête (qui peut être identique ou différente de la valeur actuelle).
Un sens de déplacement de la tête : gauche ou droite. Le déplacement sera réalisé après l’écriture de la valeur.
La valeur du nouvel état de de la machine (qui peut être identique ou différente de celle de l’état actuel)

Voici un exemple de programme…

Situation	Action
`état = 0, valeur = #`	`#, droite, 1`
`état = 0, valeur = 0`	`0, droite, STOP`
`état = 0, valeur = 1`	`1, droite, STOP`
`état = 1, valeur = #`	`#, gauche, 2`
`état = 1, valeur = 0`	`0, droite, 1`
`état = 1, valeur = 1`	`1, droite, 1`
`état = 2, valeur = #`	`#, droite, STOP`
`état = 2, valeur = 0`	`1, gauche, 3`
`état = 2, valeur = 1`	`0, gauche, 2`
`état = 3, valeur = #`	`#, droite, STOP`
`état = 3, valeur = 0`	`0, gauche, 3`
`état = 3, valeur = 1`	`1, gauche, 3`

…qui peut être représenté graphiquement comme ci-dessous :

Pour exécuter ce programme, on regarde la situation actuelle, qui est (valeur : #, état : 0). D’après le programme, l’action à réaliser qui est #, droite, 1. La valeur # est placée dans la case désignée par la tête, qui contenait déjà cette valeur, le nouvel état est 1 et la tête se déplace à droite.

On regarde la nouvelle situation, (valeur : 0, état : 1). D’après le programme, l’action à réaliser est 0, droite, 1.

Continuez à exécuter le programme à la main. Vous devriez obtenir la donnée #0100# en début de bande lorsque l’état final est atteint.

2. Conception d’un programme de simulation

Nous sommes face à un problème d’ingénierie logicielle. Nous devons réaliser un programme qui simule la machine de Turing présentée dans le section précédente. La première étape consiste à déterminer comment la machine et son programme seront représentés. Ensuite, il faudra implémenter les fonctions permettant de simuler l’exécution du programme.

Représentation de la machine

Dans le cadre de ce TP, nous utiliseront la représentation suivante de la machine sans son programme :

La bande est représentée par un mot binaire de 64 bits placé dans une variable globale de type uint64_t.
La position de la tête est représentée par une variable de type int.
L’état est représenté par une variable de type int.

uint64_t Tape = 0;
int Head = 0;
int State = 0;

Chaque case de la bande est représentée par 2 bits consécutifs avec la convention suivante :

00 représente la valeur 0,
01 représente la valeur 1,
10 représente la valeur #.

Voici la manière d’initialiser la bande avec l’exemple présenté dans la section précédente.

Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;
//        # 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Il est crucial, en ingénierie logicielle, de bien distinguer les données représentées et les représentations de ces données utilisées par un programme. Ici, par exemple, la valeur 0 d’une case de la bande est représentée par la séquence de deux bits 00, la valeur 1 est représentée par la séquence 01, la valeur # par la séquence 10.

Représentation du programme

Représentation d’une action

Les actions sont représentées par des octets (type uint8_t) avec la convention suivantes :

Les bits de rangs 0 à 2 représentent le nouvel état.
Le bit de rang 3 représente le sens de déplacement de la tête (1 pour droite, 0 pour gauche).
Les bits de rangs 4 et 5 représentent la valeur à écrire sur la bande.
Les bits de rangs 6 et 7 ne sont pas utilisés.

À titre d’exemple, voici le codage de l’action #, droite, 3 :

Pour faciliter le codage d’une action, on utilise les masques suivants, définis sous forme de constantes :

#define BLANK 0b100000 // Valeur #
#define ZERO 0b000000 // Valeur 0
#define ONE 0b010000 // Valeur 1

#define LEFT 0b000000 // Déplacement à gauche
#define RIGHT 0b001000 // Déplacement à droite

Par exemple, l’action #, droite, 3 se code :

uint8_t action = BLANK | RIGHT | 3;

Vous pouvez le vérifier en combinant les masques à l’aide du ou bitwise |.

Exercice

Essayez de coder de cette manières chacune des actions suivantes et donnez le mots binaire correspondant.

1, gauche, 2
0, droite, 4

"Réponse1"

uint8_t action = ONE | LEFT | 2; // 00010010

"Réponse2"

uint8_t action = ZERO | RIGHT | 4; // 00001100

Représentation du programme de la machine

Le programme de la machine de Turing est représenté par un tableau d’actions. Voici le programme d’exemple donné dans la section 1 :

uint8_t Prog[] =
{
ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1, // Si état 0
ZERO|RIGHT|1, ONE|RIGHT|1, BLANK|LEFT|2, // Si état 1
ONE|LEFT|3, ZERO|LEFT|2, BLANK|LEFT|STOP, // Si état 2
ZERO|LEFT|3, ONE|LEFT|3, BLANK|LEFT|STOP // Si état 3
};

Les trois premières actions du tableau sont celles à réaliser dans les situations ou l’état est 0 et la valeur lue sur la bande respectivement 0, 1 et #.

Les trois suivantes sont celles à réaliser dans les situations ou l’état est 1 et la valeur lue sur la bande respectivement 0, 1 et #.

Etc.

D’une manière plus générale, si l’état courant est etat et la valeur lue sur la bande est val, alors l’action à réaliser est Prog[(3 * etat) + val].

Exemple : Si la situation est (valeur : 0, état : 1), alors l’action à réaliser est Prog[3], c’est à dire ZERO|RIGHT|1 : écriture d’un 0 sur la bande, déplacement à droite, le nouvel état est 1.

Exercice

Quelle est l’action à réaliser, d’après le programme d’exemple, si la situation est (valeur : 1, état : 2) ?

"Réponse"

L’action est Prog[7], c’est à dire ZERO|LEFT|2 : écriture d’un 0, déplacement à gauche, le nouvel état est 2.

Constantes et variables globales

Voici le début du programme de simulation avec les constantes et variables globales que nous avons déjà présentées, plus la constante STOP qui représente la valeur de l’état final de la machine (celui qui termine l’exécution du programme).

#include
#include
#include

#define BLANK 0b100000
#define ZERO 0b000000
#define ONE 0b010000

#define LEFT 0b0000
#define RIGHT 0b1000

#define STOP 7

int Head = 0;
uint64_t Tape = 0;
int State = 0;
uint8_t Prog[] =
{
ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1, // Si état 0
ZERO|RIGHT|1, ONE|RIGHT|1, BLANK|LEFT|2, // Si état 1
ONE|LEFT|3, ZERO|LEFT|2, BLANK|LEFT|STOP, // Si état 2
ZERO|LEFT|3, ONE|LEFT|3, BLANK|LEFT|STOP // Si état 3
};

Fonctions à définir

Lecture d’une valeur sur la bande

int read(int i);

Lit la valeur située en position i sur la bande. La valeur de retour peut être 0, 1 ou 2 (qui représente la valeur #).

Affichage

void print();

Affiche la bande, la tête de lecture et l’état courant. Avec les valeurs des variables données précédemment, les lignes…

Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;
print();

…doivent produire l’affichage suivant :

# 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [0]
T

La lettre T représente la position de la tête (ici au début de la bande). La valeur entre crochet est celle de l’état courant, donnée par la variable State.

Cette fonction appelle la fonction read.

Écriture d’une valeur sur la bande

void write(int i, int val);

Écrit la valeur val (0, 1 ou 2) en position i sur la bande. La valeur 2 se représente aussi 0b10 et correspond à la valeur notée #.

Exécution du programme

uint8_t nextAction();

Retourne la prochaine action à réaliser qui dépend :

de l’état courant (variable State),
de la valeur désignée par la tête de lecture sur la bande
et du programme.

void operate(uint8_t action);

Réalise l’action désignée par le paramètre action. Cette fonction écrit une valeur sur la bande, modifie la position de la tête (variable Head), et met à jour la valeur de l’état courant (variable State).

Si la tête de lecture est en début de bande et si l’action suppose un déplacement à gauche alors la tête doit garder sa position. Si la tête est en fin de bande et si l’action impose un déplacement à droite alors la tête doit garder sa position.

Ces deux fonctions sont appelées par la fonction run, définie ci-dessous, qui assure l’exécution du programme.

void run()
{
print();
State = 0;
while(State != END_STATE)
{
uint8_t action = nextAction();
operate(action);
print();
getchar(); // Il faut presser la touche entrée pour continuer
}
printf("Exécution terminée\n");
}

Travail à réaliser

Vous devez définir les fonctions dont le code n’a pas été donné précédemment, les tester séparément, puis tester l’exécution du programme d’exemple. Ce programme réalise une incrémentation de la valeur en base 2 située en début de bande entre les 2 symboles #.

Modifications du simulateur

À ce stade, vous devez avoir un simulateur fonctionnel et comprendre les moindres détails de son implémentation et des représentations des données utilisées. Les modifications à réaliser devront être testées avec des programmes de machine de Turing conçus à cette fin.

Augmentation du nombre d’états

La machine simulée précédemment peut admettre au plus 7 états, numérotés de 0 à 6, plus l’état final qui arrête le programme.

Vous devez modifier le simulateur, en réutilisant au maximum le code existant et les principes et représentation utilisés, pour que le nombre maximum d’états soit égal à 32 (états 0 à 30 plus l’état final codé par l’entier 31). Dans la nouvelle version, tous les bits des octets représentant les actions seront utilisés, ce qui permettra de représenter les états sur 5 bits.

Augmentation de la taille de la bande

La machine simulée précédemment a une bande de 32 cases représentée par un seul entier de type uint64_t.

Vous devez réaliser une version dans laquelle la taille de la bande, multiple de 32, est définie par une constante SIZE_TAPE. Le nombre de cases de la bande sera égal à SIZE_TAP * 32 et la bande sera représentée par le tableau :

uint64_t Tape[SIZE_TAPE] = {0};

Le codage du programme de la machine de Turing simulée doit être identique et vous devez réutiliser autant que possible les principes et la structures du simulateur précédent en modifiant certaines fonctions.

L’affichage doit être modifié de manière à que la tête apparaisse au milieu de l’écran et que seules les parties de la bande située autour, dans la limite de 16 cases de chaque coté, soient affichées.

C et C++ partie E

Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Tableaux dynamiques

Activité de découverte E.dec

E.dec1 : Tableau dynamique

Prérequis

Maîtriser la partie C (tableaux et pointeurs) et la partie D (chaînes de caractères)

Objectif

Créer un tableau pouvant être détruit lorsqu’on en a plus besoin.

Dans la partie C, nous avons vu deux sortes de tableaux :

Les tableaux globaux, qui sont créés en début de l’exécution du programme et existent pendant toute la durée de son exécution. Ils peuvent être très grands (taille limitée par la mémoire disponible) et sont accessibles par toutes les fonctions du programme.
Les tableaux locaux qui n’existent que pendant l’exécution de la fonction dans laquelle ils sont déclarés et ne sont accessibles que dans cette fonction où dans une autre fonction qui à accès à leur adresse mémoire. La taille d’un tableau local est limitée par celle de la pile d’exécution.

Mais il arrive qu’on souhaite utiliser un tableau de taille arbitrairement grande (dans la limite de la mémoire disponible) pendant une durée qui n’est ni celle de l’exécution du programme, ni celle de l’exécution d’une fonction particulière. Typiquement, un tableau créé dans une fonction et détruit dans une autre.

Moyen

Réservation d’un bloc mémoire dans le tas

Il existe une zone mémoire que nous n’avons encore jamais utilisée et qui est appelée le tas (Heap en anglais). Il est possible de réserver dans cette zone des blocs mémoire pouvant notamment être utilisés comme des tableaux. Voici un exemple de fonction qui crée dans le tas une chaîne de caractère contenant la concaténation de deux chaînes passées en arguments.

char* concat(const char* s1, const char* s2)
{
    int n1 = strlen(s1);                     
    int n2 = strlen(s2);
    char* out = (char*) malloc((n1+n2+1)*sizeof(char));  // A
    strcpy(out, s1);                                     // B
    strcpy(out + n1, s2);                                // C
    return out;                                          // D
}

La fonction main suivante donne un exemple d’utilisation.

int main()
{
    char t[] = "Tim ";
    char u[] = "et Tom";
    char* s = concat(t, u);
    printf("%s\n", s);
    return 0;
}

Il y a beaucoup de choses à dire à propos de cet exemple. La première est que, contrairement à la fonction standard strcat, la fonction concat crée une nouvelle chaîne, indépendante des deux chaînes désignées par les paramètres s1 et s2, et qui est stockée dans une nouvelle zone mémoire située dans le tas.

Le bloc mémoire contenant la chaîne retournée par concat est réservé dans le tas par un appel, en ligne A, à la fonction standard malloc, dont le nom est une abréviation de "memory allocation".

void* malloc( size_t size );

Cette fonction réserve un bloc mémoire de la taille indiquée en paramètre et en retourne l’adresse. Si la réservation est impossible, la valeur de retour est NULL. Cela se produit seulement quand il ne reste plus de zone mémoire de la taille demandée, soit parce que toute la mémoire à été utilisée, soit parce qu’elle est fragmentée.

La valeur de retour de malloc est de type void*, qu’on pourrait traduire par "pointeur sur n’importe quoi". En effet, malloc peut être utilisée pour réserver des blocs permettant de stocker n’importe quel type de données. Un cast, aussi appelé transtypage, est nécessaire pour placer l’adresse du bloc dans la variable out qui est de type pointeur sur char. Dès lors, ce bloc pourra être utilisé comme un tableau de caractères, et donc contenir une chaîne.

Exercice de découverte E.dec.x1

Pourquoi la taille du bloc est-elle égale à 1 plus la somme des tailles des chaînes désignées par les paramètres ?

"Réponse"

Le bloc doit recevoir la concaténation des chaînes désignées en paramètres. Il faut que sa taille permette le stockage des caractères de ces deux chaînes plus le marqueur de fin de chaîne.

L’exécution de la ligne A place donc dans la variable out l’adresse d’un bloc mémoire de n1 + n2 + 1 octets situé dans le tas.

    char* out = (char*) malloc((n1+ n2+1)*sizeof(char)); // A

Le bloc retourné par malloc n’est pas initialisé. Son contenu est imprévisible.

En vertu de la correspondance entre tableaux et pointeurs, l’adresse du bloc peut être utilisée comme un nom de tableau et le bloc peut être utilisé comme un tableau.

Exercice de découverte E.dec.x2

Donnez les lignes de code à ajouter juste après la ligne A pour initialiser à 0xFF tous les octets du bloc venant d’être réservé.

"Réponse"

    for(int i=0; i< n1+n2+1; i++)
    {
        out[i] = 0xFF;
    }

Le tableau dynamique s’utilise strictement de le même manière que les tableaux que nous avons vu jusqu’ici.

Le reste de la définition de la fonction concat fait appel aux connaissances abordées précédemment. On copie bout à bout les chaînes à concaténer dans le nouveau bloc mémoire, dont l’adresse est ensuite retournée.

Exercice de découverte E.dec.x3

La compilation de la fonction suivante, censée avoir le même rôle que la version précédente, produit un avertissement.

char* concat(const char* s1, const char* s2)
{
    int n1 = strlen(s1);                     
    int n2 = strlen(s2);
    char out[n1 + n2 + 1];
    strcpy(out, s1);            
    strcpy(out + n1, s2);       
    return out;         
}

Qu’est-ce qui ne va pas avec cette fonction ?

"Réponse"

Le tableau out est une variable locale. Contrairement à un tableau dynamique réservé dans le tas, ce tableau local est détruit à l’issue de l’exécution de la fonction. Son utilisation ultérieure peut avoir des conséquences imprévisibles et entraîner de graves problèmes tels que plantage, écrasement des valeurs de certaines variables…

Exercice de découverte E.dec.x4

La création de la chaîne retournée par la fonction concat est réalisée par ces deux lignes :

    strcpy(out, s1);            
    strcpy(out + n1, s2);

On aurait pu la réaliser comme ceci :

    strcpy(out, s1);            
    strcat(out, s2);

Quel est l’intérêt de la première solution par rapport à la deuxième ?

"Réponse"

La fonction strcat doit d’abord localiser le marqueur de fin de la chaîne de destination avant de commencer à recopier à la suite la chaîne désignée par s2. La première version est plus efficace, bien que la différence ne soit pas visible en pratique.

Bonus

Réserver un bloc initialisé à 0 avec calloc

Nous avons vu que la fonction malloc n’initialise pas le bloc qu’elle réserve dans le tas. Il existe une autre fonction permettant de réserver un bloc et de le remplir avec des valeurs 0.

void* calloc( size_t elementCount, size_t elementSize );

La taille du bloc réservé est égale à elementCount * elementSize. Ce bloc est initialisé avec des octets 0x00. Par exemple, la ligne suivante…

int* tab = (int*)calloc(6, sizeof(int));

…réserve un bloc mémoire utilisable comme un tableau d’entiers de 6 cellules contenant initialement chacune le valeur 0. Ces cellules sont accessibles avec la notation habituelle tab[0], tab[1], … tab[5].

Exercice de découverte E.dec.x5

Donnez les lignes de code permettant de créer un tableau dynamique de double de taille 10 initialisé avec des valeurs 0.0

"Réponse"

    double* t1 = (double*)calloc(10,sizeof(double));

Comme la valeur double 0.0 est constituée d’octets 0, le tableau dynamique est initialisé avec des valeurs 0.0.

Exercice de découverte E.dec.x6

Donnez les lignes de code permettant de créer un tableau dynamique de double de taille 10 initialisé avec des valeurs 1.0.

"Réponse"

    double* t2 = (double*)malloc(10*sizeof(double));
    for(int i=0; i<10; i++) t2[i] = t1.0;

Il aurait été dommage d’utiliser calloc, qui prend du temps à remplir le bloc de 0, alors qu’immédiatement après on va remplie le tableau dynamique avec des valeurs 1.0.

E.dec2 : Gestion de la mémoire

Prérequis

Partie C et section précédente

Objectif

Utiliser de manière rationnelle la mémoire en fonction des besoins

Dans la section précédente, nous avons vu comment créer des tableaux dynamiques. Mais pour ne pas gaspiller de la mémoire, il est important de libérer tout bloc mémoire qui n’est plus utilisé.

On peut présenter les choses de la manière suivante :

À chaque fois qu’un bloc mémoire est réservé par un appel à calloc ou malloc, on contracte une dette mémoire.
Cette dette doit être remboursée en libérant chaque bloc ayant été réservé.

Moyen

La fonction free

Tout bloc mémoire réservé avec calloc ou malloc doit être libéré avec free. Un bloc ne doit être libéré qu’une seule fois. Dans la suite, une tentative d’utiliser free à mauvais escient, comme par exemple avec une adresse ne correspondant pas à un bloc réservé dans le tas ou à un bloc déjà libéré, sera appelée accident mémoire. Ce type de situation provoque souvent un plantage du programme.

void free( void* pointer );

Observons cet exemple d’utilisation de la fonction concat définie dans la section précédente.

int main()
{
    char* s = concat("Tim ", "et Tom ");    // Ligne A
    s = concat(s, "sont sur un bateau.\n"); // Ligne B
    printf("%s\n", s);
    return 0;
}

Chaque concat réserve un bloc mémoire dans le tas, mais aucun de ces blocs n’est libéré explicitement. On a ce qu’on appelle une fuite mémoire. Les blocs sont automatiquement libérés à l’issue de l’exécution du programme, mais les bonnes pratiques de programmation imposent qu’ils soit libérés avant la fin de l’exécution, par utilisation de free.

Avant de corriger notre programme, examinons ce qui se passe en mémoire après l’exécution de la ligne A et après l’exécution de la ligne B.

On voit que le premier bloc, qui contient la chaîne "Tim et Tom ", n’a pas été libéré avant que l’adresse du deuxième soit placée dans la variable s. En plus, l’adresse de ce bloc a été perdue, écrasée dans s par celle du nouveau bloc, il ne pourrait donc plus être libéré par free, même si on le voulait. On dit qu’il y a une fuite mémoire lorsqu’un bloc mémoire est réservé dans le tas et n’est jamais libéré par free.

Voici la bonne manière de procéder pour obtenir le même résultat, c’est à dire une chaîne obtenue par la concaténation de "Tim ", "et Tom " et "sont sur un bateau" pointée par s, qui est affichée à l’écran.

int main()
{
    char* s = concat("Tim ", "et Tom ");
    char* t = concat(s, "sont sur un bateau.\n");
    free(s);
    printf("%s\n", t);
    free(t);
    return 0;
}

La première chaîne produite par concat est pointée par s. On doit en garder l’adresse pour pouvoir libérer ultérieurement la mémoire qu’elle occupe dans le tas. On place donc le résultat du deuxième appel de concat dans une nouvelle variable t. On peut libérer le premier bloc, puis utiliser le deuxième, pointé par t. Une fois qu’on en a plus besoin on libère la mémoire qu’il occupe dans le tas.

Exercice de découverte E.dec.x7

Tentez d’identifier le problème dans le programme suivant.

int main()
{
    char* s = malloc(10 * sizeof(char)); // Ligne A
    s = "Bonjour";                       // Ligne B
    printf("%s\n", s);                   // Ligne B
    free(s);                             // Ligne C
}

"Réponse"

On a une fuite mémoire et un accident mémoire. Après exécution de la ligne A, la variable s pointe un bloc mémoire réservé dans le tas. Mais immédiatement après, en ligne B, la variable s reçoit l’adresse d’une chaîne située dans la zone mémoire réservée aux constantes.

L’instruction s = "Bonjour" ne copie pas "Bonjour" dans le bloc mémoire désigné par s. Pour celà il faudrait utiliser strcpy. Elle copie l’adresse de la chaîne "Bonjour" dans la variable s. La ligne B s’exécute sans problème et affiche "Bonjour", mais la ligne C tente de libérer un bloc mémoire qui n’est pas dans le tas et n’est pas celui réservé par malloc. On a donc accident mémoire. Et comme le bloc réservé par malloc ‘est pas libéré par un appel à free, on a une fuite mémoire.

Voici une version correcte du programme :

int main()
{
    char* s = malloc(10 * sizeof(char)); // Ligne A
    strcpy(s, "Bonjour");                // Ligne B
    printf("%s\n", s);                   // Ligne B
    free(s);                             // Ligne C
}

Bonus

Changer la taille d’un tableau avec realloc

La fonction standard realloc permet de modifier la taille d’un bloc déjà réservé. Seuls les bloc réservés dans le tas peuvent être redimensionnés. Redimensionner un bloc ne change pas la dette mémoire associée. Le bloc devra être libéré, une seule fois, par un appel de la fonction free.

void* realloc( void* pointer, size_t memorySize );

Le premier paramètre est l’adresse du bloc à redimensionner. Si sa valeur est NULL, alors realloc réserve un nouveau bloc, comme le ferait malloc. Le deuxième paramètre est la nouvelle taille du bloc. Elle peut être plus petite ou plus grande que la taille précédente.

Attention, cette opération peut déplacer le bloc et donc changer son adresse. La valeur de retour est la nouvelle adresse du bloc. Si le bloc est déplacé, sont ancien contenu est recopié au nouvel emplacement.

Cet exemple montre comment on utilise realloc pour augmenter la taille d’un bloc.

int main()
{
    char* s = malloc(4*sizeof(char)); // Ligne A
    strcpy(s, "aaa");                 // Ligne B
    s = realloc(s, 7*sizeof(char));   // Ligne C
    strcat(s, "bbb");                 // Ligne D
    printf("%s\n", s);   
    free(s);                          // Ligne E
}

En ligne A, on réserve un bloc mémoire dans lequel est recopié en ligne B la chaîne "aaa". On note que ce bloc doit avoir une taille permettant de stocker 4 caractères, en comptant le marqueur de fin.

En ligne C, on augmente la taille du bloc pointé par s, de manière à pouvoir concéténer, en ligne D, la chaîne "bbb" à celle initialement contenue dans le bloc.

En ligne E, la mémoire occupée par le bloc est libérée.

Exercice de découverte E.dec.x8

Voici une variante du programme précédent qui pose problème. Identifiez s’il y a fuite ou accident mémoire et expliquez pourquoi.

int main()
{
    char* s = malloc(4*sizeof(char));     // Ligne A
    strcpy(s, "aaa");                     // Ligne B
    char* t = realloc(s, 7*sizeof(char)); // Ligne C
    strcat(s, "bbb");                     // Ligne D
    printf("%s\n", t);   
    free(s);                              // Ligne E
    free(t);                              // Ligne F
}

"Réponse"

Deux scénarios sont envisageables et conduisent tous les deux à un accident mémoire.

Soit realloc ne change pas l’adresse du bloc. Dans ce cas, les variables t et s pointent le même bloc, qui sera détruit deux fois. On a donc un accident mémoire.

Soit la réallocation change l’adresse du bloc, alors t pointe le nouvel emplacement et free(t) libérera correctement la mémoire. Mais s pointera l’ancien emplacement où ne se trouve plus de bloc réservé. L’appel free(s) provoquera un accident mémoire.

E.dec3 : Tableau dynamique à 2 dimensions

Prérequis

Parties C et D et section précédentes de cette partie E.

Objectif

Exploiter des tableaux à 2 dimensions situé dans le tas

Jusqu’à maintenant, nous n’avons utilisé que des tableau à une dimension. Il existe plusieurs manières de gérer en C des tableaux à plusieurs dimensions. L’approche native consiste à représenter de tels tableaux par un seul bloc mémoire. Elle est compliquée et manque de souplesse. Nous ne l’aborderons pas dans cet enseignement. Nous allons adopter une approche plus moderne, comparable à celle utilisée par le langage Java.

Moyen

Utiliser un tableau de pointeurs sur des tableaux

Nous allons présenter le principe utilisé avec un exemple dans lequel on représente des matrices carrées de dimension 3 qui pourraient être utilisées pour modéliser des transformations géométriques.

Pour éviter d’utiliser une constante numérique littérale et pour pouvoir modifier facilement la dimension de nos matrices, nous définissions la constante :

#define DIM 3

Voici la représentation en mémoire d’un tableau de 3 lignes et 3 colonnes.

La variable m désigne un tableau dont chaque cellule pointe un tableau dont chaque cellule contient une valeur de type double.

Les valeurs située dans le tableau désigné par m sont de type double*, donc m doit être de type double**. Ce premier tableau doit être réservé par la ligne :

double** mat = (double**)malloc(DIM*sizeof(double*));

Chaque cellule de ce tableau désigne une ligne du tableau 2D, qui est elle même représentée par un tableau de double. Donc par exemple pour créer la première ligne il faut écrire :

mat[0] = (double*)calloc(DIM, sizeof(double));

La création d’un tableau de 3 x 3 nécessite donc la réservation de 4 blocs mémoire dans le tas. Il est judicieux de regrouper toutes les opérations nécessaires dans une fonction.

double** creeMatrice()
{
    double** mat = (double**)malloc(DIM*sizeof(double*));
    for(int i=0; i<DIM; i++)
    {
        mat[i] = (double*)calloc(DIM, sizeof(double));
    }
    return mat;
}

La fonction creeMatrice réalise la création d’une matrice carrée de dimension DIM dont les valeurs, de type double, sont initialisées à 0.0.

La valeur située en ligne i et colonne j est dans la cellule mat[i][j]. En effet, mat[i] est un pointeur qui désigne le tableau représentant la ligne i, et en vertu de la correspondance entre tableaux et pointeurs, mat[i][j] est la cellule d’indice j de cette ligne.

Exercice de découverte E.dec.x9

Définissez la fonction…

void afficheMatrice(double** mat);

…qui affiche la matrice désignée par mat. Chaque valeur doit être affichée au format %.02f. Les valeurs de chaque ligne doivent être séparées par des espaces.

"Réponse"

void afficheMatrice(double** mat)
{
    for(int i=0; i<DIM; i++)
    {
        for(int j=0; j<DIM; j++)
        {
            printf(" %.02f", mat[i][j]);
        }
        printf("\n");
    }
}

Exercice de découverte E.dec.x10

Réalisez une fonction main qui crée une matrice en utilisant la fonction creeMatrice et qui l’affiche en utilisant la fonction afficheMatrice.

"Réponse"

int main()
{
    double** m = creeMatrice();
    afficheMatrice(m);
}

Pour libérer correctement la mémoire occupée par une matrice, il faut libérer tous les blocs mémoires qui la constituent. Pour une matrice de 3 x 3, cela suppose 4 appels à free. Pour faciliter cette tâche, il est judicieux de définir une fonction :

void detruitMatrice(double** m)
{
    for(int i=0; i<DIM; i++)
    {
        free(m[i]);
    }
    free(m);
}

Bonus

Simplifier les notation en définissant un type.

Les notations avec plusieurs étoiles peuvent paraître un peu lourdes. Il est possible de les alléger en définissant de nouveaux type à l’aide de typedef. Par exemple, si on écrit…

typedef double** matrice;

…on définit un type matrice qui est équivalent à double**. Voici le code des fonctions de création, affichage et destruction de matrices utilisant ce type :

#define DIM 3

typedef double** matrice;

matrice creeMatrice()
{
    matrice mat = (matrice)malloc(DIM*sizeof(double*));
    for(int i=0; i<DIM; i++)
    {
        mat[i] = (double*)calloc(DIM, sizeof(double));
    }
    return mat;
}

void afficheMatrice(matrice mat)
{
    for(int i=0; i<DIM; i++)
    {
        for(int j=0; j<DIM; j++)
        {
            printf(" %.02f", mat[i][j]);
        }
        printf("\n");
    }
}

void detruitMatrice(matrice m)
{
    for(int i=0; i<DIM; i++)
    {
        free(m[i]);
    }
    free(m);
}

Exercice de découverte E.dec.x11

Définissez une fonction main qui crée la matrice :

\[ \begin{pmatrix}
1.0 & 0.0 & 0.0\\
0.0 & 1.0 & 0.0\\
0.0 & 0.0 & 1.0
\end{pmatrix}
\]

Puis l’affiche et la détruit.

"Réponse"

int main()
{
    matrice m = creeMatrice();
    m[0][0] = 1.0; m[1][1] = 1.0; m[1][1] = 1.0; 
    afficheMatrice(m);
    detruitMatrice(m);
    return 0;
}

L’activité est terminée. Vous devez évaluer votre réussite de cette activité par une valeur entre 1 et 4.

Vous n’avez presque rien compris et échoué à plus de la moitié des exercices de découverte.
Vous estimez avoir compris une partie des explications et vous avez réussi au moins la moitié des exercices de découverte, mais certaines notions sont encore floues.
Vous estimez avoir bien compris les explications et vous avez réussi presque tous les exercices de découverte, mais certaines notions abordées étaient nouvelles et vous penser avoir besoin d’un entrainement pour bien les assimiler et être en mesure de les utiliser en pratique.
Vous connaissiez déjà tout ce qui a été présenté (sauf peut être quelques détails) et il ne sera pas nécessaire que vous reveniez sur ces notions.

Si votre score est 1 ou 2, vous devrez refaire cette activité rapidement, mais après au moins une nuit de sommeil, avant de passer aux activités suivantes. Si votre score est 3 ou 4, vous devez faire les activités suivantes et il ne sera pas nécessaire de revenir sur cette activité, à part pour rechercher des informations utiles pour d’autres activités.

Activité d’entraînement E.ent

Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment. Elle se décompose en plusieurs itérations : ent1, ent2, etc.

Vous devez réaliser au moins une itération et évaluer votre niveau de réussite par une valeur entre 1 et 4 selon les critères habituels. L’itération que vous avez traité le plus récemment est appelée itération courante. On appelle itération suivante celle qui suit l’itération courante, excepté si l’itération courante est la dernière disponible, auquel cas l’itération suivante est la première itération.

Si le résultat est 1, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entraînement en réalisant à nouveau l’itération courante. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.

Si le résultat est 2, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explication de l’activité de découverte précédente et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez réaliser l’itération suivante de l’activité d’entraînement actuelle après un délai d’au moins deux jours et d’au plus une semaine.

Si le résultat est 3, vous devrez revenir traiter l’itération suivante après un délai de plusieurs semaines.

En traitant les exercices, vous devrez considérer que les paramètres des fonctions ont des valeurs correctes. Il ne vous est pas demandé de vérifier si certaines valeurs sont aberrantes au regard de ce que demande l’énoncé. Par exemple, si un paramètre doit être positif pour que le traitement demandé soit possible, vous considérerez que la fonction sera appelée avec une valeur positive de ce paramètre.

Vous pouvez utiliser un ordinateur pour tester vos solutions et les corriger en cas de comportement inattendu. C’est même recommandé, à condition de commencer par réfléchir avant de vous jeter sur le clavier. Si vous pensez avoir une solution différente de celle proposée, ce qui peut arriver souvent, vous ne devez en aucun cas rester dans le doute. Vous devez vérifier si votre solution est correcte ou non, soit en testant votre solution avec un ordinateur, soit en demandant à une personne enseignante.

Itération E.ent1

Exercice d’entrainement E.ent1.1

Définissez une fonction…

char* randStr(const char* caracteres, int n);

…qui produit une chaîne de n caractères tirés aléatoirement dans la chaîne caracteres. La chaîne produite doit être située dans le tas. Par exemple, la ligne…

char* s = randStr("abc", 4);

…produit une chaîne de 4 caractères tirés aléatoirement parmi les caractères a, b et c. Une telle chaîne pourrait par exemple être "abba", ou "cabc".

"Indice"

char* randStr(const char* caracteres, int n)
{
    char* out = (char*)malloc((n+1)*sizeof(char)); // Ligne A
    int nchars = strlen(caracteres);               // Ligne B
    // À compléter
    return out;                                    // Ligne C
}

Voici le début du code de la fonction. La ligne A réserve le bloc mémoire qui contiendra la chaîne produite. Attention, la chaîne doit contenir n caractères plus un marqueur de fin. La ligne B détermine la longueur de la chaîne contenant les caractères éligibles pour être placés dans le chaîna à produire. La ligne C retourne l’adresse de la chaîne produite après qu’elle ait été remplie avec des caractères tirés aléatoirement dans la chaîne caracteres, sans oublier le marqueur de fin.

"Réponse"

char* randStr(const char* caracteres, int n)
{
    char* out = (char*)malloc((n+1)*sizeof(char));
    int nchars = strlen(caracteres);
    for(int i=0; i<n; i++)
    {
        out[i] = caracteres[rand()%nchars];
    }
    out[n] = 0;
    return out;
}

Définissez une fonction main qui crée (en utilisant randStr) une chaîne aléatoire constituée de 6 lettre majuscules tirées au hasard dans l’alphabet, puis qui affiche cette chaîne. La mémoire réservée dans le tas doit être libérée après utilisation.

"Réponse"

int main()
{
    srand(time(NULL));
    char* s = randStr("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 6);
    printf("%s\n", s);
    free(s);
}

Exercice d’entrainement E.ent1.2

Donnez les lignes de code permettant de réaliser les actions suivantes :

Créer dans la pile un tableau d’entiers de taille 5 initialisé avec les valeurs 1,2,3,4,5.
Créer dans le tas un tableau d’entiers de taille 5 non initialisé.
Recopier les valeurs du premier tableau dans le deuxième.
Placer la valeur 12 dans la cellule d’indice 2 du deuxième tableau.
Libérer la mémoire ayant été réservée dans le tas.

"Réponse"

    int t[] = {1,2,3,5,4};
    int* w = (int*)malloc(5 * sizeof(int));
    for(int i=0; i<5; i++) w[i] = t[i];
    w[2] = 12;
    free(w);

Exercice d’entrainement E.ent1.3

Cet exercice est un bon entraînement pour ce qui concerne les pointeurs, tableaux et gestion dynamique de la mémoire. Mais pour une implémentation plus professionnelle du concept, il est préférable d’utiliser en plus la notion de structure, qui sera présentée dans la partie suivante. Il ne faut donc pas considérer l’implémentation proposée ici comme une solution définitive, mais comme une étape d’apprentissage.

On reprend le tableau 2D définit par le type matrice présenté précédemment.

#define DIM 3

typedef double** matrice;

matrice creeMatrice()
{
    matrice mat = (matrice)malloc(DIM*sizeof(double*));
    for(int i=0; i<DIM; i++)
    {
        mat[i] = (double*)calloc(DIM, sizeof(double));
    }
    return mat;
}

void afficheMatrice(matrice mat)
{
    for(int i=0; i<DIM; i++)
    {
        for(int j=0; j<DIM; j++)
        {
            printf(" %.02f", mat[i][j]);
        }
        printf("\n");
    }
}

void detruitMatrice(matrice m)
{
    for(int i=0; i<DIM; i++)
    {
        free(m[i]);
    }
    free(m);
}

Vous devez faire une première modification pour représenter, avec un type que nous nommerons tab2Ddouble, des tableaux dont le nombre de lignes est définit par une constante NLIGNES et le nombre de colonnes par une constante NCOLONNES.

#define NLIGNES 2
#define NCOLONNES 3

// À compléter

tab2Ddouble creeTab2D()
{
    // À compléter
}

void afficheTab2D(tab2Ddouble tab)
{
    // À compléter
}

void detruitTab2D(tab2Ddouble tab)
{
    // À compléter
}

"Solution"

#define NLIGNES 2
#define NCOLONNES 3

typedef double** tab2Ddouble;

tab2Ddouble creeTab2D()
{
    tab2Ddouble tab = (tab2Ddouble)malloc(NLIGNES*sizeof(double*));
    for(int i=0; i<NLIGNES; i++)
    {
        tab[i] = (double*)calloc(NCOLONNES, sizeof(double));
    }
    return tab;
}

void afficheTab2D(tab2Ddouble tab)
{
    for(int i=0; i<NLIGNES; i++)
    {
        for(int j=0; j<NCOLONNES; j++)
        {
            printf(" %.02f", tab[i][j]);
        }
        printf("\n");
    }
}

void detruitTab2D(tab2Ddouble tab)
{
    for(int i=0; i<NLIGNES; i++)
    {
        free(tab);
    }
    free(tab);
}

Une personne débutante en programmation C écrit la fonction suivante ayant pour rôle d’échanger les contenus de deux tableaux.

void exgTab2D(tab2Ddouble t1, tab2Ddouble t2)
{
    tab2Ddouble tmp = t1;
    t1 = t2;
    t2 = tmp;
}

Mais la fonction ne remplit pas son rôle. Si on exécute le programme suivant :

int main()
{
    tab2Ddouble tab1 = creeTab2D();
    tab2Ddouble tab2 = creeTab2D();
    tab1[0][0] = 3.0;
    tab2[1][2] = 9.0;
    
    printf("Avant :\n");
    afficheTab2D(tab1);
    printf("\n");
    afficheTab2D(tab2);
    
    exgTab2D(tab1, tab2);
    
    printf("\nAprès :\n");
    afficheTab2D(tab1);
    printf("\n");
    afficheTab2D(tab2);

    return 0;
}

On obtient exactement le même affichage avant et après appel de la fonction. Les tableaux désignés par tab1 et tab2 n’ont pas été échangés. Vous devez menez une enquête afin de trouver une explication du phénomène.

"Réponse"

Quand on appelle exTab2D(tab1, tab2), les valeurs de tab1 et tab2, c’est à dire les adresses des 2 tableaux, sont copiées dans les paramètres t1 et t2 de la fonction. Ce sont ce copies que le fonction échange, ce qui n’affecte pas les contenus des variables tab1 et tab2.

Voici la situation en mémoire au début de l’exécution de la fonction exTab2D.

Et voici la situation en mémoire à la fin de l’exécution de cette fonction.

Vous devez trouver un moyen de coder cette fonction de manière à ce que les contenus des tableaux soient effectivement échangés.

"Indice1"

On pourrait échanger chaque valeur du premier tableau avec la valeur située en même position dans le deuxième, mais une solution plus rapide est d’échanger le pointeur sur chaque ligne d’un des tableau avec le pointeur sur la ligne ayant la même position dans l’autre.

"Solution"

void exgTab2D(tab2Ddouble t1, tab2Ddouble t2)
{
    for(int i=0; i<NLIGNES; i++)
    {
        double* tmp = t1[i];
        t1[i] = t2[i];
        t2[i] = tmp;
    }
}

Définissez une variante qui accepte en paramètres les adresses des variables désignant les tableaux à échanger :

void exgTab2D(tab2Ddouble* t1, tab2Ddouble* t2);

Donnez la modification à faire dans la fonction main précédente pour appeler correctement la nouvelle fonction d’échange.

"Solution"

void exgTab2D(tab2Ddouble* t1, tab2Ddouble* t2)
{
    tab2Ddouble tmp = *t1;
    *t1 = *t2;
    *t2 = tmp;
}

Ce sont les valeurs pointées par t1 et t2 qu’il faut échanger, et on accède à ces valeurs par l’opérateur de "dépointage" *.

Dans la fonction main, il faut remplacer la ligne…

exgTab2D(tab1, tab2);

…par la ligne :

exgTab2D(&tab1, &tab2);

En effet, ce sont les adresses des variables tab1 et tab2 qui doivent être passées en arguments.

Dessinez la situation en mémoire au début et à la fin de l’exécution de cette nouvelle variante de la fonction appelée par main.

"Réponse"

Au début de l’exécution :

À la fin de l’exécution :

Itération E.ent2

Exercice d’entrainement E.ent2.1

Définissez une fonction…

char* cloneStr(const char* s);

…qui produit une chaîne située dans le tas, strictement identique à la chaîne désignée par s, mais complètement indépendante en mémoire (une modification de la chaîne produite ne doit pas affecter la chaîne ayant servi de modèle, et réciproquement).

"Indice"

char* cloneStr(const char* s)
{
    int n = strlen(s);
    char* out = (char*)malloc((n+1)*sizeof(char));
    // À compléter
}

"Réponse"

char* cloneStr(const char* s)
{
    int n = strlen(s);
    char* out = (char*)malloc((n+1)*sizeof(char));
    strcpy(out, s);
    return out;
}

Définissez une fonction main qui crée (en utilisant cloneStr) une copie de la chaîne "Bonjour", puis qui affiche cette chaîne. La mémoire réservée dans le tas doit être libérée après utilisation.

"Réponse"

int main()
{
    char* s = cloneStr("Bonjour");
    printf("%s\n", s);
    free(s);
}

Exercice d’entrainement E.ent2.2

Donnez les lignes de code permettant de réaliser les actions suivantes :

Créer dans le tas un tableau d’entiers de taille 5 dont les 4 premières cellules contiennent la valeur 0 et la dernière cellule contient la valeur 2.
Créer dans la pile tableau d’entiers de taille 5 non initialisé.
Recopier les valeurs du premier tableau dans le deuxième.
Libérer la mémoire ayant été réservée dans le tas.

"Réponse"

    int* t = (int*)calloc(5, sizeof(int));
    t[4] = 2;
    int w[5];
    for(int i=0; i<5; i++) w[i] = t[i];
    free(t);

Exercice d’entrainement E.ent2.3

Cet exercice est un bon entraînement pour ce qui concerne les pointeurs, tableaux et gestion dynamique de la mémoire. Mais pour une implémentation plus professionnelle du concept, il est préférable d’utiliser en plus la notion de structure, qui sera présentée dans la partie suivante. Il ne faut donc pas considérer l’implémentation proposée ici comme une solution définitive, mais comme une étape d’apprentissage.

On définit la constante et le type suivants :

#define SIZE 3
typedef char** tabstr;

Le type tabstr représente un tableau de chaînes de caractères de taille SIZE dont certaines cellules peuvent être vides. Une cellule vide contient la valeur NULL, alors qu’une cellule non vide contient un pointeur sur char désignant une chaîne stockée dans le tas.

Les fonctions suivantes permettent l’utilisation de tableaux de chaîne de type tabstr.

// Crée un tableau de SIZE cellules vides.
tabstr creeTabstr();

// Place une copie de la chaîne désignée par str dans la cellule i
// du tableau désigné par tab.
void assigne(tabstr tab, int i, char* str);

// Affiche le contenu du tableau désigné par tab.
// Les cellules vides sont représentées par ---
void affiche(tabstr tab);

// Libère toute la mémoire occupée par le tableau désigné par tab.
void detruit(tabstr tab);

Voici un exemple de mise en oeuvre de ces fonctions :

int main()
{
    tabstr t = creeTabstr();
    assigne(t,0,"Tim");
    assigne(t,1,"Tom");
    assigne(t,0,"Anne");
    affiche(t);
    detruit(t);
    return 0;
}

L’exécution de main produit l’affichage :

Anne
Tom
---

Dessinez la situation en mémoire juste après l’exécution de la fonction affiche appelé par main.

"Réponse"

Donnez les définitions des fonctions suivantes :

creeTabstr
affiche
assigne
detruit

Vous devez prêter une attention particulière à éviter les fuites et accidents mémoire. Lorsqu’on crée un tableau dynamique de pointeurs avec calloc, ces cellules contiennent toutes la valeur NULL, qui est représentée en mémoire par des octets ayant la valeur 0.

Pour coder correctement les fonctions affiche, assigne et detruit, il faut bien distinguer le cas d’une cellule contenant NULL d’une cellule pointant une chaîne préalablement assignée.

"Réponse1"

tabstr creeTabstr()
{
    tabstr out = (tabstr)calloc(SIZE, sizeof(char*));
    return out;
}

On réserve un bloc mémoire qui sera utilisé comme tableau de SIZE pointeurs de type char*. La fonction calloc initialise le bloc avec des 0, donc les cellules du tableau contiennent NULL.

"Réponse2"

void affiche(tabstr tab)
{
    for(int i=0; i<SIZE; i++)
    {
        if(tab[i]==NULL) printf("---\n");
        else printf("%s\n", tab[i]);
    }
}

Il ne faut pas utiliser printf avec le format %s dans le cas où la cellule contient NULL, mais faire un affichage spécifique dans ce cas.

"Réponse3"

void assigne(tabstr tab, int i, char* str)
{
    if(tab[i] != NULL) free(tab[i]);
    int n = strlen(str);
    tab[i] = (char*)malloc((n+1)*sizeof(char));
    strcpy(tab[i], str);
}

Il faut penser à beaucoup de choses pour coder correctement cette fonction :

Si la cellule à assigner pointe déjà une chaîne, c’est à dire si elle a déjà été préalablement assignée, il faut libérer la mémoire occupée par la chaîne précédente, sinon on aura une fuite mémoire.
Il faut réserver un bloc mémoire pour y placer la copie de la chaîne à assigner à la cellule d’indice i.
La taille du bloc à réserver doit prévoir d’y placer la copie de la chaîne à assigner sans oublier le marqueur de fin.
La copie de la chaîne à assigner dans le bloc destiné à la contenir doit être réalisée par un appel à la fonction strcpy et en aucun cas avec =.

"Réponse4"

void detruit(tabstr tab)
{
    for(int i=0; i<SIZE; i++)
    {
        if(tab[i] != NULL) free(tab[i]);
    }
    free(tab);
}

Il faut libérer la mémoire utilisée pour stocker les chaînes, mais il peut y avoir des cellules vides (contenant NULL), qui ne pointent donc aucune chaîne. Il ne faut jamais appeler free avec NULL en argument, cela provoque un accident mémoire.

Itération E.ent3

Exercice d’entrainement E.ent3.1

Définissez une fonction…

char* addChar(const char* s, char c);

…qui produit une obtenue en ajoutant le caractère c a une copie de la chaîne désignée par s. Par exemple, l’appel addChar("Tim", 'e') retourne l’adresse d’une chaîne "Time" située dans le tas.

"Indice"

char* addChar(const char* s, char c)
{
    int n = strlen(s);
    char* out = (char*)malloc((n+2)*sizeof(char));
    // À compléter
    return out;
}

La partie de la fonction donnée ici réserve le bloc mémoire dans lequel sera placé la chaîne à produire. Il faut prévoir la place pour placer le caractère à ajouter et le marqueur de fin. Il reste à terminer la construction.

"Réponse"

char* addChar(const char* s, char c)
{
    int n = strlen(s);
    char* out = (char*)malloc((n+2)*sizeof(char));
    strcpy(out, s);
    out[n] = c;
    out[n+1] = 0;
    return out;
}

Remarque : la fonction strcat n’est pas utilisable pour concaténer un caractère à une chaîne. Le caractère est ajouté directement dans le tableau représentant la chaîne, à l’emplacement approprié.

Exercice d’entrainement E.ent3.2

Donnez les lignes de code permettant de réaliser les actions suivantes :

Créer dans la pile une chaîne initialisée avec "abcde".
Créer dans le tas un tableau de 6 caractères.
Recopier dans ce tableau la chaîne créée à l’étape 1.
Libérer la mémoire ayant été réservée dans le tas.

"Réponse"

    char t[] = "abcde";
    char* s = malloc(6 * sizeof(char));
    strcpy(s, t);
    free(t);

Activité de consolidation E.top

Réaliser cette activité consiste à traiter un des exercices de consolidation proposés. Si vous réalisez plusieurs fois cette activité, laissez passer au moins une semaine entre chaque itération et traitez à chaque fois un exercice différent.

Exercice de consolidation C.top1

On appelle tableau informé de taille n un tableau d’entiers dont les valeurs sont stockées aux indices 1 à n et la longueur est stockée à l’indice 0. Un tel tableau est donc représenté par un tableau de n+1 cellules de type int. Voici un exemple de tableau de valeur de type int représentant le tableau informé de taille 4 contenant les valeurs 2, 3, 5, 7 :

On définit le type tabinf pour représenter les tableaux informés :

typedef int* tabinf;

Pour rappel, cette notation signifie que l’identificateur tabinf est équivalent à int*. En effet, un tableau informé est représenté par un tableau de valeurs de type int, qui est désigné, en vertu de la correspondance entre pointeurs et tableaux, par un pointeur sur int.

Votre première mission consiste à définir une fonction…

tabinf creeTabinf(int n);

…qui crée un tableau informé situé dans le tas contenant n valeurs 0.

"Réponse"

tabinf creeTabinf(int n)
{
 tabinf out = calloc(n+1, sizeof(int));  // Ligne A
 out[0] = n;                             // Ligne B
 return out;                             // Ligne C
}

En ligne A, un bloc mémoire permettant de stocker n+1 entiers est réservé. Ce bloc est initialisé avec des valeurs 0 et est utilisable comme un tableau classique de valeurs de type int.

En ligne B, la valeur n est placée dans la première cellule du tableau venant d’être créé, puisque ce tableau représente un tableau informé de taille n.

La ligne C retourne l’adresse du tableau informé créé.

Vous devez maintenant définir une fonction…

void printTabinf(tabinf t)

…qui affiche les valeurs d’un tableau informé (pas sa taille) séparées par des espaces.

"Réponse"

void printTabinf(tabinf t)
{
 for(int i=1; i<=t[0]; i++)
 {
     printf(" %d", t[i]);
 }
 printf("\n");
}

Définissez une fonction main qui

Crée un tableau informé de taille 10 contenant des valeurs 0 sauf à l’indice 2 où il y a la valeur 12.
Affiche ce tableau informé avec la fonction printTabinf.
Libère la mémoire utilisée par le tableau.

"Réponse"

int main()
{
 tabinf tab = creeTabinf(10);
 tab[2] = 12;
 printTabinf(tab);
 free(tab);
 return 0;
}

Nous attaquons à présent la partie plus technique de l’exercice. Vous devez définir une fonction…

void agrandit(tabinf* t, int delta);

…qui agrandit un tableau informé en lui ajoutant delta valeurs supplémentaires, toutes initialisées à 0. Vous ne devez pas utiliser (dans cette première version), la fonction realloc. Donc vous devez créer un nouveau tableau plus grand et recopier dedans les valeur de l’ancien, sans oublier de détruire l’ancien ensuite, afin d’éviter toute fuite mémoire.

Il est très important de bien comprendre pourquoi le premier paramètre est de type tabinf*, c’est à dire int**, et ce que cela implique, à savoir que lors de l’appel de la fonction, il faut lui passer en premier argument l’adresse d’une variable de type tabinf.

Voici un exemple de création, puis d’agrandissement d’un tableau informé.

int main()
{
 tabinf tab = creeTabinf(10);
 tab[2] = 12;
 printTabinf(tab);
 agrandit(&tab, 5);
 printTabinf(tab);
 free(tab);
 return 0;
}

Vous devez réfléchir et répondre à la question suivante : Pourquoi une fonction agrandit avec une paramètre de type tabinf (c’est à dire int*) ne pourrait pas permettre de réaliser correctement le travail demandé, à savoir remplacer le tableau informé initialement créé par une plus grand contenant les valeurs du premier et des 0 supplémentaires ?

"Réponse"

L’agrandissement d’un tableau informé change son adresse mémoire, qui est contenue dans la variable tab. Si on passe cette adresse en argument à la fonction d’agrandissement, c’est une copie de cette adresse qui sera transmise à la fonction. Lors de son exécution, la fonction agrandit va modifier cette copie d’adresse, mais cela ne modifiera pas contenu de la variable tab qui continuera de pointer sur l’ancien tableau ou sur son fantôme si la mémoire qu’il occupait a été libérée.

Voici une illustration en image du "scénario catastrophe".

Si vous avez bien compris pourquoi c’est l’adresse d’une variable pointant le tableau informé à agrandir qu’il faut passer en paramètre à la fonction agrandit, et non directement l’adresse du tableau, alors vous pouvez continuer l’exercice en proposant une définition de la fonction demandée. Prenez le temps de bien réfléchir à toutes les étapes nécessaires.

"Indice1"

void agrandit(tabinf* t, int delta)
{
 tabinf tab = *t;   // Ligne A
 int n = tab[0];    // Ligne B
 // À compléter
 *t = newtab;       // Ligne C
}

En ligne A, l’adresse d’implantation du tableau à agrandir, que nous appellerons ancien tableau, est récupérée et placée dans la variable tab.

En ligne B, on place dans la variable n la taille de l’ancien tableau.

En ligne C, on place dans la variable pointée par t, c’est à dire la variable qui pointe initialement l’ancien tableau, l’adresse du nouveau tableau.

Voici la situation en mémoire après l’exécution de la ligne B, en supposant que la variable m, dans la fonction main, désigne le tableau à agrandir et que ce tableau, de taille 4, contient les valeurs 2, 3, 5 et 7.

Entre les ligne B et C, il faut :

Créer le nouveau tableau en utilisant calloc.
Recopier les n valeurs de l’ancien tableau dans le nouveau.
Placer la valeur appropriée dans la première cellule du nouveau tableau.
Détruire l’ancien tableau.

"Solution"

void agrandit(tabinf* t, int delta)
{
 tabinf tab = *t;
 int n = tab[0];
 tabinf newtab = (tabinf)calloc(n+delta+1, sizeof(int));
 for(int i=1; i<=n; i++) newtab[i] = tab[i];
 newtab[0] = n+delta;
 free(tab);
 *t = newtab;
}

Proposez maintenant une variante de la fonction agrandit utilisant realloc au lieu de calloc. Attention, realloc, dans le cas d’un agrandissement, recopie les valeurs de l’ancien tableau dans le nouveau, mais n’initialise pas les valeurs suivantes du nouveau tableau.

"Solution"

void agrandit(tabinf* t, int delta)
{
 tabinf tab = *t;
 int n = tab[0];
 tab = (tabinf)realloc(tab, (n+delta+1)*sizeof(int));
 for(int i=n+1; i<=n+delta; i++) tab[i] = 0;
 tab[0] = n+delta;
 *t = tab;
}

Des variantes sont possibles. Chaque détail est important. Il est possible qu’une fonction se comporte apparemment correctement lors d’un test mais comporte néanmoins une erreur pouvant occasionner par exemple une fuite mémoire, ou placer des valeurs inopinées dans certaines cellules du nouveau tableau, mais pas à chaque fois. Un regard d’expert est nécessaire pour valider votre solution si elle est différente de celle-ci.

Contrôle continu 2 – M2 IIA

Documents autorisés : une feuille A4 recto-verso pour chacune de parties A, B, C, D, manuscrite ou imprimée.

Partie A

A1 (1 point)

Donnez les solutions, si applicable, du réseau de contraintes suivant :

Variables : $A$ de domaine $\{1,2,3\}$, $B$ de domaine $\{4,5,6\}$, $D$ de domaine $\{7,8,9\}$, $C$ de domaine $\{10,11,12\}$.

Contraintes :

$q_1$ sur $A,B$ : $\{(1,4),(2,6),(3,5)\}$
$q_2$ sur $B,C$ : $\{(4,11),(5,10)\}$
$q_3$ sur $C,D$ : $\{(10,8),(11,9),(12,9)\}$
$q_4$ sur $A,D$ : $\{(1,9),(2,7),(3,9)\}$

Solution

Une solution : $A=1, B=4, C=11, D=9$.

A2 (1 point)

Donnez la représentation en extension de le contrainte logique $C = A \vee B$ (où, bien évidemment, les variables ont toutes le domaine $\{0,1\}$).

Solution

Sur $A,B,C$ : $\{(0,0,0),(0,1,1),(1,0,1),(1,1,1)\}$.

Partie B

Soit un entier positif $N$. Soit une variable $X$ ayant pour domaine $1..N$. Soit les variables Booléennes $X_1,…,X_N$ . On appelle représentation unaire d’une assignation $X=x$ l’assignation de $X_1,…,X_N$ telle que :

$X_x = 1$,
pour tout $y\in 1..N, y\neq x$, $X_y = 0$.

Par exemple, pour $N=3$, la représentation unaire de l’assignation $X=2$ est $X_1=0, X_2=1, X_3=0$.

Soit la variable $X$ de domaine $\{1,2,3\}$ et les variables $X_1, X_2, X_3$ de domaines $\{0,1\}$. On souhaite spécifier une ensemble $Q$ de contraintes appelées contraintes de liaison (chanelling constraints en anglais) qui assure que toute assignation de $X, X_1, X_2, X_3$ satisfait toutes les contraintes de $Q$ si et seulement si les valeurs de $X_1, X_2, X_3$ constituent la représentation unaire de la valeur de $X$.

B1 (1 point)

Donnez une spécification de $Q$ en extension. Une seule contrainte est suffisante, donc on a $Q=\{q\}$ où $q$ est une contrainte sur $X, X_1, X_2, X_3$.

Solution

$q$ sur $X,X_1,X_2,X_3$ : $\{(1,1,0,0),(2,0,1,0),(3,0,0,1)\}$

B2 (2 points)

Donnez une spécification de $Q$ en compréhension avec des contraintes arithmétiques. Une solution est possibles avec 2 contraintes.

Solution

$X_1 + X_2 + X_3 = 1$

$X1 + 2X_2 + 3X_3 = X$

B3 (1 point)

Donnez une spécification de $Q$ en compréhension dans le cas général d’une contrainte de liaison entre une variable $X$ et les variables Booléennes $X_1,…,X_N$, où $N$ est un entier positif quelconque.

Solution

$\sum_{i=1}^n X_i = 1$

$\sum_{i=1}^n i X_i = X$

Partie C

Pour chacune des questions, vous devez répondre en donnant, dans un ordre plausible, les valeurs retirées lors de la restauration de la cohérence de domaines du réseau de contraintes ou de la contrainte donnée dans l’énoncé. Aucune justification n’est demandée. Vous devez juste donner la liste des valeurs retirées en utilisant la notation $V\neq x$ pour dire que la valeur $x$ est retirée du domaine de $V$.

C1 (1 point)

Restaurez la cohérence de domaine de la contrainte $\text{alldiff}(A, B, C, D, E, F)$ dont les variables ayant respectivement pour domaines $\{1, 2, 4\}$, $\{1, 3, 5\}$, $\{2,3,6\}$, $\{4,5\}$, $\{4,6\}$, $\{5,6\}$.

Solution

$A \neq 4, B \neq 5, C \neq 6$ (dans n’importe quel ordre puisqu’il y a une seule contrainte)

C2 (1,5 point)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : $A, B, C$ ayant toutes pour domaine $\{1,2,3\}$.
Contraintes :
- $q_1$ : $A + 2B + 3C = 12$.
- $q_2$ : $A + 2B + 2C = 10$.

Solution

$q_2 : A\neq 1, A\neq 3$

$q_1 : B \neq 1, B \neq 3, C \neq 1, C \neq 3$

Il reste la valeur 2 dans chaque domaine, ce qui constitue une solution.

C3 (1,5 point)

Restaurez la cohérence de domaine du réseau suivant :

Variables : $A,B,C,D$ ayant toutes pour domaine $\{1,2,3\}$.

Contraintes :

$q_1$ sur $A,B$ : $\{(3,3),(2,1),(1,2)\}$
$q_2$ sur $B,C$ : $\{(3,3),(2,1),(1,1)\}$
$q_3$ sur $C,D$ : $\{(1,2),(2,1),(3,3)\}$
$q_4$ sur $A,D$ : $\{(1,1,(2,2),(3,3)\}$

Solution

$q_2 : C \neq 2$

$q_3 : D \neq 1$

$q_4 : A \neq 1$

$q_1 : B \neq 2$

Il reste respectivement dans les domaines de $A,b,C,D$ : $\{2,3\}, \{1,3\}, \{1,3\}, \{2,3\}$.

Partie D

D1 (2 points)

Soit le réseau de contraintes suivant dont les variables ont pour domaines {0,1} (représentant les valeurs vrai et faux) :

$(\neg a \vee b)$, $(\neg a \vee \neg b \vee c)$, $(\neg a \vee \neg b \vee \neg c)$, $(a \vee b \vee \neg e)$, $(e \vee a \vee d)$, $(e \vee a \vee \neg d)$, $(a \vee \neg b \vee e)$, $(\neg e \vee \neg b \vee d)$, $(\neg e \vee \neg b \vee \neg d)$.

Donnez l’arbre de recherche illustrant le déroulement de l’algorithme MAC sur ce réseau de contraintes. Vous devez utiliser $a$ comme première variable de branchement. Précisez à chaque nœud les domaines des variables en barrant celles qui sont filtrées.

Solution

CC2 – M2BDIA

Documents autorisés : une feuille A4 recto-verso pour chacune de parties A, B, C, D, manuscrite ou imprimée.

Partie A

A1 (1 point)

Donnez les solutions, si applicable, du réseau de contraintes suivant :

Variables : $A, C$ de domaine $\{1,2,3\}$, $B,D$ de domaine $\{4,5,6\}$.

Contraintes :

Sur $A,B$ : $\{(1,5),(2,6),(3,4)\}$.
Sur $B,C$ : $\{(4,2),(5,3),(6,1)\}$.
Sur $C,D$ : $\{(1,5),(2,6),(3,4),(3,6)\}$.
Sur $A,D$ : $\{(1,6),(2,4),(3,5)\}$.

Solution

Une solution : $A=1, B=5, C=3, D=6$.

A2 (1 point)

Donnez la spécification en extension de la contrainte logique $A\vee \neg B \vee C$.

Solution

Sur $A,B,C$ : $\{(0,0,0),(0,0,1),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\}$.

Partie B

Soit $V$ un ensemble de variables, $q$ une contrainte reliant les variables de $V$ et un ensemble $Q$ de contraintes tel que les variables reliées par chaque contrainte de $Q$ appartiennent à $V$.

On dit que $Q$ est équivalent à $q$ si et seulement si toute assignation complète des variables de $V$ satisfait toutes les contraintes de $Q$ si et seulement si elle satisfait $q$.

Par exemple, l’ensemble de contraintes $Q = \{A\neq B, A\neq C, B\neq C\}$ est équivalent à la contrainte $q = \text{allDiff}(A,B,C)$.

On appelle contrainte logique toute contrainte spécifiée en compréhension uniquement à l’aide des opérateurs $\vee, \wedge, \neg$.

Dans les questions suivantes, il sera uniquement question de variables Booléennes, donc à domaine $\{0,1\}$.

B1 (1 point)

Donnez un ensemble de contraintes logiques équivalent à la contrainte $X_1+…+X_N \neq 0$. Cet ensemble peut ne contenir qu’une seule contrainte.

Solution

$X_1\vee…\vee X_N$

B2 (1 point)

Donnez un ensemble de contraintes logiques aussi petit que possible équivalent à la contrainte $A+B+C+D \leq 2$.

Solution

$(\neg A \vee \neg B \vee \neg C)$, $(\neg A \vee \neg B \vee \neg D)$, $(\neg A \vee \neg C \vee \neg D)$, $(\neg B \vee \neg C \vee \neg D)$

B3 (2 points)

Donnez un ensemble de contraintes logiques aussi petit que possible équivalent à la contrainte $X_1+…+X_N \leq 1$, pour tout entier $N$ supérieur à 1.

Solution

$\forall i \in 1..N, \forall j \in i+1..N, (\neg X_i \vee \neg X_j)$

Partie C

Pour chacune des questions, vous devez répondre en donnant, dans un ordre plausible, les valeurs retirées lors de la restauration de la cohérence de domaines du réseau de contraintes ou de la contrainte donnée dans l’énoncé. Aucune justification n’est demandée. Vous devez juste donner, à raison d’une ligne par visite d’une contrainte, la liste des valeurs retirées en utilisant la notation $V\neq x$ pour dire que la valeur $x$ est retirée du domaine de $V$.

Par exemple pour décrire le filtrage du réseau $q_1 : A<B$, $q_2 : B<C$ où $A, B, C$ ont pour domaine $\{1,2,3\}$, vous devez adopter la présentation suivante :

$q_1$ : $A\neq 3, B\neq 1$
$q_2$ : $B\neq 3, C\neq 1, C\neq 2$
$q_1$ : $A\neq 2$

C1 (2points)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : $A$ de domaine $\{1,2,3\}$, $B$ de domaine $\{4,5,6\}$, $C$ de domaine $\{7,8,9\}$.

Contraintes :

$q_1$ sur $A,B$ : $\{(1,5),(2,4),(3,6)\}$
$q_2$ sur $B,C$ : $\{(4,8),(5,7),(6,8)\}$
$q_3$ sur $A,C$ : $\{(1,7),(2,8),(3,9)\}$

Solution

$q_2 : C\neq 9$
$q_3 : A\neq 3$
$q_1 : B \neq 6$

C2 (2 points)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : $A,B,C$ de domaine $\{1,2,3\}$.

Contraintes :

$q_1$ : $A+B+C=6$
$q_2$ : $A+2B+C=9$
$q_3$ : $2A+B+3C=10$

Solution

$q_2 : B\neq 1$
$q_3 : A\neq 3, C\neq 3$
$q_1 : A\neq 1$
$q_2 : B\neq 2, C \neq 2$

Partie D

D1 (2 points)

Soit le réseau de contraintes suivant :

Variables : $A,B,C,D$ ayant toutes pour domaine $\{3,7,11\}$.

Contraintes :

$A+B+C+D \leq 17$
$A+B+C+D \geq 17$

Donnez l’arbre de recherche illustrant le déroulement de l’algorithme MAC sur ce réseau de contraintes. Précisez à chaque nœud les domaines des variables en barrant celles qui sont filtrées.

Solution

Contrôle continu 1 – M2 IIA

Documents autorisés : une feuille A4 recto-verso pour chacune de parties A, B, C, D, manuscrite ou imprimée.

Partie A

A1 (1 point)

Donnez les solutions, si applicable, du réseau de contraintes suivant :

"Solution"

Aucune solution.

A2 (1 point)

Soient les variables A, B, C de domaines respectifs {1,2}, {2,3} et {3,4}. Soient les contraintes suivantes :

q1 sur A, B : {(1,2), (2,3)}.
q2 sur B, C : {(2,4)}.
q : q1 ou q2 (la contrainte satisfaite par et seulement par les assignations de A, B, C qui satisfont q1 ou q2).

Donnez la représentation en extension de q.

"Solution"

Sur $A,B,C$ : $\{(1,2,3),(1,2,4),(2,3,3),(2,3,4),(2,2,4)\}$.

Partie B

B1 (1 point)

On veut placer $k$ personnes sur un coté d’une table rectangulaire disposant de $k$ places. On attribue, par commodité, un numéro compris entre $1$ et $k$ à chaque place et on fait de même pour chaque personne à placer.

Chaque personne $i$ peut exclure certaines autres personnes, c’est à dire refuser que ces autres personnes (si applicable) soient placées à coté de lui. Les personnes exclues par une personne $x$ sont données par un ensemble $E_x$. Voici un exemple avec $k=4$ :

\[E_1=\{2,3\}, E_2=\{1\}, E_3=\{1,4\}, E_4=\{3\}
\]

La personne 1 exclut les personnes 2 et 3,
la personne 2 exclut la personne 1,
la personne 3 exclut les personnes 1 et 4,
la personne 4 exclut la personne 3.

Voici une solution permettant de placer les 4 personnes en respectent leurs incompatibilités.

Proposez une modélisation en extension de l’exemple ci-dessus en utilisant les variables, domaines et contraintes qui vous paraissent les plus pertinentes.

"Solution"

Une variable par place : $P_1, P_2, P_3, P_4$ de domaine $\{1,2,3,4\}$. $P_i=j$ signifie que la personne $j$ occupe la place $i$.

Contraintes de compatibilité :

Sur $P_1, P_2$ : $\{(1,4), (4,1), (2,3), (2,4), (3,2), (4,2)\}$.
Sur $P_2, P_3$ : $\{(1,4), (4,1), (2,3), (2,4), (3,2), (4,2)\}$.
Sur $P_3, P_4$ : $\{(1,4), (4,1), (2,3), (2,4), (3,2), (4,2)\}$.

Contraintes de différence (pour que chaque place soit occupée par une personne différente) :

Sur $P_1, P_3$ : $\{(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)\}$.
Sur $P_1, P_4$ : $\{(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)\}$.
Sur $P_2, P_4$ : $\{(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)\}$.

B2 (3 points)

On revient au cas général où on a $k$ personnes à placer. On souhaite modéliser le problème à l’aide de variables Booléennes $P_{ix}$, pour $i$ et $x$ compris entre 1 et $k$, avec la convention suivante : $P_{ix}=1$ signifie que la place $i$ est occupée par la personne $x$.

Donnez une spécification en compréhension de toutes les contraintes nécessaires, les données du problèmes étant les ensembles $E_1$ à $E_k$. Vous pouvez utiliser des contraintes arithmétiques et / ou logiques.

"Solution"

Chaque place est occupée par une personne, chaque personne occupe exactement une place :

$\forall i \in 1..k, \sum_{x=1}^k P_{i,x} = 1$, $\forall x \in 1..k, \sum_{i=1}^k P_{i,x} = 1$.

Incompatibilités :

$\forall i\in 1..k-1, \forall x\in 1..k, \forall y\in E_x, \neg(P_{i,x}\wedge P_{i+1,y})$

$\forall i\in 1..k-1, \forall x\in 1..k, \forall y\in E_x, \neg(P_{i+1,x}\wedge P_{i,y})$

Partie C

C1 (1 point)

Restaurez la cohérence de domaine de la contrainte $\text{alldiff}(A, B, C, D, E)$ dont les variables ont les domaines suivants :

$A, B$ : $\{1, 2, 3\}$, $C$ : $\{1, 2, 3, 4\}$, $D$ : $\{4,2\}$, $E$ : $\{4,3\}$.

"Solution"

$D\neq 4$, $A\neq 2$, $B\neq 2$, $C\neq 2$, $E\neq 4$, $E\neq 3$, incohérence globale.

C2 (2 points)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : $A$ de domaine $\{1,2\}$, $B$ de domaine $\{4,5\}$, $C$ de domaine $\{4,5\}$, $X$ de domaine $\{1,2,3\}$, $Y$ de domaine $\{1,2,3\}$.
Contraintes :
- Sur $A, B, C$ : $\{(1,4,5), (1,5,4), (2,5,5)\}$.
- Sur $B, X$ : $\{(4,1), (4,2), (5,3)\}$.
- Sur $C, Y$ : $\{(4,3), (5,2)\}$.
- Sur $X,Y$ : $\{(1,2), (2,3), (3,1)\}$.

"Solution"

$Y\neq 1, X\neq 3, B\neq 5, A\neq 2, C\neq 4, Y\neq 3, X\neq 2$

Le filtrage peut être plus facile en s’appuyant sur une représentation graphique telle que celles-ci :

C3 (1 point)

Restaurez la cohérence de domaine de la contrainte $9 X_2 + 3 X_1 + X_0 = Y$ dont les variables ont les domaines suivants :

$X_0, X_1, X_2$ : $\{0,1,2\}$, $Y$ : $\{10,13,16\}$.

"Solution"

$X_2\neq 0, X_2\neq 2, X_0\neq 0, X_0 \neq 2$

Partie D

D1 (2 points)

Soit le réseau de contraintes suivant dont les variables ont pour domaines {0,1} (représentant les valeurs vrai et faux) :

$(a \vee \neg b), (a \vee c), (b \vee \neg c), (\neg a \vee c), (\neg c \vee \neg d), (\neg a \vee \neg b \vee \neg c \vee d \vee e)$.

Donnez l’arbre de recherche illustrant le déroulement de l’algorithme MAC sur ce réseau de contraintes. Choisissez les variables de branchement qui vous paraissent être pertinentes pour minimiser l’arbre de recherche. Précisez à chaque nœud les domaines des variables en barrant celles qui sont filtrées.

"Solution"

Contrôle continu 1 – M2 BDIA

Documents autorisés : une feuille A4 recto-verso pour chacune de parties A, B, C, D, manuscrite ou imprimée.

Partie A

A1 (1 point)

Donnez les solutions, si applicable, du réseau de contraintes suivant :

A2 (1 point)

"Solution"

Une solution : $A=1, B=4, C=8, D=10$.

Soient les variables A, B, C de domaines respectifs {1,2}, {2,3} et {3,4}. Soient les contraintes suivantes :

q1 : A < B.
q2 : B < C.
q : q1 et q2 (la contrainte satisfaite par et seulement par les assignations de A, B, C qui satisfont q1 et q2).

Donnez les représentations en extension de q1, q2 et q.

"Solution"

$q_1$ : sur $A,B$, $\{(1,2),(1,3),(2,3)\}$.
$q_2$ : sur $B,C$, $\{(2,3),(2,4),(3,4)\}$.
$q$ : sur $A,B,C$, $\{(1,2,3),(1,2,4),(1,3,4),(2,3,4)\}$.

Partie B

Soit $N$ un entier au mois égal à 3 et $A_1,…,A_N$, $B_1,…,B_N$ des variables Booléennes, i.e., ayant pour domaine $\{0,1\}$.

Toute assignation complète des variables $A_1,…,A_N$ représentent le positionnement d’une tâche $A$ dont l’heure de début est la plus petite valeur $i$ telle que $A_i=1$ et la durée est le nombre de valeurs de consécutives assignées à 1.

Par exemple, pour $N=5$ les valeurs autorisées des variables $A_1$ à $A_5$ pour représenter de tâche d’une durée de 3 heures sont les suivantes :

11100 // tâche A commence à 0h, durée 3h
01110 // tâche A commence à 1h, durée 3h
00111 // tâche A commence à 2h, durée 3h

Les assignations dans lesquelles un ou plusieurs 0 sont encadrés par des 1, telles que 10110, sont interdites.

La même convention est appliquée aux variables $B_1,…,B_N$ pour la représentation d’une tâche $B$.

Pour exprimer mathématiquement que tous les bits à 1 d’une assignation sont consécutifs, on dit qu’il ne peut y avoir de motif 1…01 ni de motif 10…1 dans la séquence.

Ceci correspond aux deux ensembles de contraintes suivants :

$\forall i\in 2..N-1, \forall j\in 1..i-1, \neg A_j \vee A_i \vee \neg A_{i+1}$
$\forall i\in 1..N-2, \forall j\in i+2..N, \neg A_i \vee A_{i+1} \vee \neg A_{j}$

Par exemple, l’assignation 10110 falsifie la contrainte $\neg A_1 \vee A_3 \vee \neg A_4$ qui est une des contraintes mentionnées plus haut.

Les mêmes contraintes sont appliquées aux variables $B_1,…,B_N$.

B1 (1 point)

Soient $K_A$ et $K_B$ deux entiers. On suppose que $K_A+K_B\leq N$. Donnez une spécification en compréhension (sur les variables $A_1,…,A_N$, $B_1,…,B_N$) des contraintes qui expriment les propriétés suivantes :

La durée de la tâche $A$ est $K_A$,
La durée de la tâche $B$ est $K_B$.

"Solution"

$\sum_{i=1}^N A_i = K_A$.
$\sum_{i=1}^N B_i = K_B$.

B2 (1 point)

Donnez une spécification en extension de la contrainte qui exprime que la tâche $A$ dure 2 heures, pour $N=5$.

"Solution"

Sur $A_1,A_2,A_3, A_4,A_5$ : $\{(1,1,0,0,0),(0,1,1,0,0),(0,0,1,1,0),(0,0,0,1,1)\}$.

B3 (2 points)

Donnez la spécification en compréhension les contraintes supplémentaires (sur les variables $A_1,…,A_N$, $B_1,…,B_N$) qui permettent de dire que la tâche $A$ doit être complètement réalisée lorsque la tâche $B$ commence.

Vous devez utiliser des contraintes logiques (basées sur $\neg, \vee, \wedge$) ou arithmétiques linéaires (basées sur -, +, <, >, =, etc.) ou des compositions logiques de contraintes arithmétiques.

Voici un exemple d’assignations avec $N=10$ et $K=3$ qui satisfont les contraintes supplémentaires que vous devez spécifier.

0011100000 // tâche A
0000001110 // tâche B

Et trois exemples qui doivent falsifier au moins une de ces contraintes.

0011110000 // tâche A
0000111100 // tâche B

0011100000 // tâche A
0111000000 // tâche B

0000011000 // tâche A
0110000000 // tâche B

"Solution"

$\forall i \in 1..N$, $\forall j\in 1..i$, $\neg(A_i \wedge B_j)$.

D’autres solutions existent.

Partie C

C1 (4 points)

Voici le réseau de contrainte qui modélise le problème de l’existence d’une règle de Golomb de longueur 6 à 4 graduations.

Variables :

$G_0$ de domaine $\{0\}$, $G_3$ de domaine $\{6\}$,
$G_1, G_2$ de domaine $\{1,2,3,4,5\}$
$D_0, D_1, D_2, D_3, D_4, D_5$ de domaine $\{1,2,3,4,5,6\}$.

Contraintes :

$G_0 < G_1, G_1 < G_2, G_2 < G_3$,
$D_0=G_1-G_0$, $D_1=G_2-G_0$, $D_2=G_3-G_0$, $D_3=G_2-G_1$, $D_4=G_3-G_1$, $D_5=G_3-G_2$,
AllDiff$(D_0, D_1, D_2, D_3, D_4, D_5)$

Voici une représentation graphique de ce réseau de contraintes :

Restaurez la cohérence de domaine de ce réseau de contrainte. Donnez les valeurs retirées dans un ordre cohérent avec le principe de filtrage. Utilisez la notation $V\neq x$ pour indiquer que la valeur $x$ est retirée du domaine de la variable $V$.

Par exemple, vous pouvez commencer par $D_2 \neq 1$ car la valeur $D_2=1$ n’a pas de support pour la contrainte $D_2=G_3-G_0$. Mais il existe plusieurs séquences correctes.

"Solution"

$G_1\neq 5, G_2\neq 1, D_0\neq 5, D_0\neq 6, D_3\neq 5, D_3\neq 6,$

$D_5\neq 5, D_5\neq 6, D_1\neq 1, D_1\neq 6, D_4\neq 1, D_4\neq 6,$

$D_2\neq 1, D_2\neq 2, D_2\neq 3, D_2\neq 4, D_2\neq 5.$

Partie D

D1 (2 points)

Voici un réseau de 6 contraintes logiques et le début de l’arbre de recherche de l’algorithme MAC sur ce réseau. Vous devez compléter l’arbre en choisissant au mieux (si applicable) les variables de branchement restantes. A chaque nœud ou feuille, redonnez les domaines en barrant les valeurs éliminées par filtrage ou par assignation de la variable de branchement. A chaque feuille de l’arbre de recherche, précisez s’il y a échec ou solution.

"Solution"

POO : Test d’auto-évaluation

En licence pro MI AW

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

comp-20-1

Complétez le constructeur de la classe suivante, qui représente un points dans un repère à deux dimensions.

public class Point
{
    private double x;
    private double y;

    public Point(double x, double y)
    {
        // À compléter
    }
}

"Réponse"

public Point(double x, double y)
{
    this.x = x; this.y = y;
}

comp-20-2

Réécrivez le constructeur à deux paramètres de la classe Point sans utiliser this.

"Solution"

public Point(double abscisse, double ordonnee)
{
    x = abscisse; y = ordonnee;
}

comp-20-3

Soit la méthode main suivante :

public static void main(String[] args)
{
    Point[] tab = new Point[10];
    System.out.println(tab[5]);
}

Y-a-t-il une erreur à la compilation ? À l’exécution ? Que contient la cellule tab[5] ? Qu’est-ce qui s’affiche à l’exécution, si applicable ?

"Solution"

Aucune erreur à la compilation ni à l’exécution. La cellule tab[5] (comme toutes les autres) contient la valeur null qui indique qu’elle n’a encore reçu aucune valeur. Affichage à l’exécution : null.

comp-20-4

Comment faire pour ajouter un point de coordonnées (5.2, 3.7) dans la cellule tab[5] ?

"Solution"

tab[5] = new Point(5.2, 3.7);

comp-20-5

Soit la méthode main suivante :

public static void main(String[] args)
{
    ArrayList<Point> tab = new ArrayList<>();
    System.out.println(tab.get(5));
}

Y-a-t-il une erreur à la compilation ? À l’exécution ? Que contient la cellule d’indice 5 de tab ? Qu’est-ce qui s’affiche à l’exécution, si applicable ?

"Solution"

Pas d’erreur à la compilation, mais erreur à l’exécution car la liste désignées par tab est vide, donc la cellule d’indice 5 n’existe pas.

comp-20-6

Comment faire pour ajouter un point de coordonnées (5.2, 3.7) en position 5 dans la liste désignées par tab ?

"Solution"

On ne peut pas tant qu’il n’y a rien aux positions 0, 1, 2, 3 et 4. Si ces chacune de ces cellules contiennent des références de Point ou la valeur null, alors on peu écrire :

tab.add(5, new Point(5.2, 3.7));

comp-21

Soit la classe suivante représentant un polygone constitué d’une liste de points.

public class Polygone
{
    private ArrayList<Point> liste;
  
    // À compléter
}

Réalisez le constructeur par défaut de cette classe.

"Solution"

public Polygone()
{
    liste = new ArrayList<>();
}

On peut aussi écrire :

this.liste = new ArrayList<>();
this.liste = new ArrayList<Point>();

comp-22-1

Réalisez une méthode retournant le nombre de sommets (points) du polygone courant.

"Solution"

public int nbSommets()
{
    return liste.size();
}

comp-22-2

La méthode suivante devrait permettre d’ajouter un nouveau point au polygone…

public static void addSommet(Point p)
{
    liste.add(p);
}

… mais elle comporte une erreur. Expliquez l’erreur et donnez une version corrigée.

"Solution"

Une méthode de classe ne peut accéder au attributs de l’instance courante car cette méthode peut être appelée sans être associée à une instance et même s’il n’existe aucune instance de la classe concernée.

public void addSommet(Point p)
{
    liste.add(p);
}

comp-23-1

On tente d’utiliser la classe Polygone de la manière suivante…

public static void main(String[] args)
{
    Polygone p;
    p.addSommet(new Point(12.5,5.6));
    // ...
}

…mais il y a une erreur. Indiquez quelle est cette erreur et donner une version corrigée.

"Solution"

La variable p n’est pas initialisée. Pour pouvoir utiliser la méthode d’instance addSommet, il faut une instance de la classe Polygone avec laquelle appeler cette méthode.

public static void main(String[] args)
{
    Polygone p = new Polygone();
    p.addSommet(new Point(12.5,5.6));
    // ...
}

comp-23-2

La méthode main suivante compile-t-elle sans erreur ? Si oui, y a-t-il une erreur à l’exécution ? Si non, que se passe-t-il à l’exécution ?

public static void main(String[] args)
{
    new Polygone().addSommet(new Point(12.5,5.6));
}

"Solution"

Le programme compile et s’exécute sans erreur. Une instance de Polygone est créée en mémoire dans le tas et un point est ajouté au polygone représenté par cette instance. Mais la référence de cette instance de Polygone est perdue, on ne pourra rien en faire et elle sera recyclée. l’exécution du programme ne produit aucune affichage.

comp-24-1

On déclare et initialise la variable de méthode suivante :

ArrayList<int> liste = new ArrayList<>();

Mais le programme ne compile pas. Il y a une erreur. Laquelle ? Pourquoi ? Comment résoudre le problème ?

"Solution"

Le type int est un type primitif, ce qui signifie que les données de ce type ne sont pas des objets mais de simple valeurs en mémoire. La classe ArrayList ne permet pas de créer des liste de valeurs de types primitifs. Mais on peut utiliser à la place des classes enveloppes. La classe enveloppe qui encapsule une donnée de type int est la classe Integer.

ArrayList<Integer> r = new ArrayList<>();

comp-24-2

Réalisez une méthode de classe acceptant un paramètre w désignant une instance de ArrayList représentant une liste d’entier et retournant l’instance de ArrayList obtenue en ajoutant 0 à la fin de la liste désignée par w. Attention, la liste passée en paramètre ne doit pas être modifiée.

"Solution"

Voici une solution possible.

public static ArrayList<Integer> ajoute0(ArrayList<Integer> w)
{
    ArrayList<Integer> r = new ArrayList<>();
    for(int x : w)
    {
        r.add(x);
    }
    r.add(0);
    return r;
}

Il existe d’autres solution mais dans tous les cas il est nécessaire de créer une nouvelle instance de ArrayList<Integer> et de recopier dans la nouvelle liste désignée par w, puis d’y ajouter la valeur 0.

La variante suivant utilise le constructeur en copie de la classe ArrayList :

public static ArrayList<Integer> ajoute0(ArrayList<Integer> w)
{
    ArrayList<Integer> r = new ArrayList<>(w);
    r.add(0);
    return r;
}

comp-24-3

Réalisez une méthode main qui crée une liste vide de type ArrayList<Integer>, ajoute les valeur 4 et 15 dans cette liste, puis appelle la méthode ajoute0 de la question précédente et affiche la liste retournée par cette méthode.

public static void main(String[] args)
{
    ArrayList<Integer> t = new ArrayList<>();
    t.add(4); t.add(15);
    ArrayList<Integer> u = ajoute0(t);
    System.out.println(u);
}

comp-25-1

La classe Integer est non modifiable. Ceci signifie qu’un objet de type Integer ne peut être modifié après sa création. Donnez l’affichage réalisé par l’excécution de la méthode main suivante (qui, pour information, compile sans erreur).

public static void main(String[] args)
{
    Integer x = 34;
    x = x + 1;
    System.out.println(x);
}

"Solution"

La valeur affichée est 35. Si vous vous êtes étonnés, passez à la question suivante. Et si vous n’êtes pas étonnés, passez aussi à l’exercice suivant.

comp-25-2

Soit la méthode main suivante :

public static void main(String[] args)
{
    Integer x = 34;  // Ligne A
    x = x + 1;       // ligne B
    System.out.println(x);
}

Pourquoi, alors que la classe Integer n’est pas modifiable, peut-on ajouter 1 à x ?

"Solution"

En ligne A, on crée une instance de Integer qui contient la valeur 34. La variable x ne contient pas 34. Elle contient la référence de cette instance contenant 34.

En ligne B, on crée une nouvelle instance de Integer contenant 35. La référence de cette nouvelle instance remplace dans x la référence de l’ancienne instance contenant 34. L’ancienne instance n’est plus référencée et la mémoire qu’elle utilise sera recyclée par le ramasse-miette de Java.

comp-25-3

L’affirmation suivante est elle correcte :

Toute classe dotée d’un constructeur en copie est modifiable.

"Solution"

C’est faux. Des classes modifiables et des classes non modifiables peuvent avoir des constructeurs en copie.

comp-25-4

Que faut-il rechercher dans la documentation des méthodes d’une classe pour déterminer si cette classe est modifiable ?

"Solution"

Il faut rechercher des méthodes permettant de modifier l’instance courante, c’est à dire la valeur d’au moins un de ses attributs ou de tout objet désigné par au moins un de ses attributs.

comp-25-5

Quel est le principal avantage et quel est le principal inconvénient de l’utilisation de classes non modifiables ?

"Solution"

Avantage : on supprime les effets de bord, c’est à dire la possibilité que la modification d’un objet désigné par une variable impacte l’objet désigné par une autre variable.
Inconvénient : Obtenir une version modifiée d’un objet ne peut se faire qu’en la reconstruisant complètement, ce qui consomme plus de ressources de mémoire et de ressources CPU qu’une simple modification.

comp-26-1

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne A de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();   // Ligne A
    // ...
}

"Solution"

comp-26-2

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne B de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();
    Point q = new Point(1.0, 2.0);     // Ligne B
    // ...
}

"Solution"

comp-26-3

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne C de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();
    Point q = new Point(1.0, 2.0);     
    Point[] tab = new Point[2];        // Ligne C
    // ...
}

"Solution"

comp-26-4

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne D de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();
    Point q = new Point(1.0, 2.0);     
    Point[] tab = new Point[2];
    tab[0] = q;
    tab[1] = q;                        // Ligne D
    // ...
}

"Solution"

comp-26-5

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne E de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();
    Point q = new Point(1.0, 2.0);     
    Point[] tab = new Point[2];
    tab[0] = q;
    tab[1] = q;
    poly1.addSommet(tab[0]);
    poly1.addSommet(tab[1]);           // Ligne E
    // ...
}

"Solution"

comp-26-6

Dessinez la configuration mémoire immédiatement après l’exécution de la ligne F de le méthode main suivante:

public static void main(String[] args)
{
    Polygone poly1 = new Polygone();
    Point q = new Point(1.0, 2.0);     
    Point[] tab = new Point[2];
    tab[0] = q;
    tab[1] = q;
    poly1.addSommet(tab[0]);
    poly1.addSommet(tab[1]);
    Polygone poly2 = poly1;            // Ligne F
}

"Solution"

comp-27-1

Pour mémoire, voici l’attribut de la classe Polygone.

public class Polygone
{
    private ArrayList<Point> liste = new ArrayList<>();
  
	  //...
}

Voici la définition d’un constructeur en copie de la classe Polygone.

public Polygone(Polygone m)
{
    this();
    for(Point p : m.liste)
    {
        liste.add(p);
    }
}

Ce constructeur es copie est il satisfaisant dans le cas où la classe Point est modifiable ? Et si elle est non modifiable ?

"Solution"

Dans le cas ou Point est non modifiable, il n’y a pas de problème. Mais si elle est modifiable, on risque un effet de bord, i.e. une modification d’un point dans le polygone créé en copie affecterait le polygone original, et réciproquement.

comp-27-2

En supposant que la classe Point dispose d’une méthode de clonage appelée clone, réalisez un constructeur en copie de Polygone respectant les bonnes pratiques de programmation (i.e., effectuant une copie en profondeur).

"Solution"

public Polygone(Polygone m)
{
    this();
    for(Point p : m.liste)
    {
        liste.add(p.clone());
    }
}

Si on utilisait une constructeur en copie de Point, il faudrait remplacer p.clone() par new Point(p).

comp-28-1

Soit la classe Main suivante :

public class Main
{
    public static void printTabInt(int[] t)
    {
        for(int i=0; i< t.length; i++)
        {
            System.out.print(t[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] tab1 = {1, 2, 3, 4, 5};
        int[] tab2 = tab1;           // Ligne A
        printTabInt(tab2);
        printTabInt(tab1);
    }
}

La ligne A provoque-t-elle une erreur à la compilation ? Une erreur à l’exécution ? Si le programme s’exécute, donnez les affichage réalisés.

"Solution"

Il n’y a aucune erreur et l’exécution du programme affiche :

1 2 3 4 5 
1 100 3 4 5

comp-28-2

On conserve la même classe que pour la question précédente, mais on modifie la méthode main qui devient :

{
    int[] tab1 = {1, 2, 3, 4, 5};
    int[] tab2 = tab1;   // Ligne A

    tab2[1] = 100;       // Ligne B

    printTabInt(tab2);
    printTabInt(tab1);
}

Donnez les affichages réalisés.

"Solution"

1 100 3 4 5 
1 100 3 4 5

Les deux variables désignent le même tableau, qui est modifié par la ligne B, qui, en quelque sorte, impacte la donnée désignée par la variable tab1. Il s’agit d’un effet de bord.

comp-28-3

On considère à présent une version modifiée de la classe Main précédente, dans laquelle les tableaux de int ont été remplacé par des tableau de Integer :

public class Main
{
    public static void printTabInt(Integer[] t)
    {
        for(int i=0; i< t.length; i++)
        {
            System.out.print(t[i] + " ");
        }
        System.out.println();
    }


    public static void main(String[] args)
    {
        Integer[] tab1 = {1, 2, 3, 4, 5};
        Integer[] tab2 = tab1;

        tab2[1] = 100;

        printTabInt(tab2);
        printTabInt(tab1);

    }
}

Quels sont les affichages réalisés par l’exécution du programme ?

"Solution"

1 100 3 4 5 
1 100 3 4 5

Exactement les mêmes que précédemment. On a toujours un effet de bord. La classe Integer n’est pas modifiable, mais le problème ici vient du fait qu’un tableau, quel que soit le type de ces cellules, est un objet modifiable.

comp-28-4

Dans la méthode main suivante…

public static void main(String[] args)
{
    int[] tab1 = {1, 2, 3, 4, 5};
    int[] tab2 = tab1;  // Ligne A

    tab2[1] = 100;      

    printTabInt(tab2); // Méthode d'affichage d'un tableau de int
    printTabInt(tab1);
}

La ligne A ne réalise pas une duplication du tableau désigné par tab1, ce qui entraîne ensuite un effet de bord (qui, dans une application réelle, pourrait être voulu ou au contraire inopiné et source d’un bug).

Comment faire pour réaliser une copie en profondeur qui rende le résultat de la copie complètement indépendant de l’original ?

"Solution"

Avec les connaissances transmises dans le cadre de cet enseignement, on peut réaliser une méthode de duplication d’un tableau.

public static int[] duplique(int[] original)
{
    int[] copie = new int[original.length];
    for(int i=0; i<original.length; i++)
    {
        copie[i] = original[i];
    }
    return copie;
}

La ligne A de la méthode main doit alors être remplacée par :

int[] tab2 = duplique(tab1);

Mais il est possible d’utiliser la méthode de classe standard Arrays.copyOf. Vous pouvez vous documenter à ce sujet, qui est hors programme.

comp-28-5

Soit la méthode main suivante :

public static void main(String[] args)
{
    String s1 = "aaaaa";
    String s2 = s1;       // Ligne A
    s2 = s2 + 'X';        // Ligne B

    System.out.println(s1);
    System.out.println(s2);
}

Donnez les affichages réalisés à l’exécution.

"Solution"

aaaaa
aaaaaX

Il n’y a pas d’effet de bord car la ligne B crée une nouvelle instance de String.

POO – CC2 avec corrigés

Partie A

A1 (2 points)

On rappelle que l’exécution des lignes de code suivantes…

String s = "aaa";
s = s + 'b';
System.out.println(s);

… a pour effet l’affichage :

aaab

Donner le code d’une méthode de classe rep qui accepte en paramètre un caractère c et un entier n, et qui retourne la chaîne constituée de n occurrences de c. Par exemple, l’appel…

System.out.println(rep('x', 5));

…devra avoir pour effet l’affichage :

xxxxx

"Solution"

public static String rep(char c, int n)
{
    String r = "";
    for(int i=0; i<n; i++)
    {
        r = r + c;
    }
    return r;
}

A2 (1 point)

Donnez les lignes de code permettant d’obtenir la configuration suivante en mémoire, en utilisant la méthode rep de la question précédente. Vous pouvez répondre même si vous n’avez pas traité la question précédente ou si votre réponse est incorrecte. Le correcteur considérera que la méthode rep fonctionne comme attendu.

"Solution"

String t = rep('a',3);
String u = t;

Partie B

On considère la classe Terrain suivante :

public class Terrain
{
    private String nom;
    private double x1; private double y1;
    private double x2; private double y2;

    public Terrain(String nom, double x1, double y1, double x2, double y2)
    {
        this.nom = nom;
        this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2;
    }
  
    public Terrain clone()
    {
        return new Terrain(nom, x1, y1, x2, y2);
    }

    public double surface()
    {
        return (x2-x1) * (y2-y1);
    }

    public String toString()

    {
        return "Terrain : " + nom + "(" + x1 + "," + y1 + ") (" + x2 + "," + y2 +")";
    }
}

Qui représente un terrain (par exemple agricole) délimité par des coordonnées géographiques exprimées en mètres dans une repère local quelconque.

La classe suivante représente un cadastre regroupant une collection de terrains.

public class Cadastre 
{
    private ArrayList<Terrain> terrains;

    public Cadastre()
    {
        this.terrains = new ArrayList<>();
    }

    public void add(double x1, double y1, double x2, double y2, String nom)
    {
        terrains.add(new Terrain(nom, x1, y1, x2, y2));
    }

    public double surface()
    {
        double r = 0.0;
        for(Terrain t : terrains)
        {
            r = r + t.surface();
        }
        return r;
    }
}

B1 (1 point)

Ajoutez à la classe Terrain une méthode renomme permettant de changer le nom du terrain courant. Le nouveau nom devra être passé en paramètre.

"Solution"

public void renomme(String nouveauNom)
{
    this.nom =nouveauNom;
}

B2 (2 points)

Réalisez un constructeur en copie pour la classe Cadastre. Ce constructeur doit permettre de créer une instances de Cadastre identique à celle désignée en argument, mais ne pouvant donner lieu à aucun effet de bord ultérieur : toute modification du cadastre original ne devra avoir aucun effet sur la copie, et réciproquement.

"Solution"

public Cadastre(Cadastre model)
{
    this();
    for(Terrain t : model.terrains)
    {
        terrains.add(t.clone());
    }
}

B3 (1 point)

Avec les constructeurs et méthodes disponibles dans les classes Terrain et Cadastre, (en supposant que le constructeur en copie soit correctement programmé – vous pouvez donc répondre à cette question même si vous n’avez pas répondu à la précédente, ou si votre réponse est incorrecte) est-il possible d’obtenir la configuration suivante en mémoire ?

Si oui, donnez les lignes de code permettant d’obtenir cette configuration. Si non, expliquez pourquoi.

"Solution"

Non, c’est impossible car le seul moyen d’ajouter un terrain à un cadastre est d’utiliser la méthode add qui crée une copie du terrain à ajouter. On ne peut donc avoir deux instances de Cadastre contenant une référence d’une même instance de Terrain.

Partie C

Soit la classe suivante, qui représente (partiellement, par souci de concision et simplicité) un véhicule à moteur thermique.

public abstract class VehiculeThermique
{
    private double qteCarburant; // Quantité de carburant dans le réservoir
    private int charge;          // Charge actuelle en Kg
    private String nom;          // Nom du véhicule

    public VehiculeThermique(String nom)
    {
        this.nom = nom;
        this.charge = 0;
        this.qteCarburant = 0.0;
    }

    public int getCharge() { return charge;}
    public double getQteCarburant() { return qteCarburant;}
    public void setCharge(int poids) {charge = poids;}
  
    public void remplir(double qte)
    {
        qteCarburant = qteCarburant + qte;
    }

    public abstract double consommation();

    public double autonomie()
    {
        // À compléter
    }

    public String toString()
    {
        return "Véhicule consommant " + consommation() + "l / 100Km";
    }
}

La méthode consommation retourne la consommation du véhicule courant exprimée en litres par 100Kms.

La méthode autonomie retourne le nombre de kilomètres restant à parcourir avec la quantité de carburant actuellement dans le réservoir (valeur de l’attribut qteCarburant). Pour mémoire, avec $q$ litres de carburant et une consommation de $c$ litres au 100 Kms, on peut parcourir $100 \: q/c$ Kms.

Soit la classe suivante, qui représente un modèle particulier de véhicule à moteur thermique appelé Fourgon à essence.

public class FourgonEssence extends VehiculeThermique
{
    private double indiceOctane;

    public FourgonEssence(String nom, double ioct)
    {
        // À compléter
    }

    public String getTypeCarburant() { return "Essence";}

    public String toString()
    {
        // À compléter
    }
}

C1 (2 points)

Donnez le code de la méthode autonomie de la classe VehiculeThermique et le code à ajouter à la classe FourgonEssence pour que la méthode autonomie fonctionne correctement, sachant qu’un fourgon à essence consomme, pour parcourir 100 Kms, 5 litres d’essence plus 0.02 litre par Kg de charge.

"Solution"

public double autonomie()
{
    return 100 * (getQteCarburant() / consommation());
}

public double consommation()
{
    return 5.0 + (0.02*getCharge());
}

C2 (1 point)

Donnez le code du constructeur de la classe FourgonEssence. Le deuxième paramètre est l’indice d’octane du carburant utilisable.

"Solution"

public FourgonEssence(String nom, double ioct)
{
    super(nom);
    this.indiceOctane = ioct;
}

C3 (1 point)

La classe FourgonEssence contient une méthode…

    public String getTypeCarburant() 
    { 
        return "Essence indice octane " + indiceOctane;
    }

…qui retourne le type de carburant utilisé.

Comment faire pour imposer à toute classe concrète dérivée de VehiculeThermique d’avoir une méthode ayant pour signature…

public String getTypeCarburant()

… en utilisant une interface ?

Précisez ce qu’il faut mettre dans l’interface et quel modification il faut apporter à la définition de la classe VehiculeThermique.

"Solution"

public interface Thermique
{
    String getTypeCarburant();
}

C4 (1 point)

Réalisez une méthode toString pour la classe FourgonEssence. Cette méthode doit appeler la méthode toString de la classe VehiculeThermique et utiliser sa valeur de retour. L’exécution des lignes de code suivantes…

VehiculeThermique v1 = new FourgonEssence("Fourgon d'Olivier", 0.98);
v1.setCharge(150);
System.out.println(v1);

…doit avoir pour effet l’affichage :

Fourgon à essence : Véhicule consommant 8.0l / 100Km

"Solution"

public String toString()
{
    return "Fourgon à essence : " + super.toString();
}

Partie D

La classe suivante représente un tableau évolué d’entiers dans lequel certaines cases peuvent être vides (ce qui est interdit dans un tableau d’entiers classique dans lequel toute case à une valeur). Attention, cette classe est un un prototype non finalisé qui n’a pas encore les comportements souhaités.

public class SuperTabInt
{
    private int[] data;
    private boolean[] flag;

    public SuperTabInt(int size)
    {
        this.data = new int[size];
        this.flag = new boolean[size];
    }

    public void write(int i, int val)
    {
        data[i] = val; flag[i] = true;
    }

    public int read(int i)
    {
        return data[i];
    }

    public String toString()
    {
        String r = "[ ";
        for(int i=0; i<data.length; i++)
        {
            if(flag[i]) r += data[i] + " ";
            else r += "# ";
        }
        return r + "]";
    }
}

Le principe de représentation est le suivant :

Soit une instance de SuperTabInt représentant un tableau évolué. Soit i un indice valide dans ce tableau évolué. Si la cellule d’indice i du tableau évolué est vide, alors flag[i] vaut false, sinon flag[i] vaut true. Dans le cas où la cellule d’indice i n’est pas vide, sa valeur est dans data[i].

Mais on ne peut évidemment pas utiliser les crochets pour accéder à une cellule d’un tableau évolué représenté par une instance de SuperTab. cette écriture avec crochets est réservée aux tableaux ordinaires. Pour modifier ou lire une cellule de tableau évolué, on doit utiliser les méthodes read et write .

Voici un exemple qui commence par la création d’un tableau évolué de 10 cellules…

SuperTabInt tab = new SuperTabInt(10);
tab.write(2, 55);
tab.write(3, 56);
System.out.println(tab.read(3));
System.out.println(tab); // Appel de toString

…qui produit les affichages suivants :

56
[ # # 55 56 # # # # # # ]

Mais en l’état, cette classe ne donne pas satisfaction. On souhaite qu’une exception de type BadAccess soit levée lors de certaines situations :

Tentative de lecture ou écriture à un indice négatif.
Tentative de lecture ou écriture à un indice au delà de la dernière cellule accessible.
Tentative de lecture d’une cellule vide. (Une cellule est vide tant qu’aucune valeur n’y a été écrite par la méthode write).

La classe d’exception BadAccess est définie de la manière suivante.

public class BadAccess extends Exception
{
    private int code;  // Code d'erreur
    private int index; // indice auquel l'erreur s'est produite

    public BadAccess(int code, int index)
    {
        this.code = code;
        this.index = index;
    }

    public String toString()
    {
        String msg;
        if(code==1) msg = "Negative index";
        else if(code==2) msg = "Index too large";
        else msg = "Attempt to read an empty cell";
      
        return "SuperTab error : " + msg + " at index " + index;
    }
}

Lors de la création d’une instance d’exception de cette classe, on indique un code (1, 2 ou 3) qui renseigne le type d’erreur et l’indice auquel l’erreur s’est produite.

D1 (2 points)

Réalisez des nouvelles versions des méthodes write et read de la classe SuperTabInt qui lèvent une exception de type BadAccess dans les situation décrites ci-dessus (avec les codes et indices d’erreur appropriés).

"Solution"

public void write(int i, int val) throws BadAccess
{
    if(i<0) throw new BadAccess(1, i);
    else if(i>=data.length) throw new BadAccess(2, i);
    data[i] = val; flag[i] = true;
}

public int read(int i) throws BadAccess
{
    if(i<0) throw new BadAccess(1, i);
    else if(i>=data.length) throw new BadAccess(2, i);
    else if(!flag[i]) throw new BadAccess(3, i);
    return data[i];
}

D2 (2 points)

Donnez le code complet d’une méthode main qui réalise les actions suivantes :

Création d’une instance de SuperTabInt représentant un tableau évolué de 10 entiers.
Écriture des valeurs 55, 56 et 33 aux indices 2, 3 et 5, respectivement.
Affichage de la valeur située à l’indice 4 (comme cette case est vide, une exception sera levée par la méthode read).

Dans le cas où une exception est levée, deux actions doivent être réalisées :

Affichage du tableau évolué à l’aide de la méthode toString de la classe SuperTabInt.
Affichage de la chaîne produite par la méthode toString de la classe BadAccess.

En l’occurrence, avec les actions demandées, l’affichage produit serait :

[ # # 55 56 # 33 # # # # ]
SuperTab error : Attempt to read an empty cell at index 4

Mais ce message pourrait être différent pour des variantes du programme (non demandées) qui tenteraient une lecture ou écriture à un indice incorrect.

"Solution"

public static void main(String[] args)
{
    SuperTabInt tab = new SuperTabInt(10);

    try
    {
        tab.write(2, 55);
        tab.write(3, 56);
        tab.write(5, 33);
        System.out.println(tab.read(4));
    }
    catch(BadAccess e)
    {
        System.out.println("Tableau : " + tab);
        System.out.println(e);
    }
}

Partie E

Soit la méthode de classe suivante…

public static boolean sorted(List<Double> w)
{
    for(int i=0; i<w.size()-1; i++)
    {
        if(w.get(i) > w.get(i+1)) return false;
    }
    return true;
}

… qui permet de vérifier si une liste de valeurs de type Double est triée par ordre croissant (i.e. chaque valeur est au moins égale à la précédente, si applicable).

E1(1 point)

Donnez un exemple de liste de 10 valeurs qui maximise le temps d’exécution de la méthode, et d’une liste de 10 valeurs qui minimise ce temps d’exécution.

"Solution"

Donnée facile :    2.0, 1.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0
Donnée difficile : 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0

E2 (2 points)

Soit la méthode main suivante :

public static void main(String[] args)
{
    List data = new ArrayList<Double>();
		
    // Code produisant dans data une liste de 100000 valeurs
    // qui maximise le temps d'exécution de la méthode sorted
  
    System.out.println("Liste remplie");
    System.out.println(sorted(data));
}

On exécute le programme et on constate l’affichage immédiat suivant :

Liste remplie
true

La deuxième ligne semble s’afficher sans délai après la première. En pratique, il y a un délai qui inclut le temps d’exécution de la méthode sorted, mais qui est trop court pour être perceptible par un observateur humain.

On refait l’expérience en remplaçant la première ligne de code de main par la ligne suivante :

   List data = new LinkedList<Double>();

On observe le même comportement, mais il s’écoule une dizaine de secondes entre l’affichage de Liste remplie et l’affichage de true. Expliquez pourquoi. Précisez les complexités en temps dans le pire des cas de la méthode sorted avec chacune des deux structures de données ArrayList et LinkedList.

"Solution"

Avec ArrayList, l’accès à un élément situé à une position $i$ arbitraire se fait en temps constant. La complexité de la méthode sorted est donc linéaire. Avec LinkedList, l’accès à un une position $i$ arbitraire se fait en temps linéaire. La complexité de la méthode sorted est donc quadratique.

E3 (1 point)

Réalisez une méthode sortedOpt qui fait exactement la même chose que la méthode sorted mais en ayant le même ordre de complexité en temps dans le pire des cas pour une liste de type ArrayList et pour une liste de type LinkedList.

"Solution"

En utilisant un itérateur, on peut parcourir la liste en temps linéaire tout en comparant les éléments successifs.

public static boolean sortedOpt(List<Double> w)
{
    double current = w.get(0);
    for(double x : w)
    {
        if(x < current) return false;
        current = x;
    }
    return true;
}

Projet de recherche locale stochastique

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Coloration de nombres entiers

Ce travail facultatif peut rapporter jusqu’à 3 points.

Énoncé

Le problème abordé est la coloration des entiers de 1 à $N$ en utilisant $K$ couleurs, où $N$ et $K$ sont des entiers donnés, en respectant la propriété suivante : pour tout $a,b,c$ appartenant à l’ensemble $1..N$, si $a+b=c$ alors $a,b$ et $c$ ne doivent pas tous avoir la même couleur.

Une autre manière d’énoncer le problème consiste à dire que l’ensemble $1..N$ doit être partitionné en $ K$ parties telles que pour tout triplet $(a,b,c)\in (1..N)^3$, si $a+b=c$ alors $a,b$ et $c$ ne sont pas dans la même partie. Attention, la règle s’applique aussi si $a=b$, donc par exemple 3 et 6 ne doivent pas appartenir à la même partie, ou en d’autres termes ne pas avoir la même couleur.

Voici un exemple de solution pour $N=13$ et $K=3$ :

$P_1=\{1,4,10,13\}$
$P_2=\{2,3,11,12\}$
$P_3=\{5,6,7,8,9\}$

On vérifie que les sommes inférieures ou égales à 13 de deux valeurs de $P_1$, c’est à dire $2,8,5,11$, ne sont pas dans $P_1$. Le même constat est valable pour $P_2$ et $P_3$.

Ce problème est directement lié à la notion de nombre de Schur. Vous pourrez trouver des précisions ici.

Vous devez programmer une application qui tente de trouver une solution à ce problème à l’aide d’un algorithme de recherche locale stochastique.

La solution trouvée, si applicable, doit être affichée de manière lisible et facilement vérifiable, à savoir pour chaque partie $P_i$, la liste des éléments de cette partie, puis la liste croissante des sommes de ces éléments inférieures ou égale à $N$.

Par exemple, pour $N=13$ et $K=3$, on devrait avoir l’affichage :

P1 : 1 4 10 13 [2 5 8 11]
P2 : 2 3 11 12 [4 5 6 13]
P3 : 5 6 7 8 9 [10 11 12 13]

Monôme ou binôme

Vous pouvez traiter ce sujet seul ou en binôme.

Si vous le traitez seul, vous devrez à minima implémenter l’algorithme de Métropolis et rechercher expérimentalement la température qui maximise l’efficacité de la recherche.

Si vous travaillez en binôme, vous devez implémenter en plus au moins une deuxième stratégie, comme par exemple le recuit simulé avec une variation de température en cours de la recherche.

Critères d’évaluation

Vous serez évalués sur les critères suivants :

Pertinence de la représentation des configurations, du voisinage et de la fonction coût.
Démarche expérimentale de recherche des meilleurs réglages.
Clarté et efficacité du code.
Performance de l’application.

Si vous inspirez de travaux publiés, merci de donner les références. Vous pouvez utiliser le langage de programmation de votre choix, après validation par l’enseignant si vous utilisez un autre langage de Java ou C++.

Livrables

Pour livrer ce projet, vous devez vous inscrire à l’équipe Teams Livraison projets PPC 2122 grâce au code d’accès ipr9fop. Vous aurez alors accès à un devoir permettant de livrer le projet.

Les fichiers à remettre sont les suivants. Merci de ne pas les placer dans des archives zip ou autres.

Le code commenté, dans un unique fichier. Le code devra être indenté en style Allman, c’est à dire avec un alignement strict des accolades ouvrantes et fermantes.
Un document au format pdf d’au plus 10 pages comportant :
- Une présentation et une justification (théorique et/ou expérimentale) de vos choix en matière de représentation, voisinage, fonction de coût (si applicable).
- Une description de la ou des stratégies de recherche implémentées.
- Une présentation des résultats obtenus, avec les temps de calculs correspondants.

Si vous avez travaillé en binôme,

l’un des auteurs doit livrer les deux fichiers du projet, avec le nom du coauteur mentionné dans chaque document,
et l’autre auteur doit seulement livrer un fichier pdf d’une page sur laquelle est juste indiqué le nom du coauteur.