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  Jérôme Germoni, Jean-Manuel Mény

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  Gilles Aldon, Jérôme Germoni, Jean-Manuel Mény

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  Jérôme Germoni

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 (...)
mercredi 7 avril 2010
par  Webmaster IREM

Documents (avril 2010)

Activités et corrections, fichiers Xcas à part.

Brèves

12 juillet 2021 - MOOC Entrée dans l’enseignement supérieur

L’école polytechnique propose une série de cours massifs en ligne à prendre comme un "cahier de (...)

18 octobre 2015 - Questionnaires de la CII Université

L’objectif est de collecter de nouvelles réponses pour mieux mesurer l’impact de la réforme du (...)

27 janvier 2010 - Travailler par compétences et avec le socle commun

Conférence le 10 février au CRDP de Lyon de 9 h à 12 h, avec Jean Michel Zarkhartchouk

13 novembre 2008 - Probabilités en 3e

Texte issu d’une formation aux probabilités pour les professeurs de troisième faite par Y. Ducel (...)

Sur le Web