|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чиселдипломная работа (Магистр)
- Научный руководитель: Белов Алексей Яковлевич
- Автор: Кондакова Елизавета Григорьевна
- Тип: Магистр
- Организация, в которой проходила защита: Московский Физико Технический Институт
- Год защиты: 2018
- Аннотация: Данная работа связана с задачей о поведение роботов в лабиринтах. Вопросы этой темы представляют большой интерес. Это связано с тем, что продвижения в некоторых важных задачах теоретической Computer Since могут быть получены из области поведения роботов в лабиринтах. Такое положение дел делает актуальными задачи данной тематики. Роботы в лабиринтах очень важны, в частности, им посвящено много литературы. В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Анджанса: обход роботом с генератором случайных битов целочисленных пространств при наличие камня м подпространства флажков. Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работы мы исследуем практически не изученное поведение робота с генератором случайных чисел. Представляется чрезвычайно важным перенос комбинаторных методов разработанных А. М. Райгородским в задачах этой тематики. Задачи этой темы могут принимать разные виды, но есть несколько общих частей. Основным элементом является робот или коллектив роботов. Робот - это некоторый конечный автомат, но у него может быть генератор случайных битов или память в какой-то форме. Он перемещается в некоторой среде. Её называют лабиринтом. В этой среде могут быть камни, которые робот может переносить, кроме того эта среда может быть раскрашена. Множество флагов в лабиринте, которые робот может увидеть, но не может переносить, по сути является двухцветной раскраской. В дальнейшем будем рассматривать n-цветные расскраски пространств как n-1-цветную расскраску подмножества флажков. Робот решает разные задачи такие как: встречи двух роботов, распознавание типа лабиринта и его обход, что фактически является решением нахождения клетки выхода из него. \begin{subsection}{Имеющиеся результаты для робота} В задачах ниже робот считается обходящим пространство, если для любой клетки пространства вероятность в ней побывавть равна единице. В моей бакалаврской работе были доказаны простейшие случаи возможности обхода роботом с генератором случайных чисел целочисленного пространства \begin{itemize} \item Робот обходит $\zs^2$ и не может обойти $\zs^3$ \item Робот c камнем обходит $\zs^4$ и не может обойти $\zs^5$ \item Робот c камнем и флажком обходит $\zs^6$ и не может обойти $\zs^7$ \item Робот c камнем и плоскостью флажков обходит $\zs^8$ и не может обойти $\zs^9$ \end{itemize} Аналогично решенным задачам можно показать, что робот c камнем и подпространством флажков размерности $\zs^n$ не может обойти $\zs^n+7$ Увеличение количества камней также не представляет интереса, так как робот с двумя камнями может работать, как машина Минского(это будет показано в данной работе). А машина Минского может обойти любое $\zs^n$. В связи с этим остаётся вопрос, что происходит с обходом пространства $\zs^n$ при условии размерности подпространства флажков хотя бы $n-6$ \end{subsection} \begin{subsection}{Постановка задачи} В этой работе будет доказано, что робот с генератором случайных битов и камнем может обойти $\zs^n$, если в нём будет случайно раскрашенное подпространство флажков размерности $n-6$. Подпространство флажков будем считать независимо раскрашенными в два цвета с вероятностью $\frac{1}{2}$. \end{subsection}
- Добавил в систему: Белов Алексей Яковлевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | KondakovaDiss.pdf | 500,8 КБ | 2 декабря 2018 [AlexeiBelov] | |
| 2. | Отзыв научного руководителя А.Я.Белова | RETsENZIYa_na_Kondakovu.doc | 29,0 КБ | 14 июня 2018 [AlexeiBelov] | |
| 3. | Рецензия И.А.Иванова-Погодаева | skan_retsenzii_na_dissertatsiyu_E.G.Kondakovoj_IIP.pdf | 733,3 КБ | 14 июня 2018 [AlexeiBelov] |