Fiche résumé – Calcul et algorithmique

Chapitre 17 | BTS | Mathématiques

Dernière mise à jour : 21 juin 2026

L'essentiel :

Un algorithme = suite finie, ordonnée et non ambiguë d'instructions ; entrées → traitement → sorties.
L'affectation x ← expression n'est pas une équation : x ← x+1 est valide.
Trois structures : SI (choix), POUR (nb d'itérations connu), TANT QUE (condition d'arrêt).
Hiérarchie des complexités : \(O(1)\ll O(\log n)\ll O(n)\ll O(n\log n)\ll O(n^2)\ll O(2^n)\).

Définitions clés

Définition

Variable : emplacement mémoire nommé contenant une valeur (entier, réel, booléen, chaîne, tableau).

Définition

Fonction / procédure : bloc nommé réutilisable. La fonction renvoie une valeur (RETOURNER), la procédure non.

Définition

Récursivité : une fonction s'appelle elle-même. Exige un cas de base (arrêt) et un cas récursif (problème plus petit).

Définition

Complexité \(O(\,)\) : ordre de grandeur du nombre d'opérations en fonction de la taille \(n\), dans le pire cas.

Pseudo-code ⇔ Python

Pseudo-code	Python
`x ← expression`	`x = expression`
`SI / SINON SI / SINON`	`if / elif / else`
`POUR i DE a À b`	`for i in range(a, b+1)`
`TANT QUE cond`	`while cond`

Formules à connaître

Méthode des trapèzes (intégration numérique) \[I\approx\frac{h}{2}\left[f(a)+2\sum_{k=1}^{n-1}f(a+kh)+f(b)\right],\quad h=\frac{b-a}{n}\]

Erreur en \(O(h^2)\) (rectangles : \(O(h)\)).

Newton-Raphson (recherche de racine) \[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\]

Arrêt quand \(|x_{n+1}-x_n|\lt\varepsilon\) ; convergence rapide (quadratique).

Dichotomie (si \(f\) continue et \(f(a)\cdot f(b)\lt 0\)) \[m=\frac{a+b}{2}\qquad n\ge\log_2\!\left(\frac{b-a}{\varepsilon}\right)\text{ itérations}\]

Complexité des tris

Tri	Moyen	Pire cas
À bulles / sélection	\(O(n^2)\)	\(O(n^2)\)
Rapide (quicksort)	\(O(n\log n)\)	\(O(n^2)\)
Fusion (mergesort)	\(O(n\log n)\)	\(O(n\log n)\)

Méthode — Écrire et lire un algorithme

Méthode

Analyser : identifier entrées, sorties, contraintes.
Déclarer les variables (nom et type).
Choisir la structure : SI (choix), POUR (itérations connues), TANT QUE (sinon).
Vérifier les cas limites (\(n=0\), liste vide, division par zéro).
Tracer à la main sur un exemple simple, puis traduire en Python (indentation 4 espaces).

Erreurs fréquentes

Attention

❌ Lire l'affectation comme une équation mathématique.

✅ x ← x+1 lit \(x\), ajoute 1, range le résultat dans \(x\).

❌ Boucle TANT QUE dont la condition ne devient jamais fausse.

✅ S'assurer qu'une variable du test est modifiée dans le corps, sinon boucle infinie.

❌ Utiliser la récursivité naïve de Fibonacci pour de grands \(n\).

✅ Complexité \(O(2^n)\) : préférer une version itérative.

❌ Oublier le cas de base d'une fonction récursive.

✅ Sans condition d'arrêt, les appels ne se terminent jamais.