L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Couverture optimale
Ce sujet a pour motivation principale le problème d'allocation de ressources, abordé explicitement dans la Partie III. L'approche choisie consiste ici à considérer ce problème comme une instance de celui de la couverture optimale d'ensemble.
Le problème s'énonce alors comme suit. Soit un ensemble fini. Etant donnée une famille constituée d'ensembles inclus dans telle que couvre (c'est à dire que chaque élément de appartient à au moins un ensemble de ), de combien d'ensembles de a-t-on besoin, au minimum, pour couvrir ? Dans l'exemple ci-dessous, l'ensemble est constitué de 9 points. La famille contient 5 ensembles et recouvre . Aucune sous-famille de constituée d'au plus 2 ensembles n'est couvrante. En revanche, la sous-famille constituée des 3 ensembles en traits épais sur le dessin est couvrante. Une telle famille est dite optimale.
Dans tout le sujet, les tableaux sont indicés à partir de 0 . L'accès à la ( )-ème case d'un tableau de taille , noté , n'est donc valide que pour entier compris entre 0 et au sens large. Quel que soit le langage utilisé, on suppose que les tableaux peuvent être passés comme arguments des fonctions et renvoyés comme résultat. En outre, on suppose qu'il existe une primitive allouer pour créer un tableau de taille dont chaque case contient à l'origine, ainsi qu'une primitive taille( ) qui renvoie la taille d'un tableau .
On suppose qu'il existe une fonction parite renvoyant 0 si l'entier est pair et 1 sinon; ainsi qu'une fonction quotient_div_2 ( ) renvoyant le quotient de la division euclidienne de l'entier par 2 . De plus, les booléens vrai et faux sont utilisés dans certaines questions de ce problème.
Enfin, l'utilisation de fonctions puissance et logarithme prédéfinies dans le langage est interdit.
La complexité, ou le temps d'exécution, d'un programme (fonction ou procédure) est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc...) nécessaires à l'exécution de . Lorsque cette complexité dépend d'un paramètre , on dira que a une complexité en , s'il existe tel que la complexité de est au plus , pour tout . Lorsqu'il est demandé de garantir une certaine complexité, le candidat devra justifier cette dernière si elle ne se déduit pas directement de la lecture du code.
Partie I. Autour des ensembles
Dans cette partie, on représente les ensembles finis d'entiers positifs ou nuls par des tableaux de booléens. L'ensemble correspondant au tableau contient exactement les entiers tels que est égal à vrai ; ne contient pas les entiers tels que est égal à faux, ou tel que n'est pas défini. Ainsi, le tableau [faux, vrai, vrai, faux, vrai] représente l'ensemble . On remarque qu'un même ensemble peut être représenté de multiples façons, en jouant sur la longueur du tableau. Par exemple [faux, vrai, vrai, faux, vrai, faux] et [faux, vrai, vrai, faux, vrai, faux, faux, faux, faux] sont d'autres représentations de l'ensemble .
Question 1 Écrire une fonction cardinal , qui prend en argument un tableau de booléens représentant l'ensemble , et qui renvoie le cardinal de l'ensemble .
Question 2 Écrire une fonction appartient , qui prend en argument un entier et un tableau de booléens représentant l'ensemble , et qui renvoie vrai si appartient à et faux sinon.
Question 3 Écrire une fonction diff , qui prend en argument deux tableaux de booléens et représentant les ensembles et , et qui renvoie un tableau représentant la différence ensembliste . Ici désigne l'ensemble constitué des éléments de qui ne sont pas dans .
Question 4 Écrire une fonction union , qui prend en argument deux tableaux de booléens et représentant les ensembles et , et qui renvoie un tableau représentant l'union de et .
Partie II. Représentation par entiers
Afin de pouvoir manipuler simplement des familles d'ensembles, on souhaite maintenant représenter les ensembles par des entiers. Pour ce faire, on associe à un ensemble (d'entiers positifs ou nuls) l'entier . Par exemple, l'ensemble correspond à l'entier , soit 22 . Contrairement à la représentation par tableau de booléens, cette représentation est unique. On prendra garde à ne pas confondre les entiers représentant des ensembles avec les entiers contenus dans ces ensembles.
Question 5 Si , quel est le plus grand entier représentant un sous-ensemble de ? Quel est le plus petit?
Question 6 Écrire une fonction set2int qui prend en argument un tableau de booléens représentant un ensemble , qui renvoie l'entier représentant , et dont le temps d'exécution est linéaire en la taille de .
On prendra soin de s'assurer et de justifier brièvement que le temps d'exécution de la fonction est linéaire en la taille de . On rappelle que l'utilisation de fonctions puissance et logarithme prédéfinies dans le langage est interdit.
Question 7 Écrire une fonction int2set(s) qui prend en argument un entier représentant un ensemble , et qui renvoie un tableau représentant . En estimer le temps d'exécution. On prendra soin d'expliquer de quelle manière on choisit un vecteur particulier parmi les multiples représentations possibles.
Grâce aux deux fonctions ci-dessus, il est possible d'étendre les fonctions de la partie précédente aux entiers représentant des ensembles. Dans le reste du sujet, on supposera que toutes les fonctions de la partie précédente ont été réécrite afin de pouvoir opérer directement, sur les entiers (arguments et résultat).
Partie III. Familles, sous-familles, et couvertures
On aborde maintenant le problème de couverture optimale, défini en préambule du sujet.
Question 8 Une école souhaite proposer des activités sportives à ses élèves. Il y a plusieurs activités possibles, et chaque élève est invité à dire lesquelles lui conviennent (en en choisissant au moins une). L'école souhaite minimiser le nombre d'activités à organiser, tout en garantissant que chaque élève puisse suivre une activité qui lui convient. Montrer comment ce problème peut être vu comme un problème de couverture optimale.
On peut représenter une famille finie (sous-entendue ordonnée) constituée d'ensembles finis d'entiers (positifs ou nuls) par un tableau , dont chaque case est l'entier qui représente l'ensemble au sens de la partie II. Par exemple, le tableau [17,3,8,22] représente la famille , puisque et .
On fixe désormais et une famille d'ensembles inclus dans telle que couvre l'ensemble . Dans tout le reste du sujet, on suppose que est donnée par un tableau d'entiers. On suppose aussi que le tableau et l'entier sont accessibles dans toutes les fonctions, sans avoir à les définir ni à les passer en argument.
Une sous-famille de est constituée de certains des ensembles de la famille , et est donc de la forme ( ), où est une sous-suite finie strictement croissante des indices de . Par conséquent est définie par l'ensemble des indices . Le cardinal de est donc le cardinal de l'ensemble . Au sens de la partie II, cet ensemble d'indices peut une nouvelle fois être représenté par un entier. Par exemple, si est la famille , la sous-famille , qui est constituée des ensembles et , est de cardinal 2 et est représentée par l'entier 5 , puisque .
Noter que désormais trois objets distincts sont représentés par des entiers.
Les éléments de : dans ce cas la lettre sera de préférence utilisée, et il n'y a pas de codage particulier, représente l'entier ;
Les sous-ensembles de : dans ce cas la lettre sera de préférence utilisée, et représente l'ensemble ;
Les sous-familles de : dans ce cas la lettre sera de préférence utilisée, et représente la sous-famille définie par les ensembles pour . De plus, chaque ensemble est lui-même représenté par l'entier .
Une première façon de trouver une sous-famille couvrante de petit cardinal consiste à utiliser un algorithme dit "glouton". L'idée est de construire une sous-famille étape par étape, en gardant en mémoire l'ensemble des éléments déja couverts, et en ajoutant à chaque fois l'ensemble qui permet de couvrir le plus de nouveaux éléments.
Question 9 Proposer un exemple de famille où l'algorithme glouton ne renvoie pas une sousfamille couvrante optimale.
Question 10 Écrire une fonction reste , qui prend en argument deux entiers et représentant les sous-ensembles et de , et qui renvoie le nombre d'éléments de qui ne sont pas dans .
Question 11 Écrire une fonction glouton(), qui renvoie un entier représentant une sous-famille couvrante de grâce à l'algorithme glouton décrit ci-dessus. Estimer son temps d'exécution.
Question 12 Écrire une fonction couverture , qui prend en argument un entier représentant une sous-famille de et qui renvoie vrai si est couvrante et faux sinon.
Question 13 Écrire une fonction optimale() qui parcourt toutes les sous-familles possibles afin de renvoyer une sous-famille couvrante de optimale. Estimer son temps d'exécution.
X ENS Informatique Commune PSI PT 2012 - Version Web LaTeX | WikiPrépa | WikiPrépa
