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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні дискретні автомати — покрокові перетворювачі інформації; розділ теоретичної кібернетики.

Виникнення[ред.ред. код]

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

Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 50-х рр. XX сторіччя.

Завдання, що вирішує теорія автоматів[ред.ред. код]

Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування ЕЦОМ включно.

У дискретній математиці, інформатиці, теорія автоматів вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати.

Теорія автоматів та теорія алгоритмів[ред.ред. код]

Докладніше: Теорія алгоритмів

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

Аналіз автоматів[ред.ред. код]

Докладніше: Аналіз автоматів

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

Синтез автоматів[ред.ред. код]

Докладніше: Синтез автоматів

У синтезі автоматів формують систему з елементарних автоматів, еквівалентну заданому абстрактному автомату. Такий автомат називається структурним.

Проектування ЕЦОМ залишається основною сферою практичного застосування теорії автоматів. Завдяки успішному розв'язанню проблеми спряження етапів абстрактного й структурного синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових автоматів як єдину математичну теорію, яка в перспективі повинна охопити як єдине ціле усі ЕЦОМ з будь-яким числом їхніх станів.

Тенденції[ред.ред. код]

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

Література[ред.ред. код]


Див. також[ред.ред. код]