DU ISN2 Modèles de calcul

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é

1. Complexité d'algorithme et complexité de problèmes (voir le Cormen et al.)
2. Classes de complexité, P, NP, (voir le Cormen et al.)
3. Algorithmes d'énumération récursive Transparents
4. Algorithmes randomisés Computing with coins Random machines
5. Randomisation et Simulation Simulation
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

• 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

• Chapitres 2 de Introduction à la science informatique : Pour les enseignants de la discipline informatique en lycée , Gilles Dowek (coordination de l’ouvrage collectif) Collection Repères pour agir, CRDP Académie de Paris. 2011
• 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.