Retour au programme
L'algorithmique est intégrée au programme de Mathématiques Terminale. Structures fondamentales : séquence, condition (if/else), boucle (for, while). Variables, affectation, types (entier, flottant, booléen). Algorithmes classiques en mathématiques : 1. Algorithme d'Euclide (PGCD). 2. Méthode de dichotomie (trouver une racine par encadrement successif). 3. Calcul approché d'intégrale (méthode des rectangles, trapèzes). 4. Suite récurrente : calcul du terme uₙ par itération. 5. Méthode de Newton (racines d'une fonction). Complexité algorithmique : nombre d'opérations en fonction de la taille des données. O(n) : complexité linéaire ; O(n²) : quadratique ; O(log n) : logarithmique. Récursivité : une fonction qui s'appelle elle-même (cas de base + cas récursif). Exemples : factorielle, suite de Fibonacci, algorithme d'Euclide récursif.
Exercice 1 : Méthode de dichotomie.
f(x) = x³ − 2x − 5. On sait que f admet une racine sur [2 ; 3].
Effectuez 3 étapes de dichotomie pour approcher cette racine.
Exercice 2 : Algorithme (pseudo-code).
Écrivez un algorithme qui calcule la somme 1 + 2 + ... + n pour un entier n donné.
Exercice 3 : Récursivité.
Écrivez une fonction récursive calculant n! (factorielle de n).
Comment fonctionne la méthode de dichotomie ?
Correction
On cherche une racine de f sur [a, b] avec f(a) et f(b) de signes opposés. On calcule m = (a+b)/2. Si f(m) = 0 : racine trouvée. Si f(a)·f(m) < 0 : la racine est dans [a, m] → nouvel intervalle [a, m]. Sinon : la racine est dans [m, b] → nouvel intervalle [m, b]. On répète jusqu'à obtenir une précision suffisante.
Qu'est-ce que la complexité algorithmique ?
Correction
La complexité mesure le nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n des données. O(1) = constant ; O(log n) = logarithmique (dichotomie) ; O(n) = linéaire (parcours d'un tableau) ; O(n²) = quadratique (tri à bulles) ; O(2ⁿ) = exponentiel (très lent).
Qu'est-ce qu'une fonction récursive ? Donner un exemple.
Correction
Une fonction récursive est une fonction qui s'appelle elle-même. Elle doit avoir un cas de base (condition d'arrêt) et un cas récursif. Exemple — factorielle : fact(0) = 1 (base) ; fact(n) = n × fact(n−1) (récursion). fact(4) = 4 × fact(3) = 4 × 3 × fact(2) = 4 × 3 × 2 × 1 = 24.