Algorithmes classiques

Informations administratives

Volume horaire par certificat

  • Heures encadrées :
    • 10 h cours
    • 10 h travaux dirigés
  • Heures non-encadrées :
    • 10 h travaux pratiques non encadrés en salle de TP (voir l’organisation type de la journée)
    • 20 h travail personnel

Objectif du cours

L’objectif du cours est de donner une culture algorithmique permettant au stagiaire de savoir proposer une solution algorithmique à un problème, savoir l’implanter et savoir l’analyser.

Contenu pédagogique

Page du cours

La démarche pédagogique repose sur 10 séances abordant chacune, à travers un exemple classique, un concept de l’algorithmique. Le programme prévisionnel des 10 séances :

  1. Coût d’un programme, complexité et performance
  2. Trier
  3. Diviser pour régner et tris rapides
  4. Structures séquentielles
  5. Structures arborescentes
  6. Structures ordonnées
  7. Tables de hachage et analyse en moyenne
  8. Algorithme d’optimisation, programmation dynamique
  9. Cheminements dans les graphes
  10. Algorithmes gloutons

Compétences développées

  • Savoir reconnaître et mettre en oeuvre des schémas génériques d’algorithmes (séquence, arbre, graphe…),
  • Savoir construire une solution selon une démarche allant du plus simple (algorithme naïf) au plus efficace (diviser pour régner, etc.)
  • Savoir comment évaluer la complexité d’une solution algorithmique:
    • analyser la complexité au pire, en moyenne avec des hypothèses probabilistes,
    • analyser la complexité en utilisant des mesures sur des simulations ou des jeux de test

Bibliographie

  • Chapitre 2 de Introduction à la science informatique : Pour les enseignants de la discipline en lycée informatique, Gilles Dowek (coordination de l’ouvrage collectif) Collection Repères pour agir, CRDP Académie de Paris. 2011
  • Autres références (non exhaustif)
    • Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Algorithmique. Dunod, 3e edition, 2010.
    • Robert Sedgewick and Kevin Wayne. Algorithms. Addison Wesley, 4e edition, 2011.
    • Dexter C. Kozen. The Design and Analysis of Algorithms (Monographs in Computer Science). Springer, 1991.
    • David Harel and Yishai Feldman. Algorithmics : The Spirit of Computing. Addison Wesley, 2004.