Algorithmique avancee/Diviser pour Regner

Diviser pour Regner

Face a un probleme complexe, la strategie est simple : DIVISER ! On coupe le probleme en morceaux plus petits, on resout chaque morceau, puis on combine les solutions. C'est le secret des algorithmes les plus efficaces comme le tri fusion, la recherche dichotomique, et meme l'algorithme de Karatsuba pour la multiplication rapide !

60 min Niveau 4/5 +50 XP

Objectifs

Comprendre le paradigme diviser pour regner
Identifier les 3 etapes : diviser, regner, combiner
Implementer le tri fusion (merge sort)
Analyser la complexite avec le theoreme maitre

Pieges a eviter

!Oublier le cas de base (recursion infinie)
!Ne pas diviser en sous-problemes independants
!Mauvaise fusion des solutions partielles
!Confusion entre complexite O(n log n) et O(n^2)

Cours complet

Le principe repose sur 3 etapes : DIVISER le probleme en sous-problemes, REGNER sur chaque sous-probleme (recursivement), COMBINER les solutions.

# Structure generale d'un algorithme Diviser pour Regner

def diviser_pour_regner(probleme):
    # CAS DE BASE : probleme assez petit
    if est_trivial(probleme):
        return solution_directe(probleme)

    # DIVISER : decomposer en sous-problemes
    sous_problemes = diviser(probleme)

    # REGNER : resoudre recursivement
    solutions_partielles = []
    for sp in sous_problemes:
        solutions_partielles.append(diviser_pour_regner(sp))

    # COMBINER : fusionner les solutions
    return combiner(solutions_partielles)

# Exemple classique : Recherche dichotomique
def recherche_dichotomique(liste, cible, debut=0, fin=None):
    """Recherche un element dans une liste triee."""
    if fin is None:
        fin = len(liste) - 1

    # Cas de base
    if debut > fin:
        return -1  # Non trouve

    # DIVISER : prendre le milieu
    milieu = (debut + fin) // 2

    # REGNER
    if liste[milieu] == cible:
        return milieu
    elif liste[milieu] > cible:
        return recherche_dichotomique(liste, cible, debut, milieu - 1)
    else:
        return recherche_dichotomique(liste, cible, milieu + 1, fin)

# Test
liste = [1, 3, 5, 7, 9, 11, 13, 15]
print(recherche_dichotomique(liste, 7))   # 3
print(recherche_dichotomique(liste, 8))   # -1

Quiz Diviser pour Regner

5 questions pour valider

Les 3 etapes

1. DIVISER en sous-problemes
2. REGNER recursivement
3. COMBINER les solutions

A retenir

• Tri fusion : O(n log n)
• Recherche dico : O(log n)
• Toujours un cas de base !