← Retour au sommaire

Interrogation — Ch17 : Calcul et algorithmique

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

Dernière mise à jour : 21 juin 2026

Nom : _____ Prénom : _____ Date : _____

Exercice 1 — Affectation et trace (4 pts)

On exécute l'algorithme suivant :

a ← 3
b ← 5
a ← a + b
b ← a - b
Afficher(a, b)
  1. Donner la valeur de \(a\) puis de \(b\) après chaque affectation. (3 pts)
  2. Que vaut le couple affiché \((a, b)\) ? (1 pt)

Exercice 2 — Boucle et somme (3 pts)

On considère l'algorithme :

somme ← 0
POUR i DE 1 A 4 FAIRE
    somme ← somme + i * i
FIN POUR
Afficher(somme)

Donner la valeur affichée, en détaillant le calcul. (3 pts)

Exercice 3 — Récursivité (4 pts)

On rappelle la factorielle récursive : \(\text{Fact}(n) = n \times \text{Fact}(n-1)\) avec \(\text{Fact}(0) = 1\).

  1. Dérouler le calcul de \(\text{Fact}(4)\) et donner le résultat. (2 pts)
  2. La suite de Fibonacci vérifie \(F_0 = 0\), \(F_1 = 1\), \(F_n = F_{n-1} + F_{n-2}\). Donner \(F_2, F_3, F_4, F_5, F_6\). (2 pts)

Exercice 4 — Newton-Raphson (5 pts)

On cherche \(\sqrt{2}\) en résolvant \(f(x) = x^2 - 2 = 0\) par Newton-Raphson : \(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}\), avec \(f'(x) = 2x\) et \(x_0 = 1\).

  1. Montrer que la formule se simplifie en \(x_{n+1} = \dfrac{x_n}{2} + \dfrac{1}{x_n}\). (2 pts)
  2. Calculer \(x_1\) puis \(x_2\) (valeur exacte sous forme de fraction, puis valeur décimale). (3 pts)

Exercice 5 — Complexité (4 pts)

  1. Classer du plus rapide au plus lent (pour \(n\) grand) : \(O(n^2)\), \(O(\log n)\), \(O(n)\), \(O(n\log n)\). (2 pts)
  2. Donner la complexité dans le pire cas du tri à bulles, et celle de la recherche par dichotomie. (2 pts)

Correction

Exercice 1 (4 pts)

a) Suivi des affectations (l'affectation écrase l'ancienne valeur) :

  • \(a \leftarrow 3\) : \(a = 3\)
  • \(b \leftarrow 5\) : \(b = 5\)
  • \(a \leftarrow a + b = 3 + 5 = 8\) : \(a = 8\)
  • \(b \leftarrow a - b = 8 - 5 = 3\) : \(b = 3\)

(3 pts)

b) Le couple affiché est \((8, 3)\). (1 pt)

Exercice 2 (3 pts)

La boucle ajoute \(i^2\) pour \(i = 1, 2, 3, 4\) : \[\text{somme} = 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30\] La valeur affichée est \(30\). (3 pts)

Exercice 3 (4 pts)

a) \(\text{Fact}(4) = 4 \times \text{Fact}(3) = 4 \times 3 \times \text{Fact}(2) = 4 \times 3 \times 2 \times \text{Fact}(1) = 4 \times 3 \times 2 \times 1 = 24\). (2 pts)

b) \(F_2 = 1+0 = 1\) ; \(F_3 = 1+1 = 2\) ; \(F_4 = 2+1 = 3\) ; \(F_5 = 3+2 = 5\) ; \(F_6 = 5+3 = 8\). Soit \(1, 2, 3, 5, 8\). (2 pts)

Exercice 4 (5 pts)

a) \(x_{n+1} = x_n - \dfrac{x_n^2 - 2}{2x_n} = x_n - \dfrac{x_n}{2} + \dfrac{2}{2x_n} = \dfrac{x_n}{2} + \dfrac{1}{x_n}\). (2 pts)

b) Avec \(x_0 = 1\) : \[x_1 = \dfrac{1}{2} + \dfrac{1}{1} = \dfrac{3}{2} = 1{,}5\] \[x_2 = \dfrac{3/2}{2} + \dfrac{1}{3/2} = \dfrac{3}{4} + \dfrac{2}{3} = \dfrac{9}{12} + \dfrac{8}{12} = \dfrac{17}{12} \approx 1{,}41667\] On approche bien \(\sqrt{2} \approx 1{,}41421\). (3 pts)

Exercice 5 (4 pts)

a) Du plus rapide au plus lent : \(O(\log n) \ll O(n) \ll O(n\log n) \ll O(n^2)\). (2 pts)

b) Tri à bulles, pire cas : \(O(n^2)\). Recherche par dichotomie : \(O(\log n)\). (2 pts)

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