Automates et théorie des langages formels : les coulisses des expressions régulières et de la hiérarchie de Chomsky
Catégories
70 pages
Informatique
Le lambda-calcul (Lambda Calculus) et les origines de la programmation fonctionnelle : De la théorie d'Alonzo Church à Lisp et Haskell
Machine de Turing et théorie de la calculabilité : l'expérience de pensée d'Alan Turing et le « problème de l'arrêt »
Vue d'ensemble du problème P vs NP et des classes de complexité : Explication du Problème du Prix du millénaire et son importance en programmation
Le jeu de la vie de Conway : Un automate cellulaire où la complexité de la vie émerge de règles simples
Théorème des quatre couleurs (Four Color Theorem) - N'importe quelle carte peut-elle être coloriée avec 4 couleurs ?
Le problème de l'arrêt (Halting Problem) : Le programme ultime qu'il est impossible de créer
Théorèmes d'incomplétude de Gödel : la preuve mathématique des « vérités absolument indémontrables »
Algorithme de détection de cycle de Robert Floyd (Algorithme du lièvre et de la tortue)
Limites de la factorisation en nombres premiers et explication de la notation Grand O (O)
