|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Алгоритмы обхода конечных лабиринтов конечными автоматамикурсовая работа (Бакалавр)
- Научный руководитель: Волков Николай Юрьевич
- Автор: Юлдашев Руслан Алимбаевич
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2016
- Курс: 3
- Аннотация: Данная работа посвящена анализу алгоритмов обхода конечных мозаичных лабиринтов одним автоматом. Согласно результатам Будаха-Подколзина не существует автомата, обходящего любой конечный мозаичный лабиринт. В то же время не трудно по данному лабиринту построить обходящий его автомат, или автомат, обходящий все мозаичные лабиринты с n вершинами. Для этого достаточно дать автомату возможность «рисовать» пройденную часть лабиринта в своей ограниченной памяти и перемещаться, «подсматривая» в эту конечную «карту». Такой алгоритм удобен для доказательства теоремы существования автомата, обходящего данный лабиринт. Но проблема таких алгоритмов в том, что построенный таким образом автомат будет достаточно сложен с точки зрения числа его состояний и задача написания в явном виде программы или таблицы этого обходящего автомата, является очень сложной. Решается задача исследования простых и понятных алгоритмов построения автомата, обходящего данный лабиринт, поочередных «подбором» строк программы автомата. Данные алгоритмы хорошо понятны и применимы ко всем известным лабиринтам. Однако, до сих пор данные алгоритмы не имели теоретического обоснования. Данная работа призвана теоретически обосновать эти алгоритмы. Также написала компьютерная программа на языке С++, позволяющая пользователю «нарисовать» лабиринт, генерирующую автомат, согласно исследуемому алгоритму и визуализировать движение этого автомата в этом лабиринте. Программа может строить все лабиринты с n вершинами, генерировать автоматы согласно исследуемому алгоритму и проверять факт обхода этими автоматами лабиринта. Таким образом, программа может решать поставленную задачу методом компьютерного перебора.
- Добавил в систему: Волков Николай Юрьевич