Algorithmique et Python
Structures de base en Python
Affectation, types : x = 3, f = 2.5, s = "texte", b = True.
Conditionnelle :
if condition:
...
elif autre_condition:
...
else:
...
Boucle bornée : for i in range(n) — itère \(i = 0, 1, \ldots, n-1\).
Boucle non bornée : while condition — s'arrête dès que la condition est fausse.
Fonctions
Une fonction encapsule un calcul réutilisable. Elle peut retourner une ou plusieurs valeurs.
def f(x):
return x**2 + 1
Fonctions récursives : une fonction qui s'appelle elle-même. Nécessite un cas de base pour terminer.
Listes et tableaux
L = [1, 2, 3] — indexation à partir de 0. L[0] = premier élément, L[-1] = dernier. L.append(x) ajoute en fin. len(L) donne la longueur.
Compréhension de liste : [f(i) for i in range(n)].
Algorithme de dichotomie
Pour résoudre \(f(x) = 0\) sur \([a, b]\) avec \(f\) continue et \(f(a)\cdot f(b) < 0\) :
- Calculer le milieu \(m = (a+b)/2\).
- Si \(f(a)\cdot f(m) \le 0\) : le zéro est dans \([a, m]\), poser \(b = m\).
- Sinon : le zéro est dans \([m, b]\), poser \(a = m\).
- Répéter jusqu'à \(b - a < \varepsilon\).
Nombre d'itérations nécessaires pour une précision \(\varepsilon\) :
Algorithme de Newton-Raphson
Pour approcher un zéro de \(f\) à partir d'un point \(x_0\), on suit la tangente :
Convergence quadratique (le nombre de décimales exactes double à chaque étape) si \(f'(x^*) \neq 0\).
Complexité algorithmique
La complexité mesure le nombre d'opérations en fonction de la taille \(n\) des données :
- \(O(1)\) : temps constant (accès à un élément d'un tableau).
- \(O(\log n)\) : dichotomie, algorithme d'Euclide.
- \(O(n)\) : parcours d'une liste, somme de \(n\) termes.
- \(O(n^2)\) : tri par insertion/sélection.
- \(O(n \log n)\) : tri fusion, tri rapide.
Algorithmes de tri
Tri par sélection : à chaque étape, chercher le minimum du reste et le placer en tête. Complexité \(O(n^2)\).
Tri par insertion : insérer chaque élément à sa place dans la partie déjà triée. Complexité \(O(n^2)\) au pire, \(O(n)\) si déjà trié.
Preuve : correction de la dichotomie
Invariant de boucle : à chaque étape, \(f(a) \cdot f(b) \le 0\) et l'intervalle \([a,b]\) contient un zéro de \(f\).
Initialisation : vraie par hypothèse (\(f(a)\cdot f(b) < 0\)).
Conservation : au rang \(n\), \(m = (a+b)/2\). Si \(f(a)\cdot f(m)\le0\), on pose \(b\leftarrow m\) et l'invariant est conservé ; sinon \(f(m)\cdot f(b)\le0\) (car le produit total est \(\le0\)) et on pose \(a\leftarrow m\).
Terminaison : la longueur \(b-a\) est divisée par 2 à chaque étape. Après \(n\) étapes, \(b-a = (b_0-a_0)/2^n \to 0\). \(\square\)
Preuve : nombre d'itérations de la dichotomie
Après \(n\) étapes, la longueur de l'intervalle est \(\dfrac{b-a}{2^n}\). On veut \(\dfrac{b-a}{2^n} < \varepsilon\), soit \(2^n > \dfrac{b-a}{\varepsilon}\). En passant au logarithme :
\[n > \log_2\!\left(\frac{b-a}{\varepsilon}\right) \implies n_{\min} = \left\lceil \log_2\!\left(\frac{b-a}{\varepsilon}\right) \right\rceil \quad \square\]Preuve : correction du tri par insertion
Invariant : après le \(k\)-ème passage, les \(k\) premiers éléments sont triés entre eux.
Initialisation : pour \(k=1\), un élément seul est trivialement trié.
Hérédité : on insère le \((k+1)\)-ème élément à sa place dans les \(k\) premiers (déjà triés) en décalant les éléments supérieurs. Les \(k+1\) premiers sont alors triés.
Conclusion : après \(n-1\) passages, les \(n\) éléments sont triés. \(\square\)
Preuve : terminaison d'un algorithme récursif (factorielle)
La fonction \(n! = n \times (n-1)!\) avec \(0! = 1\) est bien fondée car à chaque appel récursif l'argument diminue strictement de 1. Il atteint 0 en un nombre fini (\(n\)) d'appels. \(\square\)
Méthode 1 : Lire et compléter un algorithme
À l'examen, simuler l'algorithme pas à pas en tenant un tableau de valeurs des variables à chaque itération.
Exemple : algorithme calculant \(\sum_{k=1}^{5} k^2\) :
s = 0
for k in range(1, 6):
s = s + k**2
print(s)
Tableau : \(k=1, s=1\) ; \(k=2, s=5\) ; \(k=3, s=14\) ; \(k=4, s=30\) ; \(k=5, s=55\). Résultat : 55.
Méthode 2 : Implémenter la dichotomie
Vérifier d'abord les trois conditions : \(f\) continue sur \([a,b]\), \(f(a)\cdot f(b) < 0\), précision \(\varepsilon\) fournie. Utiliser une boucle while b - a > eps.
Méthode 3 : Calculer le seuil d'une suite par algorithme
Pour trouver le plus petit \(n\) tel que \(u_n > S\) (ou \(u_n < \varepsilon\)) :
u, n = u0, 0
while u <= S:
u = f(u) # ou u = formule(n)
n += 1
print(n, u)
Méthode 4 : Distinguer for et while
forquand le nombre d'itérations est connu à l'avance (calculer \(n\) termes d'une suite, sommer \(n\) valeurs).whilequand on s'arrête sur une condition (dichotomie, seuil, convergence).
Méthode 5 : Analyser la complexité
Compter les opérations élémentaires en fonction de \(n\) :
- Une boucle simple
for i in range(n)→ \(O(n)\). - Deux boucles imbriquées de taille \(n\) → \(O(n^2)\).
- Division de la taille par 2 à chaque étape (dichotomie) → \(O(\log n)\).
- Récursion sur \(f(n) = 2f(n/2) + O(n)\) → \(O(n\log n)\) (tri fusion).
range(n) donne \(0, 1, \ldots, n-1\) — pas \(n\)for i in range(5) produit \(i = 0, 1, 2, 3, 4\). Pour aller de 1 à \(n\) inclus : range(1, n+1). Erreur classique : décalage d'un indice (off-by-one).
Toute fonction récursive doit avoir un cas de base qui arrête les appels. Sans lui, Python lève une RecursionError. Vérifier que l'argument diminue strictement vers le cas de base.
La dichotomie ne s'applique que si \(f\) change de signe sur \([a,b]\). Sans cette condition, l'algorithme peut converger vers n'importe quel point ou boucler indéfiniment.
forModifier L pendant un for x in L donne des résultats imprévisibles. Itérer sur une copie for x in L[:] ou construire une nouvelle liste.
x = 5 affecte la valeur 5 à x. x == 5 est un test booléen. Écrire if x = 5 est une erreur de syntaxe en Python.
Calculatrice — algorithmes en mode programme
TI : PRGM → NEW. Commandes utiles : :Input X, :Disp, :For(I,1,N), :While, :If…Then…End.
Casio : menu PRGM. Syntaxe similaire, → pour l'affectation : 5→X. For 1→I To N Step 1.
Sur les deux : les programmes de dichotomie et de calcul de seuil sont très fréquents au BAC.
Python — dichotomie
def dichotomie(f, a, b, eps=1e-6):
"""Zéro de f sur [a,b] par dichotomie. Suppose f(a)*f(b) <= 0."""
assert f(a) * f(b) <= 0, "Pas de changement de signe"
while b - a > eps:
m = (a + b) / 2
if f(a) * f(m) <= 0:
b = m
else:
a = m
return (a + b) / 2
# Exemple : zéro de x^3 - 2 sur [1, 2] (= 2^(1/3))
f = lambda x: x**3 - 2
print(dichotomie(f, 1, 2)) # 1.2599210...
print(2**(1/3)) # 1.2599210...Python — méthode de Newton-Raphson
def newton(f, df, x0, eps=1e-10, max_iter=100):
"""Zéro de f par la méthode de Newton."""
x = x0
for _ in range(max_iter):
fx = f(x)
if abs(fx) < eps:
break
x = x - fx / df(x)
return x
# Zéro de f(x) = x^2 - 2 (= sqrt(2))
f = lambda x: x**2 - 2
df = lambda x: 2*x
print(newton(f, df, 1.0)) # 1.41421356...Python — tri par insertion
def tri_insertion(L):
T = L[:] # copie pour ne pas modifier l'original
for i in range(1, len(T)):
cle = T[i]
j = i - 1
while j >= 0 and T[j] > cle:
T[j+1] = T[j]
j -= 1
T[j+1] = cle
return T
print(tri_insertion([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]Python — suite récursive et seuil
# Suite u_{n+1} = sqrt(u_n + 2), u_0 = 0 — chercher seuil > 1.999
u, n = 0.0, 0
while u <= 1.999:
u = (u + 2) ** 0.5
n += 1
print(f"n = {n}, u_n = {u:.6f}")
# Fibonacci (récursif mémoïsé)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
print([fib(k) for k in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]Python — intégrale par la méthode des rectangles
def integrale_rectangles(f, a, b, n=1000):
"""Méthode des rectangles à gauche."""
h = (b - a) / n
return h * sum(f(a + i*h) for i in range(n))
import math
# Approximation de pi via ∫_0^1 4/(1+x^2) dx = pi
print(integrale_rectangles(lambda x: 4/(1+x**2), 0, 1, 10_000))
# 3.14149...Exercice 1 : Dichotomie et continuité (ch. 2)
La fonction \(f(x) = x^3 + x - 1\) est continue et strictement croissante. Montrer qu'elle admet un unique zéro sur \([0,1]\), puis écrire un algorithme de dichotomie pour l'approcher à \(10^{-3}\) près. Donner le nombre d'itérations nécessaires.
Éléments : \(f(0)=-1<0\), \(f(1)=1>0\). Nombre d'itérations : \(\lceil\log_2(1/0{,}001)\rceil = \lceil 9{,}97\rceil = 10\).
Exercice 2 : Suites et algorithme de seuil (ch. 1)
La suite \(u_n = 1 - (0{,}9)^n\) converge vers 1. Écrire un algorithme (en Python ou en pseudo-code) qui détermine le plus petit entier \(n\) tel que \(u_n > 0{,}99\).
Solution : \(1-(0{,}9)^n > 0{,}99 \iff (0{,}9)^n < 0{,}01 \iff n > \ln(0{,}01)/\ln(0{,}9) \approx 43{,}7\), donc \(n=44\). L'algorithme while confirme ce résultat.
Exercice 3 : Méthode des rectangles et intégrale (ch. 3)
Montrer que la somme de Riemann \(\dfrac{1}{n}\displaystyle\sum_{k=0}^{n-1} f\!\left(\dfrac{k}{n}\right)\) converge vers \(\displaystyle\int_0^1 f(x)\,dx\). Illustrer avec \(f(x) = e^x\) : la somme doit converger vers \(e - 1 \approx 1{,}7183\).
Exercice 4 : Newton-Raphson et fonctions ln/exp (ch. 4)
Appliquer Newton à \(f(x) = e^x - 2\) (zéro en \(x^* = \ln 2\)) à partir de \(x_0 = 1\).
Après 3 itérations : \(x_3 \approx 0{,}693147\) — convergence très rapide (quadratique).
Exercice 5 : Simulation probabiliste (ch. 8–9)
Écrire un programme Python qui simule \(N = 10\,000\) fois le lancer de \(n = 100\) pièces équilibrées et affiche la fréquence d'obtention d'exactement 50 faces. Comparer avec \(P(X=50)\) pour \(X\sim\mathcal{B}(100, 0{,}5)\).
import numpy as np
from scipy.stats import binom
N, n, p = 10_000, 100, 0.5
simul = np.random.binomial(n, p, N)
freq = np.mean(simul == 50)
print(f"Fréquence simulée : {freq:.4f}")
print(f"Probabilité exacte : {binom.pmf(50, n, p):.4f}")-
1.
range(2, 8, 2)produit les valeurs :range(start, stop, step): de 2 à 8 (exclu) par pas de 2 → 2, 4, 6. La valeur 8 est exclue. -
2. Pour approcher un zéro de \(f\) sur \([0,1]\) à \(10^{-4}\) près par dichotomie, le nombre minimal d'itérations est :
\(\lceil\log_2(1/10^{-4})\rceil = \lceil\log_2(10^4)\rceil = \lceil 13{,}29\rceil = 14\).
-
3. Quelle est la complexité du tri par insertion dans le pire cas ?
Dans le pire cas (liste triée à l'envers), chaque insertion nécessite de décaler tous les éléments précédents : \(\sum_{k=1}^{n-1} k = n(n-1)/2 \sim O(n^2)\).
-
4. Quelle instruction Python calcule la somme \(1 + 4 + 9 + 16 + 25\) ?
sum(i**2 for i in range(1,6))calcule \(1^2+2^2+3^2+4^2+5^2 = 55\). L'option A calcule \(1+2+\cdots+5=15\).