Корректность - алгоритм
Cтраница 1
Корректность алгоритма устанавливается последовательностью лемм, доказательства которых не приводятся. [1]
Корректность алгоритма зависит от того, лежат ли добавляемые диагонали целиком внутри многоугольника. Никакая другая вершина многоугольника не может находиться внутри или на границе этого треугольника, так как все такие вершины имеют у-координату, меньшую чем вершина и. Ни одна точка внутри треугольника не может быть внешней для многоугольника, так как в этом случае ломаная прошла бы через внутренность треугольника и по крайней мере одна из его вершин оказалась внутри треугольника. Таким образом, диагональ uv2 целиком лежит внутри многоугольника. Доказательства для случаев ( 2) и ( 3) проводятся аналогично, и, кроме того, довольно просто можно проверить, что свойства стека являются инвариантом алгоритма. [2]
Корректность алгоритма 6.5 следует из утверждения, данного в комментарии в начале тела цикла. Это утверждение очевидно первый раз, когда мы входим в цикл при / 1 и h - n, и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. [3]
 |
Случай, при котором алгоритм неэффективен. [4] |
Корректность алгоритма 8.12 и его модификации может быть доказана одновременным использованием математической индукции по N и теорем 8.2 и 8.3 ( упр. [5]
Корректность алгоритма доказывается непосредственно индукцией по S, и эту часть доказательства мы оставляем в качестве упражнения. [6]
Корректность алгоритмов, полученных путем конструирования, не вызывает сомнений, если алгоритмы, использованные в качестве строительного материала, дают точные результаты. Если же их результаты являются приближенными, как это часто бывает на практике, то обоснование корректности может требовать сложных исследований. [7]
Корректность алгоритмов, полученных путем сужающих преобразований, обеспечивается проверкой ( доказательством) того, что каждый результат, получаемый суженным алгоритмом, тождествен с результатом, который для того же варианта исходного данного дает исходный алгоритм. [8]
Корректность алгоритма разложения положительного целого на простые сомножители доказать очень просто. [9]
Корректность теоретически обусловленных алгоритмов гарантируется наличием соответствующих доказательств. [10]
Обосновать корректность алгоритма Эратосфена нетрудно. [11]
Обоснование корректности алгоритма предоставляем читателю. [12]
Доказательство корректности алгоритма предлагается в качестве упр. [13]
Доказательство корректности алгоритмов 8.11 ( а), ( Ь) и ( с) оставляем в качестве упр. [14]
Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется математическая индукция. [15]
Страницы: 1 2 3 4