Les machines de Turing

Faisons un peu d'infomatique théorique

a marqué ce sujet comme résolu.

Salut à tous,

Je suis en train d'écrire un petit tuto sur les machine de Turing. Parce que l'info théorique, c'est le bien !

J'aimerai bien avoir quelques retours, pour le moment j'ai un plan et mon intro. Donnez moi votre votre avis ! :)

Ce tutoriel a pour but de vous familiariser avec les machines de Turing et les applications qu'elles ont en informatique. Ce tuto traitant de l'informatique théorique, ne vous attendez pas à programmer ou apprendre à faire quelque chose de concret.

La machine de Turing est avant tout un modèle mathématique, qui permet de démontrer des résultats théoriques sur les programmes. C'est grâce à elle que l'on définit rigoureusement la complexité d'un algorithme par exemple, ou que l'on démontre la terminaison de certains d'entre eux. Si ces mots ne vous disent rien, ne vous inquiétez pas, tout ceci sera vu au moment approprié dans le cours !

Je tiens également à préciser que ce tuto se veut une initiation à l'informatique théorique, il n'a pas pour but de définir exactement toutes les notions qu'il aborde, ni de démontrer toutes les propriétés évoquées. Ce serait trop long et à mon avis trop indigeste comme premier contact avec l'informatique théorique.
Si vous souhaitez approfondir ce qui a été évoqué ici, je vous conseille vivement la lecture du livre Introduction to the theory of Computation de M. Sipser (en anglais).

  • Notion de langage : première approche avec les automates finis

    • Alphabet, langage
    • Automate fini
    • Langage rationnel
    • Automates non déterministes
    • Jouons un peu : nombreux exemples
    • Pour aller plus loin : langages non rationnels

  • Machine de Turing : première approche

    • Approche intuitive
    • Quelques exemples
    • Machines équivalentes
    • D'autres exemples

  • P, NP

    • Complexité d'un algorithme
    • Classe P
    • Classe NP
    • NP-complétude
    • Pour aller plus loin : quelques réductions

  • Décidabilité

    • Langage reconnaissable, décidable
    • Décidabilité de (N,+)

(Lien de la beta du tutoriel : Les machines de Turing )

Merci ! :)

+0 -0

Salut,

Déjà, c'est cool que quelqu'un commence à écrire sur ce genre de sujet. Cependant, j'ai quelques remarques et questions à propos du plan :

  • Pourquoi parler des langages rationnels et des automates finis? Ou plutôt, comment comptes-tu faire le lien jusqu'aux machines de Turing? Je trouve ça dommage d'aborder le sujet sans parler de la hiérarchie de Chomsky et sans introduire la notion de grammaire. Tout dépend du niveau de vulgarisation auquel tu veux te placer, mais si tu présentes les machines de Turing comme des machines (plus intuitif pour les gens habitués à programmer sans notion théorique), la notion d'automate fini n'est pas forcément indispensable pour comprendre.
  • J'aurais tendance à parler de décidabilité avant de parler de complexité. Peut être parce qu'on me l'a enseigné dans cet ordre, mais il me semble que parler de réduction dans le cas de la décidabilité permet de comprendre plus facilement les réductions polynomiales dans le cas de la complexité (+ avant de savoir combien de temps met un algo à résoudre un problème, il est important de savoir si un algo peut le faire).
  • Finalement, une remarque d'ordre général : quelle est la finalité? Parler de machines de Turing ou écrire une introduction à l'informatique théorique? Comme tu le dis, les machines de Turing n'ont en soi pas d'intéret en dehors des propriétés sur les programmes qu'elles permettent de démontrer. Si les machines de Turing ne sont pas le but du tutoriel, pourquoi ne pas introduire les notions de décidabilité et complexité avec un autre modèle de calcul équivalent qui se rapprocherait d'avantage des langages de programmation que le lecteur est suceptible d'utiliser? Pour beaucoup de personnes, ce serait certainement plus concret.

En tout cas, je te souhaite bon courage pour ce sujet pas évident, et j'espère que tu mèneras la rédaction à terme. :-)

+0 -0

Salut,

Merci pour cet avis très détaillé, et je vais répondre point par point du coup. Je suis bien sur ouvert à toute remarques et les tiennes me font réfléchir à des points auxquels je n'avais pas pensé.

  • Le but de ce chapitre était avant tout de faire comprendre la notion de langage, et le fait d’être reconnu ou non par un automate. J'en profitais pour aborder la notion d'automate fini et présenter les machines comme des automates. Ce n'est peut être pas la meilleure approche en effet. Mais du coup, je ne vois pas trop comment faire comprendre la notion de langage reconnu avec un objet plus simple qu'une machine de Turing ?
  • Pour le coup j'ai appris dans l'ordre que je présente ici, c'est donc simplement une question de point de vue, et à mon avis ces deux chapitres sont assez peu liés et peuvent se mettre dans n'importe quel ordre. A voir au moment de la rédaction si un ordre semble plus pratique.
  • Pour le dernier point c'est juste que je ne me sens pas (encore) assez à l'aise avec un autre modèle pour en faire un tuto. Bien que la finalité est plutôt une approche de l'info théorique, c'est le sujet où je serai le plus à l'aise je pense. Il y a aussi qu'avant de les étudier en cours, j'ai beaucoup entendu parler des machine de Turing, sans jamais savoir de quoi il s'agissait, et que j'aurais été content de tomber sur un tuto comme celui ci :) .

Au passage, j'envisage un premier chapitre avec une petite intro historique, mais à part Wikipédia je n'ai que peu de ressources sous la main. Si certains ont des titres de livres, des sites web, … je suis preneur :) .

+0 -0

Uniquement sur les langages rationnels, tu peux faire quelque chose d'assez concret. Par exemple, partir d'un problème simple : comment repérer un sous mot dans du texte? Tu montres que l'algorithme naïf n'est pas très efficace, et tu introduis la notion d'automate fini pour résoudre le problème. Ensuite, tu peux développer la notion, parler de l'équivalence automate fini / expression rationnelle, et terminer par montrer l'utilisation d'outils comme flex pour l'analyse lexicale.

+0 -0
Ce sujet est verrouillé.