АВТОМАТОВ ТЕОРИЯ это:

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

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

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АВТОМАТОВ ТЕОРИЯ" в других словарях:

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

  • Автоматов теория — …   Википедия

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

  • Теория механизмов и машин — Теория машин и механизмов (ТММ) это научная дисциплина об общих методах исследования, построения, кинематики и динамики механизмов и машин и о научных основах их проектирования. Содержание 1 История развития дисциплины 2 Основные понятия …   Википедия

  • ТЕОРИЯ — (1) система научных идей и принципов, обобщающих практический опыт, отражающих объективные природные закономерности и положения, которые образуют (см.) или раздел какой либо науки, а также совокупность правил в области какого либо знания млн.… …   Большая политехническая энциклопедия

  • Теория автоматов — [automa­ta theory] раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную ин­формацию дискретными же тактами. Основными… …   Экономико-математический словарь

  • Теория автоматов — [automa­ta theory] раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную ин­формацию дискретными же тактами. Основными… …   Экономико-математический словарь

  • теория автоматов — Раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными понятиями этой теории… …   Справочник технического переводчика

  • теория автоматов — сущ., кол во синонимов: 1 • тавт (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 …   Словарь синонимов

  • Теория алгоритмов — [theory of algorithms] раздел математики, изучающий общие свойства алгоритмов. Проблема построения алгоритма с теми или иными свойствами называется алгоритмической проблемой, ее неразрешимость означает отсутствие соответствующего алгоритма; если… …   Экономико-математический словарь

Книги

Другие книги по запросу «АВТОМАТОВ ТЕОРИЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»