|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Нижняя оценка сложности задачи поиска ближайшего соседа на прямой с помощью клеточного автомата с локаторами", Вестник Московского университета. Серия 1: Математикастатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
- Авторы: Васильев Д.И., Гасанов Э.Э.
- Журнал: Вестник Московского университета. Серия 1: Математика. Механика
- Номер: 5
- Год издания: 2023
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 33
- Последняя страница: 39
- DOI: 10.55959/MSU0579-9368-1-64-5-5
- Аннотация: Рассматривается применение модели клеточного автомата с локаторами к задаче поиска ближайшего соседа на прямой. Модель клеточного автомата с локаторами подразумевает возможность каждой ячейке автомата передавать через эфир сигнал на сколь угодно большие расстояния. Ранее было показано, что такая возможность позволяет решать задачу поиска ближайшего соседа за логарифмическое время. В работе получена логарифмическая нижняя оценка для сложности этой задачи.
- Добавил в систему: Гасанов Эльяр Эльдарович