Таблица состояний конечного автомата: научный проект для старшеклассников

Борис Феликсович Мельников; Михаил Эдуардович Абрамян; Елена Анатольевна Мельникова

doi:10.32603/2071-2340-2019-2-87-107

Борис Феликсович Мельников Совместный университет МГУ-ППИ, район Лунган, Даюньсиньчэн, ул. Гоцзидасюеюань, д. 1, 517182, Провинция Гуандун, Шенчжэнь, Китай
Михаил Эдуардович Абрамян Южный федеральный университет, ул. Большая Садовая, д. 105/42, 344006, Ростов-на -Дону, Россия
Елена Анатольевна Мельникова Российский государственный социальный университет, д. 4, стр. 1, Улица Вильгельма Пика, 129226, Москва, Россия

DOI: https://doi.org/10.32603/2071-2340-2019-2-87-107

Ключевые слова: оптимизационная задача, конечный автомат, эвристический алгоритм, первый шаг в науке

Аннотация

С конца 1960-х годов изучается задача минимизации недетерминированных конечных автоматов. В практических программах для больших размерностей получение точного ответа обычно занимает неприемлемо большое время. В связи с этим нас интересуют, среди прочих, эвристические алгоритмы решения задачи - алгоритмы, <<ничего не обещающие>>, однако на практике в большинстве случаев дающие за приемлемое время работы решение, близкое к оптимальному.
Предлагаемый школьникам проект направлен на частичное решение одной из вспомогательных задач, возникающих в упомянутой оптимизационной задаче. Для этого мы специальным образом определяем отношение эквивалентности на множестве таблиц заданного размера M x N, заполненных элементами 0 и 1. Получение количества неэквивалентных таблиц размерности 8 x 10 будет являться серьёзным шагом на пути к доказательству того факта, что описанный ещё в 1970 г. пример <<плохого>> автомата (так называемого автомата Ватерлоо) - минимально возможный пример, не имеющий <<меньших>> аналогов.
Для решения задачи мы сначала предлагаем плохой алгоритм, заключающийся в~простом переборе матриц. Этот алгоритм хорошо работает на матрицах малых размерностей, но, как обычно в подобных ситуациях, при переходе к большим размерностям он работает неприемлемо долго. Для уменьшения времени работы алгоритма мы предлагаем несколько эвристик и приводим результаты работы разных версий программы. Цель проекта - создание новых эвристик, ещё большее убыстрение времени работы программы и, по возможности, получение ответа (количества таблиц) для размерности 8 x 10.
Для большинства описываемых в статье вариантов алгоритма мы приводим реализацию на языке C#, использующую принципы объектно-ориентированного программирования. Мы предполагаем, что дальнейшая работа над проектом будет заключаться в дальнейшей модификации приведённых нами программ.

Биографии авторов

Борис Феликсович Мельников, Совместный университет МГУ-ППИ, район Лунган, Даюньсиньчэн, ул. Гоцзидасюеюань, д. 1, 517182, Провинция Гуандун, Шенчжэнь, Китай

Мельников Борис Феликсович, Доктор физико-математических наук, профессор Университета МГУ-ППИ в~Шэнчжэне, профессор Российского государственного социального университета.

Михаил Эдуардович Абрамян, Южный федеральный университет, ул. Большая Садовая, д. 105/42, 344006, Ростов-на -Дону, Россия

Абрамян Михаил Эдуардович, Кандидат физико-математических наук, доцент кафедры алгебры и дискретной математики Южного федерального университета.

Елена Анатольевна Мельникова, Российский государственный социальный университет, д. 4, стр. 1, Улица Вильгельма Пика, 129226, Москва, Россия

Мельникова Елена Анатольевна, Кандидат физико-математических наук, доцент Российского государственного социального университета.

Литература

Yu. Medvedev, A class of events that can be represented in a 1nite state machine. Automata, Moscow, USSR: Inostrannaya literatura, 1956, pp. 385–401 (in Russian).

Lectures by Turing Prize winners in their 1rst twenty years, Moscow, Russia: Mir, 1993 (in Russian).

A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, vol. 1, Moscow, USSR: Mir, 1978 (in Russian).

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Moscow, Russia: Williams, 2002 (in Russian).

T. Jiang and B. Ravikumar “Minimal NFA problems are hard,” SIAM Journal on Computing, vol. 22, no. 6, pp. 117–1141, 1993; doi: doi.org/10.1137/0222067

L. Pol´ak, “Minimalizations of NFA using the universal automaton,” International Journal of Foundation of Computer Science, vol.16, no. 5, pp. 999–1010, 2005; doi: 10.1142/S0129054105003431

T. Kameda and P. Weiner, “On the state minimization of nondeterministic 1nite automata,” IEEE Transactions on Computers, vol. C-19, no. 7, pp. 617–627, 1970; doi: 10.1109/T-C.1970.222994

S. Lombardy and J. Sakarovitch, “The universal automaton. Logic and Automata,” Amsterdam University Press, pp. 457–504, 2008.

F. Harary, Graph Theory, Editorial URSS, Moscow, Russia, 2003 (in Russian).

F. Harary and E. M. Palmer, Graphical Enumeration, Moscow, USSR: Mir, 1977 (in Russian).

R. Gera , S. Hedetniemi , C. Larson, Eds. Graph Theory. Favorite Conjectures and Open Problems — 1, Basel, Switzerland: Springer, 2016.

R. Gera, T. Haynes, S. Hedetniemi, Eds. Graph Theory. Favorite Conjectures and Open Problems — 2, Basel, Switzerland: Springer, 2018.

V. N. Dolgov and B. F. Melnikov, “¸onstruction of universal 1nite automaton. I. From theory to the practical algorithm,” Proceedings of Voronezh State University. Series: Physics. Mathematics, no. 2, pp. 173–181, 2013 (in Russian).

V. N. Dolgov and B. F. Melnikov, “Construction of universal 1nite automaton. II. Examples of algorithms functioning,” Proceedings of Voronezh State University. Series: Physics. Mathematics. no. 1, pp. 78–85, 2014. (in Russian).

B. Melnikov, “The complete 1nite automaton,” International Journal of Open Information Technologies, vol. 5, no. 10, pp. 9–17, 2017.

B. Melnikov and E. Melnikova, “Waterloo-like 1nite automata and algorithms for their automatic construction,” International Journal of Open Information Technologies, vol. 5, no. 12, pp. 8–15, 2017.

A. V. Krivolapova, E. A. Melnikova, and N. V. Sofonova, “Some supporting algorithms of construction of waterloo-like automata,” Proceedings of Voronezh State University. Series: Systems analysis and information technologies, no. 4, pp. 20–28, 2016 (in Russian).

M. E. Abramyan, B. F. Melnikov, and M. A. Trenina, “Implementation of the Branch and Bound Method for the Problem of Recovering a Distances Matrix Between DNA Strings,” Modern Information Technologies and IT-Education, vol. 15, no. 1, 2019 (in Russian).

B. Melnikov, A. Nichiporchuk, M. Trenina, and M. Abramyan, “Clustering of situations in solving applied optimization problems (on the examples of traveling salesman problem and distance matrix recovery),” International Journal of Open Information Technologies, vol. 7, no. 5, pp. 1–8, 2019.