Теория автоматов

Теория автоматов - логико-математическая теория, объектом исследования которой являются абстрактные дискретные автоматы - пошаговые преобразователи информации; раздел теоретической кибернетики.


1. Возникновение

Возникновение и развитие теории автоматов связанные с созданием технических средств автоматического управления, проектированием сложных дискретных вычислительных систем с программным управлением, разработкой математических моделей процессов переработки информации в сложных динамических системах подобное.

Как целостная конструктивная структурная теория теория автоматов сложилась в начале 50-х гг XX века.


1.1. Задачи, решает теория автоматов

Круг проблем, решаемых теорией автоматов, достаточно широк: от проблем "геделивського типа" ( полнота, разрешимость т.п.) к проблемам самосовершенствования, самоорганизации, самопроектирования ЭЦВМ включительно.

В дискретной математике, информатике, теория автоматов изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать.


2. Теория автоматов и теория алгоритмов

Теория автоматов теснейшим образом связана с теорией алгоритмов. Это объясняется тем, что автомат превращает дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного алгоритма. Эти преобразования возможны с помощью технических и / или программных средств. Автомат можно представить как некоторое устройство (черный ящик), на который подаются входные сигналы и снимаются выходные, и который, к тому же, может иметь некоторые внутренние состояния.


3. Анализ автоматов

В анализе автоматов изучают их реакцию на различные стимулы и минимизируют количество состояний автомата для работы по заданному алгоритму. Такой автомат называют абстрактным.

4. Синтез автоматов

В синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называется структурным.

Проектирование ЭЦВМ остается основной сферой практического применения теории автоматов. Благодаря успешному решению проблемы сопряжения этапов абстрактного и структурного синтезов, достижением теории надежного и блочного синтеза стало возможным изложить теорию синтеза цифровых автоматов как единую математическую теорию, которая в перспективе должна охватить как единое целое все ЭЦВМ с любым числом их состояний.


5. Тенденции

Современной теории автоматов свойственна тенденция к интенсивному развитию прежде всего тех ее разделов, которые возникли скорее в связи с внутренней необходимостью разработки аппарата самой теории, чем благодаря практическим потребностям. В широком смысле теория автоматов охватывает не только теорию дискретных, но и теории непрерывных (аналоговых) и гибридных автоматов.

Литература



См.. также