Pour préparer, illustrer des cours : algorithmes (sélection thématique)

Le mot « algorithme » vient du nom du grand mathématicien persan Al Khwarizmi (vers l'an 820), [1] qui introduisit en Occident la numération décimale (rapportée d'Inde) et enseigna les règles élémentaires des calculs s'y rapportant.

L'activité algorithmique a été introduite depuis 2009 dans les programmes de mathématiques de toutes les sériés du lycée [2], voici quelques activités algorithmiques effectuées dans ce cadre :

• • Javascool : Découvrir les ingrédients des algorithmes [3]
• • Educ Algo : Logiciel d’Initiation à l'algorithmique [4]
• • Javascool : Exercices algorithmes classes de seconde [5]

Briques pour préparer les cours

Il s'agit d'un ensemble de documents issus en général de cours de l'enseignement supérieur.

• → Qu’est-ce qu’un algorithme ?
  • Texte introductif provenant du site Interstice
• → Le site du Zéro - Algorithmique
  • Le "site du zéro" est une plateforme collaborative. Vous y trouverez de nombreux tutoriels pour débutants en programmation, développement web et ici algorithmique
• → Cours algorithmique [6] :
  • Document de l'association A.T.L.A.N.T.I.C, il s'agit d'un cours ressource pour la classe, avec quiz d'évaluation.

• → Eléments d'algorithmique [7]
  • Cours de l’ENSTA, on y parle de complexité, récursivité, structures de données, arbres, graphes
• → Cours d'algorithmique de BTS IG [8]
  • Cours de première année du BTS IG
• → Initiation à l'algorithmique [9]
  • Cours intégrant les algorithmes classiques - 1° année de l’Enseirb

Culture générale - illustrer les cours

Nous allons ici indiquer des liens vers des documents utilisables en classe, en particulier un ensemble d'algorithmes répondant à des problématiques classiques.

Algorithmes de tri

• • → Le problème du tri Synthèse de plusieurs algorithmes sur cette thématique, avec applet Java
  • → Les algorithmes de tri Issu du site Interstices avec Applet Java pour les illustrer
  • → Sur le site du zéro, un ensemble d'algorithmes de tri : le tri par insertion, le tri par sélection, le tri par tas, le tri à bulles, le tri rapide : QSort, le tri-fusion, mais aussi le tri ABR, le tri à paniers à découvrir sur ce site.
  • → Comparaison Tri insertion/Tri fusion Une illustration de ces deux algorithmes et de leur efficacité
  • → Voir le fonctionnement de ces algorithmes sous forme de danses : Le tri par insertion dansé, Le tri à bulles dansé
  • → Une petite vidéo pour introduire la problématique Maggie Sort Algorithm

Algorithmes de recherche

• • → La dichotomie Parcours Javascool
  • → La recherche dichotomique Exemple classe sur un problème de poker
  • → Un peu de recherche ne peut faire que du bien !! Une page synthèse du site Zéro
  • → Le « backtraking » ou recherche en profondeur, ou DFS : Le backtracking par l'exemple : résoudre un sudoku et aussi Backtracking (Mathe Prisma) - ce dernier, en allemand et sans programmation.

Graphes, Cryptographie

• Des pages spécifiques du site SILO traitent de ces deux thèmes, en particulier des algorithmes associés.

• • → Graphe
  • → Cryptographie

Génération de l'aléatoire

• • → A la découverte de l'aléatoire et des probabilités [10]
  • → Bruits et nombres aléatoires cohérents [11]

D'autres algorithmes

• • → Machine de Turing Un article d’interstices pour comprendre le fonctionnement de la machine de Turing, avec Applet Java
  • → Les suites de Syracuse
  • → Dessiner la fractale de Mandelbrot
  • → Les tours de Hanoï
  • → Les algorithmes gloutons
  • → Introduction aux algorithmes gloutons (en allemand, très bien fait, sans programmation)

Pour approfondir

• • → Entre mathématiques et informatique : l'analyse des algorithmes [12] Conférence lors du colloqium Jacques Morgenstern – INRIA
  • → Éléments d'algorithmique [13] Cours encyclopédique

Bibliographie

• • → Algorithmes en langage C: Cours et exercices [14], Auteurs : Sedgewick R., Moreau JM
  • → Introduction à l'algorithmique [15], Auteurs : Cormen T., Leiserson C., Rivest R., Stein C.
  • → Mathématiques pour l'informatique : Avec 309 exercices corrigés [16], Auteurs : Arnold A., Guessarian I.