चयनित व उन्नत कलनविधियाँ

यह अध्याय इकाई 7 को उन प्रकरणों से पूर्ण करता है जिन्हें इसके 'चयनित प्रकरण' व 'उन्नत कलनविधियाँ' उप-प्रकरण GATE CS के अपने कलनविधि-पाठ्यक्रम से आगे नामित करते हैं: संख्या-सैद्धांतिक कलनविधियाँ, बहुपद अंकगणित व द्रुत फूरिये रूपांतरण, स्ट्रिंग-मेल कलनविधियाँ, तथा उन्नत/समांतर कलनविधियों के तीन कुल (समांतर, सन्निकटन, यादृच्छिकीकृत) — साथ ही अधिकतम प्रवाह, जो इस इकाई के ग्राफ-कलनविधि उप-प्रकरण में नामित है पर उधार लिए GATE कलनविधि अध्याय की अपनी ग्राफ-कलनविधि सामग्री (BFS/DFS/MST/लघुतम पथ) से नहीं ढका।

अधिकतम प्रवाह व अधिकतम-प्रवाह न्यूनतम-कट प्रमेय

प्रवाह नेटवर्क (कोर-क्षमताओं, स्रोत s व सिंक t सहित दिष्ट ग्राफ) में, प्रवाह हर कोर को क्षमता-प्रतिबंध (प्रवाह ≤ क्षमता) व संरक्षण (हर शीर्ष पर, s व t को छोड़कर, अंतर्वाह = बहिर्वाह) मानते मान सौंपता है। फ़ोर्ड-फुल्करसन विधि बार-बार वर्धक पथ खोजकर अधिकतम प्रवाह पाती है — अवशिष्ट ग्राफ (जिसमें 'पश्च' कोर शामिल हैं जो पूर्ववत् किए जा सकने योग्य प्रवाह दर्शाते हैं) में s से t तक ऐसा पथ जिसके अनुदिश अभी भी अधिक प्रवाह धकेला जा सके — व उस पथ के अनुदिश अवरोध (न्यूनतम अवशिष्ट क्षमता) को प्रवाह में जोड़ती है, जब तक कोई वर्धक पथ न बचे। अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहता है कि अधिकतम प्रवाह का मान ठीक-ठीक न्यूनतम कट की क्षमता के बराबर है (शीर्षों का दो समुच्चयों में विभाजन, एक में s व दूसरे में t, जिसकी क्षमता s-पक्ष से t-पक्ष पार करते कोरों की क्षमताओं का योग है) — अतः एक समस्या का उत्तर खोजना दूसरी को मुफ़्त में हल कर देता है।

🎯 मूल ग्राफ के बजाय अवशिष्ट ग्राफ ही क्यों खोजना चाहिए
केवल मूल ग्राफ के अग्र कोर खोजना उस स्थानीय रूप से-अच्छे-दिखते प्रवाह पर अटक सकता है जो वैश्विक रूप से अधिकतम नहीं — अवशिष्ट ग्राफ के पश्च कोर कलनविधि को किसी पूर्ववर्ती, उप-इष्टतम मार्गन-निर्णय के भाग को 'पूर्ववत्' करने देते हैं, प्रवाह को उस कोर से दूर पुनर्मार्गित करते हुए जो अवरोध सिद्ध होता है — यही ठीक वह है जो फ़ोर्ड-फुल्करसन को केवल स्थानीय इष्टतम के बजाय सिद्ध रूप से वास्तविक अधिकतम तक पहुँचाता है।

संख्या-सैद्धांतिक कलनविधियाँ, बहुपद अंकगणित व FFT

  • यूक्लिड कलनविधि बार-बार भाग देकर gcd(a, b) गणित करती है: gcd(a, b) = gcd(b, a mod b), शेषफल 0 होने पर समाप्त होते हुए — O(log(min(a, b))) भागों में चलती है, परीक्षण-गुणनखंडन से घातांकी रूप से तेज़, व इसका विस्तारित रूप अतिरिक्त रूप से पूर्णांक x, y गणित करता है जैसे ax + by = gcd(a, b), जो संख्या-सैद्धांतिक क्रिप्टोग्राफी में सर्वत्र आवश्यक मॉड्यूलर गुणनात्मक प्रतिलोम गणित करने का आधार है।
  • मॉड्यूलर घातांकन (aᵇ mod n दक्षतापूर्वक गणित करना) बार-बार वर्गीकरण प्रयोग करता है: b को द्विआधारी में लिखकर व हर बिट पर वर्ग-व-सशर्त-गुणा करते हुए, b − 1 के बजाय O(log b) गुणनों में aᵇ mod n गणित करते हुए — यही एकल तकनीक है जो RSA-शैली सार्वजनिक-कुंजी क्रिप्टोग्राफी (जिसे विशाल घातांकों सहित मॉड्यूलर घातांकन चाहिए) को गणनात्मक रूप से बिल्कुल संभव बनाती है।
  • बहुपद गुणन व FFT: दो n-घात बहुपदों को भोले संवलन सूत्र से गुणा करने में O(n²) लगता है; द्रुत फूरिये रूपांतरण हर बहुपद को 2n विशेष रूप से चुने (सम्मिश्र मूल-एकता) बिंदुओं पर O(n log n) में उसके बिंदु-मान निरूपण में बदलता है, बिंदु-मानों को O(n) में युग्म-वार गुणा करता है (क्योंकि हर बिंदु पर गुणा अब एकल अदिश गुणन है), फिर वापस बदलता है (व्युत्क्रम FFT, भी O(n log n)) — वही O(n log n)-बनाम-O(n²) त्वरण-प्रतिरूप जो जहाँ कहीं भी समस्या को उस डोमेन में ले जाया जा सके जहाँ महँगी संक्रिया सस्ती हो जाए व फिर वापस ले जाया जाए, दिखता है।

स्ट्रिंग-मेल कलनविधियाँ

स्ट्रिंग-मेल कलनविधियाँ, बढ़ती परिष्कृति में
कलनविधिविचार व जटिलता
भोला मेलपाठ में हर आरंभिक स्थिति पर प्रतिरूप आज़माएँ; बेमेल पर, ठीक एक खिसकाएँ व नए सिरे से पुनः आज़माएँ — निकृष्टतम स्थिति O(nm), बेमेल से मिली सारी आंशिक-मेल सूचना व्यर्थ करते हुए।
KMP (नुथ-मॉरिस-प्रैट)केवल प्रतिरूप से एक विफलता फलन पहले से गणित करती है (प्रतिरूप की उस दीर्घतम उचित उपसर्ग की लंबाई जो अब तक मेल खाए का प्रत्यय भी है), अतः बेमेल पर यह किसी पहले मेल खाए पाठ-अक्षर की पुनः जाँच कभी नहीं करती — O(n + m), पाठ केवल एक बार स्कैन किया जाता है।
रैबिन-कार्पप्रतिरूप के हैश की तुलना हर पाठ-खिड़की के हैश से प्रति खिसकाव O(1) में (औसतन) करने हेतु घूर्णी हैश प्रयोग करती है; हैश-मेल को झूठा धनात्मक रद्द करने हेतु फिर भी प्रत्यक्ष अक्षर-तुलना चाहिए — औसत O(n + m), अनेक हैश-टकरावों में निकृष्टतम स्थिति O(nm)।

समांतर, सन्निकटन व यादृच्छिकीकृत कलनविधियाँ

  • समांतर कलनविधियाँ (वर्गीकरण, खोज, विलय हेतु) अनेक एक साथ प्रक्रमण-अवयवों का लाभ उठाती हैं — मानक सैद्धांतिक प्रतिरूप PRAM (समांतर यादृच्छिक अभिगम मशीन) है, व चलने के समय से आगे मुख्य मापक त्वरण (क्रमिक समय ÷ समांतर समय) है व यह प्रक्रमकों की संख्या के साथ कैसे मापित होता है, क्योंकि केवल समस्या पर अधिक प्रक्रमक फेंक देना आनुपातिक रूप से अधिक त्वरण की गारंटी नहीं देता एक बार संचार/तुल्यकालन-भार या अंतर्निहित रूप से क्रमिक अवरोध (एमडाल का नियम) प्रधान हो जाए।
  • सन्निकटन कलनविधियाँ बहुपद समय में गणना-योग्य, सिद्ध रूप से इष्टतम के परिबद्ध गुणक के भीतर हल के बदले सटीकता का व्यापार करती हैं — विशेष रूप से वहाँ प्रयुक्त जहाँ ठीक समस्या NP-कठिन हो (उदा० शीर्ष-आवरण सन्निकटन जो हर अमेलित कोर के दोनों अंत-बिंदु चुनती है, बहुपद समय में सिद्ध रूप से वास्तविक न्यूनतम शीर्ष-आवरण के 2-गुणक के भीतर)। सन्निकटन-अनुपात यह बताने का मानक तरीका है कि गारंटी कितनी अच्छी है (2-सन्निकटन कभी इष्टतम से दोगुने से बुरा नहीं होता)।
  • यादृच्छिकीकृत कलनविधियाँ कलनविधि के भीतर ही यादृच्छिकता प्रयोग करती हैं, दो नामित प्रकारों में: लास वेगास कलनविधि सदा सही उत्तर उत्पन्न करती है पर उसका चलने का समय यादृच्छिक रूप से परिवर्तनशील है (उदा० यादृच्छिकीकृत क्विकसॉर्ट का पिवट-चुनाव, जो O(n²) निकृष्टतम स्थिति को किसी विरोधी द्वारा निर्धारणात्मक रूप से ट्रिगर-योग्य होने से बचाता है), जबकि मोंटे कार्लो कलनविधि सदा परिबद्ध समय में चलती है पर इसमें गलत उत्तर की छोटी, नियंत्रणीय प्रायिकता है (उदा० यादृच्छिकीकृत अभाज्यता-परीक्षण) — दोनों नाम इस बात से जुड़े हैं कि यादृच्छिकता का व्यापार किससे हो रहा है (समय-गारंटी बनाम शुद्धता-गारंटी), कितनी यादृच्छिकता प्रयुक्त है इससे नहीं।

मुख्य बिंदु

  • फ़ोर्ड-फुल्करसन अवशिष्ट ग्राफ में बार-बार वर्धक पथों से अधिकतम प्रवाह खोजती है; अधिकतम-प्रवाह न्यूनतम-कट प्रमेय अधिकतम प्रवाह के मान को न्यूनतम कट की क्षमता के बराबर करता है।
  • यूक्लिड कलनविधि व उसका विस्तारित रूप मॉड्यूलर प्रतिलोम का आधार है; बार-बार वर्गीकरण मॉड्यूलर घातांकन (व अतः RSA) को संभव बनाता है।
  • FFT-आधारित बहुपद गुणन बिंदु-मान डोमेन में जाकर, युग्म-वार गुणा कर, फिर वापस बदलकर, भोले O(n²) की तुलना में O(n log n) प्राप्त करता है।
  • KMP पाठ को केवल एक बार स्कैन करने हेतु विफलता फलन पहले से गणित करती है (O(n+m)); रैबिन-कार्प झूठे धनात्मकों के विरुद्ध प्रत्यक्ष-तुलना जाँच सहित घूर्णी हैश प्रयोग करती है।
  • सन्निकटन कलनविधियाँ बहुपद समय में सिद्ध रूप से-परिबद्ध निकट-इष्टतम उत्तर के बदले सटीकता का व्यापार करती हैं; लास वेगास कलनविधियाँ शुद्धता हेतु चलने-के-समय की गारंटी का व्यापार करती हैं, मोंटे कार्लो इसका उल्टा।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहता है कि:

    1. अधिकतम प्रवाह का मान न्यूनतम कट की क्षमता के बराबर है
    2. अधिकतम प्रवाह सदा शून्य होता है
    3. प्रवाह नेटवर्क में कोई कट कभी विद्यमान नहीं होता
    4. न्यूनतम कट सदा अधिकतम प्रवाह से बड़ा होता है
    उत्तर देखें

    उत्तर: A — अधिकतम प्रवाह का मान न्यूनतम कट की क्षमता के बराबर है

    यही समता ठीक वह है जो दो में से एक मात्रा खोजती कलनविधि को दूसरी का उत्तर मुफ़्त में देने देती है, और यही प्रमाणित करती है कि जब कोई वर्धक पथ न बचे तो फ़ोर्ड-फुल्करसन वस्तुतः वास्तविक अधिकतम तक पहुँच चुकी है।

  2. फ़ोर्ड-फुल्करसन केवल मूल ग्राफ के अग्र कोरों के बजाय अवशिष्ट ग्राफ मुख्यतः इसलिए खोजती है:

    1. पश्च अवशिष्ट कोर इसे किसी पूर्ववर्ती उप-इष्टतम मार्गन-निर्णय के भाग को पूर्ववत् करने देते हैं
    2. मूल ग्राफ में बिल्कुल कोई कोर नहीं है
    3. यह गारंटी देता है कि उत्तर सदा शून्य है
    4. यह स्रोत या सिंक की आवश्यकता समाप्त कर देता है
    उत्तर देखें

    उत्तर: A — पश्च अवशिष्ट कोर इसे किसी पूर्ववर्ती उप-इष्टतम मार्गन-निर्णय के भाग को पूर्ववत् करने देते हैं

    अवरोध सिद्ध होते कोर से प्रवाह पुनर्मार्गित करने की क्षमता के बिना, शुद्ध रूप से अग्र खोज उस स्थानीय रूप से अच्छे पर वैश्विक रूप से उप-इष्टतम प्रवाह पर अटक सकती थी।

  3. बार-बार वर्गीकरण से मॉड्यूलर घातांकन aᵇ mod n इसमें गणित करता है:

    1. O(log b) गुणन
    2. b − 1 गुणन
    3. O(n²) गुणन
    4. शून्य गुणन
    उत्तर देखें

    उत्तर: A — O(log b) गुणन

    घातांक को द्विआधारी में लिखकर व प्रति बिट वर्ग-व-सशर्त-गुणा करके भोले b − 1 गुणनों को O(log b) में घटाया जाता है, जो ठीक वही है जो क्रिप्टोग्राफ़िक रूप से बड़े घातांकों सहित घातांकन को संभव बनाता है।

  4. FFT-आधारित बहुपद गुणन भोली O(n²) विधि पर अपना त्वरण मुख्यतः इससे प्राप्त करता है:

    1. बिंदु-मान निरूपण में बदलकर जहाँ गुणन युग्म-वार व सस्ता है, फिर वापस बदलकर
    2. गुणन को पूर्णतः छोड़कर
    3. केवल ठीक घात 1 के बहुपदों हेतु काम करके
    4. अनंत संख्या में बिंदुओं की आवश्यकता रखकर
    उत्तर देखें

    उत्तर: A — बिंदु-मान निरूपण में बदलकर जहाँ गुणन युग्म-वार व सस्ता है, फिर वापस बदलकर

    दोनों बहुपदों को पर्याप्त बिंदुओं पर मूल्यांकित कर (FFT से O(n log n)), मान-वार गुणा कर (O(n)) व वापस अंतर्वेशित कर (व्युत्क्रम FFT से O(n log n)) साथ मिलकर बड़े n हेतु भोले O(n²) संवलन को हराते हैं।

  5. KMP स्ट्रिंग-मेल कलनविधि पहले-मेल खाए पाठ-अक्षरों की पुनः जाँच मुख्यतः इससे टालती है:

    1. पाठ स्कैन करने से पहले केवल प्रतिरूप से विफलता फलन पहले से गणित करके
    2. अगली स्थिति का यादृच्छिक अनुमान लगाकर
    3. केवल पाठ को पीछे से पढ़कर
    4. प्रतिरूप व पाठ की समान लंबाई की आवश्यकता रखकर
    उत्तर देखें

    उत्तर: A — पाठ स्कैन करने से पहले केवल प्रतिरूप से विफलता फलन पहले से गणित करके

    विफलता फलन, किसी पाठ-स्कैनिंग आरंभ होने से पहले प्रतिरूप से एक बार गणित, KMP को बताता है कि बेमेल पर ठीक कितना खिसकना है, बिना कोई पहले-पुष्ट आंशिक मेल खोए, पाठ केवल एक बार स्कैन कर O(n + m) प्राप्त करते हुए।

  6. लास वेगास बनाम मोंटे कार्लो यादृच्छिकीकृत कलनविधि के विषय में निम्नलिखित में कौन सही ढंग से वर्णित करते हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. लास वेगास कलनविधि सदा सही उत्तर उत्पन्न करती है पर उसका चलने का समय परिवर्तनशील है
    2. मोंटे कार्लो कलनविधि परिबद्ध समय में चलती है पर इसमें गलत उत्तर की छोटी संभावना है
    3. दोनों सदा गलत उत्तर देती हैं
    4. यादृच्छिकीकृत क्विकसॉर्ट का पिवट-चुनाव लास वेगास तकनीक है
    उत्तर देखें

    उत्तर: A — लास वेगास कलनविधि सदा सही उत्तर उत्पन्न करती है पर उसका चलने का समय परिवर्तनशील है; B — मोंटे कार्लो कलनविधि परिबद्ध समय में चलती है पर इसमें गलत उत्तर की छोटी संभावना है; D — यादृच्छिकीकृत क्विकसॉर्ट का पिवट-चुनाव लास वेगास तकनीक है

    लास वेगास गारंटीशुदा शुद्धता हेतु स्थिर चलने-का-समय त्यागती है (यादृच्छिकीकृत क्विकसॉर्ट का पिवटिंग मानक उदाहरण है); मोंटे कार्लो स्थिर चलने-के-समय हेतु गारंटीशुदा शुद्धता त्यागती है — कोई भी 'सदा गलत' नहीं है।

  7. उस मापक का नाम बताइए, जो क्रमिक चलने-के-समय को समांतर चलने-के-समय से भाग देकर परिभाषित है, जो यह मापने हेतु प्रयुक्त होता है कि समांतर कलनविधि अनेक प्रक्रमकों के प्रयोग से वस्तुतः कितना लाभ पाती है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: speedup

    त्वरण मानक मापक है, और यह प्रक्रमक-गिनती के साथ कैसे मापित होता है (अकेले किसी एक प्रक्रमक-गिनती पर उसका मान नहीं) यही उजागर करता है कि क्या संचार/तुल्यकालन-भार या एमडाल के नियम का क्रमिक अवरोध लाभ सीमित कर रहा है।

  8. न्यूनतमीकरण समस्या हेतु 2-सन्निकटन गारंटी वाली सन्निकटन कलनविधि का अर्थ है इसका निर्गम है:

    1. वास्तविक इष्टतम मान से दोगुने से कभी बुरा नहीं
    2. सदा ठीक इष्टतम मान के बराबर
    3. सदा ठीक इष्टतम मान का आधा
    4. इष्टतम मान से पूर्णतः असंबद्ध
    उत्तर देखें

    उत्तर: A — वास्तविक इष्टतम मान से दोगुने से कभी बुरा नहीं

    सन्निकटन-अनुपात कलनविधि के उत्तर व वास्तविक इष्टतम के बीच निकृष्टतम-स्थिति अंतर परिबद्ध करता है; 2-सन्निकटन गारंटी देता है कि लौटाया मान वास्तविक न्यूनतम से अधिकतम दोगुना है, अंतर्निहित समस्या NP-कठिन होने के बावजूद बहुपद समय में गणित।