Чебышевский сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сборник, 2019, том 20, выпуск 3, страницы 296–315
DOI: https://doi.org/10.22405/2226-8383-2018-20-3-296-315
(Mi cheb813)
 

Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел

Е. Г. Кондаковаa, А. Я. Канель-Беловbc

a Московский физико-технический институт (г. Москва)
b Университет Бар-Илана (г. Рамат-Ган, Израиль)
c Колледж математики и статистики, Шэньчжэньский университет, Шэньчжэнь, 518061, Китай
Список литературы:
Аннотация: Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами. Они могут отличаться как типом лабиринта (это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством. В частности у конечного автомата может быть память (магазин) или генератор случайных битов. В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное. Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать". Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.
В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [4]. Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работе мы исследуем практически не изученное поведение робота с генератором случайных чисел. Представляется чрезвычайно важным перенос комбинаторных методов, разработанных А. М. Райгородским в задачах этой тематики.
Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов. Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности. В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах. В частности доказано, что робот обходит $\mathbb{Z}^2$ и не может обойти $\mathbb{Z}^3$; робот c камнем обходит $\mathbb{Z}^4$ и не может обойти $\mathbb{Z}^5$; робот c камнем и флажком обходит $\mathbb{Z}^6$ и не может обойти $\mathbb{Z}^7$; робот c камнем и плоскостью флажков обходит $\mathbb{Z}^8$ и не может обойти $\mathbb{Z}^9$.
Ключевые слова: обход лабиринта, конечный автомат.
Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01377
Работа поддержана Российским Научным Фондом (грант № 17-11-01377).
Поступила в редакцию: 05.10.2019
Принята в печать: 12.11.2019
Тип публикации: Статья
УДК: 519.713
Образец цитирования: Е. Г. Кондакова, А. Я. Канель-Белов, “Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел”, Чебышевский сб., 20:3 (2019), 296–315
Цитирование в формате AMSBIB
\RBibitem{KonKan19}
\by Е.~Г.~Кондакова, А.~Я.~Канель-Белов
\paper Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел
\jour Чебышевский сб.
\yr 2019
\vol 20
\issue 3
\pages 296--315
\mathnet{http://mi.mathnet.ru/cheb813}
\crossref{https://doi.org/10.22405/2226-8383-2018-20-3-296-315}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/cheb813
  • https://www.mathnet.ru/rus/cheb/v20/i3/p296
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:324
    PDF полного текста:166
    Список литературы:46
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024