Согласование (информатика)
 |
«Согласование » в разработке алгоритмов — это метод, который переплетает различные вычисления , выполняя их по существу одновременно. Алгоритмы, использующие согласование, иногда называют согласующими хвостами .
Примеры
[ редактировать ]Рассмотрим дерево , которое потенциально содержит путь бесконечной длины (но каждый узел имеет только конечное число дочерних элементов): если в этой среде выполняется поиск в глубину , поиск может двигаться вниз по бесконечному пути и никогда не возвращаться, потенциально оставляя часть дерево неизведанное. Однако если используется поиск в ширину , существование бесконечного пути больше не является проблемой: каждый узел посещается с разветвлением в соответствии с его расстоянием от корня, поэтому бесконечный путь повлияет только на часть пути. поиск, путешествуя по этому пути.
Мы можем рассматривать это дерево как аналог набора программ; в этом случае подход «сначала в глубину» соответствует запуску одной программы за раз и переходу к следующей только после завершения работы текущей программы. В случае, когда одна из программ работает бесконечное количество времени, этот переход никогда не произойдет. Подход в ширину, при котором посещение каждого дочернего элемента на одном уровне дерева является примером согласования, когда для каждой программы выполняется один шаг перед переходом к следующей. Таким образом, прогресс достигается в каждой программе, независимо от потенциального существования незавершающейся программы.
Другой пример — моделирование недетерминированной машины Тьюринга M с помощью детерминированной машины (например, универсальной машины Тьюринга ). В таком случае нам нужно использовать согласование, если одна из ветвей вычислений M содержит бесконечный цикл.
Бесконечно много одновременных вычислений
[ редактировать ]В случае бесконечного числа программ, потенциально бесконечно длинных, ни принцип «сначала в ширину», ни «сначала в глубину» не будет достаточным для обеспечения прогресса по всем программам. Вместо этого можно использовать следующий прием: выполнить первый шаг первой программы; затем выполняют второй шаг первой программы и первый шаг второй программы; затем выполняют третий шаг первой программы, второй шаг второй программы и первый шаг третьей программы; и так далее. Таким образом, это также известно как диагонализация (как используется, например, в пакете Haskell «universe» или монаде «Omega»).
Этимология
[ редактировать ]Аналогия с переплетением концов соединения «ласточкин хвост» в деревообработке .