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