АННОТАЦИЯ 4
ВВЕДЕНИЕ 6
1 Основные определения и обозначения 7
2 Минимизации автомата 11
2.1 Разбиение при помощи таблиц Pk 12
3 Описание тренажера «Минимизация конечных автоматов» 16
3.1 Логика работы тренажера 16
3.2 Проверка на изоморфизм в работе тренажера 18
3.3 Алгоритм проверки двух автоматов на изоморфизм 19
4 Описание программной реализации 21
4.1 Программная реализация тренажера «Минимизация конечных автоматов» 21
4.2 Программная реализация проверки двух автоматов на изоморфизм 25
ЗАКЛЮЧЕНИЕ 26
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 27
Приложение А_Сертификат о прохождении курса «Математика в тестировании
дискретных систем» 29
Приложение Б_Исходный код тренажера «Минимизация конечных автоматов» 30
Приложение В_Исходный код программы для проверки двух автоматов на изоморфизм 54
Конечные автоматы широко применяются при проектировании цифровых устройств, к примеру, на основе программируемых логических интегральных схем (ПЛИС). Актуальным является компактное описание работы дискретных систем при помощи конечного автомата. Поэтому возникает задача построить конечный автомат, эквивалентный исходному и имеющий наименьшее число состояний.
Умение находить минимальную форму конечного автомата важно, в частности, для построения проверяющих тестов на основе модели конечного автомата , задаче оптимизации цифровых схем и в других задачах. Данному умение обучают на одном из онлайн-курсов под названием «Математика в тестировании дискретных систем» , разработанном кафедрой информационных технологий в исследовании дискретных структур (ИТИДиС). Одна из тем, рассматриваемая в модуле 2 данного онлайн курса, является минимизация автомата. Но вместе с теоретическим материалом необходима также и практическая часть для лучшего усвоения темы. В связи с этим был проведен поиск обучающих программ/тренажеров, которые могли бы помочь в освоении данной темы; подходящих программ найдено не было.
Таким образом, целью работы является разработка тренажера , обучающего строить минимальную форму автомата. Для достижения поставленной цели в работе решаются следующие задачи:
1. Изучить курс «Математика в тестировании дискретных систем», разработанный кафедрой ИТИДиС.
2. Изучить языки HTML, CSS и JavaScript.
3. Разработать логику взаимодействия пользователя с тренажером.
4. Программно реализовать тренажер.
5. Внедрить тренажер в учебный процесс и на онлайн платформы.
В данной работе были получены следующие результаты.
Реализован тренажер «Минимизация конечных автоматов», в основу которого был положен метод минимизации конечных автоматов путем построения таблиц Pk.
Проведена апробация тренажера студентами кафедры
информационных технологий в исследовании дискретных структур и студентами онлайн курса «Математика в тестировании дискретных систем». В результате апробации были учтены пожелания и замечания.
Данный тренажер внедрен в учебный процесс в рамках курса «Теория автоматов», читаемого на кафедре информационных технологий в исследовании дискретных структур радиофизического факультета Томского государственного университета, а также добавлен в качестве неоцениваемого (тренировочного) задания в онлайн-курс «Математика в тестировании дискретных систем» на платформах Coursera и Stepik.
Результаты работы были доложены на восемнадцатой всероссийской конференции СНИИ-2021
Также был разработан алгоритм проверки двух детерминированных конечных автоматов на изоморфизм. Алгоритм реализован с использованием языка C++ и в дальнейшем планируется переписать данный алгоритм на языке JavaScript.
В качестве дальнейшего направления работы планируется модернизация тренажера: ввод минимальной формы пользователем, анализ действий пользователя (при не правильных действиях давать пользователю подробную информацию о его ошибках), увеличение числа автоматов, фиксация результата и ограничение количества попыток.
