Прекращение и исправление

Контенус

При создании алгоритмнеобходимо учитывать следующие три критерия: прекращение, исправление и сложность.

Завершение гарантирует, что алгоритм завершится после определенного числа элементарных операций. Исправление гарантирует, что алгоритм даст ожидаемый результат, когда он завершится.

Пример

Человек и собака стареют неодинаково. Для определения человеческого эквивалента возраста собаки весом менее 15 кг используется приведенная ниже таблица, где x представляет реальный возраст животного (в годах), а y - человеческий эквивалент в терминах старения.

Рассмотрим следующий алгоритм:

Проверим окончание. Это кондиционирующий набор с элементарными вычислениями внутри. Как только все условия проверены по порядку, алгоритм завершается.

С точки зрения коррекции алгоритм хорошо выполняет операции, описанные в таблице.

Сложный пример

В общем, завершение сложно проверить, потому что мы не всегда знаем априори количество выполненных инструкций. Коррекция усложняется, когда человек находится в присутствиипомогите с решением или исследования операций. Тогда необходимо использовать принципы математика доказать правильность алгоритма.

Возьмем пример расчета НОД в итеративном режиме.

Алгоритм завершается, если выполняется условие остановки цикла, т.е. если y отменяется. В цикле y заменяется остатком по модулю y. Таким образом, на каждом проходе y строго уменьшается, оставаясь положительным или равным нулю. Следовательно, y в конечном итоге достигает 0, поэтому мы выходим из цикла. Алгоритм завершается хорошо после определенного количества итераций.

Изначально x=a и y=b. В цикле мы заменяем (x, y) на (y, x mod y). Мы знаем, что gcd(x,y)=gcd(y, x mod y). Итак, на каждой итерации gcd(x,y)=gcd(a,b). В конце цикла у нас есть ay=0 или gcd(x,0)=x. По индукции мы делаем вывод, что возвращаем gcd(a,b). Алгоритм правильно вычисляет искомый НОД.

Инструмент для прекращения и исправления

Назовем сходящейся величину, принимающую свои значения в обоснованном множестве и строго убывающую при каждом проходе по циклу. Хорошо обоснованное множество — это вполне упорядоченное множество, в котором нет строго убывающей бесконечной последовательности. Существование сходящегося цикла for гарантирует, что алгоритм в конечном итоге выйдет из него. Например, в случае алгоритма Евклида y сходится.

Мы называем циклическим инвариантом свойство, которое, если оно истинно при входе в цикл, остается истинным после каждого прохода через этот цикл. Следовательно, это верно на выходе из этого цикла. Инвариант цикла аналогичен принципу повторения. Демонстрация адаптированного инварианта цикла позволяет доказать корректность алгоритма. Например, gcd(a,b)=gcd(x,y) является инвариантом цикла.

Возьмем в качестве примера алгоритм со случайностью, чтобы проверить понятия прекращения и исправления.

В информатике случайность присваивает значение в диапазоне значений. Псевдослучайность ограничена либо размером контейнера (int, double и т. д.), либо используемым алгоритмом (генерация числа по модулю очень большого числа). В алгоритме предполагается, что n и p строго положительные целые числа. Если у последнего есть операция, делающая его отрицательным, то значение 0 будет автоматически присвоено.

Во второй части условия x убывает, а y имеет случайное значение (строго ограниченное). поэтому x стремится к значению 0. В первой части условия y уменьшается к 0 от своего случайного значения. Таким образом, мы заключаем, что алгоритм уменьшает y до 0, затем уменьшает x, прежде чем снова присвоить значение y.

По индукции заключаем, что x будет стремиться к 0 после определенного числа итераций, так что вторая часть больше не будет посещена. И y тоже стремится к 0, так что выходим из цикла. Таким образом, мы доказали, что алгоритм останавливается. Говорить о коррекции в данном случае бесполезно, так как у нас не было спецификаций для проверки.

Отмечается, что некоторые алгоритмы не имеют доказательства завершения, чем знаменитая функция Сиракуз.