Bonjour à toutes et tous,
suite à notre intéressante séance d'hier, j'ai produit une version plus complète des slides de la partie complément de cours :
+ ajout de commentaires sur les solutions concernant 3-SAT (slide 3 = 38/110)
+ ajout de la version légèrement améliorée de l'algorithme proposé hier par votre camarade (slide 9 = 44/100)
Cette nouvelle version est en ligne sur Moodle et je vous la mets aussi ci-joint.
Par ailleurs, je mets aussi ci-joint à toutes fins utiles, les notes manuscrites faites sur les slides hier en cours.
Enfin, à noter que je n'ai volontairement pas traité hier la première question (machine de Turing), non pas parce que cela ne tombera pas à l'examen (si, si, il y en aura : cf aussi examen de l'an passé), mais simplement parce que vous avez déjà plusieurs autres exemple et surtout parce que cela n'a pas posé de problème/question particulière ni sur l'exemple traité la semaine passée, ni l'an dernier sur cet exemple précis.
Alors que sur la complexité des problèmes, c'était sûr qu'il allait y en avoir...
Bonne suite de week-end !
