L'enseignement des algorithmes
Définition : un algorithme est une succession d'actions simples et sans ambiguïtés répondant à une série de problèmes identifiés ( comme un recette de cuisine ! ).
Introduction : enseigner la pensée computationnelle (Computational thinking)
Le but est de trouver comment résoudre des problèmes en utilisant les techniques issues de l’informatique, telles que le processus itératif (répétition d’une séquence d’instructions), le débogage, la reconnaissance des schémas connus, la création d’algorithmes, la méthode de décomposition des problèmes (en sous - problèmes traitables plus efficacement), etc.
Étudier l’informatique implique plus que d’apprendre le code. S’inspirer des techniques qui régissent les ordinateurs permet aux élèves à s’engager dans l’abstraction, en définissant des modèles, en généralisant à partir d’occurrences spécifiques ; cela entraine différentes manières de traiter l’information et de la représenter, cela demande aussi aux élèves de travailler systématiquement à identifier et résoudre les erreurs. L’objectif est d’apprendre aux enfants à structurer des problèmes de telle sorte qu’ils puissent être résolus. La pensée informatique peut en outre être enseignée au sein de cadres variés, en mathématiques, en sciences, en arts,
Introduction : enseigner la pensée computationnelle (Computational thinking)
Le but est de trouver comment résoudre des problèmes en utilisant les techniques issues de l’informatique, telles que le processus itératif (répétition d’une séquence d’instructions), le débogage, la reconnaissance des schémas connus, la création d’algorithmes, la méthode de décomposition des problèmes (en sous - problèmes traitables plus efficacement), etc.
Étudier l’informatique implique plus que d’apprendre le code. S’inspirer des techniques qui régissent les ordinateurs permet aux élèves à s’engager dans l’abstraction, en définissant des modèles, en généralisant à partir d’occurrences spécifiques ; cela entraine différentes manières de traiter l’information et de la représenter, cela demande aussi aux élèves de travailler systématiquement à identifier et résoudre les erreurs. L’objectif est d’apprendre aux enfants à structurer des problèmes de telle sorte qu’ils puissent être résolus. La pensée informatique peut en outre être enseignée au sein de cadres variés, en mathématiques, en sciences, en arts,
Comment ?
Comme en littérature, il est fondamentale d'étudier les Grands Classiques....de l'algorithmie.
Ces algorithmes présentés sous forme de jeux, permettent de mettre en place les savoirs nécessaires à l'élaboration de la notion d'algorithme et de structurer sa manipulation pour être autonome.
Ces algorithmes présentés sous forme de jeux, permettent de mettre en place les savoirs nécessaires à l'élaboration de la notion d'algorithme et de structurer sa manipulation pour être autonome.
La littératie numérique
Les connecteurs logiques et le booléens : ET/OU/NON/OU exclusif
http://algothymio.blogspot.fr/2015/10/connecteurs-booleens.html
Un algorithme est une succession d'actions simple aboutissant à un résultat juste applicable à une famille de problèmes i.e. une stratégie gagnante.
Comment gagner au jeu de Nim, au Puissance 4 ?
http://algothymio.blogspot.fr/2015/11/jeu-de-nim.html
http://www.loria.fr/~quinson/Mediation/algo1-livret.pdf
https://interstices.info/jcms/c_33343/jeux-de-nim
Le second objectif d'un algorithme est qu'il résolve le problème le plus vite possible.
Le crépier psychorigide ( sans ambiguïté ; diviser pour régner )
« Classer les crêpes à l'endroit, de la plus grande à la plus petite »
http://www.loria.fr/~quinson/Mediation/algo1-livret.pdf
Corriger une proposition d'algorithme afin de le faire évoluer, formaliser.
Jeu du Base Ball ( Tri à Bulle )
http://www.loria.fr/~quinson/Mediation/algo1-livret.pdf
Résolution de problème à l'aide de la récursivité.
La Tour de Hanoï
http://algothymio.blogspot.fr/2015/11/jeu-de-nim.html
Le plus proche voisin/ Le plus court chemin.
Problème du voyageur de commerce/La ville embourbée ( Algorithmes de Dijkstra et Kruskal )
http://algothymio.blogspot.fr/2015/11/jeu-de-nim.html
Il est plus facile de chercher dans un liste déjà rangée
Classement du +léger au +lourd, alphabétique...
Tri par insertion / Tri à bulle / Tri par fusion ( diviser pour régner )
http://algothymio.blogspot.fr/2015/09/balance.html
https://pixees.fr/?p=741
Recherche rapide d'information dans une liste
Bataille Navale trouver un bateau sur une ligne pour une recherche rapide d'informations
( ex : moteur de recherche ; codes barre )
Algorithmes de recherche linéaire, binaire ou de hachage
https://pixees.fr/wp-content/uploads/2014/08/la-bataille-navale.pdf
Factoriser l'information en binaire
Coder une image en couleur
La couleur par les nombres
http://algothymio.blogspot.fr/2015/10/factoriser-linformation.html
Chiffrage des données
Jeu des cadenas :
C'est un pays imaginaire ou les habitants ne peuvent communiquer qu'avec la poste.
Malheureusement le postier est un voleur.
Pour se protéger, chaque habitant dispose de son cadenas et de sa clef.
Et ils mettent leur courrier dans des boites blindées.
Comment Pierre peut-il envoyer une lettre ou quelque chose a Paul sachant qu'ils ne peuvent communiquer que par la poste ?
Cryptolographie
http://algothymio.blogspot.fr/2015/11/cryptographie.html
https://pixees.fr/?p=741
Recherche de la solution optimale
Rush Hour
Arbre couvrant ( Algorithme de Kruskal )
http://www.thinkfun.com/mathcounts/play-rush-hour
Et pour aller plus loin, la structure "jeu dont vous êtes le héro"
est un formidable terrain d'exploration de la possibilité d'algorithmes simples.
Les plateformes de développement qui ont fait leurs preuves :
inform7
Twine
Squiffy
La structure du langage
*Constante et Variable(Dans une recette de gâteau faire varier la quantité d'un ingrédient)
*Structure conditionnelle
SI...ALORS...SINON
*Structure boucle itérative
POUR...DE...A...
TANT QUE...
En prolongement, une définition des algorithmes décomposée par Simon Modeste en 5 aspects :
L’aspect problème
« L’algorithme répond à une question précise posée pour une famille
d’instances.
[…] On parle d’entrée et de sortie de l’algorithme : l’entrée représente
l’instance à traiter,
la sortie la réponse à la question pour cette instance. Les points
importants sont :
– les notions d’entrée et de sortie
– la notion d’instance d’un problème auquel répond l’algorithme
– le fait qu’un algorithme réponde à une question pour toutes les
instances
du problème »
Dans le projet robotique, les entrées sont les stimuli envoyés au robot
par l’environnement
extérieur. Les sorties correspondent aux réponses données par les
actionneurs du robot
L’aspect effectivité
« Un algorithme apporte une solution effective.» En effet c’est une
méthode systématique
qu’un opérateur (machine ou humain) peut mettre en oeuvre. Il peut
s’exprimer sous forme de programme.
Il agit sur des données finies en un nombre fini d’étapes.
L’aspect preuve
Algorithme et preuve sont très liés à différents niveaux. La notion de
preuve possède différents
statuts en algorithmique.
D’une part il est nécessaire, pour valider un algorithme, de prouver
qu’il aboutit au bon résultat. Cela passe par plusieurs vérifications
des caractéristiques communes aux algorithmes :
comme l’existence d’invariant, la possibilité d’utiliser différentes
entrée et enfin l’existence d’un
nombre fini d’étapes.
L’autre lien entre preuve et algorithme concerne l’utilisation de ce
dernier pour valider
l’existence d’un objet, ou d’une propriété. Dans ces cas-ci,
l’algorithme, qui a été validé auparavant, à valeur d’outil de preuve.
L’aspect complexité
La complexité d’un algorithme fait référence aux caractéristiques de
celui-ci : sa taille ou
sa durée. Caractériser la complexité des algorithmes permet de les
comparer ou encore de chercher à les optimiser.L’aspect modèle théorique
Aucun commentaire:
Enregistrer un commentaire