Corrigé du sujet d’informatique au Capes 2018

samedi 14 avril 2018
par  Alain BUSSER

Le sujet est disponible ici. La première partie est un hommage à Édouard Lucas (auteur d’un algorithme de test de primalité découvert lors d’études sur la suite de Fibonacci) et la seconde partie porte sur des problèmes de coloration de graphes, les sommets des graphes étant des intervalles.

Problème n° 1 : Suite de Lucas

La suite Ln est ainsi définie :

  • L0=2
  • L1=1
  • Ln=Ln-1+Ln-2

I. La traduction en Python de la relation de récurrence donne

  1. a, b = 2, 1
  2. for n in range(2,8):
  3.         a, b = b, a+b
  4.         print(b)

Télécharger

Ce script donne les termes de la suite demandés : 3 4 7 11 18 29

Formule de Binet

II. La démonstration peut se faire par récurrence : Par définition L0 et L1 sont entiers, et la somme de deux entiers est un entier.

III.

  1. Le discriminant de l’équation (-1)²-4×1×(-1)=1+4=5 est strictement positif.
  2. Ensuite φ étant solution de l’équation, on a φ²=φ+1. Idem pour l’autre solution ; la somme des deux solutions est l’opposé du coefficient de x, soit 1, et le produit des deux solutions est le coefficient constant de l’équation, soit -1.

IV. Pour n=1, la propriété a été démontrée à la question précédente. Pour n=0 elle revient à dire que 2=1+1 (en élevant un réel à la puissance 0 on trouve 1). L’initialisation est donc faite pour n=0 et n=1. L’hypothèse de récurrence sera donc que la propriété est vraie aux rangs n-2 et n-1. Alors comme Ln=Ln-1+Ln-2, la propriété est aussi vraie au rang n : Par exemple comme φn-1n-2n-2(φ+1)=φn-2×φ2n et qu’on peut faire pareil avec l’autre solution de l’équation, on regroupe les termes pour finir la démonstration.

Remarque : Il s’agit en fait d’un problème d’algèbre linéaire (ce qui explique la présence de matrices plus bas) : La suite de Lucas, comme celle de Fibonacci, est élément d’un espace vectoriel de dimension 2, formé par toutes les suites décrites par la même relation de récurrence (mais pas nécessairement les mêmes premiers termes). La formule de Binet consiste à écrire ces suites dans une base formée par des suites géométriques.

V. On a vu à la question précédente que Ln est supérieur à φn. Ce qui peut s’écrire log10Ln≥n×log10φ>n×0,2. Alors si n est supérieur à 5p, log10Ln>p×0,2×5=p cqfd puisque la fonction log10 est croissante.

VI. 1.La formule de Binet donne, a priori, ce script :

  1. from math import *
  2.  
  3. def lucas1(n):
  4.     if n == 0:
  5.       return 2
  6.     phi = (1+ sqrt(5))/2
  7.     phi2 = (1 - sqrt(5))/2
  8.     return phi**n + phi2**n

Télécharger

mais les valeurs affichées ne sont pas entières ce qui est en contradiction avec la question II. Pourquoi ? Parce que les flottants de Python occupant une place limitée en mémoire machine, il y a des erreurs d’approximation qui donnent des résultats ne coïncidant pas tout-à-fait avec des entiers. Il est donc nécessaire d’opérer un transtypage. Par exemple avec

  1. from math import *
  2.  
  3. def lucas1(n):
  4.     if n == 0:
  5.       return 2
  6.     phi = (1+ sqrt(5))/2
  7.     phi2 = (1 - sqrt (5))/2
  8.     return int(round(phi**n + phi2**n))

Télécharger

2. L’énoncé propose ce script :

  1. from math import *
  2.  
  3. def lucas2(n):
  4.     if n == 0:
  5.       return 2
  6.     phi = (1+ sqrt(5))/2
  7.     if n%2 == 0:
  8.         return ceil(phi**n)
  9.     else:
  10.         return floor(phi**n)

Télécharger

D’après le IV, Ln est la somme de φn et de la puissance n-ième d’un nombre négatif. Donc

  • si n est pair, Ln est plus grand que n ;
  • si n est impair, Ln est plus petit que n.

Par ailleurs, l’erreur d’approximation consistant à remplacer Ln par φn est une suite géométrique dont la raison a une valeur absolue inférieure à 1 et tend donc vers 0. Comme de plus, le premier terme de cette suite est environ -0,618, les termes suivants sont tous inférieurs à 1 en valeur absolue. En résumé :

  • si n est pair, Lnn<Ln+1 et Ln est l’arrondi entier par défaut de φn ;
  • si n est impair, Ln-1<φn < Ln et Ln est l’arrondi entier par excès de φn.

C’est exactement ce que racontent les lignes 6 à 9 du script.

3. Remarque : L’énoncé prétend que lucas2(36) donne 33385283 mais ce n’est pas vrai avec la version 2 de Python [1]. Or même en maths il y a de multiples excellentes raisons d’utiliser Python 2.7.

Ceci dit, les erreurs d’approximation citées précédemment font que le nombre φ36 qui est très proche de 33385282 est représenté en machine, dans Python 3 tout du moins, comme très légèrement supérieur à ce nombre, et la fonction ceil lui associe 33385283. Une valeur approchée de φ36 est 33385281,99999997 [2] que l’on voit légèrement inférieur à 33385282. En JavaScript, l’arrondi est aussi inférieur à 33385282 [3]. Quant à savoir pourquoi Python 3 arrondit au-dessus là où les autres arrondissent en-dessous, une explication possible est le fait que Python 3 arrondit trop...

Récursivité

VII. 1. Voici le script complété, il ne fait que reprendre celui qui ouvre cet article mais en version programmation fonctionnelle :

  1. from math import *
  2.  
  3. def lucas3(n):
  4.     if n == 0:
  5.         return 2
  6.     if n == 1:
  7.         return 1
  8.     a, b = 2, 1
  9.     for i in range(n):
  10.         a, b = b, a+b
  11.     return b

Télécharger

2. Si, avant l’exécution de la ligne 7, a=Li et b=Li+1 alors après l’exécution de la ligne 7, a=Li+1 et b=Li+Li+1=Li+2, ce qui démontre par récurrence que les égalités en caractères gras ci-dessus constituent un invariant de boucle. Alors à la sortie de la boucle, on a a=Ln-1 et b=Ln. La fonction lucas3 renvoie donc la valeur exacte de Ln cqfd.

3. Comme la ligne 7 ne comporte qu’une seule addition, et que la boucle est parcourue n fois, il y a n additions qui sont effectuées dans la boucle.

VIII. 1. Pour démontrer la formule, on propose de s’inspirer de Donald Knuth en anticipant un peu sur la question suivante : Le script que voici

calcule aussi les nombres de Lucas mais deux par deux :

[2, 1]
[1, 3]
[3, 4]
[4, 7]
[7, 11]
[11, 18]
[18, 29]
[29, 47]
[47, 76]
[76, 123]

La démonstration est faite à la question X. Cela signifie qu’avec la matrice A de la question X, la matrice dont les éléments sont Ln, Ln-1, Ln+1 et Ln est le produit de An-1 par la matrice de départ dont les éléments sont 1, 3, 2 et 1. Or le déterminant de la matrice est Ln²-Ln+1×Ln-1, le déterminant de An-1 est (-1)n-1 et le déterminant de la matrice de départ est -5 ; Le déterminant du produit est alors 5(-1)n cqfd [4].

2. En notant φ’ l’autre solution de x²-x-1=0, on a vu que Lnn+φ’n d’où Ln+1n+1+φ’n+1 ; en multipliant ces deux égalités membre à membre, on a Ln×Ln+1=(φn+φ’n)×(φn+1+φ’n+1)=L2n+1+(-1)n après développement et en utilisant le fait que φ×φ’=-1 ; et en élevant la première des deux égalités au carré, on obtient de manière similaire Ln²=L2n2×(-1)n cqfd

IX. 1. Si k est pair, k modulo 2 est nul et l’expression vaut 1-2×0=1 ; si k est impair, k modulo 2 vaut 1 et l’expression vaut 1-2×1=-1. Dans les deux cas, l’expression coïncide avec (-1)k mais elle est a priori plus rapide à calculer puisqu’elle ne comporte pas d’exponentiation.

2. Le script complété est ici (avec choix de ne pas mettre les parenthèses superflues autour des couples) :

  1. from math import *
  2.  
  3. def lucas4(n):
  4.     if n == 0:
  5.         return 2, 1
  6.     if n == 1:
  7.         return 1, 3
  8.     k = n//2
  9.     u = 1-2*(k%2)
  10.     a, b = lucas4(k)
  11.     if n%2 == 0:
  12.         return a**2-2*u, a*b-u
  13.     else:
  14.         return a*b-u, a**2+a*b-3*u

Télécharger

La dernière expression a été obtenue en additionnant les deux égalités du VIII.2

On remarque que le calcul est fait sur deux valeurs successives de la suite, ce qui préfigure le calcul maticiel du X.

3. Si n est égal à 0 ou 1, il n’y a pas d’appels faits à la fonction lucas4. Sinon, autant d’appels sont faits à la fonction lucas4, qu’il y a de divisions par 2 pour aboutir à 0 ou 1. Le nombre d’appels récursifs est donc la partie entière de log2(n).

Algèbre linéaire

X.En multipliant A par Vn (vecteur noté L dans le script Sofus ci-dessus), on obtient pour l’abscisse Ln et pour l’ordonnée Ln-1+Ln=Ln+1. Donc A×Vn-1=Vn. On en déduit par récurrence que Vn=AnV0.

XI. 1. Une solution possible, sans boucle :

  1. def prodMat(M1,M2):
  2.         P = [[0,0],[0,0]]
  3.         P[0][0] = M1[0][0]*M2[0][0]+M1[0][1]*M2[1][0]
  4.         P[0][1] = M1[0][0]*M2[0][1]+M1[0][1]*M2[1][1]
  5.         P[1][0] = M1[1][0]*M2[0][0]+M1[1][1]*M2[1][0]
  6.         P[1][1] = M1[1][0]*M2[0][1]+M1[1][1]*M2[1][1]
  7.         return P

Télécharger

2. Le calcul d’un coefficient de la matrice produit nécessite deux multiplications et une addition. Comme il y a 4 coefficients, en tout cela fait 4 additions et 8 multiplications [5].

3. L’itérateur range(p) boucle p fois donc il y a p appels à la fonction prodMat.

XII. 1. Si n=0, aucune multiplication matricielle n’est effectuée. Si n=1, deux multiplications sont effectuées (une pour R, l’autre pour P). Si n est supérieur à 1, le nombre de divisions par 2 est log2(n). Et pour chacune de ces divisions par 2, il est effectué une (pour P) ou deux (pour R en plus) multiplications, ce qui fait un total majoré par 2+2log2(n) cqfd.

2. À chaque passage dans la boucle, P est élevée au carré, donc après i passages dans la boucle P=M2i

3. Après le 0-ième passage dans la boucle (c’est-à-dire avant d’entrer dans la boucle), n=Σj=0pcj2j-0. L’invariant de boucle est donc vrai pour i=0. Par récurrence supposons qu’après i-1 passages dans la boucle on a n=Σj=i-1pcj2j-i+1. Le i-ème passage dans la boucle a pour effet de diviser n par 2, et le quotient est Σj=ipcj2j-i cqfd.

4. Avant d’entrer dans la boucle on a R=I=M0. L’invariant de boucle est donc vrai pour i=0. Par récurrence, on suppose qu’après i passages dans la boucle on a R=Mk avec k=Σj=0i-1cj2j. Lors du i+1-ème passage dans la boucle, le chiffre des unités de n est ci, et si ce chiffre est impair on multiplie R par M2i+1 d’après le XII2. Après cette multiplication l’exposant k de M dans R a été augmenté de 2i+1 et k est devenu égal à Σj=0icj2j. Si ci=0 on a aussi k=Σj=0icj2j puisque le dernier terme est nul. Ce qui prouve par récurrence le résultat.

5. Le nombre de passages dans la boucle est la partie entière de log22. La correction de l’algorithme est une conséquence des questions 3 et 4 : À la sortie de la boucle on a toujours k=Σj=0p-1cj2j=n et donc R=Mn.

XIII. Voici une possibilité :

  1. def lucas5(n):
  2.         An = puissanceMatRapide([[0,1],[1,1]],n)
  3.         return An[0][0]*2+An[0][1]

Télécharger

Le script complet

  1. def prodMat(M1,M2):
  2.         P = [[0,0],[0,0]]
  3.         P[0][0] = M1[0][0]*M2[0][0]+M1[0][1]*M2[1][0]
  4.         P[0][1] = M1[0][0]*M2[0][1]+M1[0][1]*M2[1][1]
  5.         P[1][0] = M1[1][0]*M2[0][0]+M1[1][1]*M2[1][0]
  6.         P[1][1] = M1[1][0]*M2[0][1]+M1[1][1]*M2[1][1]
  7.         return P
  8.  
  9. def puissanceMatRapide(M,n):
  10.         R = [[1,0],[0,1]]
  11.         P = M
  12.         while n>0:
  13.                 if n%2==1:
  14.                         R = prodMat(R,P)
  15.                 P = prodMat(P,P)
  16.                 n = n//2
  17.         return R
  18.  
  19. def lucas5(n):
  20.         An = puissanceMatRapide([[0,1],[1,1]],n)
  21.         return An[0][0]*2+An[0][1]

Télécharger


Problème n° 2 : Emplois du temps et graphes d’intervalles

Le sujet est consacré à la notion de graphe d’intervalles.

I

1. Pour l’instance 1, la salle 0 est allouée à la classe C0 de 0 à 7 puis à la classe C2 de 8 à 10. La salle 1 est allouée à la classe C1 de 2 à 13.

Pour l’instance 2, la salle 0 est allouée à la classe C0 de 0 à 2 puis à la classe C2 de 4 à 11 ; la salle 1 est allouée à la classe C1 de 1 à 7 puis à la classe C4 de 8 à 11 et la salle 2 est allouée à la classe C3 de 5 à 6 puis à la classe C5 de 9 à 13.

2. Pour l’instance 1, la classe C1 ayant cours en même temps que chacune des deux autres, on ne peut descendre en-dessous des 2 salles allouées.

Pour l’instance 2, il y a un moment (de 5 à 6) où trois classes doivent être allouées simultanément, et le minimum est donc 3. Il est atteint dans la question précédente.

II

1. L’exemple 1 est représenté par la liste [[0,7],[2,13],[8,10]] et l’exemple 2, par la liste [[0,2],[1,7],[4,11],[5,6],[8,10],[9,13]]

2. Voici un script court, mais il n’est pas certain que ce soit l’attendu :

  1. def insere(l,elt):
  2.         return [x for x in l if x<elt]+[elt]+[x for x in l if x>elt]

Télécharger

Quand à la fonction insereBis dont on suppose que l’on dispose pour la suite, la voici :

  1. def insereBis(LL,li):
  2.         return [x for x in LL if x[0]<li[0]]+[li]+[x for x in LL if x[0]>li[0]]

Télécharger

III

1. En version non triée, on peut faire avec append :

  1. def traduit(liste_intervalles):
  2.         liste_evts = []
  3.         numero = 0
  4.         for cours in liste_intervalles:
  5.                 liste_evts.append([cours[0],numero,0])
  6.                 liste_evts.append([cours[1],numero,1])
  7.                 numero += 1
  8.         return liste_evts

Télécharger

2. L’agenda du problème 1 est [[0, 0, 0],[2, 1, 0],[7, 0, 1], [8, 2, 0],[10, 2, 1],[13, 1, 1]]

celui du problème 2 est [[0, 0, 0],[1, 1, 0],[2, 0, 1],[4, 2, 0],[5, 3, 0],[6, 3, 1],[7, 1, 1],[8, 4, 0],[9, 5, 0],[10, 4, 1],[11, 2, 1],[13, 5, 1]]

3. On utilise le 1 mais avec insereBis vu ci-dessus, à la place de append :

  1. def agenda(liste_intervalles):
  2.         liste_evts = []
  3.         numero = 0
  4.         for cours in liste_intervalles:
  5.                 liste_evts=insereBis(liste_evts,[cours[0],numero,0])
  6.                 liste_evts=insereBis(liste_evts,[cours[1],numero,1])
  7.                 numero += 1
  8.         return liste_evts

Télécharger

IV

1. Parmi les 4 fonctions :

  1. def valideA(agenda):
  2.         c = 0
  3.         for e in agenda:
  4.                 if e[2]==0: c += 1
  5.                 else : c -= 1
  6.                 if c<0: return False
  7.                 else : return True
  8. def valideB(agenda):
  9.         n,c,i,b = len(agenda),0,0,True
  10.         while b and (i<n):
  11.                 if agenda[i][2]==0: c += 1
  12.                 else : c -= 1
  13.                 i += 1
  14.                 b = (c>=0)
  15.         return c==0
  16. def valideC(agenda):
  17.         for i in range(len(agenda)):
  18.                 if agenda[i][2]==0:
  19.                         b = False
  20.                         for j in range(i+1, len(agenda)):
  21.                                 if agenda[j][2]==1: b = True
  22.                         if not b: return b
  23.         return True
  24. def valideD(agenda):
  25.         c = 0
  26.         for e in agenda:
  27.                 c += 1-2*e[2]
  28.                 if c<0: return False
  29.         return c==0

Télécharger

seule la dernière renvoie False s’il y a plus de 1 que de 0 au début de la liste (mais quand même égalité de 1 et de 0). C’est donc la seule réponse correcte.

2. C’est donc cette fonction qu’on se propose d’adapter, avec une variable m qui contient constamment le maximum d’intervalles simultanément couverts jusque là :

  1. def intersectionMax(agenda):
  2.         c,m = 0,0
  3.         for e in agenda:
  4.                 c += 1-2*e[2]
  5.                 m = max(m,c)
  6.                 if c<0: return False
  7.         return m

Télécharger

La variable m est croissante et sa valeur initiale est 0. Elle varie lorsque c dépasse sa valeur actuelle et à la fin de la boucle, elle contient la valeur maximale de c au cours de l’exécution de la boucle. La correction de l’algorithme vient donc de l’invariant de boucle suivant : À tout instant, c est le nombre actuel d’intervalles couverts. C’est un invariant de boucle car c est incrémenté à chaque ouverture d’intervalle, et décrémenté à chaque fermeture d’intervalle.

3. Il suffit de composer les fonctions précédentes :

  1. def nbr_optimal(liste_intervalles):
  2.         return intersectionMax(agenda(liste_intervalles))

Télécharger

V

1. Erreurs détectées :

  • La variable i n’est pas initialisée
  • Le test se fait avec « == » et non « = »
  • Le test doit porter sur l’égalité avec n-1 et non n
  • il manque une négation dans la boucle

Le script corrigé est alors

  1. def plus_petit_vrai(liste):
  2.         n,i = len(liste), 0
  3.         while not liste[i] and (i<n-1): i += 1
  4.         if i==n-1: return -1
  5.         else: return i

Télécharger

2. En fait au lieu de nb_salles = nbr_optimal(liste_intervalles) on aurait pu faire nb_salles = intersectionMax(liste) puisque la variable liste a de toute façon déjà été calculée.

Voici la fonction complétée :

  1. def allocations(liste_intervalles):
  2.         nb_cours = len(liste_intervalles)
  3.         liste = agenda(liste_intervalles)
  4.         nb_salles = nbr_optimal(liste_intervalles)
  5.         salles_dispos = [True]*nb_salles
  6.         alloc = [-1]*nb_cours
  7.         for l in liste:
  8.                 if l[2]==0:
  9.                         alloc[l[1]] = plus_petit_vrai(salles_dispos)
  10.                         salles_dispos[alloc[l[1]]] = False
  11.                 else:
  12.                         salles_dispos[alloc[l[1]]] = True
  13.         return alloc

Télécharger

Le script complet

  1. def insereBis(LL,li):
  2.         return [x for x in LL if x[0]<li[0]]+[li]+[x for x in LL if x[0]>li[0]]
  3. def agenda(liste_intervalles):
  4.         liste_evts = []
  5.         numero = 0
  6.         for cours in liste_intervalles:
  7.                 liste_evts=insereBis(liste_evts,[cours[0],numero,0])
  8.                 liste_evts=insereBis(liste_evts,[cours[1],numero,1])
  9.                 numero += 1
  10.         return liste_evts
  11. def intersectionMax(agenda):
  12.         c,m = 0,0
  13.         for e in agenda:
  14.                 c += 1-2*e[2]
  15.                 m = max(m,c)
  16.                 if c<0: return False
  17.         return m
  18. def nbr_optimal(liste_intervalles):
  19.         return intersectionMax(agenda(liste_intervalles))
  20. def plus_petit_vrai(liste):
  21.         n,i = len(liste), 0
  22.         while not liste[i] and (i<n-1): i += 1
  23.         if i==n-1: return -1
  24.         else: return i
  25.  
  26. def allocations(liste_intervalles):
  27.         nb_cours = len(liste_intervalles)
  28.         liste = agenda(liste_intervalles)
  29.         nb_salles = nbr_optimal(liste_intervalles)
  30.         salles_dispos = [True]*nb_salles
  31.         alloc = [-1]*nb_cours
  32.         for l in liste:
  33.                 if l[2]==0:
  34.                         alloc[l[1]] = plus_petit_vrai(salles_dispos)
  35.                         salles_dispos[alloc[l[1]]] = False
  36.                 else:
  37.                         salles_dispos[alloc[l[1]]] = True
  38.         return alloc
  39.  
  40. print allocations([[0,7],[2,13],[8,10]])
  41. print allocations([[0,2],[1,7],[4,11],[5,6],[8,10],[9,13]])

Télécharger


[1la version de Python utilisée est celle de ce site.

[2résultat trouvé sur alcoffeethmique avec ce script :

  1. phi = Big(5).sqrt().plus(1).div(2)
  2. affiche phi.pow(36)

Télécharger

[3Toujours sur alcoffeethmique, le script suivant donne 33385281,999999966 :

  1. phi = (racine(5)+1)/2
  2. affiche puissance phi,36

Télécharger

[4Édouard Lucas démontrait ce résultat à l’aide du développement en fractions continues du nombre d’or φ ce qui revient plus ou moins au même puisque des matrices interviennent dans les fractions continues.

[5Difficile de faire mieux : l’algorithme de Karatsuba permet de multiplier deux matrices 2×2 avec seulement 7 multiplications, ce qui est peu inférieur à 8.


Commentaires

Logo de Jérémy POSSAMAÏ
samedi 30 juin 2018 à 13h37 - par  Jérémy POSSAMAÏ

Bonjour,

Votre correction de la question V. du problème ne serait-elle pas erronée ? En effet si $n$ est impair, $\hat\phi^n$ est négatif donc $L_n < \phi^n$.