(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.

Cettc épreuve traite des tournois à ćlimination directe tels qu'on en rencontre en sport. La première partie concerne lcurs représentations. La deuxième partic consiste à exhiber les vainqueurs possibles d'un tournoi en fonction si l'on connait à l'avance les résultats de tous les matchs possibles. Enfin la troisième partie calcule les chances de victoire de chaque joueur en fonction de pronostics donnés pour chaque match possible.

La complexité, ou le temps d'exécution, d'un programme (fonction ou procédurc) est le nombre d'opérations élémentaires (addition, multiplication, affectation, test, etc...) lors de 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 .

De manière générale, on s'attachera à garantir une complexité aussi petite que possible dans les fonctions écrites. Le candidat y sera tout particulièrement sensible lorsque la complexité d'une fonction est demandée. Dans ce cas, il devra de plus justifier cette dernic̀re si elle ne se déduit pas directement de la lecture du code.

Dans tout le sujet, on considère que le nombre de joueurs est fixé à , qui est une variable globale à laquelle tous les programmes peuvent accéder, sans avoir à la définir ni à la passer en argument. On suppose aussi que les tableaux sont indexés à partir de 1 . On appelle vecteurs les tableaux à une dimension, et matrices ceux à deux dimensions.

Dans cette partie, on s'intéresse à la représentation et à la manipulation de tournois à ćlimination directe entre joueurs. Les joueurs sont représentés par les entiers de 1 à . Un tournoi entre ces joueurs est donc défini par une suite de matchs. Chaque match oppose deux joueurs, qui sont désignés soit nommément (dans la figure 1, le match "A" oppose le joueur 5 au joueur 2 ; le match "B" oppose le joneur 3 au joueur 1), soit en fonction du résultat d'un match antéricur (dans la figure 1, le match " C " oppose le vainqueur du match " B " au joueur 4 ; le match "D" oppose le vainqueur du match "A" au vainqueur du match "C"; le match "E" oppose le vainqueur du match "D" au joueur 6).

Afin de représenter un tournoi en machinc, on va identifier les matchs avec les entiers plutôt qu'avec des lettres comme dans l'exemple précédent. Ainsi dans l'exemple ci-dessus le match précédemment appelé " A " sera le match 7 ; le match " B " sera la match 8 , le match " C " sera le match 9 , le match " D " sera le match 10 et le match " E " sera le match 11. Pour représenter un match on va utiliser un tablcau de taille deux dont les éléments sont les protagonistes (joueurs ou match) du match : s'il s'agit d'un joueur on donnera son indice et s'il s'agit du vainqueur d'un match précédent on donnera l'indice du match. Pour avoir unicité de la représentation d'un match, on adoptera systematiquement la convention qu'un match est tel que . Ainsi le match 7 (précédemment appelé "A") et le match 10 (précédemment appelé "D") sont représentés par les tablcaux [2,5] et [7,9].

Par la suite, on identifiera pour tout entier , le joueur et le match . Cela permet alors de représenter un tournoi par un tableau de matchs de la façon suivante. Les premiers matchs sont les matchs , les ( ) matchs suivants étant les matchs
réels. Par excmple, le tournoi précédent pourra ctre représenté par le tableau suivant :

Bien sûr toute matrice d'entiors , de taille ne code pas un tournoi. Fn fait, un tournoi est codé par une matrice d'enticrs de taille si et seulement si :
(1) pour tout ;
(2) pour tout ;
(3) pour tout ;
(4) pour tout et ;
(5) pour tout . il existe un unique tel que .

Question 1 Donner une interprétation en français des conditions (3), (4) et (5) exprimées cidessus pour qu'une matrice soit un tournoi. Par exemple la condition (2) s'interprète commo "les n premiers éléments de la représentation d'un tournoi sont les malchs triviaux identifiés aux joueurs". La condition (1) correspond à la convention que le premier protagoniste d'un match est celui de plus petit indice.

Question 2 Ferire une fonction EstVraiCondition5 qui prend en argument une matrice d'entiors de taille et un entier tel que et qui renvoie true s'il existe un unique tel que et false sinon. Quelle est sa complexité ? On supposera, sans avoir à le vérifier, que la matrice est de taille .

Question 3 Écrire une fonction EstUnTournoi (T) qui prend en argument une matrice d'entiers et qui renvoie true si est un tournoi, ot false sinon. Quelle est sa complexité? On supposera, sans avoir à le vérifier, que la matrice est de taille .

On s'intéresse maintenant à la manière dont se déroule le tournoi, à l'aide de matrices, appelées oracles, qui prédiscnt le résultat de chaque match possible. Un oracle est une matrice de bookéens, de taille qui représente les résultats de tous les matchs possibles : contient, true si remporte les matchs joués entre et , et false sinon (il s'ensuit que, pour tous et distincts, contient true si et sculement si contient false). Par convention, on supposera que les cases de la diagonale contiennent true.

Question 4 Écrirc une fonction EstUnOracle qui prend en argument une matrice de booléens et qui renvoie true si est un oracle, el false sinon. Quelle est sa complexité? On supposera que la matrice est de taille .

La donnée d'un tournoi et d'un oracle détermine la manière dont se déroule le tournoi. Dans notre exemple, on obtient le résultat décrit dans la figure 3.

Question 5 Écrire une fonction qui prend en argument un tournoi et un oracle, et qui renvoie le vainqueur du tournoi sclon l'oracle . Quelle est sa complexité? On supposera que est un tournoi et que est un oracle.

Nous avons vu dans la Partic I qu'un tournoi et un oracle définissaient un vainqueur. Étant donné un oracle , le vainqueur d'un tournoi peut varier en fonction du tournoi considéré. Nous cherchons dans cette partie à identifier tous les vainqueurs possibles lorsque varie, mais que est fixé. On appellera ces vainqueurs les vainqueurs potentiels de .

Question 6 Donner un oracle qui n'a qu'un seul vainqueur potentiel. Donner un oracle qui a plusicurs vainqueurs potentiels.

Pour calculer efficacement tous les vainqueurs potentiels de , nous allons partir d'un premier vainqueur, pour en déduire d'autres, jusqu'à ce qu'on les ait tous trouvés.

Question 7 Écrire une fonction UnVainqueur qui prend en argument un oracle et qui renvoic un vainqueur potentiel de . Quelle est sa complexité? On supposera que est un oracle.

Question 8 Montrer que si est un vainqueur potenticl de , et que prédit que remporte le match entre et , alors est un vainqueur potenticl de .

Question 9 Montrer quc, si un ensemble non-vide de joucurs est tel que prédit que chaque joueur de gagne tous ses matchs contre les joueurs hors de , alors tous les vainqueurs potentiels de sont dans .

Question 10 En utilisant les questions 7, 8, et 9, écrire la fonction VainqueursPotentiels ( ) qui prend en argument un oracle et qui renvoie un vecteur de taille tel que true si cst un vainqueur potentiel de , et false sinon. Quelle est sa complexité? On supposera que est un oracle.

Dans cette partie, les oracles sont remplacés par des pronostics, qui donnent des chances (ou probabilités) de victoire plutôt que des certitudes. L'objectif de cette partie est de calculer la probabilité qu'a chaque joucur de remporter le tournoi.

La première difficulté réside dans le fait que l'issue d'un match ne peut, plus être déterminée avec certitude, et que donc plusieurs joucurs peuvent potentiellement participer à un même match. Il faut donc pouvoir calculer, pour chaque match, l'ensemble des joueurs susceptibles d'y participer.

Question 11 Écrire une fonction PremierJoueurPossible ( ) qui prend en argument un tournoi et un entier tel que , et qui renvoie un vecteur de bookéns de taille tel que true si le joucur peut être le premier joueur du match d'indice du tournoi , et false sinon. On supposera que est un tournoi et que est un entier compris entre 1 et .

Nous considérons maintenant, que pour chaque match possible, les chances de victoire de chaque joueur sont données par des pronostics. Un pronoslic est une matrice de réels dans , de taille , ct telle que est la probabilité que remporte un match contre (par exemple s'interprète comme "le joueur i à 3 chances sur 4 de battre le joueur "). Il s'ensuit que , pour tout ct .

Le but de la fin de cette partic est de calculer, à tournoi et pronostic donnés, les chances de remporter le tournoi pour chaque joueur. L'approche proposéc consiste à maintenir un vecteur (de taille ) de probabilités représentant les chances de chaque joueur d'être eneore présent à un moment donné du tournoi : avant le match (le premier vrai match), le vecteur ne contiendra que des 1 ; après le demier, il devra contenir les chances de victoire de chaque joucur. Si est le vecteur de probabilités courantes avant le match , alors le vecteur de probabilités après lc match est défini comme suit :

Question 12 En utilisant les fonctions PremierJoueurPossible et une fonction analogue SecondJoueurPossible (que l'on s'abstiendra d'écrire), écrire une fonction

MiseAJour ( ) qui prend en argument un tournoi , un pronostic , un match , et un vecteur de probabilités et qui met à jour le vecteur de probabilités après le match du tournoi . On supposera que est un tournoi, est un pronostic, est un entier compris entre et , et est un vecteur de réels de longueur .

Question 13 Écrire une fonction ChancesDeVictoire ( ) qui prend en argument un tournoi et un pronostic et qui renvoie un vecteur de réels tel que est la probabilité que remporte le tournoi selon le pronostic . On supposera, sans avoir à le vérifier, que est un tournoi et que est un pronostic.