Масштабный обзор актуальных исследований конечных автоматов подготовят ученые Уральского федерального университета (УрФУ, Екатеринбург) под руководством заведующего кафедрой алгебры и фундаментальной информатики Михаила Волкова. Систематизировать знания и впервые представить системный обзор на русском языке поможет грант Российского фонда фундаментальных исследований (РФФИ).
В теории алгоритмов автоматом называется абстрактная математическая модель устройства, которое, принимая, преобразуя и передавая входящие сигналы, переходит из одного состояния в другое. Мысль о том, что автоматы функционируют не сами по себе, а под воздействием окружающей их среды, и что результат взаимодействия зависит как от изначального внутреннего состояния автомата, так и от сигналов, которые он получает извне, выдвинута в далеком 1936 году британским математиком Аланом Тьюрингом в ставшей знаменитой статье «О вычислимых числах, с приложением к проблеме разрешимости».
Революционность подхода Тьюринга заключалась в переносе на математические системы свойства организмов — реагировать в зависимости от внутреннего состояния и качеств внешних воздействий.
Открытия гениального британца полностью изменили нашу жизнь — положили начало программированию, создали условия для появления компьютеров, торговых автоматов, мобильных телефонов и других гаджетов. Все это — реализации в физических устройствах математической концепции автомата: кофейный автомат, когда мы выбираем и оплачиваем сорт напитка, последовательно переходит от состояния ожидания к состоянию приготовления и выдачи порции кофе; компьютер выходит из состояния ожидания, когда мы вводим слова на клавиатуре или щелкаем мышкой, и так далее.
«Мы знаем, что автомат может находиться в разных состояниях, но нам далеко не всегда известно, в каком конкретно состоянии находится тот или иной автомат. Как уменьшить или устранить эту неопределенность? Задачу решает синхронизация автоматов. Синхронизируемые автоматы — это математические или технические системы, которые исходя из своего внутреннего, скрытого от нас состояния переходят в новое, заранее известное нам состояние под воздействием набора наших сигналов», — описывает Михаил Волков, УрФУ.
По словам Волкова, в 1950-60-х годах такая задача стояла перед разработчиками искусственных спутников Луны. На время, когда спутник заходил в невидимую зону, связь с ним и контроль над его состоянием утрачивались. При появлении спутника было необходимо привести его в заранее известное состояние, синхронизировать, что и делалось с помощью сигналов с Земли.
В наше время синхронизация играет большую роль при тестировании протоколов передачи данных, в разработке и отладке электронных устройств, таких как мобильные телефоны. На этом участке науки заметный вклад принадлежит российским ученым, в том числе Михаилу Волкову и его воспитанникам. Волков — всемирно признанный научный авторитет, соавтор фундаментальной справочной книги по теории автоматов.
«Теория автоматов — одно из тех направлений, в которых наш университет занимает ведущие позиции. По данной тематике моими учениками и научными „внуками“ защищено около десятка диссертаций, — рассказывает Михаил Владимирович. — Например, очевидно, что эффективность синхронизации зависит от скорости операций. Недавно мой ученик, кандидат физико-математических наук Михаил Берлинков решил важную научную проблему, нетривиально доказав, что в среднем типичный автомат синхронизируется достаточно быстро. Это крупное достижение всего последнего десятилетия».
Идеи Михаила Берлинкова развивает аспирант Павел Агеев. Дело в том, что реализация стандартного алгоритма синхронизации требует времени, квадратичного по отношению к размеру автомата: для автомата с десятью состояниями понадобится 100 единиц времени, для автомата со 100 состояниями — 10 тысяч единиц времени, а для автомата с тысячью состояний — миллион единиц и так далее. Поэтому для автоматов большого размера этот алгоритм работает медленно и фактически оказывается непригодным.
«Алгоритм, который воплощен Павлом Агеевым в работающей программе, „укладывается“ в линейное время: для автоматов с тысячей состояний это некая константа, умноженная на тысячу единиц времени, для автоматов с миллионом состояний — та же константа, умноженная на миллион единиц времени. Эксперименты подтвердили, что новый алгоритм работает намного быстрее, начиная с автоматов с небольшим числом состояний, порядка 30, — объясняет Волков. — Работа Агеева также значима — и в научном смысле, и в прикладном. В сложных программных системах, если рассматривать их как автоматы, очень много состояний — десятки и сотни тысяч. Сейчас понятно, что в принципе есть возможности синхронизировать и тестировать их относительно быстро».
В настоящее время Михаил Волков работает над созданием обширного исторического обзора исследований, открытий и изобретений в области синхронизации конечных автоматов.
«Одиннадцать лет назад я опубликовал подобную работу на английском языке. Но за эти годы в данной области математики появилось много нового, а системного обзора на русском языке до сих пор нет», — поясняет Михаил Владимирович.
Проект Волкова, по итогам конкурса более чем 3,3 тысяч заявок, поддержан грантом РФФИ.
УрФУ — один из ведущих университетов России, участник проекта 5-100, расположен в Екатеринбурге — столице летней Универсиады-2023. Вуз выступает инициатором создания и выполняет функции проектного офиса Уральского межрегионального научно-образовательного центра мирового уровня (НОЦ), который призван решить задачи национального проекта «Наука».
