Cтраница 2
А будет равен числу путей ив узла V; в узел Vj длиной в W дуг. Если же при возведении матрицы смежности в степень пользоваться булевской арифметикой, то есть принимать, что 0 II 0I IaI, то каждый элемент Qj ] матрицы А, равный единице, будет означать существование в орграфе по крайней мере одного пути из V; в V ] длиной в W дуг; равенство QJ: 0 означает, что ни одного такого пути нет. [16]
Нам известно, что одна из особенностей регулярной цепи Маркова состоит в существовании предельных, или финальных, вероятностей, не зависящих от начального распределения вероятностей состояний. Он состоит в возведении матрицы перехода в такую достаточно высокую степень, что строки полученной в результате этой операции новой матрицы оказываются практически ( в пределах требуемой точности вычислений) одинаковыми. [17]
А будет равен числу путей ив узла V; в узел Vj длиной в W дуг. Если же при возведении матрицы смежности в степень пользоваться булевской арифметикой, то есть принимать, что 0 II 0I IaI, то каждый элемент Qj ] матрицы А, равный единице, будет означать существование в орграфе по крайней мере одного пути из V; в V ] длиной в W дуг; равенство QJ: 0 означает, что ни одного такого пути нет. [18]
X не расщепляются при возведении матрицы X в m - ю степень. [19]
В качестве минимизируемой функции стоимости примем математическое ожидание времени реализации пакета, В предлагаемом далее алгоритме отыскиваются на каждом шаге пути наибольшей стоимости. Поэтому сначала рассмотрим вопрос о нахождении таких путей на сетях. Задача отыскания пути на сети и путей максимальной или минимальной стоимости может быть решена методами теории графов. Действительно, сеть представляет собой граф с дугами, взвешенными Неотрицательными числами, / для любой сети можно задать матрицу смежности, координатами которой являются элементы множества вершин, расположенные по направлениям строк и столбцов. Обозначим матрицу смежности через Н, тогда элемент Нц 1, если существует ребро между i и / независимо о; его ориентации. Из теории графов известно, что при возведении матрицы смежности в степень k в полученной матрице Hfe элемент / г равен 1 или 0 в зависимости от того, существует ли путь, состоящий из k ребер, из вершины i в вершину / или нет. [20]
В этом алгоритме первый цикл определяет Ф - процессоры 1-го процесса, на которых были блокирования по запросам к k - щ процессору, и заносит нуль в признак блокирования. Так как возможна ситуация, что запросивший А-процессор блокируется, не выполнив запроса от какого-либо предшествующего А-процессора этого же процесса, следовательно, также заблокированного, то при организации исполнения запроса организующая система должна проверить ситуацию на возможность самозамыкания. В отличие от исследования опасности самозамыкания во время формирования пакета задач для мультипрограммирования, где рассматривалось распределение ресурсов, самозамыкание в процессе реализации в основном происходит в результате ошибок в логике процесса. Поэтому, особенно в процессе отладки алгоритма, организующая система должна проверять ситуации, возникающие при блокировании процессов, на возможность самозамыкания. Для этого можно использовать то, что матрица г - го процесса в массиве block является матрицей смежности для графа, описывающего причины блокирования. Так как при возведении матрицы смежности в т степень элементы а будут отображать наличие путей длиной в т дуг, то при возведении матрицы связности в степень т матрица графа, не имеющего самозамыкания, будет равна нулю. [21]
В этом алгоритме первый цикл определяет Ф - процессоры 1-го процесса, на которых были блокирования по запросам к k - щ процессору, и заносит нуль в признак блокирования. Так как возможна ситуация, что запросивший А-процессор блокируется, не выполнив запроса от какого-либо предшествующего А-процессора этого же процесса, следовательно, также заблокированного, то при организации исполнения запроса организующая система должна проверить ситуацию на возможность самозамыкания. В отличие от исследования опасности самозамыкания во время формирования пакета задач для мультипрограммирования, где рассматривалось распределение ресурсов, самозамыкание в процессе реализации в основном происходит в результате ошибок в логике процесса. Поэтому, особенно в процессе отладки алгоритма, организующая система должна проверять ситуации, возникающие при блокировании процессов, на возможность самозамыкания. Для этого можно использовать то, что матрица г - го процесса в массиве block является матрицей смежности для графа, описывающего причины блокирования. Так как при возведении матрицы смежности в т степень элементы а будут отображать наличие путей длиной в т дуг, то при возведении матрицы связности в степень т матрица графа, не имеющего самозамыкания, будет равна нулю. [22]