Évaluer la solution | Exercices corrigés

Concepts & Exercices

Efficacité = \frac{Résultats}{Temps + Ressources}

Principe fondamental d'évaluation

Complexité O(1)

Constante

Temps constant quelle que soit la taille

Complexité O(n)

Linéaire

Temps proportionnel à la taille

Complexité O(n²)

Quadratique

Temps augmente exponentiellement

Critères d'évaluation :

Correctitude : La solution résout-elle le problème ?
Efficacité : Complexité temporelle et spatiale
Clarté : Lisibilité et maintenabilité du code
Robustesse : Gestion des cas limites et erreurs

Exercice 1

Évaluer la complexité d'un algorithme de recherche

Exercice 2

Valider un programme de tri par sélection

Exercice 3

Tester un algorithme de recherche dichotomique

Exercice 4

Comparer deux algorithmes de tri

Exercice 5

Optimiser un programme de calcul de factorielle

Corrigé : Exercices 1 à 3

1 Complexité de recherche

Définition :

Problème : Évaluer la complexité d'un algorithme de recherche linéaire

Méthode d'évaluation :

Identifier les opérations élémentaires
Compter le nombre d'opérations en fonction de la taille
Déterminer la classe de complexité
Comparer avec d'autres solutions possibles

Initialisation

Boucle de parcours

Comparaison

Retour du résultat

Étape 1 : Analyse de l'algorithme

FONCTION RechercheLineaire(tableau, element) : Entier
  POUR i DE 0 A LONGUEUR(tableau) - 1 FAIRE
    SI tableau[i] = element ALORS
      RETOURNER i
    FIN SI
  FIN POUR
  RETOURNER -1
FIN

Étape 2 : Comptage des opérations

• Initialisation de i : 1 opération
• Comparaison de i avec la taille : n+1 opérations
• Incrémentation de i : n opérations
• Comparaison tableau[i] = element : n opérations (au maximum)
• Retour de la valeur : 1 opération (au maximum)

Étape 3 : Calcul de la complexité

Opérations totales : 1 + (n+1) + n + n = 3n + 2
Donc complexité : O(n) - Linéaire

Complexité : O(n) - Linéaire

Évaluation :

Algorithme correct mais inefficace pour de grandes données. Meilleure complexité possible : O(log n) avec recherche dichotomique sur tableau trié.

Règles d'évaluation :

• Compter les opérations dominantes : Boucles, comparaisons

• Identifier le pire cas : Situation où l'algorithme met le plus de temps

• Simplifier l'expression : Garder le terme dominant

2 Validation du tri par sélection

Définition :

Problème : Valider un programme de tri par sélection avec des tests

Test sur tableau vide

Test sur tableau trié

Test sur tableau inversé

Test sur valeurs dupliquées

Étape 1 : Algorithme de tri par sélection

FONCTION TriSelection(tableau) : Tableau
  POUR i DE 0 A LONGUEUR(tableau) - 2 FAIRE
    min_index ← i
    POUR j DE i+1 A LONGUEUR(tableau) - 1 FAIRE
      SI tableau[j] < tableau[min_index] ALORS
        min_index ← j
      FIN SI
    FIN POUR
    ECHANGER tableau[i] ET tableau[min_index]
  FIN POUR
  RETOURNER tableau
FIN

Étape 2 : Tests de validation

• Test 1 : [] → [] (tableau vide)
• Test 2 : [1, 2, 3] → [1, 2, 3] (déjà trié)
• Test 3 : [3, 2, 1] → [1, 2, 3] (inversé)
• Test 4 : [2, 1, 2, 3, 1] → [1, 1, 2, 2, 3] (duplicata)

Étape 3 : Évaluation de la robustesse

• Gestion des tableaux vides : OK
• Gestion des doublons : OK
• Gestion des tableaux déjà triés : OK (pas de modification inutile)
• Complexité : O(n²) - Acceptable pour petits tableaux

Programme validé pour divers cas d'utilisation

Évaluation :

Algorithme correct mais complexité quadratique. Bonne robustesse mais inefficace pour de grandes données.

Règles de validation :

• Tester les cas limites : Vide, singleton, valeurs extrêmes

• Tester les cas normaux : Données typiques

• Tester les cas exceptionnels : Erreurs possibles

3 Test de recherche dichotomique

Définition :

Problème : Tester un algorithme de recherche dichotomique

Complexité_{dichotomique} = O(\log n)

Complexité_{linéaire} = O(n)

Étape 1 : Algorithme de recherche dichotomique

FONCTION RechercheDichotomique(tableau, element) : Entier
  gauche ← 0
  droite ← LONGUEUR(tableau) - 1
  
  TANT QUE gauche ≤ droite FAIRE
    milieu ← (gauche + droite) DIV 2
    SI tableau[milieu] = element ALORS
      RETOURNER milieu
    SINON SI tableau[milieu] < element ALORS
      gauche ← milieu + 1
    SINON
      droite ← milieu - 1
    FIN SI
  FIN TANT QUE
  
  RETOURNER -1
FIN

Étape 2 : Tests complets

• Test 1 : [1, 3, 5, 7, 9], 5 → 2 (élément présent)
• Test 2 : [1, 3, 5, 7, 9], 4 → -1 (élément absent)
• Test 3 : [5], 5 → 0 (singleton)
• Test 4 : [], 5 → -1 (tableau vide)

Étape 3 : Analyse comparative

Pour un tableau de 1000 éléments :
• Recherche linéaire : jusqu'à 1000 comparaisons
• Recherche dichotomique : maximum 10 comparaisons (log₂(1000) ≈ 10)

Complexité : O(log n) - Logarithmique

Évaluation :

Beaucoup plus efficace que la recherche linéaire (O(log n) vs O(n)), mais nécessite un tableau trié.

Règles d'optimisation :

• Utiliser la structure des données : Triez si possible

• Choisir l'algorithme adapté : Selon la taille et la structure

• Tester les performances : Comparer avec d'autres solutions

Corrigé : Exercices 4 à 5

4 Comparaison d'algorithmes de tri

Définition :

Problème : Comparer les tris par insertion et fusion

Tri par insertion

O(n²) au pire cas

Simple mais lent pour grands tableaux

Tri fusion

O(n log n) toujours

Plus complexe mais plus fiable

Étape 1 : Tri par insertion

FONCTION TriInsertion(tableau) : Tableau
  POUR i DE 1 A LONGUEUR(tableau) - 1 FAIRE
    cle ← tableau[i]
    j ← i - 1
    TANT QUE j ≥ 0 ET tableau[j] > cle FAIRE
      tableau[j + 1] ← tableau[j]
      j ← j - 1
    FIN TANT QUE
    tableau[j + 1] ← cle
  FIN POUR
  RETOURNER tableau
FIN

Étape 2 : Tri fusion

FONCTION Fusion(gauche, droite) : Tableau
  resultat ← []
  i ← 0
  j ← 0
  
  TANT QUE i < LONGUEUR(gauche) ET j < LONGUEUR(droite) FAIRE
    SI gauche[i] ≤ droite[j] ALORS
      AJOUTER resultat, gauche[i]
      i ← i + 1
    SINON
      AJOUTER resultat, droite[j]
      j ← j + 1
    FIN SI
  FIN TANT QUE
  
  // Ajouter les éléments restants
  TANT QUE i < LONGUEUR(gauche) FAIRE
    AJOUTER resultat, gauche[i]
    i ← i + 1
  FIN TANT QUE
  
  TANT QUE j < LONGUEUR(droite) FAIRE
    AJOUTER resultat, droite[j]
    j ← j + 1
  FIN TANT QUE
  
  RETOURNER resultat
FIN

FONCTION TriFusion(tableau) : Tableau
  SI LONGUEUR(tableau) ≤ 1 ALORS
    RETOURNER tableau
  FIN SI
  
  milieu ← LONGUEUR(tableau) DIV 2
  gauche ← SOUSTABLEAU(tableau, 0, milieu)
  droite ← SOUSTABLEAU(tableau, milieu, LONGUEUR(tableau))
  
  gauche_trie ← TriFusion(gauche)
  droite_trie ← TriFusion(droite)
  
  RETOURNER Fusion(gauche_trie, droite_trie)
FIN

Étape 3 : Comparaison des performances

Aspect	Tri insertion	Tri fusion
Complexité moyenne	O(n²)	O(n log n)
Complexité pire cas	O(n²)	O(n log n)
Stabilité	Stable	Stable
Complexité spatiale	O(1)	O(n)
Facilité d'implémentation	Simple	Complexe

Choix dépendant du contexte : performance vs simplicité

Évaluation :

Tri fusion meilleur pour grandes données, tri insertion plus simple pour petits tableaux.

Règles de comparaison :

• Évaluer selon le contexte : Taille des données, contraintes mémoire

• Considérer plusieurs critères : Temps, espace, stabilité, complexité

• Tester avec des jeux de données réalistes : Simuler conditions réelles

5 Optimisation de factorielle

Définition :

Problème : Optimiser un programme de calcul de factorielle

Version récursive naïve

Version itérative

Version avec mémorisation

Validation finale

Étape 1 : Version récursive (non optimisée)

FONCTION FactorielleRecursive(n) : Entier
  SI n = 0 OU n = 1 ALORS
    RETOURNER 1
  SINON
    RETOURNER n * FactorielleRecursive(n - 1)
  FIN SI
FIN

Complexité : O(n), Espace : O(n) à cause de la pile d'appels

Étape 2 : Version itérative (optimisée)

FONCTION FactorielleIterative(n) : Entier
  resultat ← 1
  POUR i DE 2 A n FAIRE
    resultat ← resultat * i
  FIN POUR
  RETOURNER resultat
FIN

Complexité : O(n), Espace : O(1) - Beaucoup plus efficace

Étape 3 : Gestion des cas limites

• Cas n < 0 : Retourner erreur ou 0
• Cas n = 0 ou n = 1 : Retourner 1
• Cas n très grand : Risque de dépassement de capacité

Étape 4 : Version finale avec sécurité

FONCTION Factorielle(n) : Entier
  SI n < 0 ALORS
    ERREUR "Factorielle non définie pour négatif"
    RETOURNER -1
  FIN SI
  
  resultat ← 1
  POUR i DE 2 A n FAIRE
    resultat ← resultat * i
  FIN POUR
  
  RETOURNER resultat
FIN

Version itérative : O(n) temps, O(1) espace

Évaluation :

Version itérative plus efficace que récursive. Même complexité mais meilleure utilisation de la mémoire.

Règles d'optimisation :

• Éviter la récursion si possible : Risque de débordement de pile

• Minimiser l'utilisation de la mémoire : Privilégier les versions itératives

• Gérer les cas limites : Assurer la robustesse du programme

Cours bien détaillé

Efficacité_{solution} = \frac{Correctitude × Robustesse}{Complexité_{temporelle} + Complexité_{spatiale}}

Mesure globale d'efficacité

🎯

Correctitude : La solution produit-elle les bons résultats ?

⚡

Efficacité : Complexité temporelle et spatiale.

🛡️

Robustesse : Gestion des erreurs et cas limites.

🧩

Clarté : Lisibilité et maintenabilité du code.

💡

Conseil : Toujours tester avec des jeux de données variés

🔍

Attention : Ne pas négliger les cas limites

⚡

Astuce : Comparer avec des algorithmes standards

📋

Méthode : Documenter les résultats des tests

✅

Vérification : Valider les hypothèses de départ

Méthodes d'évaluation :

Analyse de complexité : Compter les opérations élémentaires
Tests unitaires : Vérifier chaque fonction individuellement
Tests fonctionnels : Vérifier le comportement global
Profiling : Mesurer les performances réelles

Règles importantes :

La complexité théorique ne reflète pas toujours les performances réelles
Un algorithme optimal en temps peut utiliser trop de mémoire
La lisibilité du code influence la maintenabilité
Les tests doivent couvrir les cas normaux et les exceptions

Points clés à retenir :

Équilibre : Chercher le bon compromis entre efficacité, lisibilité et robustesse
Contexte : Adapter l'évaluation au contexte d'utilisation
Mesure objective : Utiliser des critères mesurables pour comparer les solutions
Amélioration continue : Réévaluer régulièrement les solutions existantes

Évaluer la solutionExercices corrigés

Évaluer la solution
Exercices corrigés