L’algorithmique est au cœur de la programmation et de l’informatique. Elle permet de résoudre efficacement une multitude de problèmes, qu’ils soient mathématiques, logiques ou liés à des applications concrètes. Certains de ces problèmes sont dits classiques car ils apparaissent régulièrement en informatique et possèdent des solutions bien établies.

Dans cet article, nous allons explorer plusieurs problèmes classiques, expliquer leurs solutions algorithmiques et discuter des approches optimales.

---

1. Recherche d’un élément dans une liste

L’un des problèmes les plus fondamentaux en algorithmique est la recherche d’un élément dans un ensemble de données.

🔹 Solution 1 : Recherche linéaire (O(n))

La recherche linéaire consiste à parcourir un tableau élément par élément jusqu’à trouver la valeur recherchée.

📌 Code en Python :

pythonCopierModifierdef recherche_lineaire(liste, cible):
    for i in range(len(liste)):
        if liste[i] == cible:
            return i  # Retourne l’index de la cible
    return -1  # Si l’élément n’est pas trouvé

✅ Avantage : Simple et fonctionne sur toute liste.
❌ Inconvénient : Lent si la liste est grande (O(n)).

---

🔹 Solution 2 : Recherche dichotomique (O(log n))

Si la liste est triée, on peut utiliser la recherche binaire pour diviser par deux l’espace de recherche à chaque étape.

📌 Code en Python :

pythonCopierModifierdef recherche_binaire(liste, cible):
    debut, fin = 0, len(liste) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

✅ Avantage : Très rapide pour les grandes listes (O(log n)).
❌ Inconvénient : Nécessite une liste triée.

---

2. Tri d’une liste

Le tri est une opération fondamentale en algorithmique. Il existe plusieurs algorithmes de tri adaptés à différents cas d’usage.

🔹 Solution 1 : Tri par insertion (O(n²))

Le tri par insertion consiste à insérer chaque élément à sa place dans une partie déjà triée.

📌 Code en Python :

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

✅ Avantage : Efficace pour les petites listes.
❌ Inconvénient : Lent pour les grandes listes (O(n²)).

---

🔹 Solution 2 : Tri rapide (Quicksort) – O(n log n) en moyenne

L’un des tris les plus efficaces en pratique. Il utilise la diviser pour régner et un pivot pour séparer la liste en deux sous-listes.

📌 Code en Python :

pythonCopierModifierdef quicksort(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[len(liste) // 2]
    gauche = [x for x in liste if x < pivot]
    milieu = [x for x in liste if x == pivot]
    droite = [x for x in liste if x > pivot]
    return quicksort(gauche) + milieu + quicksort(droite)

✅ Avantage : Très efficace pour les grandes listes.
❌ Inconvénient : Peut être O(n²) dans le pire cas (si mal implémenté).

---

3. Problème du sac à dos (Knapsack Problem)

Le problème du sac à dos est un problème d’optimisation où il faut sélectionner les objets les plus rentables à emporter, sans dépasser une certaine capacité.

🔹 Solution : Programmation dynamique (O(nW))

Si nous avons n objets et une capacité maximale W, la programmation dynamique permet d’optimiser les choix de manière efficace.

📌 Code en Python :

pythonCopierModifierdef knapsack(valeurs, poids, W):
    n = len(valeurs)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if poids[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], valeurs[i - 1] + dp[i - 1][w - poids[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][W]

✅ Avantage : Trouve la meilleure solution.
❌ Inconvénient : Gourmand en mémoire et temps de calcul.

---

4. Problème du voyageur de commerce (TSP)

Le TSP (Travelling Salesman Problem) consiste à trouver le plus court chemin pour visiter N villes exactement une fois et revenir au point de départ.

🔹 Solution 1 : Algorithme glouton (heuristique – O(n²))

L’algorithme du plus proche voisin commence par une ville et choisit toujours la plus proche suivante.

📌 Code en Python :

pythonCopierModifierdef tsp_glouton(graph, depart):
    n = len(graph)
    visite = [False] * n
    chemin = [depart]
    visite[depart] = True
    for _ in range(n - 1):
        dernier = chemin[-1]
        prochain = min((i for i in range(n) if not visite[i]), key=lambda i: graph[dernier][i])
        visite[prochain] = True
        chemin.append(prochain)
    return chemin

✅ Avantage : Simple et rapide.
❌ Inconvénient : Peut donner une solution loin de l’optimal.

---

🔹 Solution 2 : Algorithme génétique (métaheuristique – O(k * n log n))

Une approche avancée consiste à utiliser un algorithme génétique pour optimiser progressivement la meilleure route.

📌 Idée :

1. Générer une population de trajets.
2. Évaluer la distance totale de chaque trajet.
3. Sélectionner les meilleurs trajets.
4. Croiser et muter les trajets pour créer une nouvelle génération.
5. Répéter jusqu’à une solution satisfaisante.

✅ Avantage : Trouve une bonne approximation rapidement.
❌ Inconvénient : Ne garantit pas l’optimum absolu.

---

Conclusion

L’algorithmique propose une variété d’approches pour résoudre des problèmes classiques :

• Recherche rapide (recherche binaire).
• Tri efficace (quicksort).
• Optimisation dynamique (sac à dos).
• Heuristiques et métaheuristiques (voyageur de commerce).

👉 Le choix du bon algorithme dépend de la taille des données, des contraintes et du besoin de précision. 🚀