Jump to content

Согласование (информатика)

«Согласование » в разработке алгоритмов — это метод, который переплетает различные вычисления , выполняя их по существу одновременно. Алгоритмы, использующие согласование, иногда называют согласующими хвостами .

Рассмотрим дерево , которое потенциально содержит путь бесконечной длины (но каждый узел имеет только конечное число дочерних элементов): если в этой среде выполняется поиск в глубину , поиск может двигаться вниз по бесконечному пути и никогда не возвращаться, потенциально оставляя часть дерево неизведанное. Однако если используется поиск в ширину , существование бесконечного пути больше не является проблемой: каждый узел посещается с разветвлением в соответствии с его расстоянием от корня, поэтому бесконечный путь повлияет только на часть пути. поиск, путешествуя по этому пути.

Мы можем рассматривать это дерево как аналог набора программ; в этом случае подход «сначала в глубину» соответствует запуску одной программы за раз и переходу к следующей только после завершения работы текущей программы. В случае, когда одна из программ работает бесконечное количество времени, этот переход никогда не произойдет. Подход в ширину, при котором посещение каждого дочернего элемента на одном уровне дерева является примером согласования, когда для каждой программы выполняется один шаг перед переходом к следующей. Таким образом, прогресс достигается в каждой программе, независимо от потенциального существования незавершающейся программы.

Другой пример — моделирование недетерминированной машины Тьюринга M с помощью детерминированной машины (например, универсальной машины Тьюринга ). В таком случае нам нужно использовать согласование, если одна из ветвей вычислений M содержит бесконечный цикл.

Бесконечно много одновременных вычислений

[ редактировать ]

В случае бесконечного числа программ, потенциально бесконечно длинных, ни принцип «сначала в ширину», ни «сначала в глубину» не будет достаточным для обеспечения прогресса по всем программам. Вместо этого можно использовать следующий прием: выполнить первый шаг первой программы; затем выполняют второй шаг первой программы и первый шаг второй программы; затем выполняют третий шаг первой программы, второй шаг второй программы и первый шаг третьей программы; и так далее. Таким образом, это также известно как диагонализация (как используется, например, в пакете Haskell «universe» или монаде «Omega»).

Этимология

[ редактировать ]

Аналогия с переплетением концов соединения «ласточкин хвост» в деревообработке .

См. также

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 1617327821b86171fa56a25d1ca02b66__1720819200
URL1:https://arc.ask3.ru/arc/aa/16/66/1617327821b86171fa56a25d1ca02b66.html
Заголовок, (Title) документа по адресу, URL1:
Dovetailing (computer science) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)