Большая Советская Энциклопедия (цитаты)

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

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

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

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

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

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

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

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

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


Для поиска, наберите искомое слово (или его часть) в поле поиска


Новости 03.08.2021 20:24:27
20:09 Партия Порошенко призвала расследовать гибель лидера белорусских эмигрантов
20:07 Рожденная мужчиной женщина осознала свою идентичность в 34 года и сохранила брак
20:07 Реакцию борца на поражение от россиянина в финале Олимпиады посчитали слабостью
20:06 На дом главы Минобороны Афганистана напали и взорвали автомобиль
20:06 Москвичам объяснили редкое погодное явление в небе над городом
20:04 Индия отстала в борьбе за чистый воздух
20:01 Внутри печени человека нашли неизвестные структуры
19:54 PepsiCo избавится от Tropicana
19:53 Расследование подтвердило сексуальные домогательства губернатора Нью-Йорка
Больше новостей
2 августа 2021Культура Pepsi, пейджер, MTV. Как Россия полюбила «ВИА Гру», «Брата 2» и «Бандитский Петербург», но возненавидела Децла и рэп
СегодняСреда обитания Убийственная мгла. Как месторождение угля разрушило благополучие американского города и погубило его жителей
СегодняПутешествия Советская сказка. Что ждет россиян в Азербайджане и почему там должен побывать каждый
18:24 Порка связанных россиянок крапивой во дворе частного дома попала на видео
19:47 Спасение чудом выжившего водителя из-под упавшей с ЦКАД фуры попало на видео
19:46 Ведущий Первого канала вспомнил поход в гости к Путину
СегодняИнтернет и СМИ Раздвоение личностей. Хакеры взяли на вооружение системы распознавания лиц. Чем это опасно для миллионов людей?
31 июля 2021Наука и техника На Большом адронном коллайдере открыли новую форму материи. Почему ученые не понимают, с чем они столкнулись?
19:44 ФСБ показала видео задержания консула Эстонии
18:14 Карасин прокомментировал признание сертификатов использующих «Спутник V» стран
19:38 Эвакуация электросамоката в центре Москвы удивила горожан
СегодняМоя страна Край земли и острова дымящихся вулканов. Как русские первопроходцы покоряли Камчатку и какие опасности их поджидали?
1 августа 2021Спорт Белорусскую бегунью исключили из олимпийской сборной после критики в адрес чиновников. Ее хотели насильно вывезти в Минск
19:36 Британка «случайно» стала хозяйкой известного дома
19:34 Девушка продала полметра волос, отрезала их на камеру и прославилась в сети
19:25 Российскую судью назначили на финал футбольного турнира Олимпиады
2 августа 2021Ценности Резиновая мечта. Как «кроксы» превратились из обуви для моряков в модный тренд и принесли миллионы своим создателям
2 августа 2021Силовые структуры Бизнес на крови. Как жестокая банда из Подмосковья зарабатывала миллионы на квартирах и заказных убийствах
18:02 Google перестанет работать на старых смартфонах
19:20 Россияне заявили о желании полететь в Турцию вопреки пожарам
19:20 Доказано существование искусства у неандертальцев
2 августа 2021Россия «От него осталась лишь оболочка» Что ждет семьи смертельно больных людей в России и как им помочь?
1 августа 2021Россия Хвостатые в беде. Как в России спасают брошенных животных. Истории надежды, любви и преданности
18:01 Задержанный после «укола» школьницы мужчина угощал ее наркотиками
19:16 Украинский радикал рассказал о помощи убитому лидеру белорусских эмигрантов
19:16 ФСБ раскрыла планы эстонского консула получить закрытую информацию об Арктике
29 июля 2021Из жизни «Я поняла, что покончу с собой» Что вынуждает горожан уходить в леса, надевать шкуры и жить как первобытные люди
2 августа 2021Экономика Телки — на выход. Доминированию коров в сельском хозяйстве приходит конец. Как их заменят козы и почему это выгодно?
16:47 В Португалии арестовали 79-летнюю главу наркокартеля
19:02 Мэтт Дэймон пожалел об использовании гомофобных ругательств
19:09 Москвичка попыталась покончить с собой в прямом эфире
2 августа 2021Культура «Люди боялись его. Он внушал ужас» Слежка, травля, угрозы. Как Харви Вайнштейн годами избегал наказания за домогательства
30 июля 2021Спорт «Проверьте их на допинг!» Почему россияне терпят нападки на Олимпиаде в Токио и за что их хвалят иностранцы
18:53 Россия выдала Германии опасного преступника
19:06 Редкое заболевание заставило мужчину ощущать угрозу от крошечных человечков
18:51 Названы задающие главные модные тренды звезды
1 августа 2021Моя страна «Вдруг я понимаю: это следы медведя» Как москвичка изменила свою жизнь, чтобы объездить Россию и снять ее с дрона
1 августа 2021Силовые структуры Ловушка для фрау Марты. Как советский разведчик обольщал жен немецких политиков и получал секреты Третьего рейха
19:02 Популярный ведущий раскритиковал Собчак и упрекнул ее в низости
18:46 Лидера «Яблока» в Пскове Льва Шлосберга сняли с выборов в областное собрание
18:49 России предрекли исчезновение тайги
2 августа 2021 Монстры Поднебесной: самые удивительные машины Китая Король Нюрбургринга, хищная «стрекоза» и кроссовер-супергибрид
Сегодня Мощный кроссовер за 3 миллиона: Tugella vs Tiguan Битва китайского фрешмена против немецкой суперзвезды
18:44 В США придумали новый способ заработать миллионы долларов на криптовалюте
18:49 Франция вакцинирует всех мигрантов к концу августа
18:42 Россиянам назвали оптимальную стоимость билетов в Турцию в августе
1 августа 2021Россия Что изменится в жизни россиян в августе: индексация пенсий, отмена техосмотра и новые выплаты на детей
31 июля 2021Из жизни Убийца-хамелеон. Полиция 12 лет гонялась за неуловимой преступницей. Перехитрив всех, она унесла свои тайны в могилу
18:46 Старое фото заставило москвичей вспомнить очереди в городские парки
18:34 Байден назвал героями покончивших с собой полицейских-защитников Капитолия
18:42 В «Векторе» назвали долю заболевших после второй прививки от коронавируса
31 июля 2021Мир Пандемия из пробирки. Мог ли коронавирус утечь из китайской лаборатории и почему эта версия набирает популярность?
1 августа 2021Культура «Людей станут массово вытеснять» Кто в ближайшем будущем потеряет работу из-за искусственного интеллекта?
18:24 Нурмагомедов отреагировал на нападки Макгрегора
18:39 Вице-президент США отправится в Азию для борьбы с китайским влиянием
18:21 Подмосковные спасатели вытащили севшую в лужу корову
1 августа 2021Спорт «Нужно было начать новую жизнь» Как на Олимпиаде в Токио появилась сборная беженцев и от чего сбежали эти спортсмены?
31 июля 2021Культура «Его сверхспособности — идиотские» Как режиссер «Отряда самоубийц» воскресил главный кинопровал десятилетия?
18:32 Лейтенанта задержали по подозрению в изнасиловании россиянки в отделе полиции
18:20 Рестораны и фитнес-залы в Нью-Йорке закроют от непривитых граждан
18:30 Зеленский взял под личный контроль дело об убийстве лидера белорусских мигрантов
31 июля 2021Россия «Сейчас танки войдут, все разбегутся» В 1994 году российских солдат послали в Грозный и бросили. Кому это было выгодно?
30 июля 2021Бывший СССР Слили в трубу. Как сделка США и Германии по «Северному потоку-2» заставит Украину изменить отношение к России?
18:19 Украина поможет семье белорусской легкоатлетки Тимановской
18:21 Рэпера Диззи Раскала обвинили в нападении на женщину
18:15 В России объяснили обращение грузинской партии за помощью к Путину
30 июля 2021Россия «Я такого не видел никогда» В Карелии бушуют лесные пожары. Как местные жители выживают посреди огненной стихии
31 июля 2021 ПромоКарта без пластика. Современные технологии научили россиян платить по-новому. Как на это отреагировал большой бизнес?
18:19 В Верховной Раде предложили вернуть Украине славу «устричного гиганта»
18:14 Мужчина восемь лет не расставался с чучелом собаки и нашел с его помощью любовь
18:17 Рассказавшую об уколе незнакомца школьницу угостили лекарством от эпилепсии
29 июля 2021Наука и техника «У нас героем становится любой» Кем были Герои Советского Союза, за что их лишали званий и казнили?
17:52 Мужчина неверно записал номер и годами отправлял личные заметки незнакомцу
18:14 Известный блогер показал вотчину самого богатого человека России
18:06 Бывший чемпион Bellator из России выступит на одном турнире с Емельяненко
17:54 Украина заработает на хранении ненужной нефти