Documents présentés pendant le stage sur l’algorithmique et la programmation, avril 2012.

Les idées que nous voulons promouvoir :

• il faut savoir aller de l’idée de l’algorithme au code qui s’exécute ;
• il est bien plus efficace de programmer dans un style fonctionnel qu’avec des input et des print, ce qui impose de spécifier les algorithmes (variables d’entrée, sortie, corps) ; intérêts :
  • permettre à un programme (ou un algorithme) d’en utiliser un autre (comme on compose des fonctions), ce qui permet de découper des problèmes complexes en problèmes plus simples ;
  • étudier l’algorithme et pas une mise en œuvre sur un ordinateur particulier ;
  • renforcer la similitude avec une fonction et, partant, favoriser au lycée l’apprentissage conjoint des algorithmes et des fonctions ;
• supposons avoir un algorithme à disposition : il est naturel, indispensable et faisable de se poser trois questions à son propos (et on a une idée pour le faire) :
  • terminaison (idée de convergent),
  • correction (ou validité) (idée d’invariant de boucle),
  • complexité (idée d’estimer le nombre d’opérations élémentaires) ;
• on peut proposer des « types d’algorithmes », des stratégies globales efficaces dans des contextes très variés, qu’on tâchera d’illustrer par des exemples :
  • algorithmes gloutons,
  • diviser pour régner,
  • back-tracking ;
• les données peuvent parfois être structurées pour un traitement efficace, le plus souvent à l’aide d’arbres ou de graphes ; pour autant, le codage de ces données peut rester très simple (par exemple, on peut coder un arbre binaire presque complet par une liste ; mais penser cette liste comme un arbre, c’est lui ajouter de la structure et cela permet des opérations quasiment insensées ; si, si ! insensées !).

Devoir à la maison opportuniste

Peut-être va-t-il vous permettre de répondre à ce problème ?

Pour aller plus loin :

• Documents produits par les IREM
• CAR-scripts : activités proposées par l’IREM de la Réunion mêlant algorithmique et géométrie dynamique
• Formation de formateurs à l’IREM de Montpellier (5 mai 2010) : questions basiques sur ce qu’est un algorithme, une variable...
• Xcas (téléchargement, manuels, feuilles de calcul...)
• Introduction à l’algorithmique, T. Cormen, C. Leiserson, R. Rivest et C. Stein (référence de tout le monde ; attention, environ 1300 pages...)
• Cours d’algorithmique, Yves Robert : cours donné à l’ENS Lyon, certaines parties sont très accessibles (et d’autres plus spécialisées)
• Petite suite de Goodstein par son inventeur, Gilles Dowek
• Vraie suite de Goodstein dans un exposé sur la prouvabilité de Patrick Dehornoy
• Algorithme de compression de Huffman, Walid Nabhan

Références :

• Introduction à la théorie des graphes - Butinage graphique Jean-Manuel Mény, Gilles Aldon, Lionel Xavier, CRDP disponible à l’IREM
• Galejade