Базовый алгоритм восстановления конечного графа
Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые...
Збережено в:
| Опубліковано в: : | Труды Института прикладной математики и механики |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2010
|
| Онлайн доступ: | https://nasplib.isofts.kiev.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| _version_ | 1862686113171243008 |
|---|---|
| author | Татаринов, Е.А. |
| author_facet | Татаринов, Е.А. |
| citation_txt | Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики |
| 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.
|
| first_indexed | 2025-12-07T16:03:13Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-123970 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T16:03:13Z |
| publishDate | 2010 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Татаринов, Е.А. 2017-09-15T17:35:42Z 2017-09-15T17:35:42Z 2010 Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/123970 519.5 Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 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. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Базовый алгоритм восстановления конечного графа Базовий алгоритм відновлення скінченного графа Basic algorithm for reconstructing a finite graph Article published earlier |
| spellingShingle | Базовый алгоритм восстановления конечного графа Татаринов, Е.А. |
| title | Базовый алгоритм восстановления конечного графа |
| title_alt | Базовий алгоритм відновлення скінченного графа Basic algorithm for reconstructing a finite graph |
| title_full | Базовый алгоритм восстановления конечного графа |
| title_fullStr | Базовый алгоритм восстановления конечного графа |
| title_full_unstemmed | Базовый алгоритм восстановления конечного графа |
| title_short | Базовый алгоритм восстановления конечного графа |
| title_sort | базовый алгоритм восстановления конечного графа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/123970 |
| work_keys_str_mv | AT tatarinovea bazovyialgoritmvosstanovleniâkonečnogografa AT tatarinovea bazoviialgoritmvídnovlennâskínčennogografa AT tatarinovea basicalgorithmforreconstructingafinitegraph |