UE Algorithmique

1 September 2013

Objectif

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. Cela nécessite de

  • 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

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

Niveau 1 : Algorithmes classiques (certificat DU-ISN-C1.2)

Responsable Benjamin Wack

Intervenants : Benjamin Wack et Vincent Danjean

Page du cours

Contenu

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. Structures séquentielles
  3. Tables de hachage et analyse en moyenne
  4. Diviser pour régner et tris rapides
  5. Arbres de recherche et structures dynamiques
  6. Arbres, codage et compression
  7. Chaînes de caractères, automates, pré-traitement
  8. Traitement de données, programmation dynamique et apprentissage
  9. Cheminements dans les graphes, connexité et plus courts chemins
  10. Géométrie algorithmique ou algorithmes de graphe

Niveau 2 : Algorithmique : Modèles de calcul, calculabilité et complexité (certificat DU-ISN-C2.2)

Responsable Jean-Marc Vincent

Intervenants : Jean-Marc Vincent et Frédéric Prost

Page du cours

Contenu

  1. Complexité d’algorithmes et complexité de problème
  2. Classes de complexité, P, NP, réductions
  3. Algorithmes récursifs d’énumération, coupes
  4. Algorithmes et intelligence artificielle A*, alpha/beta
  5. Algorithmes randomisés
  6. Modèle PRAM et algorithmique parallèle (introduction)
  7. Modèle de processus communiquants et algorithmique distribuée (introduction)
  8. Pourquoi la cryptographie n’est pas suffisante
  9. Différentes approches du phénomène de la confidentialité
  10. Non Interférence et approches logiquesModèle de calcul et “privacy”

Bibliographie

  • Chapitres 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.
    • Michael R. Garey and David S. Johnson. Computers and Intractability : A Guide to the Theory of Np-Completeness. W.H.Freeman & Co Ltd, 1979.