Exercice 2 - Coût des algorithmes, tris et recher… · Bac Numérique et Sciences Informatiques Sujets zéro et spécimens sujet 2024 (sujet 1)

EXERCICE 2 (6 points)

Cet exercice porte sur les listes, les dictionnaires et la programmation de base en Python.

Pour son évaluation de fin d'année, l'institut d'Enseignement Néo-moderne (EN) a décidé d'adopter le principe du QCM. Chaque évaluation prend la forme d'une liste de questions numérotées de 0 à 19. Pour chaque question, 5 réponses sont proposées. Les réponses sont numérotées de 1 à 5. Exactement une réponse est correcte par question et chaque candidat coche exactement une réponse par question. Pour chaque évaluation, on dispose de la correction sous forme d'une liste corr contenant pour chaque question, la bonne réponse; c'est-à-dire telle que corr[i] est la bonne réponse à la question i. Par exemple, on présente ci-dessous la correction de l'épreuve 0:

corr0 = [4, 2, 1, 4, 3, 5, 3, 3, 2, 1, 1, 3, 3, 5, 4, 4, 5, 1, 3, 3] Cette liste indique que pour l'épreuve 0, la bonne réponse à la question 0 est 4, et que la bonne réponse à la question 19 est 3.

Avant de mettre une note, on souhaite corriger les copies question par question; c'est-à-dire associer à chaque copie, une liste de booléens de longueur 20, indiquant pour chaque question, si la réponse donnée est la bonne. Le candidat Tom Matt a rendu la copie suivante pour l'épreuve 0:

copTM = [4, 1, 5, 4, 3, 3, 1, 4, 5, 3, 5, 1, 5, 5, 5, 1, 3, 3, 3, 3] La liste de booléens correspondante est alors:

corrTM = [True, False, False, True, True, False, False, False,

False, False, False, False, False, True, False, False, False, False,

True, True]

Le professeur Paul Tager a élaboré une évaluation particulièrement innovante de son côté. Toutes les questions dépendent des précédentes. Il est donc assuré que dès qu'un candidat s'est trompé à une question, alors toutes les réponses suivantes sont également fausses. M. Tager a malheureusement égaré ses notes, mais il a gardé les listes de booléens associées. Grâce à la forme particulière de son évaluation, on sait que ces listes sont de la forme [True, True,..., True, False, False,..., False].

Pour recalculer ses notes, il a écrit les deux fonctions Python suivantes (dont la seconde est incomplète):

def renote_express(copcorr):

c = 0

while copcorr[c]:

c = c + 1

return c

def renote_express2(copcorr):

gauche = 0

droite = len(copcorr)

while droite - gauche > 1:

milieu = (gauche + droite)//2

if copcorr[milieu]:

...

else:

...

if copcorr[gauche]:

return...

else:

return...

10.

Compléter le code de la fonction Python renote_express2 pour qu'elle calcule la même chose que renote_express.

11.

Déterminer les coûts en temps de renote_express et renote_express2 en fonction de la longueur $n$ de la liste de booléens passée en paramètre.

12.

Expliquer comment adapter renote_express2 pour obtenir une fonction qui corrige très rapidement une copie pour les futures évaluations de M. Tager s'il garde la même spécificité pour ses énoncés. Cette fonction ne devra pas construire la liste de booléens correspondant à la copie corrigée, mais directement calculer la note.