Évaluation expérimentale | Exercices corrigés

Concepts & Exercices

\(\text{Temps}_{\text{exp}} = f(\text{taille}_{\text{entrée}}, \text{implémentation}, \text{machine})\)

Mesure expérimentale du temps d'exécution

Objectif

Mesurer

Performance

Outils

Chronomètre

Programme

Variables

Taille

Données

🎯

Définition : L'évaluation expérimentale mesure les performances réelles d'un algorithme.

📏

Méthode : Chronométrage de l'exécution sur différentes tailles de données.

📋

Objectifs : Valider la complexité théorique, comparer algorithmes, détecter anomalies.

⚡

Avantages : Résultats concrets, prennent en compte les spécificités matérielles.

💡

Conseil : Effectuez plusieurs mesures et calculez la moyenne pour réduire les variations

🔍

Attention : Les mesures peuvent varier selon la charge système et les optimisations

⚡

Astuce : Utilisez des jeux de données représentatifs et variés

📋

Méthode : Mesurez pour différentes tailles et tracez les courbes de performance

Exercice 1

Mesure du temps d'exécution d'un algorithme linéaire

Exercice 2

Comparaison expérimentale de deux algorithmes

Exercice 3

Tracé de courbes de performance

Exercice 4

Analyse de la variance des mesures

Exercice 5

Validation de la complexité théorique

Corrigé : Exercices 1 à 3

1 Mesure du temps d'exécution

Définition :

Évaluation expérimentale : Mesure empirique du temps d'exécution d'un algorithme.

Chronométrage : Utilisation d'un chronomètre logiciel pour mesurer le temps de calcul.

Méthode de mesure du temps d'exécution :

Enregistrer le temps avant l'exécution de l'algorithme
Exécuter l'algorithme sur un jeu de données donné
Enregistrer le temps après l'exécution
Calculer la différence pour obtenir le temps d'exécution
Répéter plusieurs fois pour réduire les erreurs

Algorithme

Somme tableau

Taille

n = 1000

Temps

0.001s

Étape 1 : Préparation de la mesure

Importer un module de chronométrage (time, timeit, etc.)

Créer un tableau de test de taille n

Étape 2 : Début de la mesure

Enregistrer le temps initial t1


import time
t1 = time.time()
# Exécuter l'algorithme
resultat = somme_tableau(tableau)
t2 = time.time()
temps_execution = t2 - t1

Étape 3 : Fin de la mesure

Calculer la différence de temps

Temps d'exécution = t2 - t1

Étape 4 : Répétition pour précision

Répéter la mesure plusieurs fois

Calculer la moyenne pour réduire les variations

Essai	Temps (s)	Commentaire
1	0.0012	Temps de base
2	0.0009	Meilleure performance
3	0.0011	Moyenne
4	0.0013	Légère variation
Moyenne	0.0011	Résultat final

                // Code Python pour mesurer le temps
                import time
                import random
                
                def somme_tableau(tableau):
                  somme = 0
                  for element in tableau:
                    somme += element
                  return somme
                
                # Création du tableau de test
                n = 1000
                tableau = [random.randint(1, 100) for _ in range(n)]
                
                # Mesure du temps
                t1 = time.time()
                resultat = somme_tableau(tableau)
                t2 = time.time()
                
                temps_execution = t2 - t1
                print(f"Temps d'exécution: {temps_execution:.6f} secondes")
              

Temps = 0.0011s (moyenne sur 4 mesures)

Réponse finale :

Le temps d'exécution de l'algorithme de somme sur un tableau de 1000 éléments est de 0.0011 secondes en moyenne.

Règles appliquées :

• Précision : Répéter les mesures pour réduire les erreurs

• Isolation : Minimiser les interférences extérieures pendant la mesure

• Reproductibilité : Utiliser des données fixes pour comparer les résultats

2 Comparaison expérimentale

Définition :

Comparaison expérimentale : Évaluation comparative des performances de plusieurs algorithmes.

Équité : Les algorithmes doivent être testés dans les mêmes conditions.

Algo 1

Tri par sélection

Algo 2

Tri à bulles

Taille

n = 500

Résultat

Sélection > Bulles

Étape 1 : Préparation des algorithmes

Implémenter les deux algorithmes à comparer

Tri par sélection et tri à bulles

Étape 2 : Création des données de test

Générer un tableau de taille n avec des valeurs aléatoires

Utiliser le même tableau pour les deux algorithmes

Étape 3 : Mesure pour le premier algorithme

Chronométrer le tri par sélection

Temps pour tri_sélection(tableau1) = t1

Étape 4 : Mesure pour le deuxième algorithme

Chronométrer le tri à bulles

Temps pour tri_bulles(tableau2) = t2

Étape 5 : Analyse comparative

Comparer t1 et t2

Identifier l'algorithme le plus performant

Algorithme	Temps (s)	Complexité	Classement
Tri sélection	0.125	O(n²)	1er
Tri bulles	0.185	O(n²)	2e
Tri fusion	0.008	O(n log n)	3e

Sélection

0.125s

Bulles

0.185s

Fusion

0.008s

                // Comparaison des tris
                import time
                import random
                
                def tri_selection(tableau):
                  n = len(tableau)
                  for i in range(n-1):
                    min_idx = i
                    for j in range(i+1, n):
                      if tableau[j] < tableau[min_idx]:
                        min_idx = j
                    tableau[i], tableau[min_idx] = tableau[min_idx], tableau[i]
                
                def tri_bulles(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]
                
                # Données de test
                taille = 500
                donnees_originales = [random.randint(1, 1000) for _ in range(taille)]
                
                # Test du tri par sélection
                tableau_test1 = donnees_originales.copy()
                t1 = time.time()
                tri_selection(tableau_test1)
                temps_selection = time.time() - t1
                
                # Test du tri à bulles
                tableau_test2 = donnees_originales.copy()
                t2 = time.time()
                tri_bulles(tableau_test2)
                temps_bulles = time.time() - t2
                
                print(f"Tri sélection: {temps_selection:.3f}s")
                print(f"Tri bulles: {temps_bulles:.3f}s")
              

Tri sélection = 0.125s vs Tri bulles = 0.185s

Réponse finale :

Le tri par sélection est plus rapide que le tri à bulles pour un tableau de 500 éléments.

Règles appliquées :

• Conditions égales : Même jeu de données pour tous les algorithmes

• Isolation : Réinitialiser les données entre chaque test

• Comparaison : Analyser les différences de performance

3 Tracé de courbes de performance

Définition :

Tracé de courbes : Visualisation graphique de la relation entre la taille des données et le temps d'exécution.

Analyse visuelle : Permet d'observer la tendance et de valider la complexité théorique.

Variable

Taille (n)

Mesure

Temps (s)

Courbe

n vs t(n)

Étape 1 : Préparation des mesures

Choisir différentes tailles de données : n = 100, 200, 500, 1000, 2000

Pour chaque taille, mesurer le temps d'exécution de l'algorithme

Étape 2 : Collecte des données

Effectuer les mesures et les enregistrer dans un tableau

Assurer la précision en répétant les mesures

Étape 3 : Construction de la courbe

Tracer le graphique avec la taille en abscisse et le temps en ordonnée

Identifier la tendance (linéaire, quadratique, etc.)

Étape 4 : Analyse de la courbe

Comparer la courbe expérimentale avec la complexité théorique

Valider ou infirmer les hypothèses sur la complexité

Taille (n)	Temps (ms)	T/n (ms)	T/n² (ms)
100	0.5	0.005	0.00005
200	2.0	0.010	0.00005
500	12.5	0.025	0.00005
1000	50.0	0.050	0.00005
2000	200.0	0.100	0.00005

n=100

0.5ms

n=200

2.0ms

n=500

12.5ms

n=1000

50.0ms

n=2000

200.0ms

                // Génération de données pour la courbe
                import time
                import random
                import matplotlib.pyplot as plt
                
                def algorithme_test(tableau):
                  # Exemple: algorithme quadratique
                  n = len(tableau)
                  for i in range(n):
                    for j in range(n):
                      if i == j:
                        continue
                
                tailles = [100, 200, 500, 1000, 2000]
                temps_mesures = []
                
                for taille in tailles:
                  tableau = [random.randint(1, 1000) for _ in range(taille)]
                  
                  t1 = time.time()
                  algorithme_test(tableau)
                  t2 = time.time()
                  
                  temps_mesures.append((t2 - t1) * 1000)  # Convertir en ms
                
                # Affichage des résultats
                for i in range(len(tailles)):
                  print(f"Taille: {tailles[i]}, Temps: {temps_mesures[i]:.2f}ms")
                
                # Tracer la courbe (simulation)
                # plt.plot(tailles, temps_mesures)
                # plt.xlabel('Taille de l\'entrée')
                # plt.ylabel('Temps d\'exécution (ms)')
                # plt.title('Courbe de performance')
                # plt.show()
              

Courbe = Temps vs Taille (validation O(n²))

Réponse finale :

La courbe montre une croissance quadratique, confirmant la complexité O(n²) de l'algorithme.

Règles appliquées :

• Échelle appropriée : Choisir des tailles suffisamment variées pour observer la tendance

• Visualisation : Les graphiques facilitent l'analyse des tendances

• Validation : Comparer avec la complexité théorique pour valider l'analyse

Corrigé : Exercices 4 à 5

4 Analyse de la variance

Définition :

Analyse de la variance : Étude des variations dans les mesures expérimentales.

Fiabilité : Comprendre les sources de variation pour améliorer la précision des mesures.

Mesures

[0.0012, 0.0009, 0.0011, 0.0013]

Moyenne

0.0011

Écart-type

0.00016

Étape 1 : Collecte des mesures répétées

Exécuter l'algorithme plusieurs fois avec les mêmes données

Enregistrer chaque mesure de temps

Étape 2 : Calcul des statistiques

Moyenne : μ = (Σxi) / n

Écart-type : σ = √(Σ(xi - μ)² / n)

Intervalle de confiance pour évaluer la précision

Étape 3 : Identification des sources de variation

Changements dans l'état du système

Autres processus en cours d'exécution

Cache CPU, gestion de la mémoire

Étape 4 : Amélioration de la précision

Augmenter le nombre de mesures

Exécuter dans un environnement contrôlé

Utiliser des outils spécialisés

Mesure	Temps (s)	Écart à la moyenne	Écart²
1	0.0012	+0.0001	0.00000001
2	0.0009	-0.0002	0.00000004
3	0.0011	0.0000	0.00000000
4	0.0013	+0.0002	0.00000004
Moyenne	0.0011	-	0.00000003
Écart-type	0.00017	-	-

\(\sigma = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(x_i - \mu)^2}\)

Formule de l'écart-type

                // Analyse statistique des mesures
                import statistics
                import time
                import random
                
                def mesurer_temps(algorithme, tableau, repetitions=5):
                  mesures = []
                  for _ in range(repetitions):
                    copie = tableau.copy()
                    t1 = time.perf_counter()
                    algorithme(copie)
                    t2 = time.perf_counter()
                    mesures.append(t2 - t1)
                  return mesures
                
                def analyser_variance(mesures):
                  moyenne = statistics.mean(mesures)
                  ecart_type = statistics.stdev(mesures) if len(mesures) > 1 else 0
                  variance = statistics.variance(mesures) if len(mesures) > 1 else 0
                  
                  print(f"Moyenne: {moyenne:.6f}s")
                  print(f"Écart-type: {ecart_type:.6f}s")
                  print(f"Variation: {(ecart_type/moyenne)*100:.2f}%")
                  
                  return moyenne, ecart_type
                
                # Exemple d'utilisation
                tableau_test = [random.randint(1, 100) for _ in range(1000)]
                mesures = mesurer_temps(lambda x: sorted(x), tableau_test)
                moyenne, ecart_type = analyser_variance(mesures)
              

Écart-type = 0.00017s (1.5% de la moyenne)

Réponse finale :

La variance des mesures est faible (1.5% de la moyenne), indiquant une bonne précision.

Règles appliquées :

• Statistiques : Utiliser la moyenne et l'écart-type pour évaluer la précision

• Fiabilité : Un faible écart-type indique des mesures fiables

• Amélioration : Augmenter le nombre de mesures pour réduire la variance

5 Validation de la complexité

Définition :

Validation expérimentale : Confirmation de la complexité théorique par des mesures réelles.

Corrélation : Comparaison entre la complexité prédite et les résultats expérimentaux.

Théorie

O(n²)

Expérience

O(n²)

Validation

Confirmée

Étape 1 : Hypothèse de complexité

Basé sur l'analyse théorique, on suppose une complexité O(n²)

Pour un algorithme de tri par sélection

Étape 2 : Mesures pour différentes tailles

Effectuer des mesures pour n = 100, 200, 500, 1000, 2000

Calculer le ratio T(n) / n² pour chaque mesure

Étape 3 : Analyse des ratios

Si la complexité est O(n²), les ratios T(n) / n² devraient être constants

Observation de la tendance des ratios

Étape 4 : Conclusion

Si les ratios sont approximativement constants, la complexité O(n²) est validée

Sinon, il faut réviser l'hypothèse de complexité

Taille (n)	Temps (s)	T/n	T/n²	T/n³
100	0.005	0.00005	0.0000005	0.000000005
200	0.020	0.00010	0.0000005	0.000000003
500	0.125	0.00025	0.0000005	0.000000001
1000	0.500	0.00050	0.0000005	0.0000000005
2000	2.000	0.00100	0.0000005	0.00000000025

T/n

T/n²

T/n³

                // Validation de la complexité
                import time
                import random
                
                def tri_selection(tableau):
                  n = len(tableau)
                  operations = 0
                  for i in range(n-1):
                    min_idx = i
                    for j in range(i+1, n):
                      operations += 1  # Compter les comparaisons
                      if tableau[j] < tableau[min_idx]:
                        min_idx = j
                    tableau[i], tableau[min_idx] = tableau[min_idx], tableau[i]
                  return operations
                
                tailles = [100, 200, 500, 1000]
                resultats = []
                
                for taille in tailles:
                  tableau = [random.randint(1, 1000) for _ in range(taille)]
                  
                  # Mesure du temps
                  t1 = time.time()
                  ops = tri_selection(tableau.copy())
                  t2 = time.time()
                  
                  temps = t2 - t1
                  theorique = (taille * (taille - 1)) / 2  # Pour tri sélection
                  
                  resultats.append({
                    'taille': taille,
                    'temps': temps,
                    'theorique': theorique,
                    'ratio_temps': temps / (taille * taille),
                    'ratio_ops': ops / theorique
                  })
                
                # Affichage des résultats
                print("Validation de la complexité O(n²):")
                for r in resultats:
                  print(f"n={r['taille']}: temps={r['temps']:.4f}s, "
                        f"ratio_t={r['ratio_temps']:.6f}, ratio_ops={r['ratio_ops']:.3f}")
              

Ratio T(n)/n² ≈ constant → O(n²) validée

Réponse finale :

Les ratios T(n)/n² sont constants (~0.0000005), confirmant la complexité O(n²).

Règles appliquées :

• Validation : Comparer les mesures expérimentales avec la théorie

• Ratio constant : Pour une complexité O(f(n)), T(n)/f(n) devrait être constant

• Confirmation : Des ratios stables valident la complexité supposée

Cours bien détaillé

\(\lim_{n \to \infty} \frac{T_{\text{exp}}(n)}{T_{\text{théorique}}(n)} = c\)

Validation expérimentale de la complexité

🎯

Définition : L'évaluation expérimentale mesure les performances réelles d'un algorithme.

📏

Méthode : Chronométrage de l'exécution sur différentes tailles de données.

📋

Objectifs : Valider la complexité théorique, comparer algorithmes, détecter anomalies.

⚡

Avantages : Résultats concrets, prennent en compte les spécificités matérielles.

💡

Conseil : Effectuez plusieurs mesures et calculez la moyenne pour réduire les variations

🔍

Attention : Les mesures peuvent varier selon la charge système et les optimisations

⚡

Astuce : Utilisez des jeux de données représentatifs et variés

📋

Méthode : Mesurez pour différentes tailles et tracez les courbes de performance

✅

Vérification : Comparez les résultats expérimentaux avec la complexité théorique

🔄

Amélioration : Répétez les tests dans différentes conditions pour valider les résultats

Étapes de l'évaluation expérimentale :

Préparation : Définir les algorithmes à tester et les jeux de données
Mesure : Chronométrer l'exécution des algorithmes
Répétition : Effectuer plusieurs mesures pour améliorer la précision
Enregistrement : Sauvegarder toutes les mesures pour analyse
Visualisation : Tracer des graphiques pour observer les tendances
Analyse : Comparer avec la complexité théorique et valider les résultats

Règles importantes :

L'évaluation expérimentale complète l'analyse théorique mais ne la remplace pas
Les mesures peuvent être influencées par des facteurs matériels et logiciels
Plusieurs mesures sont nécessaires pour obtenir des résultats fiables
La validation de la complexité se fait par l'observation de tendances sur plusieurs tailles

Avantages

Réaliste

Résultats concrets

Limites

Variables

Environnement dépendant

Validité

Complémentaire

À la théorie

\(T_{\text{exp}}(n) \approx c \cdot f(n)\)

Relation entre mesure expérimentale et complexité

Points clés à retenir :

• L'évaluation expérimentale permet de mesurer les performances réelles des algorithmes
• Elle complète l'analyse théorique en fournissant des résultats concrets
• La méthode consiste à chronométrer l'exécution sur différentes tailles de données
• Plusieurs mesures sont nécessaires pour assurer la fiabilité des résultats
• Les courbes de performance aident à visualiser et valider les complexités théoriques

Évaluation expérimentaleExercices corrigés

Évaluation expérimentale
Exercices corrigés