Algorithmie

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,

Comment ?

Des problèmes canoniques mettant en lumière des structures algorithmiques qui deviendront un savoir-faire réutilisable.


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.

 

La littératie numérique 

 

La grammaire des algorithmes :
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 
Comme toute science, il existe en algorithmique des modèles théoriques différents. Ces modèles (machine de Turing, par exemple) « peuvent être considérés comme d’autres définitions, plus théoriques, de ce qu’est un algorithme ». Ils permettent ainsi de catégoriser les algorithmes.

Aucun commentaire:

Publier un commentaire