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

Автоматів теорія - це ... Що таке Автоматів теорія?
частина теоретичної кібернетики (Див. Кібернетика), об'єктом дослідження якої є різні перетворювачі дискретної інформації; виникла на початку 50-х рр. 20 в. в зв'язку з вимогами практики проектування обчислювальних машин і з розробкою математичних моделей процесів переробки інформації в біологічних, економічних і інших системах. А. т. - самостійний розділ математики, що має різноманітну проблематику і додатки. Основними поняттями А. т. Є поняття абстрактного автомата і поняття композиції автоматів. Ці поняття є розумними абстракціями реально існуючих дискретних пристроїв - Автоматів. Поняття абстрактного автомата дозволяє характеризувати пристрій з точки зору Алгоритму його функціонування, т. Е. Алгоритму переробки інформації, який воно реалізує. Поняття композиції автоматів дозволяє характеризувати пристрій з точки зору його структури, іншими словами, дає уявлення, яким чином даний пристрій побудовано з інших, більш елементарних. А. т. Складається з ряду розділів. Один з розділів: абстрактно-алгебраїчна А. т. У цьому розділі абстрактні автомати вивчаються з точки зору дослідження їх властивостей і різних способів завдання. Абстрактним автоматом називають об'єкт А = А (u, X, Y, δ, λ), що складається з трьох непустих множин: U - станів, Х - вхідних сигналів, Y - вихідних сигналів, і двох функцій, які здійснюють однозначне відображення множини U × Х в U, δ ( а, х ) переходів і безлічі U × х в Y, λ ( а, x ) виходів.Абстрактний автомат називається кінцевим, якщо безлічі U, X , Y - кінцеві. В абстрактно-алгебраїчної А. т. Можна виділити теорію кінцевих автоматів і теорію нескінченних автоматів. Основні питання теорії кінцевих автоматів можна вважати вирішеними. Найбільш цікавими результатами теорії кінцевих автоматів є: теорема аналізу і синтезу кінцевих автоматів, яка дає характеристику подій, представлених в кінцевих автоматах, теореми про визначальні співвідношеннях в алгебрі регулярних подій, оцінки довжини експериментів з кінцевими автоматами, а також ряд результатів по дослідженню алгебраїчних властивостей абстрактних автоматів. В теорії нескінченних автоматів розглядаються різні концепції безконечних автоматів, точніше виділяються класи безконечних автоматів спеціального виду. Цей розділ важливий тісним зв'язком із загальною теорією формальних мов і граматик (див. Математична лінгвістика), а також з теорією алгоритмів (див. Алгоритмів теорія). В рамках абстрактно-алгебраїчної А. т. Намітився (кінець 60-х рр.) Підхід до вирішення проблеми створення алгебри алгоритмів і побудови апарату для формальних перетворень виразів в цій алгебрі, що дозволяє абсолютно по-новому підійти до вирішення такого роду завдань, як еквівалентність схем алгоритмів, і дає можливість ефективно вирішувати оптимізаційні завдання в проектуванні дискретних пристроїв. Іншим розділом А. т. Є структурна А. т. Тут автомат представляється у вигляді мережі, елементи якої вибираються з деякої заданої сукупності елементарних автоматів, з'єднані між собою деяким спеціальним чином і здійснюють запам'ятовування і перетворення елементарних сигналів.Основними результатами структурної А. т. Є: практична методика побудови складних логічних мереж, дослідження по асимптотическим оцінками складності їх, вирішенню проблеми повноти системи елементарних автоматів, кодування станів автоматів, оптимальної реалізації логічних мереж в різних елементних структурах і т. Д. Структурна А. т. тісно пов'язана з теорією кодування, загальною теорією переключательних функцій, теорією комбінаційних схем, теорією інформації, теорією надійності дискретних пристроїв і т. п. Тре тьім розділом А. т. є теорія імовірнісних автоматів і систем, що самоорганізуються. Основні програми А. т. Має в практиці проектування і автоматизації проектування дискретних пристроїв і, зокрема, обчислювальних машин. Вона набуває все більш важливе значення для таких класичних математичних дисциплін, як теорія алгоритмів, з одного боку, і таких сучасних теорій в математиці і кібернетиці, як теорія формальних систем, теорія програмування, теорія формальних мов і граматик - з іншого. Літ. : Автомати. Зб. ст. , Під ред. Е. Шеннона і Дж. Маккарті, пров. з англ. , М., 1956; Глушков В. М, Трахтенброт Б. А, Введення в теорію кінцевих автоматів, М., 1962; Логіка. Автомати. Алгоритми, М., 1963; Гілл А., Введення в теорію кінцевих автоматів, пров. з англ. , М. 1966. Ю. В. Капітонова.

Велика радянська енциклопедія. - М.: Радянська енциклопедія. 1969-1978.