Éd. 1971-1976

automates (théorie des) (suite)

La fonction séquentielle ne fournit aucun renseignement explicite sur la structure interne de l’automate, et la question est alors de savoir quelles conclusions on peut tirer au sujet de l’espace d’état Q d’une boîte noire à partir d’expériences, quand seuls sont connus les alphabets X et Y et le fait qu’il s’agit d’un automate fini. L’apport fondamental de cette théorie est l’identification : quand le nombre maximal d’états possibles est connu, un algorithme (l’équivalence de Nérode, 1958) permet de constituer à partir d’un nombre fini d’expériences le quintuple d’un automate initialisé réalisant la même fonction séquentielle (« simulant » la boîte noire). Son espace d’état est alors l’ensemble des paramètres formels qui suffisent à prédire la sortie finale de la boîte noire pour n’importe quel mot d’entrée.

Décompositions

La synthèse des machines logiques requiert des méthodes de réalisation d’un automate par interconnexion de sous-automates dotés de propriétés avantageuses. Deux modes d’interconnexion sont envisageables. Lorsque les sous-automates opèrent en cascade, le flot d’information est unidirectionnel et la décomposition est « sans boucle ». L’automate de poupe A₁, gouverne l’automate de proue A₂. Selon les cas, cette interconnexion peut se simplifier en type série ou parallèle.

Lorsque les sous-automates opèrent en tourbillon, une boucle de réinformation (réaction ou feedback) accroît la complexité et les possibilités de l’automate résultant.

Le semi-groupe

Le point de vue algébrique consiste à considérer l’automate comme un ensemble de transformations induites par les signaux d’entrée et à en étudier les propriétés mathématiques. Or, un semi-groupe S est un ensemble d’éléments (s, s′, s″...) tel qu’à toute paire ordonnée (s, s′) corresponde un élément noté ss′ de S et satisfaisant à l’axiome d’associativité : [(s, s′), s″] = [s, (s′, s″)] = ss′s″. Un automate abstrait est alors une fonction de sortie σ sur un semi-groupe fini S. Le passage du point de vue expérimental au point de vue abstrait est effectué par un algorithme d’identification (la congruence de Myhill, 1960) associant à toute fonction séquentielle un semi-groupe.

Acceptabilité

Un automate fini peut effectuer la « reconnaissance » d’un sous-ensemble L de mots de X*, s’il les accepte, en émettant un symbole (oui) de Y, mais rejette les autres (non). Un automate reconnaisseur accepte un ensemble de mots L dit « régulier ». Pour accepter des ensembles plus complexes (langages), d’autres types d’automates doivent être définis (automates à pile, automates stochastiques). La machine de Turing (1936) est l’interconnexion d’un automate fini A et d’une bande de mémoire B potentiellement infinie, munie d’une tête de lecture et d’écriture mobile commandée par A. Si la machine, partie de l’état q₀ avec un mot m de X* sur la bande, s’arrête en écrivant un symbole d’acceptation, le mot m appartient à un ensemble dit « récursif ». Cette machine formalise tout calcul que peut effectuer un homme appliquant un algorithme A ou bien un calculateur numérique exécutant des instructions sur des données m.

M. D.

C. E. Shannon et J. McCarthy, Automata Studies (Princeton, 1956). / R. D. Luce, R. R. Bush et E. Galanter, Handbook of Mathematical Psychology (New York, 1963-1965 ; 3 vol.). / E. F. Moore, Sequential Machines. Selected Papers (Reading, Mass., 1964). / J. F. Hart et S. Takasu (sous la dir. de), Systems and Computer Science (Toronto, 1967). / M. A. Arbib (sous la dir. de), Algebraic Theory of Machines, Languages and Semigroups (New York, 1968).

automatique

Ensemble des disciplines théoriques et technologiques qui interviennent dans la conception et la construction des divers systèmes automatiques.

On peut la considérer comme l’aspect technique de la cybernétique, théorie de la commande et de la communication chez l’animal et la machine. Elle présente des liens étroits avec d’autres disciplines scientifiques, telles que les mathématiques, les statistiques, la théorie de l’information, l’informatique, la recherche opérationnelle, ainsi qu’avec toutes les sciences et techniques de l’ingénieur, tout particulièrement l’instrumentation. On distingue l’automatique théorique, constituée par l’ensemble des méthodes mathématiques d’analyse et de synthèse des systèmes automatiques et de leurs éléments, et l’automatique appliquée, qui traite les problèmes pratiques d’automatisation en s’appuyant sur la théorie, et sur la technologie des capteurs (instrumentation), des amplificateurs, des actionneurs et des ordinateurs.

Structure générale des systèmes automatiques

Les notions fondamentales relatives aux systèmes automatiques peuvent être mises en évidence à la lumière d’un exemple familier, l’ascenseur. Lorsque le passager enfonce le bouton de l’étage où il désire se rendre, l’information de commande, constituée par le niveau désiré de la cabine, matérialisé par le niveau de l’étage de destination, est enregistrée dans un organe de mémoire souvent constitué, encore actuellement, par des relais électromagnétiques. D’autre part, le niveau actuel de la cabine, qui constitue une information d’état, est également enregistré dans un autre organe de mémoire. La comparaison du niveau actuel avec le niveau désiré, qui constitue une opération élémentaire de traitement de l’information, permet de donner à l’actionneur, constitué par le moteur du treuil, un ordre de mise en marche dans le sens convenable. Cependant, le mouvement ne démarre effectivement que si toutes les portes palières sont fermées et si la charge de la cabine ne dépasse pas la valeur maximale prescrite (information d’état supplémentaire) ; cette information d’état spéciale, dite « de sécurité », est fournie par des capteurs généralement constitués par des contacts électriques (contacts témoins de fermeture des portes et contact dynamométrique de charge de la cabine). Une fois la cabine en route, d’autres capteurs à contacts indiquent son passage au droit de chaque étage ; cette information, associée au sens de marche, permet de tenir à jour le contenu de la mémoire du niveau actuel de la cabine. Lorsque ce contenu devient égal au niveau désiré, le système de commande du treuil reçoit un ordre de ralentissement, puis d’arrêt.