Общие стратегии доказательства, чтобы показать правильность рекурсивных функций? - PullRequest
Новая
       43

Общие стратегии доказательства, чтобы показать правильность рекурсивных функций?

12 голосов
/ 02 марта 2012

Мне интересно, существует ли какое-либо правило / схема продолжения проверки правильности алгоритма? Например, у нас есть функция $ F $, определенная для натуральных чисел и определенная ниже: 

function F(n,k)
begin
  if k=0 then return 1
  else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
  else return F(n div 2, k div 2);
end;

где $ n \ \ text {div} \ 2 = \ left \ lfloor \ frac {n} {2} \ right \ rfloor $

задача состоит в том, чтобы доказать, что $ F (n, k) = \ begin {case} 1 \ Leftrightarrow {n \ choose k} \ \ text {mod} \ 2 = 1 \ 0 \ text {else} \ end {случаи} $

Это не выглядит очень сложно (я не прав?), Но я не знаю, как следует структурировать такого рода доказательства. Буду очень признателен за помощь.

Ответы [ 3 ]

6 голосов
/ 02 марта 2012

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

В вашем случае основой являются все случаи, когда k = 0 или когда k нечетно, а n четно.

Для индуктивного шага необходимо доказать, что при правильном f(n,k), f(2*n,2*k), f(2*n+1,2*k), f(2*n,2*k+1) и f(2*n+1,2*k+1) все верны.

6 голосов
/ 02 марта 2012

Помимо математического доказательства вашей логики (пример: индуктивное доказательство ), есть некоторые результаты в вычислительной науке, связанные с этим.

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

Логика Hoare может решить вашу частичную корректность.

Что касается завершения для этой конкретной проблемы:

Если (n% 2 == 0 и k% 1 == 1) или (k == 0) программа завершается, в противном случае она возвращается к случаю n / 2, k / 2.
Использование strongПо индукции по k мы можем показать, что программа всегда достигает одного из терминальных узлов, где k == 0.(Это может закончиться раньше в первом предложении, но нам нужно было только показать, что оно вообще заканчивается, что и происходит)

Так что я оставил вам подтверждение частичной корректности (потому что я не знаю,этот материал)

2 голосов
/ 02 марта 2012

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

В этом случае я бы попытался доказать путем обоснованной индукции.В частности, я бы доказать, что

  1. Функция корректна для всех входов в форме (n, 0).
  2. Предполагая, что для всех входов (n ', k')так что (n ', k') лексикографически меньше, чем (n, k), функция верна, докажите, что она верна для (n, k).

Особенности этого доказательствапотребуется использовать специфику вашей функции и bahvaior биномиальных коэффициентов, но общий шаблон такой же, как указано выше.

Надеюсь, это поможет!

...