Professeur expérimentateur

• Mathilde Boehm
• Lycée Les Pierres Vives– Carrières sur Seine (78)

Niveau - Thèmes

• Lycée
• Première NSI

Introduction

Une séquence pédagogique sous forme de notebook pour présenter les algorithmes de tri à l’aide de différentes ressources numériques.

Contenus disciplinaires

• Algorithmique : Tris par insertion, tri par sélection.
• Compétences exigibles : Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction partielle des algorithmes de tris par insertion et par sélection. Montrer la terminaison de ces algorithmes.
• Capacité numérique : Programmer en Python un algorithme de tri par insertion et de tri par sélection.

Compétences

• Concevoir des solutions algorithmiques.
• Traduire un algorithme dans un langage de programmation, en spécifier les interfaces et les interactions, comprendre et réutiliser des codes sources existants, développer des processus de mise au point et de validation de programmes.
• Développer des capacités d’abstraction et de généralisation.

Objectifs disciplinaires

• Analyser et comprendre le fonctionnement des algorithmes de tri
• Repérer des boucles bornées ou non
• Apprendre à distinguer des algorithmes ayant les mêmes spécifications
• Comprendre les preuves et complexités des algorithmes de tris au programme
• Savoir implémenter les algorithmes de tri en Python de manière autonome (en vue de l’épreuve pratique éventuelle de terminale)

Objectifs pédagogiques ou transversaux

• Communiquer des résultats en utilisant un vocabulaire précis
• Synthétiser l’information

Description succincte de l’activité

Présentation des algorithmes de tri par sélection et par insertion dans une activité Capytale intégrant l’utilisation de ressources permettant de visualiser leurs actions pas à pas (Interstices, Visualgo, Python Tutor).

Pré-requis

• Programmation : bases de Python (affectation, types simples, instructions conditionnelles, boucles et fonction), connaître le type list et savoir le manipuler
• Algorithmique : la notion de spécification, de preuve et de complexité, les tableaux algorithmiques

Outils utilisés / Matériel

• Capytale
  

  

• Interstices (description des algorithmes pas à pas et visualisation des étapes + nombre de comparaisons)
  

  

• Visualgo.net (visualisation pas à pas du déroulement des algorithmes implémentés dans un autre langage de programmation)
  

  

• Python tutor (pour visualiser les étapes de son programme)
  

  

Gestion du groupe

• En présentiel en salle informatique
• Asynchrone (travail à la maison entre les séances)

Déroulement de la séquence

• Temps 1 (1h en classe) : découverte du tri par sélection à l’aide des outils de visualisation et mise en commun des observations (activité Capytale)
• Temps 2 (30 minutes à la maison) : fin de l’activité sur le tri par sélection (implémentation de l’algorithme + preuve et complexité)
• Temps 3 (2h en classe) : synthèse et correction de l’activité (première partie du cours est distribuée) puis travail sur le tri par sélection avec mise en commun (pour information cours distribué)
• Temps 4 (30 minutes à la maison) : fin de l’activité
• Temps 5 (1h en classe) : synthèse du tri par insertion (seconde partie du cours)
• Temps 6 (30 minutes à la maison) : exercices (pour information feuille d’exercices utilisée)
• Temps 7 (30 minutes en classe) : correction des exercices

• Revoir les boucles (parcours de tableaux et boucle non bornée)
• Réviser les tableaux algorithmiques et le type list en Python

• Première séance (temps 1) : le tri par sélection (notebook Capytale jusqu’à l’explication en plénière du principe de l’algorithme)
• Deuxième séance (temps 3) : correction de l’implémentation du tri par insertion et de la partie preuve et complexité et synthèse (distribution d’un cours reprenant ce qui a été vu dans l’activité) puis travail individuel sur le tri par insertion jusqu’à la mise en commun sur le principe général de l’algorithme.
• Troisième séance (temps 5) : correction de l’implémentation du tri par insertion, synthèse et lien avec le cours distribué.
• Dernière séance (temps 7) : correction des exercices sur les tris

• Après la première séance en classe (temps 2) : les élèves doivent finir d’implémenter l’algorithme du tri par sélection et finir de répondre aux questions sur la preuve et la complexité et le professeur analyse rapidement les réponses données par les élèves pour une éventuelle remédiation.
• Après la deuxième séance en classe (temps 4) : implémentation et fin de l’activité par les élèves
• Après la troisième séance en classe (temps 6) : exercices sur les tris

Retour d’expérience

• Le travail est individualisé : chaque élève expérimente les tris avec un tableau différent
• La collaboration : les échanges entre élèves, notamment sur certaines configurations, constituent un levier
• L’engagement des élèves : les élèves apprécient de manipuler eux-mêmes les outils de visualisation, ce qui est un facteur de motivation
• Le découpage de l’activité en plusieurs temps facilite l’apprentissage en permettant des points de synthèse réguliers et de revenir sur les notions
• Les élèves peuvent avancer à leur rythme ce qui améliore l’autonomie des élèves et facilite la gestion de classe
• La trace écrite des élèves est disponible grâce à la plateforme Capytale et permet de faire le point avec la classe entre les séances en s’appuyant sur leurs productions
• L’aspect numérique de l’activité permet aux élèves d’effectuer des copier-coller du tableau à chaque étape du tri et cela rend le travail moins fastidieux malgré la longueur du tableau (16 éléments)

• La nécessité d’avoir accès à des ordinateurs connectés à internet
• La taille du groupe : un effectif réduit semble plus adapté
• Pour le tri par sélection, la ressource Interstices recherche le maximum des valeurs à trier pour le placer à la fin de la partie non triée du tableau alors que Visualgo recherche le minimum pour le placer au début ce qui peut dérouter certains élèves

• Réécrire l’application en Javascript afin de proposer, comme dans Interstices, des explications pas à pas en français ainsi que les calculs de comparaison, et s’inspirer de Visualgo pour permettre d’utiliser des tableaux avec doublons, des valeurs négatives (pas uniquement les valeurs de 1 à 16) et choisir d’utiliser le minimum plutôt que le maximum pour le tri par sélection
• Proposer des tableaux pertinents à utiliser avec Visualgo pour mieux comprendre les algorithmes