Exercice 3 - Gestion de bugs et tests · Bac Numérique et Sciences Informatiques Asie jour 1 - Remplacement 2025

Exercice 3 (8 points)

Cet exercice porte sur l'algorithmique des tableaux, la gestion de bugs, les listes, les piles et la programmation orientée objet.

Le but de cet exercice est d'implémenter un algorithme de pseudo-tri, appelé le tri dictatorial.

L'exercice est constitué de trois parties indépendantes.

Pour chaque question, on peut considérer acquis les résultats et les fonctions demandés dans les questions précédentes, même sans les avoir traitées.

Le pseudo-tri dictatorial d'une série d'entiers suit le principe suivant:

s'il n'y a aucun ou un seul élément, la série est considérée comme triée et n'est donc pas modifiée;

sinon: on conserve le premier élément de la série;

pour chaque élément de la série à partir du deuxième: si l'élément est plus petit que le dernier élément conservé alors on l'élimine;

sinon on le conserve.

Par exemple, si on considère la série 2, 3, 1, 8:

on conserve le 2 qui est le premier élément;

le 3 n'est pas plus petit que le dernier conservé (qui est 2) donc on le conserve;

le 1 est plus petit que le dernier conservé (qui est 3) donc on l'élimine;

le 8 n'est pas plus petit que le dernier conservé (qui est toujours 3) donc on le conserve.

La série triée obtenue après cet algorithme est donc 2, 3, 8.

Partie A

Dans cette partie, on implémente le tri dictatorial en utilisant le type list de Python pour représenter une série d'entiers.

On souhaite coder une fonction tri_dictatorial qui:

prend en paramètre une liste d'entiers serie de type list;

renvoie une nouvelle liste d'entiers obtenue en suivant l'algorithme présenté en introduction, c'est-à-dire une liste triée, éventuellement vide, ne contenant que les éléments de serie à conserver;

ne modifie pas serie.

Par exemple, si s = [5, 2, 6, 8, 3, 7], l'appel tri_dictatorial(s) devrait renvoyer la liste [5, 6, 8] sans modifier s. On remarque que la liste obtenue est en effet triée.

1.

Donner le résultat que doit renvoyer l'appel: tri_dictatorial([31, 45, 41, 28, 37, 108, 127, 2, 124, 421]).

2.

Expliquer pourquoi le tri dictatorial n'est pas un algorithme de tri.

Edgar a écrit le programme suivant, qui prétend implémenter le tri dictatorial:

def tri_dictatorial(serie):

serie_triee = [serie[0]]

for i in range(1, len(serie)):

if serie[i] >= serie[i - 1]:

serie_triee.append(serie[i])

return serie_triee Edgar souhaite tester si sa fonction fait bien ce qu'elle est censée faire.

3.

Edgar réalise l'appel tri_dictatorial([8, 2, 9, 6, 12]).

Expliquer pas à pas comment la liste serie_triee se construit après cet appel.

4.

Edgar réalise maintenant l'appel tri_dictatorial([]) et obtient l'erreur suivante:

Traceback (most recent call last):

File "tri_edgar.py", line 8, in <module>

tri_dictatorial([])

File "tri_edgar.py", line 2, in tri_dictatorial

result = [serie[0]]IndexError: list index out of range Expliquer précisément l'erreur obtenue et proposer une modification du code d'Edgar afin que cet appel soit conforme à l'algorithme du tri dictatorial décrit en introduction.

Dijkstra lors de la réception de son prix Turing en 1972, a notamment déclaré:

« Program testing can be a very effective way to show the presence of bugs, but it is hopelessly inadequate for showing their absence. »

ce que l'on peut traduire par:

« Tester les programmes peut être un moyen très efficace d'y trouver des bugs, mais c'est un moyen désespérément inadéquat pour prouver leur absence. »

5.

Expliquer pourquoi des tests ne peuvent pas prouver de façon certaine l'absence de bugs d'un programme en général.

Edgar décide de procéder à un test supplémentaire et réalise l'appel tri_dictatorial([8, 2, 3, 5, 12]). La fonction renvoie alors [8, 3, 5, 12] qui n'est pas une liste triée.

6.

Expliquer la cause du problème et proposer une modification du code d'Edgar afin de la corriger.