Terminale — Programme officiel (BO 2019) · Math@mine
Un moteur de recherche doit trier des millions de résultats par pertinence en une fraction de seconde. La différence entre un algorithme de tri en \(O(n^2)\) et un en \(O(n\log n)\) est colossale : pour un million d’éléments, c’est la différence entre 10 minutes et 0,02 seconde.
Le mot « algorithme » vient du nom du mathematicien persan Al-Khwarizmi (IXe siecle), qui a systematise les méthodes de résolution d’équations. Aujourd’hui, les algorithmes sont au coeur de l’informatique. Les algorithmes de tri et de recherche, etudies ici, comptent parmi les plus anciens et les plus fondamentaux de l’informatique.
L’ordinateur choisit un nombre entre 1 et 1000. A chaque essai, il repond « trop grand » ou « trop petit ». Combien d’essais au maximum faut-il pour trouver le nombre ?
L = [3, 1, 4, 1, 5, 9] print(L[0]) # 3 (premier element) print(len(L)) # 6 (longueur) L.append(2) # ajoute 2 en fin de liste L.sort() # trie la liste en place
| Opération | Syntaxe Python | Complexite |
|---|---|---|
| Acces par indice | L[i] | \(O(1)\) |
| Longueur | len(L) | \(O(1)\) |
| Ajout en fin | L.append(x) | \(O(1)\) |
| Insertion | L.insert(i, x) | \(O(n)\) |
| Recherche | x in L | \(O(n)\) |
Acces \(O(1)\) : En Python, une liste est stockee comme un tableau contigu en memoire. L’adresse de l’élément \(i\) se calcule directement : adresse = début + \(i \times\) taille. Pas de parcours nécessaire.
Insertion \(O(n)\) : Pour inserer en position \(i\), il faut decaler les \(n - i\) éléments suivants d’une case vers la droite. Dans le pire cas (\(i = 0\)), c’est \(n\) déplacements.
Recherche \(O(n)\) : Sans information sur l’ordre, il faut parcourir la liste élément par élément. Dans le pire cas (élément absent), on examine les \(n\) éléments.
Les listes par comprehension sont un outil puissant en Python :
carres = [k**2 for k in range(10)] # [0, 1, 4, 9, ..., 81] pairs = [x for x in L if x % 2 == 0] # filtre les nombres pairs
Cette notion n'est pas au programme de la spécialité Maths (BO 2019), mais elle figure au programme de NSI (Numérique et Sciences Informatiques). Elle est présentée ici pour les élèves qui suivent les deux spécialités, ou pour enrichir les compétences Python en vue du supérieur.
Un dictionnaire est une collection non ordonnée de paires clé : valeur. Contrairement à une liste qui est indicée par des entiers, un dictionnaire est indicé par n'importe quel type immuable (chaîne, entier, tuple). En Python, on le crée avec des accolades.scores = {"Alice": 15, "Bob": 12, "Chloe": 18}
print(scores["Alice"]) # 15 (accès par clé)
scores["David"] = 14 # ajout d'une paire
del scores["Bob"] # suppression
print(len(scores)) # 3 (nombre de paires)
for nom, note in scores.items():
print(nom, "→", note)
| Critère | Liste | Dictionnaire |
|---|---|---|
| Indexation | entier \(0, 1, \ldots\) | clé de tout type immuable |
| Ordre | ordonnée | non ordonné (*) |
| Accès | \(O(1)\) par indice | \(O(1)\) par clé (en moyenne) |
| Recherche d'une valeur | \(O(n)\) | \(O(n)\) |
| Test d'appartenance | x in L — \(O(n)\) | k in D — \(O(1)\) |
(*) Depuis Python 3.7, l'ordre d'insertion est préservé mais ne doit pas être exploité pour la logique de l'algorithme.
mots = ["pomme", "banane", "pomme", "kiwi", "pomme", "banane"]
compteur = {}
for m in mots:
compteur[m] = compteur.get(m, 0) + 1
print(compteur) # {'pomme': 3, 'banane': 2, 'kiwi': 1}
Le dictionnaire est l'outil idéal pour associer des informations à des étiquettes (fréquences, scores, coordonnées, etc.).
On parcourt la liste élément par élément jusqu’à trouver la valeur cherchee ou atteindre la fin.
def recherche_seq(L, x):
for i in range(len(L)):
if L[i] == x:
return i
return -1 # non trouve
Complexite : \(O(n)\) dans le pire cas (élément absent ou en fin de liste).
Si la liste est triee, on compare avec l’élément central et on elimine la moitie à chaque étape.
def recherche_dicho(L, x):
a, b = 0, len(L) - 1
while a <= b:
m = (a + b) // 2
if L[m] == x:
return m
elif L[m] < x:
a = m + 1
else:
b = m - 1
return -1
Complexite : \(O(\log_2 n)\). Pour \(n = 10^6\), au plus 20 comparaisons.
A chaque étape, on cherche le minimum de la partie non triee et on le place en bonne position.
def tri_selection(L):
n = len(L)
for i in range(n - 1):
i_min = i
for j in range(i + 1, n):
if L[j] < L[i_min]:
i_min = j
L[i], L[i_min] = L[i_min], L[i]
return L
Complexite : \(O(n^2)\) comparaisons dans tous les cas.
On insere chaque élément a sa place dans la partie déjà triee.
def tri_insertion(L):
for i in range(1, len(L)):
cle = L[i]
j = i - 1
while j >= 0 and L[j] > cle:
L[j + 1] = L[j]
j -= 1
L[j + 1] = cle
return L
Complexite : \(O(n^2)\) dans le pire cas, mais \(O(n)\) si la liste est déjà presque triee.
sorted() de Python utilise l’algorithme Timsort (melange de tri par insertion et tri fusion), de complexite \(O(n \log n)\).
| Complexite | Nom | Exemple (\(n = 10^6\)) |
|---|---|---|
| \(O(1)\) | Constante | 1 opération |
| \(O(\log n)\) | Logarithmique | 20 opérations |
| \(O(n)\) | Lineaire | \(10^6\) opérations |
| \(O(n \log n)\) | Quasi-lineaire | \(2 \times 10^7\) opérations |
| \(O(n^2)\) | Quadratique | \(10^{12}\) opérations |
| \(O(2^n)\) | Exponentielle | Intraitable |
Recherche dichotomique \(O(\log n)\) : A chaque étape, l’intervalle de recherche est divise par 2. Apres \(k\) étapes, il reste \(n/2^k\) éléments. On s’arrete quand \(n/2^k \leq 1\), soit \(k \geq \log_2 n\). ✓
Tri par selection \(O(n^2)\) : La boucle externe fait \(n-1\) tours. Au tour \(i\), la boucle interne fait \(n-1-i\) comparaisons. Total : \((n-1) + (n-2) + \cdots + 1 = \dfrac{n(n-1)}{2}\), qui est proportionnel a \(n^2\). ✓
Tri par insertion \(O(n^2)\) pire cas : Si la liste est triee en ordre inverse, au tour \(i\), l’élément est déplace de \(i\) positions. Total : \(1 + 2 + \cdots + (n-1) = \dfrac{n(n-1)}{2}\). Mais si la liste est déjà triee, chaque élément est déjà a sa place : \(O(n)\) comparaisons. ✓
Pour trier \(n = 10\,000\) éléments :
Le tri fusion est environ 750 fois plus rapide.
import random
def simulation_des(n):
"""Simule n lancers d'un de et renvoie les frequences."""
compteur = [0] * 6
for _ in range(n):
face = random.randint(1, 6)
compteur[face - 1] += 1
return [c / n for c in compteur]
def proba_au_moins_un_six(n_lancers, n_simulations):
"""Estime P(au moins un 6 en n_lancers lancers)."""
succes = 0
for _ in range(n_simulations):
if any(random.randint(1, 6) == 6 for _ in range(n_lancers)):
succes += 1
return succes / n_simulations
Pour 4 lancers : la probabilité theorique est \(1 - (5/6)^4 \approx 0{,}518\).
def binomiale(n, p, nb_simulations=10000):
"""Simule une loi B(n,p) et trace l'histogramme des frequences."""
resultats = [0] * (n + 1)
for _ in range(nb_simulations):
succes = sum(1 for _ in range(n) if random.random() < p)
resultats[succes] += 1
return [r / nb_simulations for r in resultats]
def dichotomie(f, a, b, epsilon=1e-10):
"""Trouve x tel que f(x) = 0, avec f(a)*f(b) < 0."""
while b - a > epsilon:
m = (a + b) / 2
if f(a) * f(m) <= 0:
b = m
else:
a = m
return (a + b) / 2
# Exemple : approcher √2 = racine de x² - 2 sur [1, 2]
racine = dichotomie(lambda x: x**2 - 2, 1, 2, 1e-10)
print(racine) # 1.4142135623...
Pour résoudre \(f(x) = 0\) (avec \(f\) dérivable et \(f'(x_n) \neq 0\)), on construit la suite récurrente :
\(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}\)
Géométriquement : \(x_{n+1}\) est l'abscisse du point d'intersection de la tangente à la courbe en \((x_n, f(x_n))\) avec l'axe des abscisses. La convergence (lorsqu'elle a lieu) est très rapide : le nombre de décimales correctes double approximativement à chaque itération (convergence quadratique).
def newton(f, fp, x0, epsilon=1e-10, n_max=100):
"""f : fonction ; fp : derivee de f ; x0 : initialisation."""
x = x0
for _ in range(n_max):
fx = f(x)
if abs(fx) < epsilon:
return x
x = x - fx / fp(x)
return x
# Exemple : approcher sqrt(2) = racine de x^2 - 2
racine = newton(lambda x: x**2 - 2, lambda x: 2*x, 1.5)
print(racine) # 1.4142135623730951 (16 decimales en 5 iterations)
def euler(f, x0, y0, xfin, n):
"""Resolution approchee de y' = f(x, y), y(x0) = y0."""
h = (xfin - x0) / n
x, y = x0, y0
points = [(x, y)]
for _ in range(n):
y = y + h * f(x, y)
x = x + h
points.append((x, y))
return points
# Exemple : y' = -2y + 4, y(0) = 0, sur [0, 3] en 300 pas
points = euler(lambda x, y: -2*y + 4, 0, 0, 3, 300)
print(points[-1]) # (3.0, 2.0...) tend vers la valeur d'equilibre 2
def integrale_rectangles(f, a, b, n):
"""Approximation de l'integrale de f de a à b."""
h = (b - a) / n
somme = sum(f(a + i * h) for i in range(n))
return somme * h
# Exemple : approcher ∫₀¹ x² dx = 1/3 ≈ 0.333...
approximation = integrale_rectangles(lambda x: x**2, 0, 1, 10000)
print(approximation) # ≈ 0.33328...
Plus \(n\) est grand, plus l’approximation est precise.
Pour \(n = 10^6\) éléments :
Le choix de l’algorithme fait la différence entre un résultat instantané et une attente de 17 minutes. On mesure l’efficacite par la complexite algorithmique en notation \(O\) : elle decrit comment le temps de calcul evolue avec la taille de l’entree \(n\).
Règle pratique : si \(n > 10\,000\), un algorithme en \(O(n^2)\) devient lent ; au-dela de \(n = 10^6\), seuls les algorithmes en \(O(n \log n)\) ou mieux sont raisonnables.
En utilisant la recherche dichotomique, on divise l’intervalle par 2 à chaque étape. Il faut au plus \(\lceil\log_2(1000)\rceil = 10\) essais. C’est la puissance de la recherche dichotomique en \(O(\log n)\).
| Algorithme | Complexite |
|---|---|
| Recherche sequentielle | \(O(n)\) |
| Recherche dichotomique | \(O(\log n)\) |
| Tri par selection / insertion | \(O(n^2)\) |
| Tri fusion / Timsort | \(O(n \log n)\) |
| Dichotomie (precision \(\varepsilon\)) | \(O\!\left(\log\frac{b-a}{\varepsilon}\right)\) |
| Méthode d’Euler | \(O(n)\) pas |
Algorithmique : teste d’abord ton intuition.
« Une boucle while termine toujours. »
Cette affirmation est-elle correcte ?
Faux. Une boucle while peut ne jamais terminer si la condition reste toujours vraie (boucle infinie). Par exemple : while True: pass. C’est la différence fondamentale avec la boucle for qui a un nombre d’iterations fixe. Prouver la terminaison d’un while necessite un variant de boucle.
for : termine toujours. Boucle while : il faut vérifier (variant de boucle).Mini-test : n = 10; while n > 0: n = n - 1 termine-t-elle ?
« Le tri par insertion a une complexite \(O(n \log n)\). »
Cette affirmation est-elle correcte ?
Faux. Le tri par insertion a une complexite dans le pire cas en \(O(n^2)\) (liste triee a l’envers). Sa complexite dans le meilleur cas est \(O(n)\) (liste déjà triee). La complexite \(O(n \log n)\) est celle des tris plus efficaces comme le tri fusion ou le tri rapide (en moyenne).
Mini-test : quel tri a une complexite \(O(n \log n)\) dans le pire cas ?
« Un algorithme glouton donne toujours la solution optimale. »
Cette affirmation est-elle correcte ?
Faux. Un algorithme glouton fait à chaque étape le choix localement optimal, mais cela ne garantit pas l’optimum global. Exemple classique : le rendu de monnaie avec le système {1, 3, 4}. Pour rendre 6 : le glouton donne 4+1+1 (3 pieces), mais l’optimal est 3+3 (2 pieces).
Mini-test : le rendu de monnaie glouton avec les pieces {1, 2, 5, 10} est-il toujours optimal ?
« On peut appliquer la recherche dichotomique sur n’importe quelle liste. »
Cette affirmation est-elle correcte ?
Faux. La recherche dichotomique ne fonctionne que sur une liste triee. Elle compare l’élément cherche au milieu de la liste et elimine une moitie à chaque étape. Sur une liste non triee, cette strategie peut manquer l’élément recherche.
Mini-test : complexite de la recherche dichotomique dans une liste triee de \(n\) éléments :
« On peut modifier la taille d’une liste tout en iterant dessus avec for sans risque. »
Cette affirmation est-elle correcte ?
Faux. Modifier la taille d’une liste (ajout ou suppression) pendant qu’on itere dessus avec for provoque des comportements imprevisibles : éléments sautes ou traites deux fois. Il faut iterer sur une copie ou utiliser une autre approche.
for x in liste: liste.remove(x). Utiliser une copie : for x in liste[:]: ...Mini-test : pour supprimer les pairs de [1,2,3,4], on utilise :
« Un algorithme en \(O(n)\) est plus efficace qu’un algorithme en \(O(n^2)\) pour \(n\) grand. »
Cette affirmation est-elle correcte ?
C’est vrai ! La notation \(O\) decrit le comportement asymptotique. Pour \(n\) suffisamment grand, un algorithme \(O(n)\) sera toujours plus rapide qu’un algorithme \(O(n^2)\). Par exemple, pour \(n = 10\,000\) : \(O(n) \approx 10^4\) opérations contre \(O(n^2) \approx 10^8\).
Mini-test : pour \(n = 1\,000\,000\), combien de fois \(O(n^2)\) est-il plus lent que \(O(n)\) ?