Stage « Algorithmique »

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
Articles publiés dans cette rubrique
mardi 29 octobre 2013
par ,
par ,
Atelier aux Journées nationales de l’APMEP (Marseille 2013)
Diaporamas présentés par Jérôme Germoni et Jean-Manuel Mény à l’atelier des Journées nationales de l’APMEP (Marseille 2013)
Le fichier zip contient le diaporama d’exemples pour la classe. Les liens de ce diaporama ciblent les fichiers ipynb qui se trouvent dans le dossier. ipynb est le format des (...)
mardi 27 mars 2012
par , ,
par , ,
Documents (algorithmique mars 2012)
Documents proposés pendant le stage des 13 et 22 mars 2012.
Mise à jour le 27 mars : ajout des documents du 22 mars.
mercredi 12 mai 2010
par
par
Spécification d’un algorithme
Cet article est la suite d’une conversation avec Nicolas Saby, directeur de l’IREM de Montpellier, à propos d"une formation en algorithmique à laquelle il a participé récemment. Le travail mené à Montpellier avec les informaticiens a mis en évidence une possible différence de conception (...)