Interrogation — Ch25 : Algorithmique appliquée

BTS | Mathématiques | Durée : 40 min | /20

Dernière mise à jour : 21 juin 2026

Nom : _____ Prénom : _____ Date : _____

Exercice 1 — Recherche dichotomique (4 pts)

On dispose du tableau trié de 7 cotes (en mm), indexé à partir de 0 :

Indice	0	1	2	3	4	5	6
Valeur	2	5	7	9	12	15	21

On recherche la valeur cible \(15\) par dichotomie. Donner la suite des indices « milieu » testés et l'indice final retourné. (3 pts)
Quel est l'avantage de la recherche dichotomique par rapport à la recherche séquentielle ? (1 pt)

Exercice 2 — Tri à bulles (4 pts)

On veut trier par ordre croissant le tableau \([4, 1, 5, 2, 3]\) avec le tri à bulles (comparaisons d'éléments adjacents, échange si l'élément de gauche est plus grand).

Détailler les comparaisons et échanges de la première passe. (3 pts)
Quel élément est définitivement à sa place à la fin de cette passe ? (1 pt)

Exercice 3 — Complexité (Big-O) (4 pts)

Donner la complexité dans le pire cas, en notation Big-O, de : la recherche séquentielle, la recherche dichotomique, le tri à bulles, le tri rapide (en moyenne). (2 pts)
Ranger ces complexités de la plus rapide à la plus lente : \(O(n^2)\), \(O(1)\), \(O(n\log n)\), \(O(\log n)\), \(O(n)\). (2 pts)

Exercice 4 — Structures de données (3 pts)

On dispose d'une structure initialement vide. On effectue dans l'ordre les opérations : insérer 10, insérer 20, insérer 30, puis extraire un élément.

Si la structure est une pile (LIFO), quel élément est extrait ? (1,5 pt)
Si la structure est une file (FIFO), quel élément est extrait ? (1,5 pt)

Exercice 5 — Récursivité (5 pts)

On considère la fonction Python : def f(n): return 1 if n == 0 else n * f(n - 1)

Quel est le cas de base ? Que calcule cette fonction ? (2 pts)
Dérouler les appels successifs pour \(f(4)\) et donner le résultat. (2 pts)
Pour le problème des tours de Hanoï à \(n\) disques, le nombre de déplacements est \(2^n - 1\). Combien de déplacements pour \(n = 4\) disques ? (1 pt)

Correction

Exercice 1 (4 pts)

a) Initialement \(g = 0\), \(d = 6\). (3 pts)

milieu \(= (0+6)//2 = 3\), valeur \(t[3] = 9\). Comme \(9 < 15\), on cherche à droite : \(g = 4\).
milieu \(= (4+6)//2 = 5\), valeur \(t[5] = 15 =\) cible. Trouvée à l'indice 5.

Indices milieu testés : 3 puis 5 ; indice retourné : 5.

b) La dichotomie divise la zone de recherche par 2 à chaque étape : sa complexité est \(O(\log n)\) au lieu de \(O(n)\), donc beaucoup plus rapide sur de grands tableaux triés. (1 pt)

Exercice 2 (4 pts)

a) Première passe sur \([4, 1, 5, 2, 3]\) : (3 pts)

Comparer 4 et 1 : \(4 > 1\) → échange → \([1, 4, 5, 2, 3]\).
Comparer 4 et 5 : \(4 > 5\) ? Non → pas d'échange → \([1, 4, 5, 2, 3]\).
Comparer 5 et 2 : \(5 > 2\) → échange → \([1, 4, 2, 5, 3]\).
Comparer 5 et 3 : \(5 > 3\) → échange → \([1, 4, 2, 3, 5]\).

b) À la fin de la première passe, le plus grand élément 5 a « remonté » jusqu'à la dernière position : il est définitivement à sa place. (1 pt)

Exercice 3 (4 pts)

a) Recherche séquentielle : \(O(n)\) ; recherche dichotomique : \(O(\log n)\) ; tri à bulles : \(O(n^2)\) ; tri rapide (moyenne) : \(O(n \log n)\). (2 pts)

b) De la plus rapide à la plus lente : \[O(1) \;\ll\; O(\log n) \;\ll\; O(n) \;\ll\; O(n\log n) \;\ll\; O(n^2).\] (2 pts)

Exercice 4 (3 pts)

a) Pile (LIFO, dernier entré – premier sorti) : on extrait le dernier inséré, soit 30. (1,5 pt)

b) File (FIFO, premier entré – premier sorti) : on extrait le premier inséré, soit 10. (1,5 pt)

Exercice 5 (5 pts)

a) Le cas de base est \(n = 0\), qui renvoie \(1\). La fonction calcule la factorielle \(n! = 1 \times 2 \times \cdots \times n\). (2 pts)

b) Déroulement pour \(f(4)\) : (2 pts)

\(f(4) = 4 \times f(3) = 4 \times 3 \times f(2) = 4 \times 3 \times 2 \times f(1) = 4 \times 3 \times 2 \times 1 \times f(0) = 4 \times 3 \times 2 \times 1 \times 1 = 24\).

Résultat : \(f(4) = 24\).

c) Pour \(n = 4\) : \(2^4 - 1 = 16 - 1 = 15\) déplacements. (1 pt)

Total : 4 + 4 + 4 + 3 + 5 = 20 points.