Chapitre 25 – Algorithmique appliquée

1. Rappels algorithmiques

Ce chapitre s'appuie sur les notions du chapitre 17 (variables, structures de contrôle, fonctions). Rappels essentiels en Python :

# Variables et types de base
n = 10           # entier
x = 3.14         # flottant
nom = "Alice"   # chaîne
tableau = [5, 3, 8, 1, 9, 2]  # liste (mutable, indexée à 0)

# Boucle for
for i in range(5):
    print(i)          # affiche 0, 1, 2, 3, 4

# Boucle while
i = 0
while i < 5:
    i += 1

# Fonction avec docstring
def maxi(tableau):
    """Retourne le maximum d'une liste."""
    m = tableau[0]
    for x in tableau:
        if x > m:
            m = x
    return m

2. Algorithmes de recherche

2.1 Recherche séquentielle

def recherche_sequentielle(tableau, cible):
    """Retourne l'indice de cible, ou -1 si absent."""
    for i in range(len(tableau)):
        if tableau[i] == cible:
            return i
    return -1

# Exemple d'utilisation
t = [5, 3, 8, 1, 9, 2]
print(recherche_sequentielle(t, 8))  # → 2
print(recherche_sequentielle(t, 7))  # → -1

2.2 Recherche dichotomique

def recherche_dichotomique(tableau, cible):
    """Retourne l'indice de cible dans un tableau trié, ou -1."""
    gauche, droite = 0, len(tableau) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == cible:
            return milieu
        elif tableau[milieu] < cible:
            gauche = milieu + 1   # chercher à droite
        else:
            droite = milieu - 1  # chercher à gauche
    return -1

# Exemple : tableau trié
t = [1, 2, 3, 5, 8, 9]
print(recherche_dichotomique(t, 8))  # → 4
print(recherche_dichotomique(t, 7))  # → -1

À chaque étape, on ne conserve que la moitié du tableau contenant la cible : la zone de recherche est divisée par 2.

3. Algorithmes de tri

3.1 Tri à bulles (Bubble Sort)

def tri_bulles(t):
    """Tri à bulles (modifie t en place)."""
    n = len(t)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if t[j] > t[j+1]:
                t[j], t[j+1] = t[j+1], t[j]
                echange = True
        if not echange:   # déjà trié → arrêt anticipé
            break

Trace d'exécution sur \([5, 3, 1, 4, 2]\) — passe 1 :

3.2 Tri par insertion

def tri_insertion(t):
    """Tri par insertion (modifie t en place)."""
    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]   # décaler vers la droite
            j -= 1
        t[j+1] = cle    # insérer à la bonne position

3.3 Tri par sélection

def tri_selection(t):
    """Tri par sélection (modifie t en place)."""
    n = len(t)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if t[j] < t[i_min]:
                i_min = j
        t[i], t[i_min] = t[i_min], t[i]  # échange

3.4 Tri rapide (Quicksort)

def tri_rapide(t, gauche=0, droite=None):
    """Tri rapide récursif (modifie t en place)."""
    if droite is None:
        droite = len(t) - 1
    if gauche < droite:
        pivot_idx = partition(t, gauche, droite)
        tri_rapide(t, gauche, pivot_idx - 1)
        tri_rapide(t, pivot_idx + 1, droite)

def partition(t, gauche, droite):
    """Partition autour du dernier élément (pivot)."""
    pivot = t[droite]
    i = gauche - 1
    for j in range(gauche, droite):
        if t[j] <= pivot:
            i += 1
            t[i], t[j] = t[j], t[i]
    t[i+1], t[droite] = t[droite], t[i+1]
    return i + 1

3.5 Comparaison des algorithmes de tri

4. Structures de données linéaires

4.1 Pile (LIFO — Last In First Out)

# En Python, une liste s'utilise efficacement comme pile
pile = []
pile.append(10)    # push → pile = [10]
pile.append(20)    # push → pile = [10, 20]
pile.append(30)    # push → pile = [10, 20, 30]
sommet = pile.pop()  # pop  → sommet = 30, pile = [10, 20]

# Implémentation sous forme de classe
class Pile:
    def __init__(self):
        self._data = []
    def push(self, val): self._data.append(val)
    def pop(self):
        if self._data:
            return self._data.pop()
    def peek(self):
        return self._data[-1] if self._data else None
    def est_vide(self): return len(self._data) == 0

4.2 File (FIFO — First In First Out)

from collections import deque

file = deque()            # file vide
file.append("alerte_1")  # enqueue
file.append("alerte_2")  # enqueue
file.append("alerte_3")  # enqueue
premier = file.popleft()  # dequeue → "alerte_1"

# deque est O(1) pour popleft()
# list.pop(0) serait O(n) — à éviter pour les grandes files

# Version pile (liste)            # Version file (deque)
p = []                          f = deque()
p.append(10)                   f.append(10)
p.append(20)                   f.append(20)
p.append(30)                   f.append(30)
x = p.pop()                     x = f.popleft()
p.append(40)                   f.append(40)
y = p.pop()                     y = f.popleft()

4.3 Liste chaînée

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

class ListeChainee:
    def __init__(self): self.tete = None

    def inserer_debut(self, val):
        nouveau = Noeud(val)
        nouveau.suivant = self.tete
        self.tete = nouveau

    def parcourir(self):
        courant = self.tete
        while courant:
            print(courant.valeur, end=" -> ")
            courant = courant.suivant
        print("None")

5. Algorithmes récursifs

5.1 Principe de la récursivité

5.2 Factorielle

def factorielle(n):
    """Calcule n! récursivement. n doit être un entier >= 0."""
    if n == 0:         # cas de base : 0! = 1
        return 1
    return n * factorielle(n - 1)  # appel récursif

# Arbre d'appels pour factorielle(4) :
#  factorielle(4) = 4 × factorielle(3)
#                       = 3 × factorielle(2)
#                             = 2 × factorielle(1)
#                                   = 1 × factorielle(0) = 1

5.3 Suite de Fibonacci

def fibonacci_recursif(n):
    """F(n) récursif — complexité O(2^n), à éviter pour grands n."""
    if n <= 1: return n
    return fibonacci_recursif(n-1) + fibonacci_recursif(n-2)

def fibonacci_iteratif(n):
    """F(n) itératif — complexité O(n), recommandé."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fibonacci_memo(n, cache={}):
    """F(n) avec mémoïsation — complexité O(n)."""
    if n in cache: return cache[n]
    if n <= 1: return n
    cache[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    return cache[n]

5.4 Tours de Hanoï

def hanoi(n, source, cible, intermediaire):
    """Déplace n disques de source vers cible via intermediaire."""
    if n == 1:
        print(f"Déplacer disque 1 : {source} → {cible}")
        return
    hanoi(n-1, source, intermediaire, cible)
    print(f"Déplacer disque {n} : {source} → {cible}")
    hanoi(n-1, intermediaire, cible, source)

# hanoi(3, 'A', 'C', 'B')  → 7 déplacements
# Nombre de déplacements pour n disques = 2^n - 1

5.5 Récursion vs itération

6. Algorithmes de traitement de données

def statistiques(data):
    """Calcule moyenne, médiane, variance, min, max d'une liste."""
    n = len(data)
    if n == 0: return None

    # Minimum et maximum
    minimum = maximum = data[0]
    for x in data:
        if x < minimum: minimum = x
        if x > maximum: maximum = x

    # Moyenne
    somme = sum(data)
    moyenne = somme / n

    # Variance et écart-type
    variance = sum((x - moyenne)**2 for x in data) / n
    ecart_type = variance ** 0.5

    # Médiane (nécessite un tableau trié)
    trie = sorted(data)
    if n % 2 == 1:
        mediane = trie[n // 2]
    else:
        mediane = (trie[n//2 - 1] + trie[n//2]) / 2

    return {
        "n": n, "min": minimum, "max": maximum,
        "moyenne": moyenne, "médiane": mediane,
        "variance": variance, "écart_type": ecart_type
    }

def filtrer(data, predicate):
    """Retourne les éléments vérifiant predicate."""
    return [x for x in data if predicate(x)]

def compter(data, predicate):
    """Compte les éléments vérifiant predicate."""
    return sum(1 for x in data if predicate(x))

7. Complexité algorithmique

7.1 Notation Big-O

Pour de grandes tailles \(n\), l'écart entre les classes de complexité devient énorme : \(O(2^n)\) et \(O(n^2)\) explosent, tandis que \(O(\log n)\) reste quasi plate.

7.2 Complexité temporelle et spatiale

8. Application — Traitement de données industrielles

Programme complet de traitement des données de cotes de pièces pour Karim. Il lit les mesures, les trie, calcule les statistiques et génère un rapport d'anomalies.

#!/usr/bin/env python3
"""
Contrôle qualité automatique — Analyse des cotes de fabrication.
Utilisation : python3 controle_qualite.py
"""
from collections import deque
import math

TOLERANCE = 0.5    # mm
COTE_NOMINALE = 100.0  # mm

def charger_mesures(fichier):
    """Simule le chargement de mesures depuis un fichier CSV."""
    # En production : with open(fichier) as f: ...
    import random
    random.seed(42)
    return [100.0 + random.gauss(0, 0.3) for _ in range(500)]

def detecter_anomalies(mesures, cote_nom, tol):
    """Retourne les indices et valeurs des mesures hors tolérance."""
    return [(i, v) for i, v in enumerate(mesures)
            if abs(v - cote_nom) > tol]

def statistiques(data):
    """Calcule les statistiques descriptives."""
    n = len(data)
    moy = sum(data) / n
    var = sum((x - moy)**2 for x in data) / n
    trie = sorted(data)
    med = trie[n//2] if n%2 else (trie[n//2-1]+trie[n//2])/2
    return {"n":n, "min":min(data), "max":max(data),
             "moy":moy, "med":med, "ecart":math.sqrt(var)}

def recherche_dichotomique_trie(trie, cible, tol):
    """Vérifie rapidement si une valeur proche de cible existe."""
    g, d = 0, len(trie)-1
    while g <= d:
        m = (g+d)//2
        if abs(trie[m]-cible) <= tol: return True
        elif trie[m] < cible: g = m+1
        else: d = m-1
    return False

def main():
    # 1. Chargement
    mesures = charger_mesures("mesures.csv")
    print(f"Mesures chargées : {len(mesures)} valeurs")

    # 2. Statistiques
    stats = statistiques(mesures)
    print(f"Moyenne : {stats['moy']:.4f} mm | Écart-type : {stats['ecart']:.4f} mm")
    print(f"Médiane : {stats['med']:.4f} mm | Min : {stats['min']:.4f} | Max : {stats['max']:.4f}")

    # 3. Détection des anomalies
    anomalies = detecter_anomalies(mesures, COTE_NOMINALE, TOLERANCE)
    print(f"Pièces hors tolérance : {len(anomalies)} / {len(mesures)}")

    # 4. File d'alertes FIFO
    alertes = deque()
    for idx, val in anomalies:
        alertes.append({"piece": idx+1, "cote": val,
                         "ecart": val-COTE_NOMINALE})

    print("\n=== Rapport d'alertes (file FIFO) ===")
    while alertes:
        a = alertes.popleft()
        print(f"  Pièce #{a['piece']:4d} : {a['cote']:.4f} mm (écart {a['ecart']:+.4f} mm)")

if __name__ == "__main__":
    main()