L'usage de calculatrices électroniques de poche n'est pas autorisé.
Ce sujet, composé de 30 questions, étudie une classe de programmes simples avec variables à valeurs dans . Les questions peuvent être résolues en admettant les résultats des questions précédentes. Les questions des parties II ou III sont indépendantes des questions des autres parties tandis que des questions de la partie IV dépendent de la partie III.
Les algorithmes peuvent être donnés dans la notation de votre choix du moment qu'elle soit suffisamment précise. Pour chaque algorithme proposé, il est indispensable de justifier sa correction et de donner sa complexité en temps dans le pire des cas en choisissant les paramètres pertinents. Comme d'habitude, il est demandé d'apporter le plus grand soin à la rédaction.
L'usage des calculatrices est interdit.
NOTATIONS
Dans la suite, et représentent respectivement l'ensemble des entiers naturels et l'ensemble des entiers relatifs. Pour représente l'ensemble des entiers relatifs tels que . Un élément est dénoté par . Pour , on note l'élément de tel que pour , nous avons . Pour dénote l'ensemble des fonctions . Etant donnés et , on note , la restriction de à ( est défini de façon analogue). Ainsi, pour , nous avons . Pour , l'ordre partiel sur est défini ainsi : pour . On note lorsque et . Le cardinal d'un ensemble est dénoté par . NB : dans la suite dénote l'inclusion ensembliste stricte tandis que dénote l'inclusion non stricte.
Partie I : Systèmes d'addition de vecteurs
Nous allons introduire une famille de programmes simples qui peuvent être vus comme des automates finis auxquels on adjoint la possibilité de mettre à jour des compteurs (variables à valeurs dans ). Les valeurs des compteurs sont représentées par des vecteurs d'entiers naturels. Un système d'addition de vecteurs avec états (SAVE) est un triplet tel que (la dimension).
est un ensemble fini non-vide (les états de contrôle).
est un sous-ensemble fini de (les transitions).
Ainsi, peut être vu comme un automate fini dont l'alphabet est un sous-ensemble fini de , automate cependant privé des états initiaux et finaux. Une transition de est aussi notée , et est appelée la mise à jour de la transition. Une paire dans est appelée une configuration de . Une configuration est dite admissible lorsqu'elle appartient à . Soit la relation représentant un pas de calcul et définie ainsi : il existe une transition dans telle que . On note la restriction de aux seules configurations admissibles. Un pseudo-calcul [resp. calcul] de est une séquence de configurations telle que [resp. ]. Un calcul est donc une exécution du SAVE vu comme un programme avec compteurs, de la configuration initiale à la configuration . On écrit alors lorsqu'il existe un calcul de la forme . Les relations et dépendent donc toujours d'un SAVE et dans la suite il sera toujours clair quel est le SAVE sous-jacent lorsque ces relations sont utilisées.
QUESTION 1. Ecrire en pseudo-code un algorithme qui prenne en entrée un et une séquence non vide de configurations et qui détermine si la séquence est un calcul de .
Les questions 2,3 et 5 vont faire référence au SAVE tel que
La figure ci-dessous représente graphiquement : chaque noeud correspond à un état de contrôle et chaque arc représente une transition, la mise à jour étiquetant l'arc. Dans les réponses, on pourra utiliser les noms de transition se trouvant entre crochets.
Question 2. Calculer l'ensemble .
Question 3. Montrer que
On dit alors que calcule faiblement la multiplication. Les SAVE permettent de calculer faiblement de nombreuses autres fonctions usuelles.
Question 4. Déterminer la fonction telle que
pour le SAVE représenté ci-dessous
Dans la suite, nous cherchons à résoudre les problèmes ci-dessous.
(P1) Etant donnés un SAVE , une configuration admissible et un état de contrôle (acceptant) , existe-t-il tel que ? En d'autres termes, existe-t-il un calcul qui puisse atteindre un état de contrôle à partir d'une configuration admissible initiale ?
(P2) Etant donnés un SAVE et une configuration admissible , l'ensemble des configurations telles que est-il infini?
Question 5. Pour le SAVE , existe-t-il tel que l'ensemble
soit infini? On justifiera sa réponse.
Question 6. Ecrire en pseudo-code un algorithme qui prenne en entrée un tuple et qui retourne l'ensemble des tuples tels que . On évaluera le temps de calcul en fonction de .
Par définition, une transition est une auto-transition lorsque .
Question 7. Montrer que si l'on possède un algorithme pour résoudre les problèmes (P1) et (P2) restreints aux SAVE sans auto-transition, alors il existe un algorithme pour résoudre les problèmes et (sans aucune restriction).
SAV. Pour résoudre les problèmes sur les SAVE, nous introduisons une famille de systèmes un peu plus rudimentaires, qui sont des SAVE sans états de contrôle explicites. Un système d'addition de vecteurs (SAV) est la donnée d'un entier (sa dimension) et d'un ensemble fini (dans la suite on identifiera le SAV avec ). Un élément sera appelé une transition. Un chemin est une séquence finie de transitions. Le chemin est un sous-chemin du chemin il existe tel que , ce qui sera noté .
Promenade. Une configuration du SAV est un élément de . Une configuration est dite admissible lorsque . Si est un chemin, la promenade est la suite de configurations telle que et pour . La promenade est dite induite par le chemin et de longueur est de longueur . La configuration est initiale dans la promenade et est dite finale. De plus, est dite accessible de . La promenade est dite admissible lorsque toutes les configurations intermédiaires sont dans . Dans ce cas, la configuration est dite positivement accessible de . Ce qui nous intéresse vraiment, ce sont les promenades admissibles, ne serait-ce pour résoudre nos problèmes sur les SAVE qui font appel à des configurations admissibles : toutes les composantes sont positives. Cependant, la possibilité d'avoir des valeurs négatives pour certaines configurations d'une promenade d'un SAV, nous sera utile quelquefois.
Dans le reste du sujet, on s'intéresse aux deux problèmes suivants sur les SAV.
(P1') Etant donnés un SAV et deux configurations admissibles , existe-t-il une configuration positivement accessible de telle que ? Le triplet est appelé une instance du problème de couverture et est appelée une solution.
(P2') Etant donnés un SAV et une configuration admissible , existe-t-il un nombre infini de configurations positivement accessibles de ?
Question 8. Montrer que si l'on possède un algorithme pour résoudre les problèmes ( ) et ( ) sur les SAV, alors il existe un algorithme pour résoudre les problèmes (P1) et (P2) sur les SAVE.
Partie II : Atteignabilité d'un État acceptant
L'objectif de cette partie est de proposer un algorithme qui résolve le problème ( ).
Tailles. Le pic minimal d'un élément , noté pic , est . Le maximum d'un élément , dénoté est .
On note le maximum . Le pic minimal d'un SAV , dénoté par pic , est . La taille de , notée taille , est la valeur . On peut remarquer que et que ( ) correspond à un nombre suffisant de bits pour représenter l'entier en binaire (pour les entiers relatifs, un bit est aussi utilisé pour le signe).
Question 9. Définir une instance du problème de couverture ayant au moins une solution et dont chaque solution soit positivement accessible de avec une promenade de longueur au moins égale à .
Dans la suite, on se fixe un SAV et une configuration à couvrir . Pour , une promenade est dite -admissible lorsque pour et , nous avons . Une promenade est dite - -admissible avec si pour et , nous avons . Une promenade est dite -couvrante si pour , nous avons , c'est-à-dire .
QUESTION 10. Soient et une promenade -admissible et -couvrante.
Pour chaque tel que , montrer que la séquence est une promenade -admissible et -couvrante.
Supposons qu'il existe tels que avec . Montrer que la séquence est une promenade -admissible et -couvrante.
QUESTION 11. Soit une promenade - -admissible induite par le chemin avec et . Montrer qu'il existe un chemin de longueur strictement inférieure à tel que soit - -admissible et . Si de plus, est -couvrante, alors est aussi -couvrante.
QUESTION 12. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance et un entier et détermine s'il existe une configuration positivement accessible de avec un chemin de longueur au plus telle que .
Pour et , on note la plus petite longueur d'une promenade admissible et -couvrante dont la configuration initiale est . Si une telle promenade n'existe pas, prend la valeur zéro par défaut.
Dans la suite, on verra que possède un maximum. Soit : ). On remarque que dépend implicitement de et de . De plus, pour , et pour ).
Question 13. Calculer .
QUESTION 14. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance telle que et qui détermine s'il existe une configuration positivement accessible de telle que . De plus, lorsque , majorer .
Dans la suite, on suppose que . On dit que satisfait la propriété dans le cas suivant : pour toute promenade -admissible et -couvrante, il existe un chemin de longueur au plus tel que et soit -admissible et -couvrante.
QUESTION 15. Soient et une promenade -admissible et -couvrante avec tels que
satisfait la propriété ( ), est -admissible avec et ,
pour , nous avons si et seulement si .
Montrer qu'il existe un chemin de longueur au plus tel que et est -admissible et -couvrante.
QUESTION 16. Soit tel que pour chaque , l'ensemble de composantes vérifie la propriété . Montrer que si est une promenade -admissible et -couvrante alors il existe un chemin tel que est -admissible et -couvrante, et de longueur inférieure à .
QUESTION 17. Lorsque le produit pic vaut au moins 1 , majorer en fonction de , et , par exemple par .
QUESTION 18. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance et qui retourne une configuration positivement accessible de telle que si elle existe, sinon false. On justifiera la correction de l'algorithme et on évaluera le temps de calcul.
Partie III : Chemins
Cette partie met en relation les graphes orientés finis et des systèmes d'inéquations, ce qui sera utile dans la partie IV dédiée à la résolution du problème (P2').
Graphe orienté. Un graphe orienté fini est une paire composée d'un ensemble fini de sommets et d'un ensemble d'arcs . Pour tout arc , on note or l'origine de et ex(a) l'extrémité . Un chemin est une séquence d'arcs de telle que pour . L'origine du chemin , notée , est et son extrémité, notée , est . On dit alors que est un chemin de vers . On admet aussi des chemins vides de longueur 0 , un pour chaque sommet de graphe. Deux chemins sont dits consécutifs si . Lorsque et sont consécutifs, on note le chemin obtenu en concaténant avec .
L'image d'un chemin est la fonction qui compte combien de fois chaque arc est utilisé, c'est-à-dire pour , nous avons . Etant donnée une fonction , on note le graphe tel que
.
est l'ensemble de sommets pour lequels il existe un arc tel que ou .
Un graphe est dit connexe lorsque pour de , il existe un chemin de vers dans le graphe .
Question 19. Construire un graphe dont on puisse montrer l'existence des images ci-dessous. On donnera des justifications.
Il existe des images de chemin telles que ne soit pas l'image d'un chemin de . est défini par pour chaque arc .
Il existe des fonctions qui ne soient images d'aucun chemin de et dont est l'image d'un chemin.
Il existe une fonction qui soit image de deux chemins distincts de .
Question 20. Soient et deux chemins ayant un sommet en commun et dont or . Montrer qu'il existe un chemin tel que , or or et .
Question 21. Soient un graphe orienté fini et un chemin de à avec pour image . Montrer les propriétés ci-dessous.
(I) est connexe.
(II) Si alors pour .
(III) Si alors
Question 22. Soient un graphe orienté fini et une fonction. Montrer que est l'image d'un chemin dans si et seulement s'il existe tels que les conditions (I), (II) et (III) de la question 21 soient vérifiées.
Système d'inéquations. Soient et trois entiers naturels, une matrice avec lignes et colonnes et . Posons : , l'ensemble des solutions entières positives. Borosh et Treybis ont montré qu'il existe une constante indépendante de et telle que si est non vide alors est aussi non vide. Dans la suite on admettra cette propriété et on supposera connue la constante . On note une fonction qui retourne false si est vide, sinon un élément de .
QUESTION 23. Soient et . Définir un algorithme pour déterminer s'il existe tel que et en utilisant la fonction .
Question 24. Soit et deux graphes orientés finis tels que , et est connexe ( est un sous-graphe de ). Soient une matrice avec et . A l'aide de la procédure , définir un algorithme qui détermine s'il existe un chemin dans tel que
, avec et pour , étant donnée une bijection arbitraire (contrainte sur l'image de ).
Partie IV : Problème de finitude
Cette partie est dédiée à la conception d'un algorithme pour résoudre le problème ( ).
Etant donné un SAV , une promenade (pas nécessairement admissible) est dite autocouvrante lorsqu'il existe tel que . Etant donnés un SAV et une configuration admissible , Karp et Miller ont montré l'équivalence des propositions ci-dessous :
il existe un nombre infini de configurations positivement accessibles de ,
il existe une promenade admissible auto-couvrante de configuration initiale . Nous admettrons cette équivalence dans la suite.
Pour et , on note la plus petite longueur d'une promenade admissible et auto-couvrante dont la configuration initiale est . Si une telle promenade n'existe pas, prend la valeur zéro par défaut. On verra que possède un maximum. Soit . On remarque que dépend de seulement. De plus, pour et pour , .
Dans la suite, on se fixe un SAV de dimension .
QUESTION 25. Soit une promenade auto-couvrante. Montrer que pour est aussi auto-couvrante.
Question 26. Soient et un SAVE tels que et ,
Pour et tr , nous avons . est connexe.
Montrer que s'il existe un pseudo-calcul dans tel que , et , alors il existe un pseudo-calcul dans tel que
et ,
, taille ) où , taille est une expression à définir, construite à partir de fonction polynômes, exponentielles. et de constantes (indépendantes des arguments).
On pourra par exemple chercher à majorer , taille par .
Question 27. Soient et tels qu'il existe une promenade - -admissible et auto-couvrante. Montrer qu'il existe alors une telle promenade commençant en de longueur au plus , taille .
Question 28. Majorer en fonction de et taille .
QUESTION 29. Pour , majorer en fonction de , , taille et . On pourra par exemple montrer , pic , taille .
Question 30. Définir un algorithme qui prenne en entrée un SAV T et une configuration admissible et qui détermine si l'ensemble des configurations positivement accessibles de est infini.
Fin du sujet
ENS Informatique MP 2010 - Version Web LaTeX | WikiPrépa | WikiPrépa
