Le coût algorithmique

👨‍🏫 Introduction

Objectif

Ces travaux pratiques ont pour objectif la mesure du coût algorithmique de trois algorithmes de recherche.

Important

Un compte rendu sera à réaliser dans le cadre de ces travaux pratiques et à rendre en fin de séance :

• Envoyer obligatoirement votre compte rendu au format PDF
• Effectuer le rendu uniquement depuis l'application Exercices de l'ENT, via l'exercice intitulé [9TP1] Coût algorithmique

Préparation

Afin de garder organisées les productions réalisées en TP, mettre à jour l'arborescence NSI selon l'ordinateur utilisé :

💻 Ordinateur portable

1. Lancer l'explorateur de fichiers
2. Se rendre dans le dossier Documents
3. Créer le dossier NSI s'il n'existe pas
4. Dans le dossier NSI, créer le dossier chapitre_09
5. Dans le dossier chapitre_09, créer le dossier tp1_cout_algorithmique

🖥 Ordinateur fixe des salles informatiques

1. Depuis le bureau, cliquer sur l'icône intitulée Zone personnelle
2. Créer le dossier NSI s'il n'existe pas
3. Dans le dossier NSI, créer le dossier chapitre_09
4. Dans le dossier chapitre_09, créer le dossier tp1_cout_algorithmique

Téléchargement des fichiers

Pour effectuer ce TP, il est nécessaire de télécharger certains fichiers :

1. Télécharger le fichier ZIP contenant les fichiers du TP : 📦 télécharger
2. Ouvrir le fichier ZIP
3. Copier/coller tous les fichiers dans le dossier NSI\chapitre_09\tp1_cout_algorithmique

🔎 Partie 1 - Recherche dans un tableau

Étape 1 - Implémentation

1. Ouvrir le fichier partie1_recherche.py
2. Implémenter la fonction recherche
3. Lancer les tests pour vérifier le bon fonctionnement de la recherche

💡 Algorithme de recherche

Entrées : un tableau nommé "tableau" et la valeur recherchée nommée "valeur"
Sortie : l'indice de la valeur recherchée ou -1 sinon

Début
|  pour i compris entre 0 et la taille du tableau - 1
|   |
|   |  Si l'élément d'indice i = valeur alors
|   |   |  renvoyer i
|   |  Fin si
|   |
|  fin pour
|
|  renvoyer -1
Fin

Étape 2 - Mesures

Pour évaluer le coût en temps, il est nécessaire de compter le nombre d'opérations élémentaires. Nous nous limiterons ici aux comparaisons. En utilisant le module compteur, modifier la fonction rechercher de façon à compter le nombre de comparaisons.

1. Importer le module compteur
2. À l'intérieur de la fonction recherche, initialiser le compteur à zéro en appelant la fonction compteur.initialiser
3. À l'intérieur de la fonction recherche, compter le nombre de comparaisons en appelant la fonction compteur.incrementer. Attention à placer cet appel au bon endroit.
4. À l'extérieur de la fonction recherche, vérifier que le compte soit correct en vérifiant la valeur de retour de compteur.total

>>> recherche([1,2,3,4], 99)
-1
>>> compteur.total()
4

Étape 3 - Nombre d'opérations moyen

Nous souhaitons évaluer le coût en temps moyen de l'algorithme de recherche dans un tableau de taille n. Pour cela, il nous faut écrire une fonction chargée d'exécuter plusieurs fois l'algorithme afin d'obtenir une moyenne du nombre d'opérations. Vous trouverez ci-après l'algorithme de cette fonction.

💡 Algorithme de calcul du nombre d'opérations moyen

Entrées : taille n du tableau dans lequel effectuer la recherche
Sorties : nombre d'opérations moyen pour 1000 recherches

Début
 |  operations ← 0
 |  tableau ← génération d'un tableau de taille n (utils.generer_tableau(...))
 |
 |  répéter 1000 fois
 |   |  valeur ← nombre aléatoire entre 1 et n inclus
 |   |  recherche(tableau, valeur)
 |   |  opérations ← opérations + nombre d'opérations de la recherche (compteur.total(...))
 |  fin répéter
 |
 |  renvoyer opérations // 1000
Fin

• Implémenter la fonction mesurer_recherche en suivant l'algorithme
• Pour générer un tableau de taille n, importer le module utils et appeler la fonction generer_tableau

Étape 4 - Relevé du nombre d'opérations

Appeler la fonction mesurer_recherche de manière à obtenir le nombre d'opérations moyen pour les valeurs de n suivantes : 10, 20, 50, 100, 1000, 5000. Vous intègrerez vos réponses dans votre compte rendu sous forme d'un tableau comparable à celui-ci :

Taille n du tableau	10	20	50	100	1000	5000
Nb. opérations moy.

Étape 5 - Tracé de la courbe

Nous aimerions tracer une courbe à partir des données obtenues afin de pouvoir apprécier l'évolution du nombre d'opérations moyen en fonction de la taille n du tableau.

1. Ouvrir le fichier courbe.py
2. Modifier les données des tableaux donnees_x et donnees_y afin de les faire correspondre à vos relevés
3. Lancer le tracé de la courbe et l'intégrer au compte rendu

🔎 Partie 2 - Recherche dans une matrice carrée

Étape 1 - Implémentation

1. Ouvrir le fichier partie2_recherche_matrice.py
2. Implémenter la fonction recherche_matrice
3. Lancer les tests pour vérifier le bon fonctionnement de la recherche

💡 Algorithme de recherche dans une matrice

Entrées : un tableau à deux dimensions nommé "matrice" et la valeur recherchée nommée "valeur"
Sortie : la ligne et la colonne de la valeur recherchée ou -1 sinon

Début
|  pour ligne compris entre 0 et la taille du tableau - 1
|   |  pour colonne compris en 0 la taille de tableau[ligne] - 1
|   |   |
|   |   |  Si l'élément d'indices (ligne, colonne) = valeur alors
|   |   |   |  renvoyer (ligne, colonne)
|   |   |  Fin si
|   |   |
|   |  fin pour
|  fin pour
|
|  renvoyer -1
Fin

Étape 2 - Mesures

Pour évaluer le coût en temps, il est nécessaire de compter le nombre d'opérations élémentaires. Nous nous limiterons ici aux comparaisons. En utilisant le module compteur, modifier la fonction rechercher de façon à compter le nombre de comparaisons.

1. Importer le module compteur
2. À l'intérieur de la fonction recherche_matrice, initialiser le compteur à zéro en appelant la fonction compteur.initialiser
3. À l'intérieur de la fonction recherche_matrice, compter le nombre de comparaisons en appelant la fonction compteur.incrementer. Attention à placer cet appel au bon endroit.
4. À l'extérieur de la fonction recherche_matrice, vérifier que le compte soit correct en vérifiant la valeur de retour de compteur.total

>>> recherche([[1,2,3],[4,5,6]}, 99)
-1
>>> compteur.total()
6

Étape 3 - Nombre d'opérations moyen

Nous souhaitons évaluer le coût en temps moyen de l'algorithme de recherche dans une matrice carrée de taille n. Pour cela, il nous faut écrire une fonction chargée d'exécuter plusieurs fois l'algorithme afin d'obtenir une moyenne du nombre d'opérations. Vous trouverez ci-après l'algorithme de cette fonction.

💡 Algorithme de calcul du nombre d'opérations moyen

```
Entrées : taille n de la matrice dans laquelle effectuer la recherche
Sorties : nombre d'opérations moyen pour 1000 recherches

Début
|  operations ← 0
|  tableau ← génération d'une matrice carrée de taille n (utils.generer_matrice_carree(...))
|
|  répéter 1000 fois
|   |  valeur ← nombre aléatoire entre 1 et n² inclus
|   |  recherche_matrice(tableau, valeur)
|   |  opérations ← opérations + nombre d'opérations de la recherche (compteur.total(...))
|  fin répéter
|
|  renvoyer opérations // 1000
Fin
```

• Implémenter la fonction mesurer_recherche_matrice en suivant l'algorithme
• Pour générer une matrice carrée de taille n, importer le module utils et appeler la fonction generer_matrice_carree

Étape 4 - Relevé du nombre d'opérations et courbe

Appeler la fonction mesurer_recherche_matrice de manière à obtenir le nombre d'opérations moyen pour les valeurs de n suivantes : 10, 20, 30, 50, 100, 200. Intégrer les réponses au compte rendu sous forme d'un tableau comparable au tableau ci-après ainsi que la courbe correspondante.

Taille n de la matrice carrée	10	20	30	50	100	200
Nb. opérations moy.

🔎 Partie 3 - La recherche dichotomique

Étape 1 - Implémentation

1. Ouvrir le fichier partie3_recherche_dichotomique.py
2. Implémenter la fonction recherche_dichotomique
3. Lancer les tests pour vérifier le bon fonctionnement de la recherche

Algorithme de recherche dichotomique

Entrées : un tableau non vide et trié nommé tableau et la valeur recherchée nommée element
Sortie : l'indice de l'élément recherché s'il a été trouvé, -1 sinon

Début
|  indice_debut ← 0
|  indice_fin   ← taille(tableau) − 1
|
|  tant que indice_debut <= indice_fin faire
|   |  indice_milieu ← (indice_debut + indice_fin) // 2
|   |
|   |  si tableau[indice_milieu] = element alors
|   |   |  renvoyer indice_milieu
|   |  sinon si tableau[indice_milieu] > element alors
|   |   |  indice_fin ← indice_milieu − 1
|   |  sinon
|   |   |  indice_debut ← indice_milieu + 1
|   |  fin si
|   |
|  fin tant que
|
|  renvoyer -1
Fin

Étape 2 - Mesures

Pour évaluer le coût en temps, il est nécessaire de compter le nombre d'opérations élémentaires. Nous nous limiterons ici aux comparaisons. En utilisant le module compteur, modifier la fonction rechercher de façon à compter le nombre de comparaisons.

1. Importer le module compteur
2. À l'intérieur de la fonction recherche_dichotomique, initialiser le compteur à zéro en appelant la fonction compteur.initialiser
3. À l'intérieur de la fonction recherche_dichotomique, compter le nombre de comparaisons en appelant la fonction compteur.incrementer. Attention à placer cet appel aux bons endroits.
4. À l'extérieur de la fonction recherche_dichotomique, vérifier que le compte soit correct en vérifiant la valeur de retour de compteur.total

Étape 3 - Nombre d'opérations moyen

Nous souhaitons évaluer le coût en temps moyen de l'algorithme de recherche dans un tableau trié de taille n. Pour cela, il nous faut écrire une fonction chargée d'exécuter plusieurs fois l'algorithme afin d'obtenir une moyenne du nombre d'opérations. Vous trouverez ci-après l'algorithme de cette fonction.

💡 Algorithme de calcul du nombre d'opérations moyen

```
Entrées : taille n du tableau trié dans lequel effectuer la recherche
Sorties : nombre d'opérations moyen pour 1000 recherches

Début
|  operations ← 0
|  tableau ← génération d'un tableau trié de taille n (utils.generer_tableau_trie(...))
|
|  répéter 1000 fois
|   |  valeur ← nombre aléatoire entre 1 et n inclus
|   |  recherche_dichotomique(tableau, valeur)
|   |  opérations ← opérations + nombre d'opérations de la recherche (compteur.total(...))
|  fin répéter
|
|  renvoyer opérations // 1000
Fin
```

• Implémenter la fonction mesurer_recherche_dichotomique en suivant l'algorithme
• Pour générer une matrice carrée de taille n, importer le module utils et appeler la fonction generer_tableau_trie

Étape 4 - Relevé du nombre d'opérations et courbe

Appeler la fonction mesurer_recherche_matrice de manière à obtenir le nombre d'opérations moyen pour les valeurs de n suivantes : 100, 500, 2000, 10000, 50000, 200000. Intégrer les réponses au compte rendu sous forme d'un tableau comparable au tableau ci-après ainsi que la courbe correspondante.

Taille n du tableau trié	100	500	2000	10000	50000	200000
Nb. opérations moy.