Séance Séminaire

Séminaire de culture générale Mathématique

P=NP par les Machines de Turing (le retour)

Cet exposé fait suite à celui proposé en juin, qui n’avait pas permis d’aller jusqu’aux classes P et NP. Je repartirai de la notion de Machine de Turing, imaginée par Alan Turing en 1936. Je reprendrai quelques éléments importants du premier exposé pour aller vers les questions de complexité que permettent d’étudier les machines de Turing, puis je présenterai les classes P et NP permettant de comprendre la fameuse conjecture P = NP, considérée comme l’une des plus importante de l’informatique théorique. Cet exposé ne demandera aucune connaissance préalable avancée en mathématiques ou en informatique, si ce n’est de bonnes bases de logique. J’essaierai de faire en sorte qu’il puisse être suivi sans avoir assisté à l’exposé de juin. Je me baserai essentiellement sur l’ouvrage pédagogique pour la licence « Introduction à la calculabilité » de Pierre Wolper (Dunod).\r\n