Bonsoir,

je suis actuellement en train de suivre un cours sur la théorie de la complexité (en allemand .. )

Et à vrai dire je me retrouve avec un poly. blindé de formule de lemme de définition de corolaire etc. Mais je ne sais que trop en faire ..

J'aimerais donc trouver des cours d'explication, (mais pas trop vulgarisé non plus) en français.

J'ai déjà écumé pas mal de site d'uni sans grand succés..

Merci bien.

Mens.

Pour ma part, j'utilise comme référence introductive le livre "Langages formels, Calculabilité et Complexité" d'Olivier Carton. Je ne sais pas s'il est meilleur que les autres dans ce domaine, mais c'est celui que j'ai lu et je le trouve satisfaisant. Si tu y as accès dans une bibliothèque universitaire, tu peux l'emprunter pour regarder. Sinon, des PDFs du support de cours (avant publication du livre) circulent sur internet, tu en trouveras facilement par une simple recherche Google.

Attention néanmoins, ce livre est pleins de petites coquilles ! Mais pédagogiquement excellent.

Néanmoins, un errata sur le site web de l'auteur contient la plupart de ces coquilles.

Y'a pas mal d'autres "étourderies", des démonstrations pas terribles etc. Faire attention donc.

Je n'ai pas été très satisfait de ce bouquin, je ne l'ai pas trouvé assez cadré sur mes problèmes.

Voici quelques autres lecture que l'on m'a conseillé :
"Computational Complexity: A Modern Approach"
[URL]http://www.enseignement.polytechnique.fr/informatique/INF561/uploads/Main/poly-good.pdf[/URL]

Tiens je ne connaissais pas ce dernier poly. Je crois que sa référence principale est l'excellent http://www.cs.princeton.edu/theory/ind [...] ompbook/Draft que je conseille. Il traite beaucoup de sujets et reste très pédagogique.

Sinon une autre excellente référence (mais toujours anglophone) sur la complexité est le livre de Papadimitrious Computational Complexity, un must absolu.

Et on ne peut pas ne pas citer le génial Introduction to the theory of computation de Sipser, peut-être plus facile que les deux références précédentes.