Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Poly automates info1 Mathématiques IUT INFO - Licence Creative Commons MAJ janvier Machines de TURING Langages Automates Grammaires Guillaume CONNAN CTA B L E D E S M AT I È R E S Machines de Turing Approche historique Les machines de TURING Description s

Mathématiques IUT INFO - Licence Creative Commons MAJ janvier Machines de TURING Langages Automates Grammaires Guillaume CONNAN CTA B L E D E S M AT I È R E S Machines de Turing Approche historique Les machines de TURING Description sommaire Un exemple pour découvrir Dé ?nitions Fonctions MT-calculables Fonctions récursives EXERCICES Machines de TURING Fonctions récursives Langages et automates Langages Un exemple pour découvrir Dé ?nitions et notations Langages Langages et expressions rationnels ou réguliers Automates Dé ?nitions Langage reconnaissable Langage reconnu par un automate ?ni Automates équivalents Automates standards Automates déterministes Automates émondés Automate minimal Opérations rationnelles sur les automates Théorème de KLEENE Automate associé à un langage dé ?ni par une expression rationnelle Automates séquentiels Automates à pile Machines de TURING le retour Grammaires Syntaxe et sémantique Grammaires algébriques ou hors contexte Grammaire régulière Lemme de la pompe Analyse syntaxique parsing ? Correspondance automate ?ni grammaire régulière EXERCICES Langages Langages et expressions rationnels C Généralités sur les automates Expression rationnelle associée à un automate Automates standards et émondés Automates déterministes Construction d ? automates Automates séquentiels Automates à pile Problèmes divers Grammaires Révisions Logique Présentation générale de la logique des propositions Syntaxe Sémantique EXERCICES Bibliographie Guillaume CONNAN - IUT de NANTES - Département informatique - Licence Creative Commons BY C janvier C CHAPITRE Machines de TURING En informatique tout a commencé avant la construction du premier ordinateur dans le cerveau fécond de quelques mathématiciens CCHAPITRE MACHINES DE TURING Approche historique A TURING - Les essais de formalisation de la pensée ont commencé bien avant l ? apparition des ordinateurs notamment avec LEIBNIZ au XVIIe siècle mais ont réellement pris leur essor avec les travaux de BOOLE ?n du XIXe La période qui va surtout in uencer le monde informatique se situe pendant l ? entre-deuxguerres marquée par les travaux d ? Alonzo CHURCH Alan TURING Stephen KLEENE Haskell CURRY entre autres car elle marque les prémisses de l ? informatique avant même la construction du premier ordinateur ?-calcul calculabilité complexité algorithmique équivalence entre fonctions mécaniquement calculables et dé ?nitions formelles des fonctions récursives Nous n ? allons pas voguer dans les hautes sphères de la logique mathématique et de l ? informatique théorique mais il est important pour un e informaticien ne d ? aborder ces notions de mécanisation de la pensée qui sont l ? essence de sa discipline Nous aborderons la logique comme un exemple de système formel que nous étudierons plus en détail à travers la théorie des langages des grammaires et des automates qui sont à la base de la construction des compilateurs Mais pour commencer par le commencement nous étudierons brièvement l ? ordinateur le plus simple qu ? on puisse imaginer la machine de TURING Nous ferons le lien entre calculabilité et récursivité Les machines de Turing Description sommaire Alan TURING est le véritable homme à la pomme dont il a utilisé un exemplaire pour s ? empoisonner de l ? informatique car il en a posé les fondements et