RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2017, том 29, выпуск 2, страницы 27–76 (Mi tisp210)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Общий подход к решению задач на графах коллективом автоматов

И. Б. Бурдонов, А. С. Косачев

Институт системного программирования РАН

Аннотация: Предложен общий подход к решению задач на неориентированном упорядоченном корневом связном графе коллективом автоматов, расположенных в вершинах графа и обменивающихся сообщениями по рёбрам графа. Автоматы считаются полуроботами, т.е. размер их памяти может расти вместе с ростом числа $n$ вершин и числа $m$ рёбер графа, но описание графа может не помещаться в памяти автомата. В разделе 2 классифицируются модели коллектива автоматов на графе в зависимости от размера памяти автомата, времени срабатывания автомата и ёмкости ребра (числа сообщений, одновременно перемещающихся по ребру). Выбрана модель максимального распараллеливания, в которой время срабатывания автомата считается нулевым, а ёмкость ребра неограниченной. Это позволяет получать нижние оценки сложности алгоритмов решения задач. Раздел 3 определяет правила оценки алгоритмов. В разделе 4 описаны базовые процедуры обработки сообщений и проводится классификация используемых сообщений в зависимости от маршрутов, проходимых сообщениями, и способа размножения или слияния сообщений. На основе этих процедур предлагается строить алгоритмы решения задач на графах, что демонстрируется в следующих разделах статьи. В разделах 5-9 предложены алгоритм построения остова графа, алгоритм универсального «стопора», определяющего конец работы любого алгоритма по отсутствию в графе сообщений, используемых этим алгоритмом, алгоритм построения дерева кратчайших путей, алгоритм нумерации вершин графа, и алгоритм сбора полуроботами информации о графе в неограниченной памяти автомата корня. Предложенные алгоритмы имеют линейную сложность от $n$ и $m$, и используют число сообщений, линейно зависящее от $n$ и $m$. В разделе 10 рассматривается задача поиска максимального пути в нумерованном графе, которая относится к классу NP. За счёт неограниченного (экспоненциального) числа сообщений алгоритм решения этой задачи имеет линейную сложность. В заключении подводятся итоги и намечаются направления дальнейших исследований: решение других задач на графах и расширение подхода на ориентированные графы, а также недетерминированные и динамические графы.

Ключевые слова: неориентированные графы, задачи на графах, асинхронные распределённые системы, распределенные алгоритмы.

DOI: https://doi.org/10.15514/ISPRAS-2017-29(2)-2

Полный текст: PDF файл (963 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76

Цитирование в формате AMSBIB
\RBibitem{BurKos17}
\by И.~Б.~Бурдонов, А.~С.~Косачев
\paper Общий подход к решению задач на графах коллективом автоматов
\jour Труды ИСП РАН
\yr 2017
\vol 29
\issue 2
\pages 27--76
\mathnet{http://mi.mathnet.ru/tisp210}
\crossref{https://doi.org/10.15514/ISPRAS-2017-29(2)-2}
\elib{http://elibrary.ru/item.asp?id=29118077}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp210
  • http://mi.mathnet.ru/rus/tisp/v29/i2/p27

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Игорь Бурдонов, Александр Косачев, Александр Сортов, “Распределённые алгоритмы на корневых неориентированных графах”, Труды ИСП РАН, 29:5 (2017), 283–310  mathnet  crossref  elib
    2. И. Б. Бурдонов, А. С. Косачев, “Проблема отката в ориентированной распределенной системе”, Труды ИСП РАН, 30:2 (2018), 167–194  mathnet  crossref  elib
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:140
    Полный текст:49
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020