|
109 Если же принять Л: = 0,4 и считать, что реализации имеют вероятности Р, = Р(к), оценки которых даны в таблице 3.2, то, перечисляя реализации для всех к = 0,4 и умножая их на оценки Р(к) из таблицы 3.2, получим взвешенные реализации на рисунке 3.6, б. 4. Обобщение реализаций (построение вероятностного алгоритма). Эта операция по существу принадлежит совместно и этапу алгоритмизации и этапу синтеза, так как обобщение реализаций и вероятностный алгоритм это есть синтез алгоритма по реализациям. Операция обобщения является основой для синтеза стохастических алгоритмических структур. Сложные структуры обобщаются в матричной форме. Но простые структуры, какими являются многие реализации, можно обобщать непосредственно по их графам. Обобщение по графам реализаций сводится к следующему: а) объединяются вершины графа; б) все «одноимённые» дуги суммируются по их весам; в) проверяется равенство полусгепенных входов и выходов в каждой вершине. Например, обобщение двух реализаций на рисунке 3.6,а приводит к варианту вероятностного алгоритма, показанному ни рисунке 3.7, а. 0,5 Рисунок 3.7. Варианты вероятностного алг оритма а при двух равновероятностных и б при пяти неравновероятностных реализациях При равновероятностном варианте взвешивания можно обобщить и у невзвешенные реализации, например, как показано на рис.3.7, а. Тогда получается, что /вх = /вх = п , где п число обобщаемых реализаций. В этом I |
Таблица 3.2. по Оценки вероятностей Р(к) реализаций алгоритма с циклом к-ой степени (для наиболее вероятных значений к) к 0 1 2 3 4 Р(к) 0,38 0,26 0,17 0,11 0,08 Умножить .рю реализацию на вероятность Ру это практически означает надписать над всеми дугами реализации значение Ру Так. например, если принять к =0,4 и считать реализацию на рисунке 3.6, а и реализацию 1) на рисунке 3.6, б равновероятными Р} = 0,5), то, умножая их на 0,5, получаем взвешенные реализации на рисунке 3.6, а. Если же принять к = 0,4 и считать, что реализации имеют вероятности Р} = Р(к), оценки которых даны в таблице 3.2, то, перечисляя реализации для всех к = 0,4 и умножая их на оценки Р(к) из таблицы 3.2, получим взвешенные реализации на рисунке 3.6, б. 4. Обобщение реализаций (построение вероятностного алгоритма). Эта операция по существу принадлежит совместно и этапу алгоритмизации и этапу синтеза, так как обобщение реализаций и вероятностный алгоритм это есть синтез алгоритма по реализациям. Операция обобщения является основой для синтеза стохастических алгоритмических структур. Сложные структуры обобщаются в матричной форме. Но простые структуры, какими являются многие реализации, можно обобщать непосредственно по их графам. Обобщение по графам реализаций сводится к следующему: а) объединяются вершины графа; б) все «одноименные» дуги суммируются по их весам; в) проверяется равенство полустепенных входов и выходов в каждой вершине. Например, обобщение двух реализаций на рисунке 3.6,а приводит к варианту вероятностного алгоритма, показанному ни рисунке 3.7, а. 112 > 4. 0,5 Рис.3.7. Варианты вероятностного алгоритма а при двух равновероятностных и б-при пяти неравновероятностных реализациях При равновероятностном варианте взвешивания можно обобщить и невзвешенные реализации, например, как показано на рис.3.7, а. Тогда получается, что /м ~/вх = п , где п число обобщаемых реализаций. В этом случае, чтобы привести алгоритм к форме, удобной для дальнейшего синтеза, необходимо его нормировать числом п. а) невзвешенные реализации: 1) элементарный путь; 2) сложный путь с однократным циклом б) взвешенный граф алгоритма, обобщенный по реализациям 1) и 2); в нормированный граф 1> |