Базовый алгоритм восстановления конечного графа
Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2010
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/123970 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-123970 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1239702017-09-16T03:03:57Z Базовый алгоритм восстановления конечного графа Татаринов, Е.А. Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 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. 2010 Article Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/123970 519.5 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые понижают верхнюю оценку временной сложности. Найдены операции над графами, результирующий граф которых имеет верхнюю оценку сложности выполнения базового алгоритма не хуже, чем исходный. |
| format |
Article |
| author |
Татаринов, Е.А. |
| spellingShingle |
Татаринов, Е.А. Базовый алгоритм восстановления конечного графа Труды Института прикладной математики и механики |
| author_facet |
Татаринов, Е.А. |
| author_sort |
Татаринов, Е.А. |
| title |
Базовый алгоритм восстановления конечного графа |
| title_short |
Базовый алгоритм восстановления конечного графа |
| title_full |
Базовый алгоритм восстановления конечного графа |
| title_fullStr |
Базовый алгоритм восстановления конечного графа |
| title_full_unstemmed |
Базовый алгоритм восстановления конечного графа |
| title_sort |
базовый алгоритм восстановления конечного графа |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2010 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/123970 |
| citation_txt |
Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT tatarinovea bazovyjalgoritmvosstanovleniâkonečnogografa |
| first_indexed |
2023-10-18T20:45:23Z |
| last_indexed |
2023-10-18T20:45:23Z |
| _version_ |
1796151026939592704 |