N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
Les calculatrices sont interdites
Les deux parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Partie I. Logique et calcul des propositions
Nous nous intéressons dans cet exercice à l'étude de quelques propriétés de la logique propositionnelle tri-valuée. En plus des deux valeurs classiques VRAI ( T ) et FAUX que peut prendre une expression, la logique propositionnelle tri-valuée introduit une troisième valeur INDETERMINE (?). est l'ensemble des variables propositionnelles et l'ensemble des formules construites sur . Pour , les tables de vérité des opérateurs classiques dans cette logique propositionnelle sont les suivantes :
(a)
T
T
T
T
T
T
T
(b)
(c)
(d)
Définitions
Définition 1 Tri-valuation.
Une tri-valuation est une fonction .
On étend alors de manière usuelle la notion de tri-valuation sur l'ensemble des formules :
Définition 2 Une tri-valuation sur l'ensemble des formules est une fonction .
Définition 3 Une tri-valuation satisfait une formule si . On notera alors .
Définition 4 Formule.
Une formule est :
une conséquence d'un ensemble de formules si toute interprétation qui satisfait toutes les formules de satisfait . On notera dans ce cas ;
une tautologie si pour toute tri-valuation . On notera dans ce cas .
Questions
I.1. Montrer que n'est pas une tautologie.
I.2. Proposer alors une tautologie simple dans cette logique.
Posons et .
I.3. Proposer un calcul simple permettant de trouver la table de vérité de en fonction de et . Même question pour .
I.4. En logique bi-valuée classique, les propositions et sont équivalentes. Qu'en est-il dans le cadre de la logique propositionelle tri-valuée?
I.5. En écrivant les tables de vérité, indiquer si les propositions et sont équivalentes.
I.6. Donner la table de vérité de la proposition . Cette proposition est-elle une tautologie?
Un nouvel opérateur d'implication, noté , est alors défini, dont la table de vérité est la suivante :
I.7. est-elle une tautologie ?
I.8. Montrer qu'il n'existe aucune tautologie en utilisant uniquement cette définition de l'implication.
I.9. La proposition suivante est-elle une tautologie :
On définit alors un type FormuleLogique représentant les formules de la manière suivante : type FormuleLogique
|Vrai (* Constante Vrai*)
|Faux (* Constante Faux*)
|Indétermine (* Constante Indeterminé*)
|Var of string (* Variable propositionnelle*)
|Non of FormuleLogique (* Négation d'une formule*)
|Et of FormuleLogique*FormuleLogique (* conjonction de deux formules*)
|Ou of FormuleLogique*FormuleLogique (* disjonction de deux formules*)
|Implique of FormuleLogique*FormuleLogique (* implication*)
I.10. Avec la représentation précédente, écrire en CaML la formule :
I.11. Écrire alors une fonction récursive CaML lectureFormule, prenant en argument une formule et renvoyant une chaîne de caractères spécifiant comment un lecteur lirait la formule. Ainsi, par exemple, pour , lectureFormule renvoie A et non B .
Partie II. Algorithmique et programmation
Le calcul de flots dans des graphes permet de modéliser et de répondre à une très large classe de problèmes, dont l'interprétation correspond à la circulation de flux physiques sur un réseau : distribution électrique, acheminement de paquets de données sur Internet, ...
Il s'agit en général d'acheminer la plus grande quantité possible de "matière" (courant, données, ...) entre une source et une destination . Les liens permettant d'acheminer les flux ont une capacité limitée et il n'y a ni perte ni création de "matière" lors de l'acheminement : pour chaque noeud intermédiaire du réseau, le flux entrant (ce qui arrive) doit être égal au flux sortant (ce qui repart).
Dans la suite de ce problème, nous nous intéressons à une modélisation de ces problèmes de flot par des graphes, dits réseaux de transport. Nous détaillons un algorithme de recherche d'un flot maximal, que nous relions à d'autres notions sur les graphes, telles que les coupes ou les couplages.
Définitions et premières propriétés
Dans toute la suite, nous considérons un graphe pondéré orienté, où est l'ensemble des sommets de et l'ensemble des arcs de . désigne le cardinal de , c'est-à-dire le nombre de sommets.
Définition 5 Réseau de transport. est un réseau de transport si :
il existe dans deux sommets particuliers, la source et le puits ;
il existe une fonction , appelée capacité et évaluant les arcs de .
Dans cette définition, est un élément absorbant pour tous les opérateurs arithmétiques, sauf l'inversion.
Définition 6 Flot.
Un flot de est une fonction , qui associe à chaque arc de une quantité de flot .
On définit pour une fonction bilan , telle que :
Le flot est alors de valeur si :
et
II.1. Donner une interprétation des équations (1) et (2).
Le problème du flot maximum consiste à maximiser en respectant les contraintes imposées par (1) et (2).
Nous supposons dans la suite de ce problème que :
ne contient aucun circuit orienté de vers composé uniquement d'arcs de capacité infinie ;
est un graphe symétrique, ce qui est possible car nous autorisons les arcs à avoir une capacité nulle. Seuls les arcs dont la capacité est strictement positive seront représentés.
La valeur maximum d'un flot peut être reliée avec une autre caractéristique du réseau de transport .
Définition -coupe.
Soit et tels que et . Les arcs dont l'origine est dans et l'extrémité terminale dans forment une s,t-coupe de . On note la capacité de la coupe.
Définition 8 Coupe minimale.
Une coupe minimale est une coupe de capacité minimale parmi toutes les s,t-coupe de .
II.2. Soit un flot de valeur dans et ( ) une s,t-coupe de . Montrer que :
Indication : faire la somme des relations (1) pour tous les sommets de .
Définition 9 Flot maximal.
Soit un réseau de transport et un flot sur . Si la valeur du flot est égale à la capacité d'une coupe minimale de , alors le flot est maximal. A l'inverse, si une coupe de a une capacité égale à la valeur d'un flot maximal, alors cette coupe est minimale.
Cette relation sera utilisée pour stopper dans de bonnes conditions un algorithme itératif de maximisation de flot.
Modélisation
Dans la suite, un graphe sera représenté par sa matrice d'adjacence représentant la capacité de l'arc ( ). Le réseau de transport suivant sera utilisé pour répondre aux questions de ce paragraphe :
II.3. Proposer en CAML des types reseau_transport et flot permettant de modéliser un réseau de transport et un flot. Préciser en particulier comment indiquer que deux sommets ne sont pas reliés dans le graphe et comment modéliser une capacité infinie.
Déclarer alors le réseau de transport .
II.4. Écrire en CAML une fonction flot_admissible:reseau_transport bool, qui teste qu'un flot vérifie les équations (1) et (2) pour le réseau de transport passé en paramètre.
Algorithme de Ford et Fulkerson
Algorithme 1: schéma général de l'algorithme de Ford et Fulkerson
Entrées:
Un réseau de transport $G=\left(V_{G}, E_{G}\right)$
Sorties:
Un flot $x$
pour tout $(u, v) \in E_{G}$ faire
$x(u, v) \leftarrow 0$
tant que il existe un chemin améliorant $P$ de $s_{G}$ à $t_{G}$ faire
Calculer $\alpha$, l'augmentation maximum sur le chemin $P$
$x(u, v) \leftarrow x(u, v)+\alpha$ pour tous les arcs ( $u, v$ ) pris dans le sens direct
$x(u, v) \leftarrow x(u, v)-\alpha$ pour tous les arcs $(u, v)$ pris dans le sens contraire
retourner $x$
Soit un réseau de transport et un flot.
Définition 10 Chemin dans un graphe.
Un chemin d'origine et d'extrémité dans un graphe est défini par une suite finie d'arcs consécutifs, reliant à .
Plusieurs chemins peuvent exister entre deux sommets de .
II.5. Définir une fonction récursive CaML chemin ( ) qui donne la liste des sommets successifs dans le graphe pour passer de à . Dans le cas où plusieurs chemins existent, la fonction doit retourner un de ces chemins. Il pourra être pertinent d'utiliser une structure de pile, à définir, pour mémoriser le chemin.
Définition 11 Chemin améliorant.
Un chemin de à dans est dit améliorant de valeur lorsqu'il construit un flot à partir de tel que :
si l'arc est pris dans le sens direct, son flot peut être augmenté de unités : et il faut ,
si l'arc est pris dans le sens contraire, son flot peut être diminué de unités : et il faut .
II.6. Montrer que est toujours un flot de . Donner la valeur de en fonction de .
II.7. Soit un chemin améliorant. Pour un , donner la capacité maximum d'augmentation , suivant qu'il soit parcouru dans le sens direct ou contraire, pour que reste un flot du réseau de transport . En déduire, pour donné, l'augmentation maximale possible de pour que reste un flot de . L'algorithme de Ford et Fulkerson, décrit dans l'algorithme 1, reprend l'idée de chemin améliorant pour construire un flot maximum dans un réseau de transport.
II.8. Démontrer que l'algorithme de Ford et Fulkerson s'arrête effectivement.
Graphes des résidus et algorithme d'étiquetage
Tel qu'il est décrit en algorithme 1, l'algorithme n'est pas exploitable, en raison de sa complexité élevée.
II.9. Si est le nombre de sommets du réseau de transport et est le nombre d'arcs, évaluer la complexité de l'algorithme de Ford et Fulkerson, dans le cas où les capacités sont entières et bornées .
L'algorithme 1 présente un principe général qui a donné lieu à de nombreuses variantes en vue d'en diminuer la complexité. Les questions suivantes traitent l'une de ces variantes.
Définissons alors un graphe des résidus permettant de construire une variante efficace de l'algorithme de Ford et Fulkerson.
Définition 12 Graphe des résidus.
Soit un réseau de transport, muni d'une fonction capacité . Soit un flot dans . Le graphe des résidus de , noté , possède les mêmes sommets et arcs que . Chaque arc ( ) est valué par un résidu , donné par :
II.10. Définir en CaML un type residu permettant de modéliser un graphe des résidus.
II.11. Écrire une fonction CAML graphe_residu:reseau_transport residu qui, à partir d'un réseau de transport et d'un flot , retourne un graphe des résidus de type residu spécifiant le graphe des résidus entre le réseau de transport et le flot . Cette fonction fera impérativement appel à une fonction récursive.
Utilisons alors pour construire un algorithme dérivant de Ford et Fulkerson, appelé algorithme d'étiquetage (algorithme 2), qui est étudié dans la suite de ce problème. Dans cet algorithme, la constante NULL désigne l'absence de valeur associée à la variable correspondante.
Algorithme 2: algorithme d'étiquetage
Entrées:
Un réseau de transport $G=\left(V_{G}, E_{G}\right)$
Sorties:
Un flot $x$
pour tout $(u, v) \in E_{G}$ faire
$x(u, v) \leftarrow 0$
Marque $[\mathrm{t}] \leftarrow$ vrai
tant que Marque[t] faire
pour tous les $u \in V_{G}$ faire
Marque $[u] \leftarrow$ faux
Pred[u] $\leftarrow$ NULL
Marque[s] $\leftarrow$ vrai
$S \leftarrow\{s\}$
************ Phase 1 ************
tant que $S \neq \varnothing$ et $\operatorname{Non}($ Marque $[t])$ faire
Choisir $u \in S$
$S \leftarrow S \backslash\{u\}$
pour tous les $(u, v) \in G[x]$ faire
si $r(u, v)>0$ et $\operatorname{Non}($ Marque $[v])$ alors
$\operatorname{Pred}[\mathrm{v}] \leftarrow u$
Marque[v] $\leftarrow$ vrai
$S \leftarrow S \cup\{v\}$
************ Phase 2 ************
si Marque[t] alors
$P \leftarrow\{(u, v) / \operatorname{Pred}[v]=u\}$
$\alpha \leftarrow \min \{r(u, v) /(u, v) \in P\}$
MiseAJour $((u, v), P, x, \alpha)$
retourner $x$
II.12. Montrer que l'on a toujours .
II.13. Montrer, à l'aide d'un exemple simple d'un réseau de transport à deux sommets, qu'il est possible d'avoir .
Il n'est donc pas toujours possible d'ajouter le résidu au flot de l'arc correspondant.
II.14. Soit un chemin améliorant de dans , empruntant l'arc , de capacité et de flot , tels que mais . Proposer une stratégie d'amélioration de permettant d'augmenter la valeur du flot de la quantité , tout en conservant les contraintes (2). En déduire une interprétation du résidu. A quelle étape de l'algorithme 2 correspond cette stratégie?
Nous nous intéressons maintenant à la phase 2 de l'algorithme 2 .
II.15. Si la condition Marque[t] est vérifiée, que cela implique-t-il sur la recherche de chemins dans le réseau de transport? Que représentent alors et ?
L'algorithme 2 poursuit son exécution tant qu'un chemin améliorant de à dans existe. À l'arrêt, notons l'ensemble des sommets marqués et .
II.16. Montrer que ( ) est une s,t-coupe de et que pour tout couple . En déduire que :
(i). pour tout arc de vers ;
(ii). pour tout arc de vers .
II.17. Soit un flot de valeur dans . En utilisant la question II.2., montrer alors que :
La valeur d'un flot maximum de à est donc égale à la plus petite capacité d'une s,t-coupe.
Application : problème de couplage
Soit un graphe non-orienté et une partition de .
Définition 13 Couplage.
Un couplage de est un ensemble d'arêtes , tel que les arêtes de soient deux à deux non adjacentes.
En considérant une partition ( ) de , un couplage de peut aussi être vu comme un ensemble d'arêtes , tel que toute arête de relie un sommet dans à un sommet de .
Dans la suite, nous recherchons un couplage de qui contient un maximum d'arêtes (couplage maximum).
II.18. Montrer que ce problème peut se modéliser comme un problème de flot. Définir le réseau de transport correspondant et le flot associé.
II.19. Proposer une implémentation récursive en CAML de la recherche d'un couplage maximum.
Fin de l'énoncé
CCINP Option Informatique MP 2016 - Version Web LaTeX | WikiPrépa | WikiPrépa
