jeudi 18 juin 2015

Introduction

La  notion  des  Automates  s’inscrit  dans  le  cadre  de  l’Informatique  théorique.  Cette notion  intervient  dans  d’autres  domaines  informatiques  tels  que  la  calculabilité, discipline qui a pour but de voir ce qui est calculable ou  soluble et ce qui ne l’est pas,   par   l’informatique,   la   compilation   (Théorie   des   langages),   comme   un soubassement ou un pilier incontournable.
Il convient de le dire, que, la notion des Automates est indiscutablement d’un intérêt capital  pour  tout  ingénieur  et  beaucoup  plus  pour  un  apprenant  dans  la  filière Informatique, vu que cette notion est aussi une voie de modélisation de système.
Les  automates  trouvent  leur  emploi  dans  les  domaines  suivants (méthodologies  et approche scientifique) :
¨    La modélisation mathématique des problèmes informatiques.
¨    La recherche de solutions.
¨    L'analyse des solutions.
¨    La présentation des solutions.
¨    Les  analyseurs  (lexicaux,  syntaxiques,  sémantiques),  dans  la  théorie  des langages ;
¨    Etc. (la suite un peu plus bas)


Cette  petite  liste  juste  ci-haute  montre  donc  la  motivation  pour  laquelle  on apprendrait les automates.
Une  autre  bonne  raison  ou  motivation  pour laquelle on  apprendrait  les  automates,  c’est  le problème  de  la  solubilité  des  problèmes, comme dit tantôt,  qui  peut  mieux  se  résumer  à  cette question fondamentale de l’informatique :
Quels problèmes peut-on résoudre à l'aide d'une "machine à calculer"?
C'est-à-dire : Existe-t-il une limite à ce qu'on peut programmer? Et c’est la quelle ?
Voici les réponses :
Il existe des problèmes qui ne puissent être résolu à l’aide d’un ordinateur, même si ce dernier aurait une mémoire illimitée.
A cet effet, les classes d’automates, les classes de fonctions et la machine de Turing sont utilisées pour évaluer cette limite (voir le cours de Calculabilité).
L’étude de la question au-dessus a été menée par Alan Turing en 1930, avant même qu’il  apparaisse  le  premier  ordinateur.  Elle  était  basée  sur  une  machine abstraite,  un automate appelé   Machine de Turing. Sa réponse à ces questions s'applique à tous les modèles d'ordinateur qu'on connait aujourd'hui.
Il  faut  dire  que,  les  automates  ont  été  définis  dans  les  années  40  et  50,  avec  une motivation  tablée  sur  l’étude  du  cerveau  humain ;  mais  aujourd’hui  ils  sont  utilisés dans beaucoup d’autres domaines tels que :
¨      Conception de matériels informatiques.
¨      Compilation des langages.
¨      Reconnaissance de texte.
¨      Conception et vérification des protocoles (de communication).
¨      Synthèse des programmes.
¨      Vérification des programmes ou des circuits électroniques.
¨      Compression de données
¨      Recherche d’occurrence dans un texte (moteur de recherches sur le web, etc.) 
¨      Compilation 
¨      Biologie (génomique) 

Les  automates  sont  des  objets  mathématiques,  très  utilisés  en  informatique,  qui permettent de modéliser un grand nombre de systèmes (informatiques). Elle se base sur de nombreuses techniques (topologie, théorie des graphes, logique, algèbre, etc.).
De  façon  très  informelle,  un  automate  est  un  ensemble  “d’états  du système”, reliés entre eux par des “transitions” qui sont marquées par des symboles. Étant donné un “mot” fourni en entrée, l’automate lit les symboles du mot un par un et va d’état  en  état  selon  les  transitions.  Le  mot  lu  est  soit  accepté  par  l’automate soit rejeté.
En  dehors  de  ces  utilisations  “pratiques”  des  automates  ci-haut,  notons  qu’ils  sont aussi utilisés pour modéliser les ordinateurs et pour comprendre ce qu’un ordinateur peut faire (décidabilité) et ce qu’il sait faire efficacement (complexité). C’est donc une notion fondamentale de l’informatique.
Ce cours a donc  pour objectif, d’apprendre aux Étudiants, des futurs ingénieurs informaticiens, la notion des Automates qui sont des objets mathématiques très utilisés en informatique permettant de modéliser un grand nombre des systèmes informatiques.