Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Курганский А. Н., Сапунов С. В. О направленном перемещении коллектива автоматов без компаса на одномерной целочисленной решетке // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2016. Т. 16, вып. 3. С. 356-365. DOI: 10.18500/1816-9791-2016-16-3-356-365

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
14.09.2016
Полный текст:
(downloads: 90)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.7

О направленном перемещении коллектива автоматов без компаса на одномерной целочисленной решетке

Авторы: 
Курганский Алексей Николаевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Сапунов Сергей Валерьевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация: 

Рассматривается задача сохранения однонаправленного движения коллективом конечных автоматов на одномерной целочисленной решетке. Автоматы не различают вершины среды по их координатным направлениям (т. е. автоматы не имеют компаса). Мы рассматриваем коллективы, состоящие из одного автомата и нескольких камней, расположение которых полностью определяется автоматом. В работе доказано, что автомат с двумя и менее камнями не может сохранять однонаправленного движения на одномерной целочисленной решетке, а автомат с тремя камнями может.

Список источников: 
  1. Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. М. : Физматлит, 2002. 288 с.
  2. Капитонова Ю. В., Кривой С. Л., Летичевский А. А., Луцкий Г. М. Лекции по дискретной математике. СПб. : БХВ-Петербург, 2004. 624 с.
  3. Novikov D. A. Cybernetics: From Past to Future. Springer, 2016. 115 p.
  4. Kline R. R. The Cybernetics Moment : Or Why We Call Our Age the Information Age. Baltimore, Maryland : Johns Hopkins Univ. Press, 2015. 352 p.
  5. 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.
  6. Глушков В. М., Летичевский А. А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики. Новосибирск : Наука, 1973. С. 5–39.
  7. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М. : Наука, 1985. 320 с.
  8. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Независимые системы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, вып. 2. С. 3– 39. DOI: https://doi.org/10.1515/156939203322385847.
  9. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Коллективы автоматов в лабиринтах // Дискретная математика. 2003. Т. 15, вып. 3. С. 3–39. DOI: https://doi.org/10.1515/156939203322694736.
  10. Стаматович Б. Распознавание односвязных цифр автоматом // Интеллектуальные системы. 1998. Т. 3, вып. 3–4. С. 281–305.
  11. Стаматович Б. Распознавание двусвязных цифр коллективом автоматов // Интеллектуальные системы. 1998. Т. 4, вып. 1–2. С. 321–337.
  12. Деглина Ю. Б., Козловский В. А., Костогрыз К. А. Автоматное распознавание оцифрованных многоугольников // Искусственный интеллект. 2004. № 3. С. 443–452.
  13. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge : Cambridge Univ. Press, 2010, 406 p.
  14. 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.
  15. 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.
  16. 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
  17. Бабичев А. В. Ориентирование в лабиринте // Автоматика и телемеханика. 2008. Вып. 2. С. 135-145. DOI: https://doi.org/10.1134/S0005117908020100.