Algorithmique : Modèles de calcul, calculabilité et complexité

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 d’étendre la culture algorithmique à des modèles de calculs plus élaborés, prenant en compte les générateurs aéatoires, la concurrence, la distribution.

Le cours se terminera par une ouverture vers l’informatique et la confidentialité

Contenu pédagogique

Page du cours

  1. Complexité d’algorithme et complexité de problèmes
  2. Classes de complexité, P, NP, réductions
  3. Algorithmes d’énumération récursive
  4. Algorithmes et intelligence artificielle, A*, alpha/beta
  5. Algorithmes randomisés
  6. Modèle PRAM et algorithmique parallèle (intro)
  7. Modèle de calcul des processus et algorithmique distribuée (intro)
  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 logiques

Compétences développées

  • connaissance de différents modèles de calcul, notion de machine abstraite
  • sensibilisation aux notions de classes de complexité liées à un modèle de calcul
  • connaissance des classes P, NP , de quelques méthodes de réduction et d’algorithmes d’approximation

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.