Séquence sur la complexité et performances d’algorithmes
Type de ressource : Activité d’introduction : travaux pratiques de mise en évidence. Deux synthèses de cours
Public : Élèves de première spécialité NSI.
Parties du B.O. travaillées : Programme de 1e NSI : Thème Algorithmique : Quelques algorithmes classiques sont étudiés. L’étude de leurs coûts respectifs prend tout son sens dans le cas de données nombreuses, qui peuvent être préférentiellement des données ouvertes.
- Parcours séquentiel d’un tableau : On montre que le coût est linéaire
- Tris par insertion, par sélection : On montre que leur coût est quadratique dans le pire des cas.
Autres savoir-faires sollicités : Lire, comprendre et utiliser un programme codé en python pour comparer la performance de deux algorithmes de recherche. Un critère de comparaison de performance deux algorithmes étant choisis, analyser et interpréter les mesures relevées.
Prérequis et place dans la progression annuelle : Séquence à traiter après les éléments suivants :
- Constructions élémentaires
- Tableaux indexés
- Parcours séquentiels (sauf coût)
- Recherche dichotomique dans un tableau trié
- Tri par insertion, par sélection (sauf coût)
Domaine : Algorithmique, évaluation de la complexité des algorithmes.
Mots clés : algorithmes, complexité, recherche séquentielle, recherche dichotomique, coût linéaire, coût logarithmique.
Objectifs pédagogiques
Exécuter un algorithme donné :
- Sensibiliser les élèves à la différence de performances entre deux algorithmes satisfaisant la même demande fonctionnelle (recherche, tri, etc.).
- Donner des notions de vocabulaire liées au coût d’un algorithme : complexité (spatiale, temporelle), notation de Landau O(f(n))
- Donner des grands types de complexités (temps constant, linéaire, logarithmique, quadratique), sur des exemples et sur des algorithmes vus au programme.
Galerie
Exemples de mise en oeuvre :
Scénario 1
Du côté de l’enseignant :
L’enseignant manipule, exécute les programmes de l’activité d’introduction.
L’enseignant interpelle les élèves sur les temps de traitement relevés.
L’enseignant anime les échanges avec les élèves sur le bilan de l’activité et sur le cours.
Du côté de l’élève :
Les élèves relèvent les temps de traitement et complètent le tableau.
Les élèves observent et commentent les relevés.
Les élèves interagissent avec l’enseignant et complètent le cours.
Scénario 2
Du côté de l’enseignant :
L’enseignant fournit les programmes et l’activité d’introduction.
L’enseignant anime et fait la synthèse de l’activité sur la base des travaux et observations des élèves.
L’enseignant fait la synthèse de cours sur la complexité.
Du côté de l’élève :
Les élèves exécutent les programmes et complètent l’activité hors classe
Les élèves proposent leurs observations lors du retour en classe
Les élèves suivent la synthèse de cours et posent des questions
Les avantages
- L’activité et la trace écrite rendent la complexité plus concrète en s’appuyant sur son aspect mesurable.
- Les élèves ont bien pris conscience du lien entre complexité temporelle et « rapidité d’exécution des algorithmes » notamment sur de gros volumes de données.
- Ce travail met en valeur l’intérêt d’étudier différents algorithmes remplissant le même objectif pour sélectionner le plus performant.
- La trace écrite propose un exemple d’algorithme pour chacune des complexités suivantes : temps constant, linéaire, logarithmique, quadratique.
Les limites de l'activité :
- On se limite à une approche expérimentale de la notion de coût pour les algorithmes désignés par le programme officiel de 1ère NSI.
- Aucune technicité de mesure de complexité temporelle n’est attendue conformément au programme officiel de 1ère NSI
- L’objectif visé est « l’élève connaît le coût des algorithmes de tri par insertion et sélection et celui de parcours séquentiel d’un tableau ».
- Évaluation limitée à l’implication des élèves dans l’activité. Elle a donc été mesurée par le ressenti de l’enseignant.
Description de l’activité d’introduction :
Les élèves sont invités à étudier un programme écrit en python fournissant 2 fonctions implantant respectivement une recherche séquentielle et dichotomique d’un élément dans une liste.
Le programme contient une fonction permettant de comparer la durée de chaque algorithme.
Le programme principal permet de comparer les performances en termes de temps d’exécution des deux algorithmes sur des listes de tailles différentes.
Documentation, liens et téléchargements
L’archive téléchargeable contient les éléments suivants :
- Fiche descriptive en pdf
- Dans le dossier “Activité d’introduction” :
- Les fichiers “Activité d’introduction.odt” et “Activité d’introduction.pdf”
- comparaison.py : programme principal de l’activité d’introduction
- Comparaison_plot.py : un programme à destination de l’enseignant, permettant d’afficher le graphique de comparaison des performances des deux algorithmes
- Dans les dossiers “Scenario 1” et “Scenario 2”, deux propositions de traces écrites correspondant aux deux scénarios
- Captures d’écran
Auteurs
Mathieu Palosse, David Raynal, Sandrine Sudres, Franck Silvestre