Algorithmique I

Objectifs d’apprentissage

Le plan d’études pour l’informatique en tant que discipline obligatoire à l’École de maturité propose les contenus suivants pour l’introduction à l’algorithmique, ici Algorithmique I :

  • Décomposition d’un problème

  • Algorithmes classiques

  • Conception d’algorithmes simples

En lien avec le plan d’études, nous avons identifié les objectifs d’apprentissage suivants :

  • Résoudre un problème en construisant une solution par étapes

  • Formaliser une solution sous forme d’algorithme

  • Implémenter un algorithme sous forme de programme

  • Intégrer la pluralité des algorithmes

Ces objectifs pédagogiques sont articulés dans trois chapitres principaux dans la partie Appprendre, disponibles également sous la forme d’un document pdf, téléchargeable en haut de la page d’accueil et de la page d’introduction :

  1. Introduction

  2. Les algorithmes

  3. Trie, cherche et trouve

  4. Des algorithmes aux programmes

  5. Conclusion

Dans la partie Enseigner vous trouverez les solutions des exercices proposés dans la partie Appprendre :

Six activités au choix complètent ces ressources dans la partie Enseigner :

Nom

Description

Les algorithmes de tri

Une activité exploratoire débranchée et collaborative pour découvrir les algorithmes de tri en triant des cartes

Modéliser une épidémie

Une introduction à la démarche de modélisation en utilisant python pour des élèves sachant déjà un peu programmer

Monochromes

Une activité progressive de programmation pour sensibiliser à l’importance de choisir la bonne représentation des données

Stroboscope

Une activité progressive de programmation pour explorer la randomisation

L’algorithme du plus court chemin de Dijkstra

Une activité débranchée pour découvrir l’algorithme de Dijkstra en mode collectif et en se déplaçant dans la salle

Minimax / Puissance 4

Une activité de programmation d’un jeu de puissance4 sur 4 périodes pour des élèves maitrisant déjà bien la programmation

Approche pédagogique de la thématique Algorithmique I

Partie Apprendre

La partie “apprendre” a été conçue pour être utilisable de manière autonome par les élèves.

Au niveau de la durée, chaque chapitre est conçu comme un cours de 2 périodes ou 90 minutes.

Le troisième chapitre, « des algorithmes aux programmes », ne peut être traité qu’après avoir vu le thème programmation, car il fait le lien entre les algorithmes et les programmes.

Ces chapitres ne sont pas à faire dans leur entièreté, des contenus optionnels sont toujours prévus, l’hétérogénéité des élèves étant importante en informatique.

Pour la conception, nous avons suivis quatre principes :

  1. Approche orientée principes plutôt que formules mathématiques. Il est important que les élèves qui ont des difficultés en mathématiques puissent entrer dans la matière informatique. Nous sommes convaincus qu’au niveau gymnasial, l’algorithmique peut s’enseigner sans équations, en ce concentrant sur les concepts et les principes.

  2. Storytelling – raconte une histoire cohérente. Le choix d’enseigner les algorithmes de tri a été opéré afin de pouvoir raconter une histoire unique et cohérente qui couvre tous les objectifs pédagogiques. En effet, il existe plusieurs algorithmes de tri, de complexité différente (au programme de 2e année), dont plusieurs sont basés sur la stratégie algorithmique plus complexe « diviser pour régner ». De plus, les algorithmes de tri sont tous accessibles aux élèves, car « tout le monde sait ce que c’est que trier ».

  3. Références à la vie pratique, aux autres disciplines et à des casse-têtes encourageant la réflexion. Pour la motivation des élèves, nous avons tenté d’utiliser autant que possible des exemples concrets qui parlent aux élèves, ainsi que des problématiques qui nous espérons réveilleront leur curiosité et stimuleront leur réflexion.

  4. Activités collaboratives basées sur des problématiques concrètes. En informatique, on travaille régulièrement en équipe et nous souhaitons que le cours reflète cette réalité du terrain.

Activités

Chaque activité proposée dans la partie “enseigner” est prévue comme un labo sur 1 à 4 périodes en branché ou en débranché.

La conception des activités a suivi les principes suivants :

  • Apprivoiser les notions clés de manière (un peu) ludique

  • Développer une compréhension intuitive des concepts

  • Faire réfléchir les élèves (avec leur tête, mais aussi avec leur corps)

  • Induire des questionnements de type algorithmique

L’apprentissage passe par tous les sens, et lorsque possible, nous avons fait appel aux modalités suivantes :

  • La manipulation

  • Le mouvement

  • La collaboration

Parcours dans la thématique

Un algorithme de parcours possible pour la thématique est proposé sur l’image ci-dessous :

../_images/Parcours.png

L’algorithmique pourrait s’insérer de la manière suivante dans un exemple de planification annuelle (voir tableau ci-dessous). On commence par la représentation de l’information pour que les élèves comprennent comment on arrive à représenter le monde (les entiers, les caractères, les images ou le son) dans un ordinateur. En parallèle, lors des périodes branchées en demi-groupe on commence la programmation, car la programmation est synonyme de l’informatique dans la conception des élèves, et cela répond à leur attente, certains sont impatients de programmer. Pour consolider les bases, il est important d’étudier les concepts importants en programmation également en mode débranché. Cela permet de prendre des bonnes pratiques, en particulier le réflexe qui consiste à réfléchir avant de faire, et non pas de faire et refaire et refaire tant que ça ne marche pas. Il faut noter que deux parcours de programmation différents sont possibles, un parcours plus formel basé sur les concepts, et un parcours plus ludique basé sur turtle. Le choix dépendra de la classe que vous avez. Après chaque thème il est opportun d’aborder une thématique des enjeux sociaux, pour permettre une respiration.

Au deuxième semestre on aborde la machine, ou comment les 0 et 1 que l’on a vu au premier semestre prennent vie dans une machine. Cela ferme la boucle de la « démystification de l’informatique ». Pour finir, on se pose la question des algorithmes, ou comment résoudre un problème et existe-t-il plusieurs solutions possibles ? En mobilisant les compétences acquises au cours de programmation, on peut utiliser l’ordinateur pour résoudre quelques problèmes concrets, qui font des liens avec le thème de représentation de l’informatique. On redonne ainsi sens à l’intégralité du programme de première année.

Les parties d’algorithmique sont en gras.

Semaine

Classe entière en débranché (1 période)

Demi-groupes en branché (2 périodes)

1

Magie binaire et 1. Entiers / Ga-Bu-Zo-Meu

Types - opérateurs / Dessiner - Définir*

2

1. Entiers

3

2. Caractères

input() - print() / Colorier - Répéter

4

3. Images

5

4. Son

Format BMP / Images numériques / Enchantillonage

6

5. Redondance et Révisions

7

TEST Représentation de l’information

Les enchères du Web / Cercler - Mémoriser

8

Economie du numérique

9

Conditions (if, range)

Conditions / Parcourir - Typographier

10

Boucles (for)

11

Listes

Boucles / Itérer - Paramétrer

12

Boucles (while)

13

Fonctions

Listes - Fonctions / Randomiser - Questionner

14

TEST Programmation

15

Citoyenneté et gouvernance

Ordinateur antique / Décider - Ecrire / Micro:bit

16

Réserve

17

Réserve

18

1. Portes logiques

Ordinateur antique / Attendre - Renvoyer / Micro:bit

19

2. Additionneur

20

3. ALU

Sélecteur de chien / Grouper- Trier / Micro:bit

21

4. Mémoire

22

5. Architecture générale et composants

Afficheur à 7 segments + Soustracteur / Projet(Dessin) / Micro:bit

23

6. Le microprocesseur

24

TEST Architecture des ordinateurs

Projet(Dessin) / Micro:bit / Intelligence artificielle

25

Vie privée et surveillance

26

1. Les algorithmes

Algorithmes de tri

27

1. Les algorithmes (suite)

28

2. Trie, cherche et trouve

Compression et codage de Huffman

29

2. Trie, cherche et trouve (suite)

30

3. Des algorithmes aux programmes

Epidémie / Monochromes / Stroboscope

31

3. Des algorithmes aux programmes (suite)

32

TEST Algorithmique

Epidémie / Monochromes / Stroboscope

33

Réserve

34

Réserve