DM 2

PCSI 1
Devoir à la maison no 2
2014/2015
Informatique
A rendre pour jeudi 11 décembre
une liste v de taille n tel que v[i] = True si i est un vaiqueur potentiel
de O et v[i] = False sinon.
On supposera que O est un oracle.
Toutes les questions portent sur le document : Tournois et pronostics.
On considèrera les fonctions, situées en annexe, qui ont été étudiées dans le
devoir à la maison précédent.
2. Invariants de boucles
1. Compréhension et écriture de fonctions
Etant donné un oracle O, le vainqueur d’un tournoi peut varier en fonction
du tournoi T considèré. Nous cherchons à identifier tous les vainqueurs possibles lorsque T varie, mais que O est fixé. On appellera ces vainqueurs les
vainqueurs potentiels de O.
(a) On considère, pour j ∈ N∗ , la propriété suivante :
P(j) :"après j itérations de la boucle, pour tout k ∈ [[n, n + j − 1]] le
nombre k n’apparaît plus dans le tournoi T et il a été remplacé par le
vainqueur du match k. "
Montrer que cette propriété est un invariant de boucle pour la fonction
Vainqueur et prouver le résultat renvoyé par cette fonction.
(a) Donner un oracle qui n’a qu’un seul vainqueur potentiel. Donner un
oracle qui a plusieurs vainqueurs potentiels.
(b)
(c)
(d)
(e)
(b) Déterminer et prouver un invariant de boucle pour la fonction
VainqueurBis puis prouver le résultat renvoyé par cette fonction.
Pour calculer efficacement tous les vainqueurs potentiels de O, nous allons partir d’un premier vainqueur, pour en déduire d’autres, jusqu’à ce
qu’on les ait tous trouvés.
Ecrire une fonction UnVainqueur(O) qui prend en argument un oracle O
et qui renvoie un vainqueur potentiel de O.
On supposera que O est un oracle.
Montrer que si i est un vainqueur potentiel de O, et que O prédit que j
remporte le match entre i et j, alors j est un vainqueur potentiel de O.
Montrer que, si un ensemble X non vide de joueurs est tel que O prédit
que chaque joueur de X gagne tous ses matchs contre les joueurs hors
de X, alors tous les vainqueurs potentiels sont dans X.
En utilisant les questions 1.b, 1.c et 1.d écrire une fonction
VainqueursPotentiels(O) qui prend en argument un oracle O et qui renvoie
3. Complexité
(a) Déterminer la complexté de la fonction EstUnOracle.
(b) Déterminer la complexté de la fonction EstVraiCondition5.
(c) Déterminer la complexté de la fonction EstUnTournoi.
(d) Déterminer et comparer les complextés des fonctions
VainqueurBis (fonction écrite par Ilan).
Vainqueur et
(e) Déterminer la complexité de la fonction UnVainqueur écrite à la question
1.b.
(f) Déterminer la complexité de la fonction VainqueursPotentiels écrite à la
question 1.e.
1
PCSI 1
ANNEXE
Devoir à la maison no 2
Informatique
def EstUnOracle(O) :
for i in range(len(O)) :
if O[i][i]==False :
return False
for j in range(len(O)) :
if i !=j and O[i][j]==O[j][i] :
return False
return True
def EstVraiCondition5(T,k) :
i=0
for j in range(k+1,len(T)) :
if k==T[j][0] or k==T[j][1] :
i+=1
if i==1 :
return True
else :
return False
def EstUnTournoi(T) :
n=(len(T)+1)//2
for k in range(len(T)) :
if T[k][0]>T[k][1] :
return False
for k in range(n) :
if T[k][0] !=k or T[k][1] !=k :
return False
for k in range(n,len(T)) :
if T[k][0]==T[k][1] :
return False
for k in range(n,len(T)) :
if T[k][0]<0 or T[k][0]>=k or T[k][1]<0 or T[k][1]>=k :
return False
for k in range(len(T)-1) :
if EstVraiCondition5(T,k)==False :
return False
return True
def Vainqueur(T,O) :
L=copy.deepcopy(T)
for k in range((len(L)+1)//2,len(L)-1) :
if O[L[k][0]][L[k][1]]==True :
for i in range(k,len(L)) :
if L[i][0]==k :
L[i][0]=L[k][0]
elif L[i][1]==k :
L[i][1]=L[k][0]
else :
for i in range(k,len(T)) :
if L[i][0]==k :
L[i][0]=L[k][1]
elif L[i][1]==k :
L[i][1]=L[k][1]
if O[L[len(L)-1][0]][L[len(L)-1][1]]==True :
return L[len(L)-1][0]
else :
return L[len(L)-1][1]
def VainqueurBis(T,O) :
L=copy.deepcopy(T)
for k in range((len(L)+1)//2,len(L)) :
i=L[k][0]
j=L[k][1]
if i >=n :
i=L[i]
if j >=n :
j=L[j]
if O[i][j]==True :
L[k]=i
else :
L[k]=i
return L[len(L)-1]
2014/2015

Download Report