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

Question

Мне интересно, существует ли какое-либо правило/схема работы с доказательством правильности алгоритма? Например, мы имеем функцию $ 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; 

где $ п \ \ текст {ДИВ} \ 2 = \ слева \ lfloor \ гидроразрыва {п} {2} \ right \ rfloor $

Задача состоит в том, чтобы доказать, что $ F (n, k) = \ begin {cases} 1 \ Leftrightarrow {n \ select k} \ \ text {mod} \ 2 = 1 \ 0 \ text {other} \ end {cases} $

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

Answer 1

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

В вашем случае основой являются все случаи, когда 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) все правильно.

Answer 2

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

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

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

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

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

Answer 3

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

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

Hoare logic может решить вашу частичную правильность.

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

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

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