🏂🏽 ◀️ 🥁 "पायथन में शास्त्रीय कंप्यूटर विज्ञान कार्य" पुस्तक ✌🏾 🙌🏼 👩🏻‍💻

कंप्यूटर विज्ञान के क्षेत्र में कई कार्य, जो पहली नज़र में नए या अद्वितीय लगते हैं, वास्तव में शास्त्रीय एल्गोरिदम, कोडिंग विधियों और विकास सिद्धांतों में निहित हैं। और स्थापित तकनीक अभी भी ऐसी समस्याओं को हल करने का सबसे अच्छा तरीका है!

पुस्तक आपको पायथन भाषा को गहराई से जानने, समय-परीक्षण किए गए कार्यों, अभ्यासों और एल्गोरिदम का परीक्षण करने का अवसर देगी। आपको दर्जनों प्रोग्रामिंग कार्यों को हल करना होगा: सरलतम से (उदाहरण के लिए, बाइनरी सॉर्टिंग का उपयोग करके सूची आइटम खोजना) जटिल लोगों के लिए (k- साधन विधि का उपयोग करके डेटा को क्लस्टर करना)। खोज, क्लस्टरिंग, ग्राफ़ आदि के लिए समर्पित उदाहरणों के माध्यम से काम करते हुए, आपको याद होगा कि आप अपनी समस्याओं को सुलझाने के लिए शास्त्रीय तकनीकों के बारे में क्या भूल गए थे और मास्टर थे।

यह पुस्तक किसके लिए है?

यह पुस्तक मध्यम और उच्च स्तर के प्रोग्रामर के लिए है। अनुभवी पेशेवर जो पायथन के अपने ज्ञान को गहरा करना चाहते हैं, यहां उन कार्यों को मिलेगा जो उस समय से परिचित हैं जो उन्होंने कंप्यूटर विज्ञान या प्रोग्रामिंग सिखाया था। मध्य स्तर के प्रोग्रामर अपनी चुनी हुई भाषा में इन क्लासिक कार्यों से परिचित हो जाएंगे - पायथन। डेवलपर्स के लिए जो एक प्रोग्रामिंग साक्षात्कार की तैयारी कर रहे हैं, प्रकाशन के लिए मूल्यवान तैयारी सामग्री बनने की संभावना है।

पेशेवर प्रोग्रामर के अलावा, इस पुस्तक को कंप्यूटर विज्ञान में स्नातक कार्यक्रमों और पाइथन में रुचि रखने वाले छात्रों के लिए उपयोगी माना जा सकता है। यह डेटा संरचनाओं और एल्गोरिदम के लिए एक कठोर परिचय होने का दावा नहीं करता है। यह डेटा संरचनाओं और एल्गोरिदम पर एक ट्यूटोरियल नहीं है। आपको इसके पृष्ठों पर प्रमेय का प्रमाण या O बड़ी सूचनाओं का प्रचुर उपयोग नहीं मिलेगा। इसके विपरीत, यह पुस्तक समस्याओं को हल करने के तरीकों के लिए एक सुलभ व्यावहारिक मार्गदर्शिका के रूप में तैनात है जो डेटा संरचना, एल्गोरिदम और कृत्रिम बुद्धि के वर्गों का अध्ययन करने का अंतिम उत्पाद बनना चाहिए।

मैं फिर से जोर देता हूं: यह माना जाता है कि पाठक पायथन के वाक्यविन्यास और शब्दार्थ से परिचित हैं। शून्य प्रोग्रामिंग अनुभव वाले पाठक को इस पुस्तक से लाभ होने की संभावना नहीं है, और पायथन में शून्य अनुभव वाला एक प्रोग्रामर शायद मुश्किल होगा। दूसरे शब्दों में, "पायथन में शास्त्रीय कंप्यूटर विज्ञान कार्य" पायथन प्रोग्रामर और कंप्यूटर विज्ञान के छात्रों के लिए एक पुस्तक है।

अंश। 1.5। हनोई टावर

तीन लम्बे ऊर्ध्वाधर स्तंभ हैं (बाद में - टॉवर)। हम उन्हें नामित करेंगे ए, बी और सी। केंद्र में छेद के साथ डिस्क टॉवर ए पर फैली हुई है। सबसे व्यापक डिस्क - हम इसे डिस्क 1 कहेंगे - नीचे स्थित है। इसके ऊपर स्थित शेष डिस्क संख्याओं को बढ़ाकर और धीरे-धीरे टेंपर करके इंगित किए जाते हैं। उदाहरण के लिए, यदि हमारे पास तीन डिस्क हैं, तो सबसे चौड़ी, नीचे वाली, नंबर 1 होगी। अगली 2 पर सबसे चौड़ी डिस्क, डिस्क के ऊपर स्थित होगी। 1. अंत में, सबसे छोटी डिस्क, नंबर 3 पर डिस्क 2 पर झूठ होगा।

हमारा लक्ष्य निम्नलिखित प्रतिबंधों को ध्यान में रखते हुए टॉवर ए से टॉवर सी तक सभी ड्राइव को स्थानांतरित करना है।

डिस्क को केवल एक बार में ही स्थानांतरित किया जा सकता है।
चलने के लिए उपलब्ध एकमात्र ड्राइव किसी भी टॉवर के शीर्ष पर स्थित है।
एक संकीर्ण एक के ऊपर एक व्यापक ड्राइव कभी नहीं रखी जा सकती है।
योजना के अनुसार, कार्य अंजीर में दिखाया गया है। 1.7।

1.5.1। टॉवर मॉडलिंग

स्टैक एक डेटा संरचना है जो अंतिम-इन-पहले (एलआईएफओ) सिद्धांत पर आधारित है। आखिरी चीज जो स्टैक पर मिलती है वह पहले वाली हो जाती है जिसे वहां से लाया जाता है। स्टैक के दो मुख्य संचालन पुश (पुट) और पॉप (एक्सट्रैक्ट) हैं। पुश ऑपरेशन स्टैक पर एक नए आइटम को धकेलता है, और पॉप इसे स्टैक से हटा देता है और अंतिम आइटम को सम्मिलित करता है। आप बैकअप स्टोरेज के रूप में सूची का उपयोग करके पायथन में स्टैक को आसानी से मॉडल कर सकते हैं (लिस्टिंग 1.20)।

लिस्टिंग 1.20। hanoi.py

from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container)

प्रस्तुत स्टैक वर्ग __repr __ () विधि को लागू करता है, जो टॉवर की सामग्री की जांच करना आसान बनाता है। __repr __ () क्या है जब आउटपुट स्टैक पर लागू किया जाता है।

जैसा कि परिचय में कहा गया है, पुस्तक में टाइप एनोटेशन का उपयोग किया जाता है। एक इनपुट मॉड्यूल से जेनेरिक आयात करना स्टैक को एक विशेष प्रकार के एनोटेशन में पैरामीट्रिक वर्ग होने की अनुमति देता है। एक मनमाना प्रकार T को T = TypeVar ('T') में परिभाषित किया गया है। T किसी भी प्रकार का हो सकता है। जब हनोई टॉवर समस्या को हल करने में स्टैक के लिए बाद में एनोटेशन का उपयोग किया जाता है, तो प्रॉम्प्ट स्टैक [इंट] होगा, अर्थात, टी के बजाय इंट टाइप का उपयोग किया जाएगा। दूसरे शब्दों में, यहाँ स्टैक पूर्णांक का एक स्टैक है। यदि आपको टाइप एनोटेशन से कठिनाई हो रही है, तो परिशिष्ट B पर एक नज़र डालें।

हनोई टावर चुनौती के लिए ढेर हैं। टॉवर में डिस्क को स्थानांतरित करने के लिए, हम पुश ऑपरेशन का उपयोग कर सकते हैं। डिस्क को एक टॉवर से दूसरे टॉवर में ले जाने के लिए, हम इसे पहले (पॉप) से धक्का दे सकते हैं और दूसरे (पुश) पर रख सकते हैं।

स्टैक ऑब्जेक्ट के रूप में टावरों को परिभाषित करें और डिस्क के साथ पहले एक भरें (लिस्टिंग 1.21)।

लिस्टिंग 1.21। hanoi.py (जारी)

 num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i)

1.5.2। हनोई टावर्स समस्या का समाधान

मैं हनोई टावरों की समस्या को कैसे हल कर सकता हूं? मान लीजिए हम केवल एक ड्राइव को स्थानांतरित करने की कोशिश कर रहे हैं। तब हमें पता होगा कि यह कैसे करना है, है ना? वास्तव में, एक डिस्क को स्थानांतरित करना इस समस्या के पुनरावर्ती समाधान के लिए एक मूल मामला है। एकाधिक ड्राइव को स्थानांतरित करना एक पुनरावर्ती मामला है। मुख्य बिंदु यह है कि वास्तव में, हमारे पास दो परिदृश्य हैं जिन्हें एन्कोडेड करने की आवश्यकता है: एक डिस्क (बेस केस) और कई डिस्क (पुनरावर्ती मामले) को स्थानांतरित करना।

पुनरावर्ती मामले को समझने के लिए, एक विशिष्ट उदाहरण पर विचार करें। मान लीजिए कि हमारे पास तीन डिस्क हैं - ऊपरी, मध्य और निचला, टॉवर ए पर स्थित है, और हम उन्हें टॉवर सी में स्थानांतरित करना चाहते हैं (इसके बाद, यह समस्या का योजनाबद्ध रूप से वर्णन करने में मदद करेगा।) पहले हम ऊपरी डिस्क को टॉवर सी में स्थानांतरित कर सकते थे। फिर ... मध्य डिस्क को टॉवर बी में ले जाएं, और फिर टॉवर सी से टॉवर बी तक ऊपरी डिस्क। अब हमारे पास निचले डिस्क अभी भी टॉवर ए पर स्थित हैं और टॉवर बी पर दो ऊपरी डिस्क आवश्यक रूप से, हम पहले से ही सफलतापूर्वक दो स्थानांतरित कर चुके हैं एक टॉवर (ए) से दूसरे (बी) तक ड्राइव करें। निचली डिस्क को A से C पर ले जाना मूल मामला (चलती एक डिस्क) है। अब हम B से C तक दो ऊपरी डिस्क को A से B तक एक ही प्रक्रिया का उपयोग करके स्थानांतरित कर सकते हैं। हम ऊपरी डिस्क को A, मध्य डिस्क को C और अंत में ऊपरी डिस्क को A से C में स्थानांतरित करते हैं।

कंप्यूटर विज्ञान कक्षाओं में, इन टावरों के छोटे मॉडल अक्सर पाए जाते हैं, जो पिन और प्लास्टिक डिस्क से निर्मित होते हैं। आप तीन पेंसिल और कागज की तीन शीट के साथ अपना मॉडल बना सकते हैं। शायद यह आपको समाधान की कल्पना करने में मदद करेगा।

तीन डिस्क के साथ उदाहरण में, एक डिस्क को स्थानांतरित करने का एक सरल मूल मामला था और एक अस्थायी तीसरे टॉवर का उपयोग करके शेष डिस्क (दो इस मामले में) को स्थानांतरित करने का एक पुनरावर्ती मामला था। हम पुनरावर्ती मामले को निम्न चरणों में तोड़ सकते हैं।

एक मध्यवर्ती टॉवर के रूप में C का उपयोग करके टॉवर A से टॉवर B (अस्थायी) तक शीर्ष n - 1 ड्राइव को स्थानांतरित करें।
लो ड्राइव को A से C पर ले जाएं।
टॉवर बी से टॉवर सी, एन ए के 1 डिस्क्स, टॉवर ए मध्यवर्ती है।

हैरानी की बात है, यह पुनरावर्ती एल्गोरिदम न केवल तीन के लिए, बल्कि किसी भी संख्या में डिस्क के लिए काम करता है। इसे एक हनोई () फ़ंक्शन के रूप में एनकोड करें, जो तीसरे अस्थायी टॉवर (लिस्टिंग 1.22) का उपयोग करके डिस्क को एक टॉवर से दूसरे तक ले जाने के लिए जिम्मेदार है।

लिस्टिंग 1.22। hanoi.py (जारी)

 def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1)

हनोई () को कॉल करने के बाद, आपको यह सुनिश्चित करने के लिए टॉवर ए, बी और सी की जांच करने की आवश्यकता है कि डिस्क सफलतापूर्वक स्थानांतरित हो गई हैं (लिस्टिंग 1.23)।

लिस्टिंग 1.23। hanoi.py (जारी)

 if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c)

आप पाएंगे कि ड्राइव वास्तव में चले गए हैं। हनोई टॉवर समस्या के समाधान को कोड करते समय, टॉवर ए से टॉवर सी तक कई डिस्क को स्थानांतरित करने के लिए आवश्यक हर कदम को समझना आवश्यक नहीं है। हम किसी भी संख्या में डिस्क को व्यवस्थित करने के लिए सामान्य पुनरावर्ती एल्गोरिथ्म को समझने और इसे व्यवस्थित करने के लिए आए, जिससे कंप्यूटर को आराम करने की अनुमति मिलती है। यह समस्याओं के पुनरावर्ती समाधान तैयार करने की शक्ति है: हम अक्सर प्रत्येक व्यक्तिगत कार्रवाई के मानसिक प्रतिनिधित्व पर ऊर्जा बर्बाद किए बिना, सार में समाधान की कल्पना कर सकते हैं।

वैसे, हनोई () फ़ंक्शन को डिस्क की संख्या के आधार पर तेजी से निष्पादित किया जाएगा, जो 64 डिस्क के अनुपयुक्त होने पर भी समस्या का समाधान करता है। आप चर num_discs को बदलकर डिस्क की एक अलग संख्या के साथ इसे निष्पादित करने का प्रयास कर सकते हैं। जैसे-जैसे डिस्क की संख्या बढ़ती है, हनोई टॉवर कार्य को पूरा करने के लिए चरणों की संख्या तेजी से बढ़ती है, कई स्रोतों में अधिक विवरण पाया जा सकता है। यदि आप इस समस्या के पुनरावर्ती समाधान के पीछे गणित के बारे में अधिक जानने में रुचि रखते हैं, तो "ऑन हनोई टावर्स" लेख में कार्ल बर्च का विवरण देखें।

1.6। वास्तविक अनुप्रयोग

इस अध्याय में प्रस्तुत किए गए विभिन्न तरीके (पुनरावृत्ति, ज्ञापन, संपीड़न, और बिट स्तर पर हेरफेर) आधुनिक सॉफ्टवेयर के विकास में इतने व्यापक हैं कि उनके बिना कंप्यूटिंग की दुनिया की कल्पना करना असंभव है। इस तथ्य के बावजूद कि कार्यों को उनके बिना हल किया जा सकता है, इन विधियों का उपयोग करके उन्हें हल करना अक्सर अधिक तार्किक या समीचीन होता है।

विशेष रूप से, पुनरावृत्ति न केवल कई एल्गोरिदम, बल्कि संपूर्ण प्रोग्रामिंग भाषाओं को भी रेखांकित करती है। कुछ कार्यात्मक प्रोग्रामिंग भाषाओं में, जैसे कि स्कीम और हास्केल, पुनरावर्तन अनिवार्य भाषाओं में प्रयुक्त लूप को बदल देता है। हालांकि, यह याद रखना चाहिए कि पुनरावर्ती पद्धति का उपयोग करके प्राप्त किया जा सकता है कि सब कुछ भी iteratively किया जा सकता है।

संस्मरण का उपयोग सफलतापूर्वक पार्सर्स के काम को तेज करने के लिए किया गया है - प्रोग्राम जो भाषाओं की व्याख्या करते हैं। यह उन सभी कार्यों में उपयोगी है जहां हाल ही में गणना के परिणाम को फिर से अनुरोध किए जाने की संभावना है। संस्मरण के लिए कार्रवाई का एक अन्य क्षेत्र प्रोग्रामिंग भाषा रनटाइम है। इनमें से कुछ रनटाइम, उदाहरण के लिए, प्रोलॉग संस्करण के लिए, स्वचालित रूप से फ़ंक्शन कॉल (ऑटो-मैश) के परिणामों को सहेजते हैं, इसलिए अगली बार उसी कॉल के साथ फ़ंक्शन को निष्पादित नहीं करना पड़ता है। यह fib6 में @lru_cache () डेकोरेटर के समान है ()।

कम्प्रेशन ने इंटरनेट की दुनिया को, अपने सीमित बैंडविड्थ के साथ, अधिक सहने योग्य बना दिया है। धारा 1.2 में चर्चा की गई बिट स्ट्रिंग विधि वास्तविक दुनिया में सरल डेटा प्रकारों पर लागू होती है जिनमें सीमित संख्या में संभावित मान होते हैं, जिसके लिए 1 बाइट भी बेमानी है। हालांकि, अधिकांश संपीड़न एल्गोरिदम एक डेटासेट में पैटर्न या संरचनाओं की तलाश में काम करते हैं जो डुप्लिकेट जानकारी को समाप्त करते हैं। वे खंड 1.2 में वर्णित की तुलना में बहुत अधिक जटिल हैं।

डिस्पोजेबल सिफर सामान्य एन्क्रिप्शन मामलों के लिए उपयुक्त नहीं हैं। उन्हें यह आवश्यक है कि एनकोडर और डिकोडर दोनों के पास मूल डेटा को पुनर्स्थापित करने के लिए कुंजी (हमारे उदाहरण में डमी डेटा) में से एक है, जो बहुत बोझिल है और अधिकांश एन्क्रिप्शन योजनाओं में कुंजी को गुप्त रखने के लक्ष्य को प्राप्त करने की अनुमति नहीं देता है। लेकिन आपको यह जानने में दिलचस्पी हो सकती है कि नाम "डिस्पोजेबल सिफर" का आविष्कार जासूसों द्वारा किया गया था, जिन्होंने शीत युद्ध के दौरान एन्क्रिप्टेड संदेशों को बनाने के लिए उनमें दर्ज किए गए काल्पनिक डेटा के साथ वास्तविक पेपर नोटबुक का उपयोग किया था।

ये विधियां कार्यक्रमों के निर्माण खंड हैं, अन्य एल्गोरिदम उन पर आधारित हैं। निम्नलिखित अध्यायों में आप देखेंगे कि वे कितने व्यापक रूप से लागू होते हैं।

लेखक के बारे में

डेविड कोपेक वर्मोंट के बर्लिंगटन में चम्पलेन कॉलेज में कंप्यूटर विज्ञान और नवाचार में एक वरिष्ठ व्याख्याता हैं। वह एक अनुभवी सॉफ्टवेयर डेवलपर और स्विफ्ट (मैनिंग, 2018) में क्लासिक कंप्यूटर साइंस प्रॉब्लम्स के लेखक और डार्ट फॉर एब्सोल्यूट बिगिनर्स (एप्रेस, 2014) के लेखक हैं। डेविड ने अर्थशास्त्र में स्नातक की डिग्री और डार्टमाउथ कॉलेज से कंप्यूटर विज्ञान में स्नातकोत्तर की डिग्री हासिल की। आप उनसे ट्विटर पर @davekopec से संपर्क कर सकते हैं।

»पुस्तक की अधिक जानकारी प्रकाशक की वेबसाइट पर पाई जा सकती है
» सामग्री
» अंश

फेरीवालों के लिए कूपन पर 25% की छूट - पायथन

पुस्तक के पेपर संस्करण के भुगतान पर, एक इलेक्ट्रॉनिक पुस्तक ई-मेल द्वारा भेजी जाती है।