Теорія автоматів
Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні дискретні автомати — покрокові перетворювачі інформації; розділ теоретичної кібернетики.
Зміст |
Виникнення [ред.]
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматичного керування, проектуванням складних дискретних обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 50-х рр. XX сторіччя.
Завдання, що вирішує теорія автоматів [ред.]
Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування ЕЦОМ включно.
У дискретній математиці, інформатиці, теорія автоматів вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати.
Теорія автоматів та теорія алгоритмів [ред.]
Теорія автоматів якнайтісніше пов'язана з теорією алгоритмів. Це пояснюється тим, що автомат перетворює дискретну інформацію по кроках у дискретні моменти часу і формує результуючу інформацію по кроках заданого алгоритму. Ці перетворення можливі за допомогою технічних та/або програмних засобів. Автомат можна уявити як деякий пристрій (чорна скринька), на який подаються вхідні сигнали і знімаються вихідні, і який, до того ж, може мати деякі внутрішні стани.
Аналіз автоматів [ред.]
В аналізі автоматів вивчають їх реакцію на різні стимули та мінімізують кількість станів автомата для роботи згідно із заданим алгоритмом. Такий автомат називають абстрактним.
Синтез автоматів [ред.]
У синтезі автоматів формують систему з елементарних автоматів, еквівалентну заданому абстрактному автомату. Такий автомат називається структурним.
Проектування ЕЦОМ залишається основною сферою практичного застосування теорії автоматів. Завдяки успішному розв'язанню проблеми спряження етапів абстрактного й структурного синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових автоматів як єдину математичну теорію, яка в перспективі повинна охопити як єдине ціле усі ЕЦОМ з будь-яким числом їхніх станів.
Тенденції [ред.]
Сучасній теорії автоматів властива тенденція до інтенсивного розвитку насамперед тих її розділів, які виникли скоріше у зв'язку з внутрішньою необхідністю розробки апарату самої теорії, ніж завдяки практичним потребам. У широкому розумінні теорія автоматів охоплює не лише теорію дискретних, а й теорії неперервних (аналогових) і гібридних автоматів.
Література [ред.]
- «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973, рос. вид. 1974;
- «Філософський словник» / За ред. В. І. Шинкарука. — 2.вид., перероб. і доп. — К.: Голов. Ред. УРЕ, 1986.
