Для цитирования:
Курганский А. Н., Сапунов С. В. О направленном перемещении коллектива автоматов без компаса на одномерной целочисленной решетке // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2016. Т. 16, вып. 3. С. 356-365. DOI: 10.18500/1816-9791-2016-16-3-356-365, EDN: WMIIJZ
О направленном перемещении коллектива автоматов без компаса на одномерной целочисленной решетке
Рассматривается задача сохранения однонаправленного движения коллективом конечных автоматов на одномерной целочисленной решетке. Автоматы не различают вершины среды по их координатным направлениям (т. е. автоматы не имеют компаса). Мы рассматриваем коллективы, состоящие из одного автомата и нескольких камней, расположение которых полностью определяется автоматом. В работе доказано, что автомат с двумя и менее камнями не может сохранять однонаправленного движения на одномерной целочисленной решетке, а автомат с тремя камнями может.
- Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. М. : Физматлит, 2002. 288 с.
- Капитонова Ю. В., Кривой С. Л., Летичевский А. А., Луцкий Г. М. Лекции по дискретной математике. СПб. : БХВ-Петербург, 2004. 624 с.
- Novikov D. A. Cybernetics: From Past to Future. Springer, 2016. 115 p.
- Kline R. R. The Cybernetics Moment : Or Why We Call Our Age the Information Age. Baltimore, Maryland : Johns Hopkins Univ. Press, 2015. 352 p.
- Shannon Cl. E. Presentation of a maze-solving machine // Cybernetics: Circular, Causal and Feedback Mechanisms in Biological and Social Systems: Transactions of VIII Conference. N. Y. : Josiah Macy Jr. Foundation, 1952. P. 169–181.
- Глушков В. М., Летичевский А. А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики. Новосибирск : Наука, 1973. С. 5–39.
- Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М. : Наука, 1985. 320 с.
- Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Независимые системы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, вып. 2. С. 3– 39. DOI: https://doi.org/10.1515/156939203322385847.
- Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Коллективы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, вып. 3. С. 3–39. DOI: https://doi.org/10.1515/156939203322694736.
- Стаматович Б. Распознавание односвязных цифр автоматом // Интеллектуальные системы. 1998. Т. 3, вып. 3–4. С. 281–305.
- Стаматович Б. Распознавание двусвязных цифр коллективом автоматов // Интеллектуальные системы. 1998. Т. 4, вып. 1–2. С. 321–337.
- Деглина Ю. Б., Козловский В. А., Костогрыз К. А. Автоматное распознавание оцифрованных многоугольников // Искусственный интеллект. 2004. № 3. С. 443–452.
- Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge : Cambridge Univ. Press, 2010, 406 p.
- Blum M., Kozen D. On the Power of the Compass // SFCS ’78 Proc. 19th Annu. Symp. Found. Comput. Sci. IEEE Computer Society Washington, 1978. P. 132–142. DOI: https://doi.org/10.1109/SFCS.1978.30.
- Donald B. R. The Compass That Steered Robotics // Logic and Program Semantics. Springer, 2012. P. 50–65. DOI: https://doi.org/10.1007/978-3-642-29485-3-5.
- Bhatt S., Even S., Greenberg D., Tayar R. Traversing Directed Eulerian Mazes // J. Graph Algorithms and Appl. 2002. Vol. 6, № 2. P. 157– 173. DOI: https://doi.org/10.7155/jgaa.00049
- Бабичев А. В. Ориентирование в лабиринте // Автоматика и телемеханика. 2008. Вып. 2. С. 135-145. DOI: https://doi.org/10.1134/S0005117908020100.
- 826 просмотров