WikiLuc

Guest connection: login: Guest, password: anonymous

User Tools

Site Tools


agreg:cours:complexite

Agrégation 2013: Complexité des algorithmes

www.oxfordmartin.ox.ac.uk_images_about_complexity_20small_20landscape_202.jpg

Luc Bougé 2013/06/30 23:32


Foire aux questions

Toutes les questions qui ont été posées pendant le cours, avec la meilleure réponse que nous connaissons à ce jour.

Plan du cours

jeremykun.files.wordpress.com_2012_02_pvsnp.jpg

Lundi 1er juillet: Luc Bougé

Complexité, de la Machine de Turing à la NP-complétude

  • Machine de Turing, un exemple facile pour commencer
  • Complexité en pire cas et en moyenne, en temps et espace
  • Les classes classiques: log(n), n, n^2, e^n, complexité polynomiale et exponentielle
  • Complexité déterministe et non-déterministe
  • P et NP, SAT, NP-complétude

Mercredi 3 juillet: Judicaël Courant

Applications de la complexité en cryptographie

Nous présenterons une brève introduction à l'utilisation des outils de complexité en cryptographie en montrant, sur quelques exemples, quelles sont les propriétés de sécurité qu'on peut désirer, comment les modéliser et les démontrer.

Vendredi 5 juillet: Luc Albert, Éric Merle

Algorithms + Data Structures + Complexity Evaluation = Programs

  • L'arbre des suffixes et la surprenante linéarité
  • Un tas pour des rapaces, ou la puissance des algorithmes gloutons
  • Composantes connexes et Union-Find
  • Quadtree et images

Samedi 6 juillet: Nicolas Schabanel

Probabilistically Checkable Proofs et applications… à la correction efficace des copies

Dans cet exposé, nous allons présenter des techniques pour écrire une preuve de sorte qu'on puisse en vérifier efficacement la validité. Ce résultat repose sur de jolies applications de l'algèbre linéaire et est à l'origine d'avancées importantes sur l'inapproximabilité des problèmes NP. Nous présenterons surtout des exemples et les grandes lignes du raisonnement qui conduit à cette caractérisation étonnante des problèmes NP: ce sont ceux dont il suffit de lire 3 bits de la preuve pour être convaincu de sa validité.


Bibliographie

www.images.hachette-livre.fr_media_imgarticle_dunod_2009_9782100515882-g.jpg

Portes d'entrée dans le domaine

www.cs.princeton.edu_theory_complexity_cover.jpg

La Bible, dernière édition

:-O Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak, Cambridge University Press, 2009

Applets

Pour information, la page de Glucose, le champion du monde 2012 des solveurs SAT, conçu par Laurent Simon et Gilles Audemard

Aspect généraux
Algorithmique

Quelques ressources électroniques sur ce thème

Complexité probabiliste
Complexité de Kolmogov
agreg/cours/complexite.txt · Last modified: 2017/04/05 17:06 (external edit)