Combiner algorithmes et données | Exercices corrigés

Concepts & Exercices

Algorithme \land Structure_{données} = Solution_{efficace}

Combinaison optimale

Tri

trie(données)

Ordonner les éléments

Recherche

recherche(données, cible)

Trouver un élément

Manipulation

traiter(structure)

Transformer les données

🎯

Définition : Associer des algorithmes aux structures de données appropriées.

📊

Performance : Choisir la structure qui optimise l'algorithme.

🔗

Adéquation : L'algorithme doit correspondre à la structure.

⚡

Efficacité : Minimiser le temps et l'espace de traitement.

Exercice 1

Trier un tableau de dictionnaires selon une clé spécifique

Exercice 2

Rechercher un élément dans une liste triée avec dichotomie

Exercice 3

Filtrer des données en utilisant une structure appropriée

Exercice 4

Manipuler des piles et files pour traiter des données

Exercice 5

Analyser les performances d'algorithmes avec différentes structures

Corrigé : Exercices 1 à 3

1 Tri de dictionnaires

Définition :

Tri personnalisé : Ordonner des objets complexes selon une propriété spécifique.

Méthode de tri :

Identifier la clé de tri dans les dictionnaires
Utiliser la fonction sorted() avec une lambda
Spécifier la clé de tri avec key=lambda
Retourner le tableau trié

donnees = [
    {"nom": "Dupont", "age": 35, "ville": "Paris"},
    {"nom": "Martin", "age": 28, "ville": "Lyon"},
    {"nom": "Petit", "age": 42, "ville": "Marseille"}
]

# Tri par âge
tris_par_age = sorted(donnees, key=lambda x: x["age"])

# Résultat: [{"nom": "Martin", ...}, {"nom": "Dupont", ...}, {"nom": "Petit", ...}]
              

Étape 1 : Analyser la structure des données

Chaque élément est un dictionnaire avec des clés nom, age, ville.

Étape 2 : Choisir la clé de tri

Nous voulons trier selon la clé "age" de chaque dictionnaire.

Étape 3 : Appliquer la fonction de tri

Utiliser sorted() avec une fonction lambda pour extraire la clé.

Tri par âge: Martin(28) → Dupont(35) → Petit(42)

Réponse finale :

Le tri est effectué en utilisant une fonction lambda pour extraire la clé de tri de chaque dictionnaire.

Règles appliquées :

• Clé de tri : Spécifier la propriété utilisée pour ordonner

• Fonction lambda : Extraire la valeur de tri pour chaque élément

• Immutabilité : sorted() crée une nouvelle liste triée

2 Recherche dichotomique

Définition :

Recherche dichotomique : Algorithme de recherche dans une liste triée avec complexité logarithmique.

def recherche_dichotomique(tab, element):
    debut = 0
    fin = len(tab) - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == element:
            return milieu
        elif tab[milieu] < element:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return -1  # Non trouvé

# Exemple
donnees_triees = [1, 3, 5, 7, 9, 11, 13, 15]
position = recherche_dichotomique(donnees_triees, 7)
# Retourne: 3 (indice de 7)
              

Étape 1 : Vérifier que la liste est triée

La recherche dichotomique ne fonctionne que sur une liste triée.

Étape 2 : Initialiser les bornes

Variables debut et fin encadrent la zone de recherche.

Étape 3 : Itérer en divisant par deux

À chaque itération, on compare l'élément central et ajuste les bornes.

Complexité: O(log n) vs O(n) pour la recherche linéaire

Réponse finale :

La recherche dichotomique divise la zone de recherche par deux à chaque étape.

Règles appliquées :

• Précondition : La liste doit être triée

• Complexité : O(log n) pour une liste de taille n

• Diviser pour régner : Diviser la zone de recherche par deux

3 Filtrage de données

Définition :

Filtrage : Extraire les éléments d'une structure qui satisfont un critère donné.

def filtrer_etudiants(etudiants, seuil):
    return [etud for etud in etudiants if etud["note"] >= seuil]

# Données
etudiants = [
    {"nom": "Alice", "note": 14},
    {"nom": "Bob", "note": 12},
    {"nom": "Charlie", "note": 16},
    {"nom": "Diana", "note": 9}
]

# Filtrage
admis = filtrer_etudiants(etudiants, 10)
# Résultat: [{"nom": "Alice", "note": 14}, {"nom": "Bob", "note": 12}, {"nom": "Charlie", "note": 16}]
              

Étape 1 : Définir le critère de filtrage

Seuil minimal pour être admis (dans cet exemple: note ≥ 10).

Étape 2 : Choisir la structure appropriée

Liste de dictionnaires pour stocker les informations des étudiants.

Étape 3 : Appliquer le filtre

Utiliser une compréhension de liste pour sélectionner les éléments correspondants.

Filtrage: 3 admis sur 4 étudiants

Réponse finale :

Le filtrage extrait les éléments qui satisfont une condition spécifique.

Règles appliquées :

• Structure adaptée : Utiliser une structure qui permet l'accès aux critères

• Condition claire : Définir une condition de filtrage précise

• Efficacité : Compréhension de liste pour une implémentation concise

Corrigé : Exercices 4 à 5

4 Piles et files

Définition :

Pile (LIFO) : Dernier entré, premier sorti. File (FIFO) : Premier entré, premier sorti.

class Pile:
    def __init__(self):
        self.elements = []
    
    def empiler(self, element):
        self.elements.append(element)
    
    def depiler(self):
        if not self.est_vide():
            return self.elements.pop()
        return None
    
    def est_vide(self):
        return len(self.elements) == 0

# Exemple
pile = Pile()
pile.empiler(1)
pile.empiler(2)
pile.empiler(3)
print(pile.depiler())  # Sortie: 3

from collections import deque

class File:
    def __init__(self):
        self.elements = deque()
    
    def enfiler(self, element):
        self.elements.appendleft(element)
    
    def defiler(self):
        if not self.est_vide():
            return self.elements.pop()
        return None
    
    def est_vide(self):
        return len(self.elements) == 0
              

Étape 1 : Comprendre les propriétés des structures

Pile (LIFO): Le dernier élément ajouté est le premier retiré. File (FIFO): Le premier élément ajouté est le premier retiré.

Étape 2 : Implémenter les opérations de base

Empiler/dépiler pour la pile, enfiler/défiler pour la file.

Étape 3 : Gérer les cas limites

Vérifier si la structure est vide avant de retirer un élément.

Pile: [1,2,3] → dépilage: 3,2,1 | File: [1,2,3] → défilage: 1,2,3

Réponse finale :

Les piles et files sont des structures de données avec des comportements spécifiques pour l'ajout et le retrait d'éléments.

Règles appliquées :

• LIFO/FIFO : Respecter l'ordre d'entrée/sortie des structures

• Opérations atomiques : Empiler/enfiler et dépiler/défiler

• Sécurité : Vérifier l'état avant les opérations de suppression

5 Analyse de performance

Définition :

Complexité : Mesure de l'efficacité d'un algorithme en fonction de la taille des données.

import time

def tri_bulle(tableau):
    n = len(tableau)
    for i in range(n):
        for j in range(0, n-i-1):
            if tableau[j] > tableau[j+1]:
                tableau[j], tableau[j+1] = tableau[j+1], tableau[j]

def tri_rapide(tableau):
    if len(tableau) <= 1:
        return tableau
    pivot = tableau[len(tableau) // 2]
    gauche = [x for x in tableau if x < pivot]
    milieu = [x for x in tableau if x == pivot]
    droite = [x for x in tableau if x > pivot]
    return tri_rapide(gauche) + milieu + tri_rapide(droite)

# Comparaison de performance
tailles = [100, 500, 1000]
for taille in tailles:
    donnees = list(range(taille, 0, -1))  # Données inversées
    
    # Tri bulle
    start = time.time()
    tri_bulle(donnees.copy())
    temps_bulle = time.time() - start
    
    # Tri rapide
    start = time.time()
    tri_rapide(donnees.copy())
    temps_rapide = time.time() - start
    
    print(f"Taille: {taille}, Bulle: {temps_bulle:.4f}s, Rapide: {temps_rapide:.4f}s")
              

Étape 1 : Identifier les algorithmes à comparer

Tri à bulle (O(n²)) vs tri rapide (O(n log n) en moyenne).

Étape 2 : Créer des jeux de données de différentes tailles

Utiliser des données inversées pour tester le pire cas des algorithmes.

Étape 3 : Mesurer les temps d'exécution

Chronométrer chaque algorithme sur les mêmes données.

Tri rapide: O(n log n) vs Tri bulle: O(n²) → gain exponentiel

Réponse finale :

L'analyse comparative révèle l'impact crucial du choix de l'algorithme sur les performances.

Règles appliquées :

• Complexité théorique : Comparer les ordres de grandeur des algorithmes

• Tests pratiques : Mesurer les temps d'exécution réels

• Conditions équitables : Utiliser les mêmes données pour chaque test

Cours bien détaillé

\text{Efficacité} = f(\text{Algorithme}) \times f(\text{Structure}_{données})

Efficacité combinée

🎯

Objectif : Associer le bon algorithme à la bonne structure de données.

📊

Performance : Optimiser le temps et l'espace de traitement.

🔄

Complexité : Analyser le comportement asymptotique des solutions.

💡

Choix stratégique : Sélectionner les structures adaptées au problème.

💡

Conseil : Choisir la structure de données avant l'algorithme

🔍

Attention : Considérer les opérations les plus fréquentes

⚡

Astuce : Utiliser des structures natives pour des gains de performance

📋

Méthode : Analyser la complexité en temps et en espace

✅

Vérification : Tester avec des jeux de données variés

Associations courantes :

Recherche rapide : Dictionnaire (hash table) + recherche en O(1)
Tri : Liste + tri rapide ou fusion (O(n log n))
Parcours : Arbre + parcours en profondeur ou largeur
Historique : Pile (LIFO) pour annuler/refaire des actions

Structures de données :

Liste : Accès indexé, insertion/suppression au milieu coûteuse
Dictionnaire : Accès par clé en O(1), non ordonné (Python 3.7+)
Ensemble : Éléments uniques, recherche rapide
Arbre binaire : Recherche, insertion, suppression en O(log n) si équilibré

Règles importantes :

Identifier les opérations les plus fréquentes dans votre algorithme
Choisir la structure qui optimise ces opérations
Considérer la complexité en temps et en espace
Tester avec des données réalistes pour valider le choix
Prendre en compte la lisibilité et la maintenance du code

Combiner algorithmes et donnéesExercices corrigés

Combiner algorithmes et données
Exercices corrigés