книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов
.pdfшина ее остается неизменной, а начальной служит дополнительная вершина.
Построим логическую функцию, соответствующую составному алгоритму решения задачи в транспортном отделе и в отделе обо рудования.
Построение логической функции начинаем с записи логической формулы равного начального подпути Пх.
П^ВСрХ |
(СрПхПСр |
+ СрСрХ |
(СрПхПСр |
+ СрСрХ |
{СрПхПСр |
+ |
СрПхПСр)))Х(СрПрхПрСр+\)Х |
||
СрСрХ(СрСр±СрСхССхССрX |
(1 + |
СрПрXПрСX |
||
СрСр))ХСрУхУСхССр •
Непосредственно за П\ в алгоритмах следуют неравные под пути:
(СрС+ (СрСрХ (СрПрхПрСр |
+ |
СрСрХСрПрХПрВсХ |
||||
|
ВсСр) XСрС |
+ |
СрСрХСрС)); |
|
|
|
(1 + (СрСрX |
(1 + СрСрX |
(1 + СрС) X СрПрX |
ПрСр) |
X |
||
|
СрПрХПрВсхВсСр)хСрС) |
. |
|
|
||
Подпуть П{ заканчивается операцией |
сравнения, в |
соответст |
||||
вии с правилами |
объединения |
неравные |
подпути |
дополняются со |
||
ответствующими начальными подпутями СрСр и имеют вид пер вый:
СрСрХ |
(СрС+ |
(СрСрХ |
(СрПрХПрСр |
+ |
СрСрХСрПрХ |
|
ПрВсхВсСр)ХСрСхСрСрхСрС)); |
|
|
||
вид второй: |
|
|
|
|
|
СрСрХ |
(1 + |
(СрСрХ |
(1 +СрСрХ |
|
(\+СрС)хСрПрХ |
|
ПрСр)хСрПрхПрВсХВсСр)хСрС) |
|
'.. |
||
Соединяем полученные пути дизъюнктивной связью и заклю чаем в круглые скобки. Объединенные неравные подпути присое диняются к равному подпути П\ с помощью конъюнктивной связи. В результате получим следующую формулу:
ВСрХ |
(СрПхПСр |
+ СрСрХ |
(СрПхПСр |
+ |
СрСрХ |
||||
(СрПX |
ПСр + СрПх |
ПСр))) |
X (СрПр хПрСр |
+ |
\)Х |
||||
СрСрХ |
(СрСр + СрСхССхССрХ(\ |
+ |
|
СрПрХПрСрХ |
|||||
СрСр))ХСрУхУСхССрХ |
|
(СрСрХ |
(СрС |
+ |
СрСрХ |
||||
((СрПр |
X ПрСр |
+ СрСр X СрПр X ПрВс |
X ВсСр) |
X СрС + |
|||||
СрСрХСрС))+СрСрХ |
(1 + |
(СрСрХ |
(\+СрСрХ |
|
(1 + |
||||
СрС)ХСрПрХПрСр)хСрПрХПрВсхВсСр)хСрС)) |
|
|
|
. |
|||||
Далее к неравным подпутям без каких-либо изменений присое диняется с помощью конъюнктивной связи равный подпуть:
П2=СДхДУХУУхУСхСДхДУХУПчХПчСр |
, |
120
Затем осуществляется присоединение ряда подпутей из оди нарных круглых скобок. В процессе присоединения эти скобки сохраняются, а внутри скобок происходит присоединение по общим
правилам. Первым присоединяется |
равный подпуть |
П3 |
= СрОВ + |
|
-\-СрПрХПрПр. |
Непосредственно |
за Я 3 следуют |
два |
неравных |
подпути.
Так как предшествующий им равный подпуть заканчивается вершиной Пр, отличной от сравнения, то предполагается наличие дополнительной вершины сравнения. Это означает, что равный подпуть продляется на одну дугу, а начальные дуги неравных под путей соответствующим образом изменяются.
Таким образом, равный подпуть Я 3 будет иметь вид:
|
П3=СрОВ |
+ |
|
СрПрХПрПрХПрСр, |
|
|
|
|
|
|||||
а присоединяемые неравные пути |
|
|
|
|
|
|
|
|
||||||
|
|
ПрПрхПрВс |
|
и |
ПрВс'хВсВс |
|
|
|
|
|
||||
соответственно видоизменяются в пути следующего вида: |
|
|
|
|||||||||||
|
|
СрПрхПрВс |
|
и |
СрВсхВсВс, |
|
|
|
|
|
||||
Последним |
присоединяется |
равный |
подпуть Я 4 . Длина |
нерав |
||||||||||
ных подпутей больше |
нуля, |
поэтому |
Я 4 |
присоединяется |
|
без |
изме |
|||||||
нений. Результатом присоединения является логическая |
|
функция |
||||||||||||
вида: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ф = ВСрХ |
|
(СрПхПСр |
|
+ СрСрХ |
(СрПхПСр |
+ |
СрСрХ |
|
||||||
(СрП |
|
хПСр |
+ |
|
|
|
СрПхПСр)))Х{СрПрХПрСр+\)Х |
|||||||
СрСр |
Х(СрСр |
+ СрС хССхССрХ{\ |
+ |
СрПрхПрСрХ |
||||||||||
СрСр)) |
X СрУх |
УСX |
ССрХ{СрСрX |
(СрС |
+ |
СрСрX |
|
|||||||
((СрПрXПрСр |
+ СрСрX |
СрПрXПрВсХВсСр) |
|
ХСрС |
+ |
|
||||||||
СрСрХСрС)) |
+СрСрХ |
(1 + (СрСрХ |
|
(1 + СрСрХ |
(1 |
+ |
|
|||||||
СрС) XСрПрXПрСр) |
|
хСрПрXПрВсхВсСр) |
XСрС)) |
|
х |
|||||||||
СДхДУхУУхУСхСДхДУХУПчХПчСрХ |
|
|
|
|
|
|
|
|
||||||
{СрОВ + СрПрXПрПрX.ПрСрX |
(СрПрXПрВс |
|
+ |
СрВсх |
||||||||||
|
|
|
ВсВс)ХВсВсХВсСр). |
|
|
|
|
|
|
|
||||
Подобным образом можно построить логическую функцию, ото бражающую присоединение любого числа алгоритмов. Процесс присоединения алгоритмов может быть выполнен механизирован ным путем после разработки соответствующего алгоритма.
Для механизированной реализации процесса синтеза алгорит
мов операции |
над графами целесообразно заменить операциями |
|||
над соответствующими матрицами смежности. |
|
|||
Выполняя |
синтез |
с применением |
матриц смежности, |
можно |
использовать |
тот же |
алгоритм, что |
и при использовании |
графов. |
Только теперь роль равных подпутей будут играть равные клетки матриц. В то же время, используя свойства матриц смежности,
можно несколько упростить алгоритм синтеза. Процесс синтеза
вэтом случае будет состоять из следующих этапов:
1.Построение матриц смежности, соответствующих графам ал горитмов.
2.Выполнение операции сложения этих матриц.
3.Корректировка итоговой матрицы с целью получения матри цы составного алгоритма.
Поскольку первые два этапа не требуют пояснений, остановим ся на последнем этапе.
Корректировка итоговой матрицы заключается в следующем. Среди элементов матрицы отыскиваются те, значения которых равны двум. (Если таких элементов нет, то алгоритмы не имеют общих частей.) Значение этих элементов заменяется единицей. После этого из матрицы выделяются строки, соответствующие операциям сравнения, и по каждой из них определяется сумма элементов. Если такой строки не найдется, то синтез алгоритмов закончен и полученная матрица есть матрица смежности графа, представляющего составной алгоритм. Если же найдется строка, сумма элементов которой больше двух, то к матрице добавляются две строки и два столбца, соответствующие дополнительным опе рациям сравнения при расширении графа. Значение элементов в этих строках определяется по элементам строки, в которой сумма элементов больше двух. Они соответственно переносятся. В най
денной же строке ставятся единицы на |
пересечении с вновь вве |
|||||||
денными |
столбцами. |
Соответствующим |
образом |
корректируется |
||||
и связь других |
операций с данной'операцией |
сравнения. |
||||||
Рассмотрим |
в качестве примера один |
из |
фрагментов задачи |
|||||
составления сводки |
о реализации фондов |
в |
отделе |
оборудования |
||||
и транспортном |
отделе. Графы |
алгоритмов |
этих задач приведены |
|||||
на рис. 21 и 22. |
|
|
|
|
|
|
|
|
Строим |
матрицы смежности |
фрагментов Ai и А2 |
(см. стр. 123— |
|||||
125). Вершины этих фрагментов выделены на графах кружками. Поскольку в матрице А имеются элементы, равные двум, то
производим корректировку ее (см. стр. 126). В результате коррек тировки получается матрица А*, число столбцов и строк которой на два элемента больше, чем в матрице А. Это результат расшире
ния |
графа, так как в строке с номером Ср4 |
сумма элементов после |
||
замены двоек единицами оказалась больше двух. |
А*, |
|
||
|
На рис. 23 часть графа, соответствующая матрице |
отмече |
||
на |
кружками. |
|
|
|
|
Задавая вектор операций конкретного |
алгоритма |
и |
выбирая |
из матрицы А* соответствующие строки, получаем матрицу смеж ности этого алгоритма.
Для оценки алгоритмов синтеза был проведен эксперимент на машине «Минск-22» для матриц размерностью 4X4, 12X12, 36Х
Х36. В табл. 2 приведены |
данные о времени |
синтеза алгоритмов |
по методу Карпа —строка |
К и с применением |
графов — строка Г. |
Время в таблице исчисляется в секундах. |
|
|
122
|
U |
|
|
о 3" |
t: |
|
|
>г |
СО |
|
о |
|
|
|
а-" CQ |
|
О |
|
||||
|
|
|
|
|
|
о |
3 |
|
|
|
|
|
|
|
||||||||
Cpi |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
npi |
l |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Cp2 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
СРъ |
0 0 |
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
||||||||||||||||||||
Пр2 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
c2 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
У1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Cp4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Ci |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Л\ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
У2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Уз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Сръ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
Пр3 |
0 0 0 0 0 0 0 0 0 0 |
|
0 0 0 0 |
0 0 1 0 о jo |
||||||||||||||||||
Bct |
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 |
0 0 0 |
||||||||||||||||||||
CPs |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
с. |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 0 0 0 0 0 0 0 0 с 0 0 0 0 1 0 0 0 0 0 |
|||||||||||||||||||||
123
ё |
со |
осо 3 о |
00 |
4S |
|
||||
«з- 1? о о |
а- |
oq |
Cpi |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
npi |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
СPi |
0 0 0 |
1 0 |
1 0 0 0 0 0 |
0 0 0 0 0 0 0 0 |
||||||||||||||||
Срг |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
Пр2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
с, |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
с, |
0 0 |
0 |
1 0 0 |
0 |
0 0 0 0 |
0 0 |
0 0 0 |
0 |
0 |
| 0 |
||||||||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
= с3 |
0 0 0 0 0 0 0 0 0 |
1 0 |
0 |
0 |
0 0 0 0 |
0 0 |
||||||||||||||
Cpi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
с, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
у, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Уз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Ср7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
Пръ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Ср& |
0 0 0 0 0 0 0 0 0 0 |
1 0 0 0 0 0 |
0 1 0 |
|||||||||||||||||
Пре |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Вс2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Суммируем матрицы Ах и А2 и получаем матрицу А.
|
о о о О о о о о о о о о о о о о о о о о о о |
о - о |
|||
CD о о с о о о о о о о о о о о о о о о о о о о |
- о о |
||||
|
<= о о о о о о о о о о о о о » о о 5о о 1—1о о о о |
||||
а- |
о о о о о о о о о о о о о о о о о о о о - о о о |
||||
г- |
о о о о о о о о о т—< о о о о о о о о о о о о о о о |
||||
|
|||||
|
о о о о о о о о о о о о о о о о о |
- |
о о о о о о |
||
о |
о о о о о •= о о о о о о о о о о о |
- |
о о о о о о о |
||
со |
|
|
|
|
|
CD о о о о о о о о о о о о о о - |
о о о о о о о о о о |
||||
CQ - |
о о о о о о о о о о о о о о |
- о о о о о о о о о |
|||
•о1 |
о о о » о о о о о о о о о о - о о о о о о о о о |
||||
п |
|||||
а. |
|||||
о о = о о о о о о ~ о о о о о о о о о о о о о о
о
а-
«
о
1
со
i f
о |
о о |
о о о о о о о о о сч о о о о о о о о о о о о |
о о о о « о о о о о о (М о о о о о о о о о о о о о |
||
о о о о о - о о о о сч о о о о о о о о о о о |
о о о |
= о о о о о о о о сч о о с о о о о о о о о о |
- о о |
о о о о о о о о сч о о о о о о = - о о о о - |
о о - |
о о о о о о о <мо о о о о о о о о о о о о о о о о
о о |
с СЧ |
о о о о о о о о о о о о о о о о о о о о о |
||
о о о о |
о о |
о о о <=> о |
о о о о о о о о о о о о о |
|
о о сч о о ( N |
о о о о о ~ о о о о о о о о о о о о о |
|||
о о о сч о о о о о о о о о о о о о о о о о о о о о |
|
о о сч о о о CN о о о о о о о |
о о о о о о о о о о о |
<мо о о сч о о о о => о о о о |
о о о о о о о о о о о |
см о о о о о о о о о о о о о о о о о = о о о о о о |
|
о сч о о о о о о о о о о о о о о о о о о о о о => о |
|
|
со |
о ^ |
in |
со |
<s |
с». |
|
<и >г о |
|
||||
|
|
|
|
|
ОС а |
|
3" с5 а" |
|
II |
5- а-оа о |
с5 о |
||
|
|
|
|
|
|
|
12а
|
о о о о о о о о о о о о о о о о о о о < о о о о |
|
Ч Э |
о о о о о о о о о о о о о о о о о о о о о о о о о |
|
Ъд |
о о о о о о о о о о о о о о о о о о о о о о г—1о о о |
|
Чц |
о о о о о о о о о о о о о о о о о о о о о о - о о о о |
|
Ч Э |
о о о о о о о о о о о о о о о о о о о о - о о о о о о |
|
Чц |
с о о о о о о о о о о о о о о о о о о о о о о о о о |
|
Ч Э |
о о о о о о о о о о о о о о о о о о о |
- о о о о о о - |
Чц |
о о о о о о о о о о о о о о о о о f—« - |
о о о о о = о о |
ЯЭ о о о о о о о о о о о о о о о о о »—< о о о о о о о о о
чэ о о о о о о о о о о о о о о « о о о о о о => о о о о о
Ьд |
о о о о о о о о о о о о о о о о о с о о о о о о о о |
ч и |
о о о о о о о о о о о о о о 1—» с о о о о о о о о о о о |
Ч Э |
о о о о о о о о о о о о о о о о о о о - о о о о о ~ о |
2Л о о о о о о о о о о о о о о о о о о о о о о о о о
ZA о о о о о о о о о о о < о о о о о о о о с о о о о о
lV о о о о о о о о о о о о о о о о о о о о о о о о о о |
|||||||||||
fD |
о о о о о о о о о о о о о о о о о о о о о о - |
о о ~ |
- |
||||||||
4D |
о о о о о о о о " о о о о о о о о о о о о о о о о о о |
||||||||||
еэ |
о о о о о о о t—< о о о о о о о о о о о о о о о о о о о |
||||||||||
|
|
|
|
|
|
|
|
|
|
' Л |
|
lA |
о о о о о о о о о о о о о о о о о о о о о о о о о о |
||||||||||
ZD |
о о о о о о о о о о о о о о о о о о о о о о о о о о о |
||||||||||
lD |
о о |
- |
о |
о т—' о о о о о о о о о о о о о о о о |
о о о о |
||||||
4U |
о о о |
- |
о о о о о о о о о о о о о о о о о о о |
- о о о |
|||||||
4D |
о о |
~ |
о |
о о |
о о о о о |
о |
о о |
- |
о о о с о о о |
о о о |
о |
|
|
|
|
ч—4 |
|
|
|
||||
ч э |
т—* о о о |
- о о о о о о о о о о о о о о о о о о о о о |
|||||||||
ч и |
т—< о о <=> |
о о о о о о о о о о о о о о о о о о о о о о о |
|||||||||
|
о о о о о о о о о о о о о о о о о о о о о о о о о |
||||||||||
с* со |
о |
|
СО |
so |
-* |
00 со |
05 о |
ft. |
-* |
а- |
« 1 ft. |
а-а- |
0Q |
<5 |
|
|
с» со |
|
|
|
со |
|
II
12ft
|
|
|
Т а б л и ц а 2 |
|
Разыер |
|
|
|
|
—«^матрицы |
4X4 |
12X12 |
36X36 |
|
Метод ^^"--^^^ |
||||
|
|
|
||
К |
31 |
45 |
137 |
|
г |
60 |
62 |
68 |
График зависимости стоимости обработки от размера матрицы приведен на рис. 24.
9 |
10 12 |
36 |
Размер матрицы
Рис. 24. График зависимости стоимости обработки от размера матрицы по раз личным методам
Данные экспериментальной проверки показывают, что для матриц размерностью свыше 12X12 по времени и по стоимости выгоднее использовать алгоритм синтеза, основанный на примене нии графов.
Глава V О Ц Е Н К А С Л О Ж Н О С Т И
А Л Г О Р И Т М О В
§ 5. 1. ОЦЕНКА с л о ж н о с т и с п о м о щ ь ю СИГНАЛИЗИРУЮЩИХ ФУНКЦИЙ
|
|
Одной из важных задач анализа алгоритмов, связан |
ного |
с эквивалентными преобразованиями и установлением опти |
|
мальности, |
является задача определения сложности алгоритмов. |
|
Эта |
задача |
возникает в связи с тем, что при составлении алгорит |
мов управления производством необходимо учитывать возможно сти их технической реализации, т. е. учитывать характеристики алгоритма, связанные с временем реализации, объемом запоми нающих и регистрирующих устройств, необходимым для хранения исходной, промежуточной и конечной информации, способами ма тематического описания алгоритмов и др. С этой точки зрения возможны два подхода к оценке сложности в зависимости от того, оценивается ли сложность алгоритма или же сложность вычисли тельного процесса, протекающего в соответствии с алгоритмом.
В качестве меры сложности алгоритма рассматривается функ ционал, соотносящий каждому из алгоритмов Л = {Ль Л 2 , . . . } не-
.которое число М (Лг-), характеризующее его громоздкость, напри мер число команд в Л*, длину записи или какой-либо другой пара метр, характеризующий объем информации, содержащейся в Л*.
Подобные функционалы уже давно применяются в теоретикокибернетических исследованиях схем, реализующих функции ал гебры логики, а также в вычислительной математике, где слож ность схемы оценивается количеством арифметических операций, реализующих алгоритм.
В качестве меры сложности вычислений рассматривается функ
ционал, соотносящий |
каждой |
паре |
{Л,-, 3*}, |
где Л; — алгоритм, |
|
Зг — индивидуальная |
задача из |
бесконечного |
класса задач, |
кото |
|
рые алгоритм Л* решает, некоторое |
число р |
(Л{, 3*). Это |
число |
||
характеризует сложность работы алгоритма Л* применительно к исходным данным задачи 3* до выдачи соответствующих резуль татов.
В качестве р можно брать число элементарных шагов, из кото рых складывается эта работа, длительность вычислений или объ ем памяти, необходимый для реализации алгоритма.
128
Поскольку для каждого алгоритма Л* однозначно определен класс задач 3,, который он решает, то в качестве меры сложности работы алгоритма (вычисления) можно принять некоторый опе ратор, сопоставляющий с каждым алгоритмом Л» соответствую
щую функцию |
(3i). |
Такой подход |
к оценке сложности вычислений содержится в |
работе Б. А. Трахтенброта [70]. Б. А. Трахтенброт ввел специаль ные функции, измеряющие объем памяти, необходимый для вы полнения заданных вычислений, и назвал их сигнализирующими функциями.
Определяя некоторую меру сложности для алгоритмов или вы числений, необходимо получить удобный инструмент для сравне ния алгоритмов, а также для оценки объективной трудности, при сущей различным вычислительным процессам. Оказывается, су ществует различие в оценке сложности в зависимости от того, рас
сматривается ли мера |
сложности алгоритма или мера сложности |
его работы. Поскольку |
сложность алгоритма измеряется действи |
тельным числом, то любые два алгоритма сравнимы по сложности. Более того, обычно считают, что мера сложности алгоритма при нимает лишь натуральное значение, поэтому для каждого вычис лительного процесса существует алгоритм с минимальной слож ностью.
Если рассматривать меру сложности вычислений, то необходи мо учитывать возможные пути реализации алгоритма при обра
ботке конкретных данных задачи. В этом случае |
меру сложности |
||||||
вычислений |
оценивают |
на |
базе |
нижней — pmin |
и |
верхней —рШ ах |
|
оценок, удовлетворяющих следующим условиям: |
|
|
|
||||
1) существует алгоритм |
Ai реализации задачи |
со сложностью |
|||||
Рг, не превосходящей р ш а х; |
|
реализации задачи A i t его |
|
||||
2) каков |
бы ни был |
алгоритм |
слож |
||||
ность р» не менее рт ш. |
|
и нижней оценок |
сложности |
мера |
|||
При сближении верхней |
|||||||
сложности вычислений может быть охарактеризована более точно. В том случае, когда получение верхних и нижних оценок за труднено, оценка сложности может производиться с помощью со ответствующих сигнализирующих функций. Мера сложности опи сания алгоритма зависит от концепции алгоритма. Под слож ностью нормального алгоритма понимают длину его изображения. Под сложностью машины Тьюринга понимается произведение числа внутренних состояний на число символов внешнего алфави та. А. Н. Колмогоров предложил меру сложности, не зависящую от концепции алгоритма. Под сложностью объекта А. Н. Колмо горов понимает минимальную длину программы, позволяющей
восстановить слово X.
Наиболее часто в качестве модели алгоритма используются машины Тьюринга. Применительно к машинам Тьюринга в теории алгоритмов определены соответствующие сигнализирующие функ ции. Рассмотрим эти функции применительно к вычислительным
9 Заказ 4239 |
129 |