Локальные вычисления на графах: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Локальные вычисления на графах''' (''Local computation on graphs'') - метод решения задач ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Локальные вычисления на графах''' (''Local computation on graphs'') - | '''Локальные вычисления на графах''' (''[[Local computation on graphs]]'') - метод решения задач на [[граф|графах]], рассматриваемых как вычислительная система, у которой каждая [[вершина]] соответствует процессору, а каждое [[ребро]] ([[дуга]]) --- каналу связи (одностороннему каналу связи). Вся начальная и вычисляемая информация хранится в вершинах в виде меток | ||
метод решения задач на графах, рассматриваемых как вычислительная | |||
система, у которой каждая вершина соответствует процессору, а каждое | |||
ребро (дуга) --- каналу связи (одностороннему каналу связи). Вся | |||
начальная и вычисляемая информация хранится в вершинах в виде меток | |||
и доступна только соседним вершинам. Всякие глобальные механизмы, | и доступна только соседним вершинам. Всякие глобальные механизмы, | ||
вроде общей памяти, отсутствуют. Успех или неуспех решения задачи | вроде общей памяти, отсутствуют. Успех или неуспех решения задачи | ||
| Строка 10: | Строка 6: | ||
в связи с развитием теории параллельных вычислений. К известным на | в связи с развитием теории параллельных вычислений. К известным на | ||
сегодня результатам следует отнести локальные алгоритмы Ю.И.Журавлева, | сегодня результатам следует отнести локальные алгоритмы Ю.И.Журавлева, | ||
локальные вычислительные | локальные вычислительные алгоритмы В.А.Евстигнеева, интеллигентные | ||
графы Э.Розенстиля и др., эхо-алгоритмы Чанга, ''системы переписывания графов'' и ряд других. | графы Э.Розенстиля и др., эхо-алгоритмы Чанга, ''системы переписывания графов'' и ряд других. | ||
==Литература== | ==Литература== | ||
{[WG'90] | {[WG'90] | ||
Версия от 12:17, 20 ноября 2009
Локальные вычисления на графах (Local computation on graphs) - метод решения задач на графах, рассматриваемых как вычислительная система, у которой каждая вершина соответствует процессору, а каждое ребро (дуга) --- каналу связи (одностороннему каналу связи). Вся начальная и вычисляемая информация хранится в вершинах в виде меток и доступна только соседним вершинам. Всякие глобальные механизмы, вроде общей памяти, отсутствуют. Успех или неуспех решения задачи зависит только от взаимодействия соседних вершин. Интерес к такого рода вычислениям поддерживается как из-за чисто научных проблем, так и в связи с развитием теории параллельных вычислений. К известным на сегодня результатам следует отнести локальные алгоритмы Ю.И.Журавлева, локальные вычислительные алгоритмы В.А.Евстигнеева, интеллигентные графы Э.Розенстиля и др., эхо-алгоритмы Чанга, системы переписывания графов и ряд других.
Литература
{[WG'90]