(Durée : 2 heures)
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.

On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.
Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute :

Dans tout le problème, un tableau d'entiers strictement positifs contient les chiffres d'affaires en euros de petites et moyennes entreprises ( ). La variable sera supposée être une constante globale.

Ces entreprises décident de s'allier pour devenir leader de leur secteur dominé par l'entreprise qui a un chiffre d'affaires de euros. Il s'agit donc de trouver un sous-ensemble d'entreprises tel qu'on ait . Un tel ensemble d'entreprises est appelé une alliance réussie. Malheureusement, les alliances apportent parfois des désagréments. Pour minimiser ce risque, on cherche à réaliser une alliance réussie stable (une alliance stable en abrégé) vérifiant pour tout strictement inclus dans .

On supposera dans tout l'énoncé qu'une telle alliance existe c'est-à-dire que et on dira que le chiffre d'affaires Obj est l'objectif des alliances considérées.

Une alliance est représentée par un tableau de booléens tel que vaut vrai si l'entreprise est dans l'alliance et faux sinon . On pourra poser vrai et faux .

Question 1 Écrire une fonction somme(c,a) qui retourne, en temps linéaire par rapport à , la somme des chiffres d'affaires des entreprises de l'alliance représentée par le tableau .

Question 2 Écrire une fonction estReussie( ) qui retourne, en temps linéaire par rapport à , la valeur vrai si l'alliance représentée par le tableau est une alliance réussie pour l'objectif Obj. La valeur retournée est faux sinon.

Question 3 Écrire une fonction estStable(c,a, Obj) qui retourne, en temps linéaire par rapport à , la valeur vrai si l'alliance représentée par le tableau est une alliance stable pour l'objectif Obj. La valeur retournée est faux sinon.

Question 4 On suppose les entreprises triées selon leur chiffre d'affaires . Écrire une fonction allianceMin( ) qui imprime, en temps linéaire par rapport à , les numéros des entreprises d'une plus petite (en nombre d'entreprises) alliance stable pour l'objectif Obj.

Dans cette partie, on imprime toutes les alliances stables en énumérant toutes les alliances et en testant à chaque fois s'il s'agit d'une alliance stable pour l'objectif Obj. Au tableau a, on fait correspondre de manière unique le nombre bin(a) défini par :

de représentation binaire ( ). Ainsi, pour et l'alliance des entreprises , le nombre associé est 26 de représentation binaire ( ). Il suffit donc d'énumérer les nombres binaires qu'on peut écrire avec bits pour énumérer toutes les alliances possibles.

Question 5 Écrire une fonction suivanteDe(a) qui modifie, en temps linéaire par rapport à , le tableau a pour donner l'alliance suivante telle que . Cette fonction retourne la valeur vrai si cette opération est possible, et faux sinon (dans ce cas, il n'y a pas d'alliance suivante).

Question 6 Écrire une fonction imprimer(a) qui imprime l'alliance correspondant au tableau . Ainsi pour , et , l'impression donnera .

Question 7 Écrire une fonction imprimerStables(c, Obj) qui affiche toutes les alliances stables pour l'objectif Obj. Donner un ordre de grandeur du nombre d'opérations effectuées par rapport à .

On définit l'ordre binaire par si et seulement si . Dans la partie II, on a imprimé les alliances stables dans l'ordre binaire croissant. Dans cette partie, on optimise l'impression de ces alliances en supposant que les entreprises sont classées par chiffres d'affaires croissants. On suppose donc .

Pour réaliser cette impression rapide, on construit le tableau vérifiant pour .

Question 8 Écrire une fonction cumuls( ) qui calcule, en temps linéaire par rapport à , le tableau .

Pour trouver , première alliance stable dans l'ordre binaire, on cherche l'indice minimum tel que . L'entreprise est dans l'alliance , et on doit compléter cette alliance avec des entreprises de chiffres d'affaires plus petits pour dépasser la somme restante . Pour compléter cette alliance partielle , on cherche le plus petit tel que . On sait qu'il existe puisqu'on a . Donc est aussi dans l'alliance et on recommence à nouveau pour dépasser la somme restante en complétant l'alliance partielle jusqu'au moment où la somme restante devient négative ou nulle.

Question 9 Écrire une fonction completer qui, pour la somme restante , retourne minimum appartenant à première alliance stable suivante de dans l'ordre binaire ( est l'entreprise minimale appartenant à ). Cette fonction modifie ses paramètres et en ajoutant quelques comme indiqué dans le procédé de complétion précédemment décrit. (On se place dans le cas où et

Soit le plus petit indice d'une entreprise appartenant à l'alliance . Soit alors le plus grand entier tel que les entreprises sont toutes dans . Pour créer l'alliance stable suivante, on définit l'alliance qui part de à laquelle on a enlevé les entreprises . Soient et l'objectif Obj diminué des chiffres d'affaires des entreprises de . Si , alors il n'y a pas de stable suivante, sinon on a nécessairement par construction . On ajoute alors l'entreprise à l'alliance et on complète celle-ci comme pour la question précédente. On obtient alors la prochaine alliance stable.

Question 10 Écrire une fonction prelude qui retourne l'entier défini ci-dessus, s'il existe. Sinon, on retourne . Cette fonction modifie ses paramètres et Obj en retirant de tous les indices entre les entiers et . Ainsi, a sera devenue l'alliance et sera égal au nouvel objectif .

Question 11 En déduire une fonction imprimerAStables1(c, Obj) qui imprime rapidement toutes les alliances stable pour l'objectif Obj. Donner un ordre de grandeur du temps d'exécution en fonction de et du nombre d'alliances imprimées.