DU ISN2 Modèles de calcul
Table of Contents
Page du cours DU ISN2 : Modèles de calcul (partie algorithmique avancée)
1 Objectifs de l'UE
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é
2 Programme prévisionnel
- Complexité d'algorithme et complexité de problèmes (voir le Cormen et al.)
- Classes de complexité, P, NP, (voir le Cormen et al.)
- Algorithmes d'énumération récursive Transparents
- Algorithmes randomisés Computing with coins Random machines
- Randomisation et Simulation Simulation
- 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
3 Documents liés au post-confinement
3.1 Mercredi 3 juin
- Cours Intro
- Cours parcours de graphes
- Espaces de chemins et structures algébriques
- Optimalité
- TD1-DIU-5.6
- TD1-DIU-5.6b
- TD1-DIU-5.6c
- pour le fun Ghostbusters (extrait et adapté de l'ouvrage de Cormen et all)
4 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
5 Bibliographie
- 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.