Корректность - алгоритм
Cтраница 2
Доказательство корректности алгоритма 3.1 проводится индукцией по числу выполнений внешнего цикла. Предположение индукции таково: после г выполнений этого цикла кортежи в ОЧЕРЕДИ будут расположены в лексикографическом порядке по их г последним компонентам. [16]
 |
Процедура НОД. [17] |
Доказательство корректности алгоритма 8.7 тривиально, если доказать, что он заканчивает свою работу. Таким образом, корректность алгоритма вытекает из анализа времени его работы, что составляет содержание следующей теоремы. [18]
Доказательство корректности алгоритма будет завершено, если мы докажем лемму. [19]
Доказательство корректности алгоритма М служит темой улр. [20]
Доказательством корректности алгоритмов, полученных с помощью эквивалентных преобразований, является правильность преобразований. Мы не можем пока более определенно говорить об эквивалентных преобразованиях, потому что накопленные нами, читатель, знания об алгоритмах еще недостаточны. [21]
Чтобы доказать корректность алгоритма ( иными словами, убедиться, что он делает именно то, что и предусмотрено), нам нужно проверить все изменения переменных, в нем используемых до, в течение и после работы алгоритма. [22]
 |
Остовное дерево с со значениями функции НИЖНИЙ. [23] |
Что касается корректности алгоритма, то лемма 5.5 гарантирует, что точки сочленения будут найдены правильно. Даже если корень не является точкой сочленения, алгоритм обращается с ним как с таковой, чтобы выделить двусвязную компоненту, содержащую корень. [24]
Чтобы доказать корректность алгоритма, достаточно показать индукцией по числу тех вызовов процедуры ПОИСКВ, которые завершили работу, что по окончании ПОИСКВ ( v) значение НИЖ-НЯЯСВЯЗЬЫ вычислено правильно. После строк 12 - 16 процедуры ПОИСКВ узел v становится корнем сильно связной компоненты тогда и только тогда, когда НИЖНЯЯСВЯЗЬЫи. А именно, узлы, находящиеся в стеке выше узла v, являются его потомками, а их корни не были найдены ранее v, поскольку эти узлы все еще находятся в стеке. [25]
Продолжим доказательство корректности алгоритма. [26]
Для доказательства корректности алгоритма 8.6 требуется лишь показать, что значения lowlink вычисляются корректно; доказательство можно провести по индукции ( упр. [27]
В доказательство корректности алгоритма 4.5 входит доказательство того, что окончательное разбиение не оказывается слишком грубым. Иными словами, надо доказать следующее. [28]
Для доказательства корректности алгоритма нужно, как и в тексте, провести доказательство выделенного на стр. [29]
Формальные доказательства корректности алгоритма разбора ПСС и различных алгоритмов построения таблиц не входят в число вопросов, затрагиваемых в настоящей книге. Однако потенциальный пользователь этих алгоритмов должен знать, до какой степени гарантируется их успешная работа. В данном разделе этот вопрос обсуждается неформально. [30]
Страницы: 1 2 3 4