Logiciel pédagogique de simulation de divers modèles de calcul (JFLAP) [jar]
Pour creuser plus loin
Script du cours de calculabilité de Benoît Monin[pdf]
Livre en anglais un peu daté mais qui donne une bonne introduction à la complexité : Computational Complexity par Christos H. Papadimitriou chez Addison-Wesley.
Livre en français de Sylvain Perifel plus récent, plus formel et plus complet que le précédent [pdf]
Babbage's mechanical computer
Alan Turing
Autres ressources en lien avec des discussions qu'on a eu en cours
Trois articles vulgarisés (en anglais) parlant de SAT, de NP et des solveurs SAT modernes[pdf1, pdf2, pdf3]
Un article qui explique de manière détaillée le fonctionnement d'un solveur SAT moderne (en particulier à la fin la structure de donnée pour faire une propagation paresseuse mais un bactrack sans mise à jour) [pdf]
Problème combinatoire proche du problème d'emploi du temps discuté avec un groupe [wikipedia]
Sources tex et pdf un peu en vrac de cours de graphes et automates données avec Malika More à Clermont-Ferrand. La première version est avec des TPs que je faisais avec sage (probablement transposable facilement en python pur en dehors de sage) et de visualiser certains algos de graphe dont les parcours en largeur et profondeur [zip]. La seconde version est de retour sur des TPs sur papier
[zip]
