📘 Algorithmique et notion de listes — Terminale

En Terminale, l’algorithmique prolonge le programme de Première avec des algorithmes plus élaborés : tri, recherche de zéros, simulation de lois de probabilités et algorithmes sur les suites.

📐 I. Rappels sur les listes Python

Définition : une liste est une collection ordonnée d’éléments délimitée par des crochets.

liste = [3, 7, 2, 9]
liste[0]         # premier element → 3
liste[-1]        # dernier element → 9
len(liste)       # longueur → 4
liste.append(x)  # ajouter x en fin
liste[i] = v     # modifier l'element d'indice i
sorted(liste)    # renvoie une nouvelle liste triee

📐 II. Algorithme de tri par insertion

def tri_insertion(lst):
    for i in range(1, len(lst)):
        cle = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > cle:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = cle
    return lst

Complexité : O(n²) au pire. Adapté aux petites listes ou aux listes presque triées.

📐 III. Algorithmes sur les suites

Premiers termes d’une suite récurrente :

def termes_suite(u0, n):
    u = [u0]
    for i in range(n):
        u.append(2 * u[-1] - 1)  # u(n+1) = 2*u(n) - 1
    return u

Premier indice dépassant un seuil :

def premier_indice(u0, seuil):
    u, n = u0, 0
    while u < seuil:
        u = 2 * u - 1
        n += 1
    return n

📐 IV. Simulation de lois de probabilités

import random

# Loi de Bernoulli de parametre p
def bernoulli(p):
    return 1 if random.random() < p else 0

# Loi binomiale B(n, p)
def binomiale(n, p):
    return sum(bernoulli(p) for _ in range(n))

# Estimation de la proportion par frequence
def estimation(n_sim, n, p):
    return sum(binomiale(n, p) for _ in range(n_sim)) / (n * n_sim)

📐 V. Dichotomie — recherche d'un zéro

def dichotomie(f, a, b, precision):
    while b - a > precision:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

Convergence en O(log₂((b − a)/précision)) itérations.

📐 VI. Méthode de Newton

def newton(f, df, x0, precision):
    x = x0
    while abs(f(x)) > precision:
        x = x - f(x) / df(x)
    return x

Convergence rapide (quadratique) si x₀ est bien choisi et f'(x) ≠ 0 au voisinage de la racine.

💡 À retenir

• Indices Python de 0 à len − 1 ; dernier : liste[−1].
• Tri insertion : O(n²) ; dichotomie : O(log n) itérations ; Newton : convergence quadratique.
• random.random() renvoie un réel dans [0 ; 1[.
• Schéma de Bernoulli simulé : répéter bernoulli(p) n fois et sommer.