Базовый алгоритм восстановления конечного графа
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Базовый алгоритм восстановления конечного графа
|
|
| Creator |
Татаринов, Е.А.
|
|
| Description |
Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые понижают верхнюю оценку временной сложности. Найдены операции над графами, результирующий граф которых имеет верхнюю оценку сложности выполнения базового алгоритма не хуже, чем исходный.
Розглядається задача відновлення графа агентом, який переміщується по його ребрах, що прочитує ізмінює мітки на елементах графа. Запропоновано базовий метод відновлення. Алгоритм потребує 2 різні фарби і кубічного, від числа вершин графа, числа кроків. Знайдено модифікації алгоритму, які знижують верхню оцінку часової складності. Знайдено операції над графами, результуючий граф яких має верхню оцінку складності виконання базового алгоритму не гірше, ніж вихідний. The problem of reconstructing a graph agent moving through his edges, read and modify marks on the elements of the graph. We propose a basic method of reconstruction. The algorithm requires 2 different colors and cube of the number of vertices number of steps. Found modification of the algorithm, which lowers the upper bound of time complexity. Found the operation on graphs, the resulting graph which has an upper bound for the complexity of the basic algorithm is not worse than the original. |
|
| Date |
2017-09-15T17:35:42Z
2017-09-15T17:35:42Z 2010 |
|
| Type |
Article
|
|
| Identifier |
Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос.
1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/123970 519.5 |
|
| Language |
ru
|
|
| Relation |
Труды Института прикладной математики и механики
|
|
| Publisher |
Інститут прикладної математики і механіки НАН України
|
|