UJF-INP / M2R Mathematiques-Informatique

Description  

Cette partie du cours introduit les algorithmes et la complexité probabiliste. L'ouvrage de référence pour ce cours est l'article [1]. Le cours est organisé en 4 séances:

• Algorithmes probabilistes et classes de complexité. Atlantic City, Monte-Carlo, Las Vegas. Hiérarchie BPP, RP, co-RP et ZPP.
  Exemples de base: Min-Max, vérification d'idendités algénriques (Schwartz-Zippel).
  Transparents du cours
• Algorithmes Las Vegas avec probailité d'échec et sans échec; bornes inférieures de complexité.
  Inégalité de Markov et de Chebyshev. Exemple: MAX-SAT et 2-SAT.
  Transparents du cours
• Chaines de Markov, marches aléatoires, bornes de Chernov. Exemples: tri, sélection et treap.
  Exemples: Algorithmes parallèles randomisés.
  Transparents du cours
• Preuves probabilistes; classes de complexité interactives, IP et NP. Application: preuves à divulgation nulles de connaissance.
  Transparents du cours
• Dérandomisation et complexité non-uniforme.
  Transparents du cours

Articles proposés pour les lectures/travail personnel

Annales d'examen

• 2010-2011 partie complexité probabiliste

• Articles
  • [0] Randomized algorithms, chapitre 13 du livre "Algorithm Design" [http://www.aw-bc.com/info/kleinberg/index.html], John Kleinberg, Eva Tardos, Pearson Ed., 2006.
  • [1] An introduction to randomized algorithms. R.M. Karp, Discrete Applied Mathmeatics, 34:165-201, 1991. Preversion ICSI Technical Report TR-90-024, June 1990.
  • [1'] http://portal.acm.org/citation.cfm?id=234313.234327. ^I Rajeev Motwani and Prabhakar Raghavan. ACM Computing Surveys (CSUR) Volume 28 , Issue 1 (March 1996)
  • [2] Randomised Algorithms. D.J.A. Welsh, Discrete Applied Mathmeatics, 34:165-201, 1991.
• Livres
  • [3] Randomized Algorithms. R. Motwani and P. Taghavan, Cambridge Universty Press, 1995
  • [4] M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
  • [5] Introduction à l'algorithmique probabiliste, Philippe Duchon (v4), 2007