Informations administratives
- Cours de niveau 2
- Certificat : DU-ISN-C2.2
- Domaine informatique : Algorithmique
- Responsable : Jean-Marc Vincent
- Intervenants : Jean-Marc Vincent, Frédéric Prost
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
- Complexité d’algorithme et complexité de problèmes
- Classes de complexité, P, NP, réductions
- Algorithmes d’énumération récursive
- Algorithmes et intelligence artificielle, A*, alpha/beta
- Algorithmes randomisés
- Modèle PRAM et algorithmique parallèle (intro)
- Modèle de calcul des processus et algorithmique distribuée (intro)
- Pourquoi la cryptographie n’est pas suffisante
- Différentes approches du phénomène de la confidentialité
- 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.