पुनरावर्ती कार्यों की शुद्धता दिखाने के लिए सामान्य प्रमाण रणनीतियां?

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; 

जहां $ n \ \ text {div} \ 2 = \ बाईं \ lfloor \ frac {n} {2} \ दाएं \ rfloor $

कार्य यह साबित करना है कि $ एफ (एन, के) = \ प्रारंभ {मामलों} 1 \ Leftrightarrow {n \ select k} \ \ text {mod} \ 2 = 1 \ 0 \ text {अन्यथा} \ end {case} $

यह बहुत जटिल नहीं दिख रहा है (क्या मैं गलत हूं?), लेकिन मुझे नहीं पता कि इस तरह के सबूत को कैसे संरचित किया जाना चाहिए। मैं मदद के लिए बहुत आभारी होंगे।

Answer 1

रिकर्सिव एल्गोरिदम की सुधार अक्सर mathematical induction द्वारा सिद्ध की जाती है। इस विधि में दो भाग होते हैं: सबसे पहले, आप आधार स्थापित करते हैं, और फिर आप एक अपरिवर्तनीय चरण का उपयोग करते हैं।

आपके मामले में, आधार सभी मामलों में है जब के = 0, या जब के विषम है लेकिन एन भी है।

आगमनात्मक कदम साबित आवश्यक होता है कि जब 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. फ़ंक्शन फ़ॉर्म (एन, 0) के सभी इनपुट के लिए सही है।
2. मानते हैं कि सभी इनपुट (एन ', के') के लिए (एन ', के') लेक्सिकोोग्राफिक रूप से (एन, के) से कम है, फ़ंक्शन सही है, साबित करें कि यह सही है (एन, के) ।

इस सबूत के विनिर्देशों को आपके कार्य के विनिर्देशों और द्विपक्षीय गुणांक के बहावियर का लाभ उठाने की आवश्यकता होगी, लेकिन सामान्य टेम्पलेट ऊपर जैसा है।

आशा है कि इससे मदद मिलती है!

Answer 3

गणितीय रूप से आपके तर्क को साबित करने के बाहर (उदाहरण: inductive proof), इस से संबंधित विज्ञान की गणना करने में कुछ परिणाम हैं।

आप विषय की एक रूपरेखा के लिए यहाँ शुरू कर सकते हैं: अपने विशेष मामले के लिए Correctness
, आप पता चलता है कि इस सवाल का जवाब इच्छित एक है आंशिक शुद्धता में रुचि होगी। फिर कार्यक्रम को समाप्त करने के लिए कुल शुद्धता।

Hoare logic आपकी आंशिक शुद्धता को हल कर सकता है।

इस विशेष समस्या के लिए समाप्ति के लिए के रूप में:

हैं (एन% 2 == 0 और कश्मीर% 1 == 1) या (कश्मीर == 0) कार्यक्रम समाप्त हो जाता है, अन्यथा यह n करने के लिए recurses/2, के/2 मामले।
के पर strong induction का उपयोग करके, हम दिखा सकते हैं कि कार्यक्रम हमेशा टर्मिनल नोड्स में से एक तक पहुंचता है जहां k == 0। (यह पहले खंड पर पहले समाप्त हो सकता है, लेकिन हमें केवल यह दिखाने की ज़रूरत है कि यह बिल्कुल समाप्त हो गया है, जो यह करता है)

इसलिए मैंने आपको आंशिक शुद्धता का प्रमाण छोड़ दिया है (क्योंकि मुझे वह सामान नहीं पता है)