Значение слова "АВТОМАТОВ ТЕОРИЯ" найдено в 3 источниках

АВТОМАТОВ ТЕОРИЯ

найдено в "Большой Советской энциклопедии"

часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50-х гг. 20 в. в связи с требованиями практики проектирования вычислительных машин и с разработкой математических моделей процессов переработки информации в биологических, экономических и других системах. А. т. — самостоятельный раздел математики, имеющий разнообразную проблематику и приложения.

Основными понятиями А. т. являются понятия абстрактного автомата и понятие композиции автоматов. Эти понятия являются разумными абстракциями реально существующих дискретных устройств — Автоматов. Понятие абстрактного автомата позволяет характеризовать устройство с точки зрения Алгоритма его функционирования, т. е. алгоритма переработки информации, который оно реализует. Понятие композиции автоматов позволяет характеризовать устройство с точки зрения его структуры, иными словами, даёт представление, каким образом данное устройство построено из других, более элементарных.

А. т. состоит из ряда разделов. Один из разделов: абстрактно-алгебраическая А. т. В этом разделе абстрактные автоматы изучаются с точки зрения исследования их свойств и различных способов задания. Абстрактным автоматом называют объект А = А (U, X, Y, δ, λ), состоящий из трёх непустых множеств: U — состояний, Х — входных сигналов, Y — выходных сигналов, и двух функций, осуществляющих однозначное отображение множества U×Х в U, δ (а, х) переходов и множества U×Х в Y, λ (а, x) выходов. Абстрактный автомат называется конечным, если множества U, X, Y — конечны. В абстрактно-алгебраической А. т. можно выделить теорию конечных автоматов и теорию бесконечных автоматов. Основные вопросы теории конечных автоматов можно считать решенными.Наиболее интересными результатами теории конечных автоматов являются: теорема анализа и синтеза конечных автоматов, которая даёт характеристику событий, представленных в конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных событий, оценки длины экспериментов с конечными автоматами, а также ряд результатов по исследованию алгебраических свойств абстрактных автоматов. В теории бесконечных автоматов рассматриваются различные концепции бесконечных автоматов, точнее выделяются классы бесконечных автоматов специального вида. Этот раздел важен тесной связью с общей теорией формальных языков и грамматик (см. Математическая лингвистика), а также с теорией алгоритмов (см. Алгоритмов теория). В рамках абстрактно-алгебраической А. т. наметился (конец 60-х гг.) подход к решению проблемы создания алгебры алгоритмов и построения аппарата для формальных преобразований выражений в этой алгебре, что позволяет совершенно по-новому подойти к решению такого рода задач, как эквивалентность схем алгоритмов, и даёт возможность эффективно решать оптимизационные задачи в проектировании дискретных устройств.

Другим разделом А. т. является структурная А. т. Здесь автомат представляется в виде сети, элементы которой выбираются из некоторой заданной совокупности элементарных автоматов, соединены между собой некоторым специальным образом и осуществляют запоминание и преобразование элементарных сигналов. Основными результатами структурной А. т. являются: практическая методика построения сложных логических сетей, исследования по асимптотическим оценкам сложности их, решению проблемы полноты системы элементарных автоматов, кодированию состояний автоматов, оптимальной реализации логических сетей в различных элементных структурах и т. д. Структурная А. т. тесно связана с теорией кодирования, общей теорией переключательных функций, теорией комбинационных схем, теорией информации, теорией надёжности дискретных устройств и т. п.

Третьим разделом А. т. является теория вероятностных автоматов и самоорганизующихся систем.

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

Лит.: Автоматы. Сб. ст., под ред. Э. Шеннона и Дж. Маккарти, пер. с англ., М., 1956; Глушков В. М, Трахтенброт Б. А, Введение в теорию конечных автоматов, М., 1962; Логика. Автоматы. Алгоритмы, М., 1963; Гилл А., Введение в теорию конечных автоматов, пер. с англ., М. 1966.

Ю. В. Капитонова.

найдено в "Математической энциклопедии"

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

Большинство задач А. т.- общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и др. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства (см. Автомата поведение, Эксперименты, с автоматами). Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием (см. Синтеза задачи). К этой задаче примыкают проблемы, связанные с оценкой сложности автоматов, обладающих заданным поведением, а также с построением алгоритмов, дающих в определенном смысле оптимальные автоматы (см. Автоматов минимизация). Кроме того, применительно к классам исходных автоматов или автоматных отображений возникает проблема полноты (см. Функциональные системы, Автоматов полные системы). Задача эквивалентных преобразований ставится как для автоматов, так и для различных заданий их поведения (см. Эквивалентные преобразования). Помимо перечисленных постановок задач, общих для многих управляющих систем, в А.т. имеются специфич. проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автоматов удобно задавать на разных языках (регулярные выражения, канонич. уравнения, язык логики предикатов и т. д., см. Автоматов способы задания), в связи с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Для конечных автоматов выработаны достаточно простые алгоритмы, позволяющие по регулярным выражениям получать автоматы, представляющие соответствующие события и имеющие минимальное возможное число состояний (см. Автоматов минимизация). Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Напр., при переходе от недетерминированного автомата (источника), представляющего (порождающего) регулярное множество слов, к конечному автомату, представляющему это же множество, число состояний может возрастать как показательная функция. Специальный раздел А. т. связан с так наз. экспериментами с автоматами. Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах контроля автоматов (см. Надежность и контроль управляющих систем). В разделах игры автоматов и автоматов поведение в случайной среде рассматриваются вопросы взаимодействия автоматов друг с другом или с определенными внешними средами. Многие из перечисленных выше задач могут рассматриваться как массовые (алгоритмические) проблемы. Для конечных автоматов большинство из них имеет положительное решение.

А. т. находит применение как в других областях математики, так и в решении практич. задач. Напр., средствами А. т. доказывается разрешимость нек-рых формальных исчислений. Применение методов и понятий А. т. к изучению формальных и естественных языков привело к возникновению раздела теории алгоритмов - математической лингвистике. Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение А. т. в различных научных и прикладных исследованиях.

Лит.:[1] Автоматы. Сб. ст., пер. с англ., М., 1956; [2] Глушков В. М., Синтез цифровых автоматов, М., 1962; [3] Трахтенброт Б. А., Барздинь Я. М., Конечные автоматы, М., 1970. В. Б. Кудрявцев, Ю. И. Янов.

найдено в "Русско-белорусском математическом словаре"

аўтаматаў тэорыя

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z