The Complexity of Songs
"द कॉम्प्लेक्सिटी ऑफ सॉन्ग्स" 1977 में कंप्यूटर वैज्ञानिक डोनाल्ड क्नुथ का एक विद्वतापूर्ण लेख है, जो कम्प्यूटेशनल जटिलता सिद्धांत के बारे में एक मजाक के रूप में है। लेख लोकप्रिय गीतों की लंबी और विषय-वस्तु से भरपूर गाथागीतों से लेकर बहुत कम या कोई सार्थक विषय-वस्तु के साथ अत्यधिक दोहराए जाने वाले ग्रंथों की प्रवृत्ति को बढ़ावा देता है। लेख में कहा गया है कि लंबाई एन शब्दों का एक गीत याद रखते हुए बनाया जा सकता है, उदाहरण के लिए, केवल शब्द (गीत की "स्थान जटिलता") या उससे भी कम। लेख सारांश क्नुथ लिखते हैं कि "हमारे प्राचीन पूर्वजों ने गीतों की स्थान जटिलता को कम करने के लिए संयम की अवधारणा का आविष्कार किया", जो तब महत्वपूर्ण हो जाता है जब बड़ी संख्या में गीतों को किसी की स्मृति के लिए प्रतिबद्ध किया जाना होता है। क्नुथ के लेम्मा 1 में कहा गया है कि यदि एन एक गीत की लंबाई है, तो विराम गीत की जटिलता को सीएन तक कम कर देता है, जहां कारक सी <1 है। नुथ आगे ओ () जटिलता के साथ गीतों के निर्माण का एक तरीका प्रदर्शित करता है, एक दृष्टिकोण "ओ मैकडोनाल्ड नामक एक स्कॉटिश किसान द्वारा और सुधार किया गया"। अधिक सरल दृष्टिकोण जटिलता ओ () के गीत देते हैं, एक वर्ग जिसे "दीवार पर बीयर की एम बोतलों" के रूप में जाना जाता है। अंत में, 20वीं शताब्दी के दौरान प्रगति-इस तथ्य से प्रेरित है कि "आधुनिक दवाओं के आगमन ने अभी भी कम स्मृति की मांग की है"-अंतिम सुधार की ओर ले जाता हैः अंतरिक्ष जटिलता ओ (1) के साथ मनमाने ढंग से लंबे गाने मौजूद हैं, जैसे। पुनरावृत्ति संबंध द्वारा परिभाषित एक गीत 'यही तरीका है', 'मुझे यह पसंद है', सभी के लिए 'उह हुह', 'उह हुह' आगे के विकास सैन डिएगो स्टेट यूनिवर्सिटी के प्रो. कर्ट आइज़मैन ने एसीएम के संचार को अपने पत्र में बाद वाले प्रतीत होने वाले अपराजेय अनुमान में और सुधार किया है। वह एक अवलोकन के साथ शुरू करते हैं कि व्यावहारिक अनुप्रयोगों के लिए बिग ओह संकेतन में "छिपे हुए स्थिरांक" सी का मान व्यवहार्यता और व्यवहार्यता के बीच अंतर करने में महत्वपूर्ण हो सकता हैः उदाहरण के लिए 1080 का एक स्थिर मान किसी भी ज्ञात उपकरण की क्षमता से अधिक होगा। उन्होंने आगे ध्यान दिया कि मध्यकालीन यूरोप में पहले से ही एक तकनीक ज्ञात है जिसके द्वारा एक मनमाने धुन की पाठ्य सामग्री को पुनरावृत्ति संबंध के आधार पर दर्ज किया जा सकता है, जहां, 2 के बराबर बड़े-ओह स्थिरांक c का मूल्य प्राप्त होता है। हालांकि यह पता चला है कि एक अन्य संस्कृति ने ओ (0) की पूर्ण निचली सीमा हासिल की। जैसा कि प्रो. आइज़मैन कहते हैंः "जब मेफ्लावर समुद्री यात्री पहली बार इन तटों पर उतरे, तो मूल अमेरिकियों को सूचना भंडारण और पुनर्प्राप्ति के सिद्धांत में अपनी उपलब्धि पर गर्व था, पहले तो उन्होंने पूरी खामोशी के साथ अजनबियों का स्वागत किया। इसका उद्देश्य गीतों की जटिलता में उनकी चरम उपलब्धि को व्यक्त करना था, अर्थात् यह प्रदर्शन कि सी = 0 जितनी कम सीमा वास्तव में प्राप्त करने योग्य है। हालाँकि यूरोपीय लोग इस धारणा को समझने के लिए तैयार नहीं थे, और प्रमुखों ने अपनी उपलब्धियों को व्यक्त करने के लिए एक सामान्य आधार स्थापित करने के लिए बाद में आवर्ती संबंध द्वारा वर्णित एक दृष्टिकोण का प्रदर्शन करने के लिए आगे बढ़े, जहाँ, सी = 1 द्वारा दी गई एक उप-इष्टतम जटिलता के साथ। ओ (1) अंतरिक्ष जटिलता परिणाम को गाय एल. स्टील, जूनियर द्वारा भी लागू किया गया था, जिसे शायद क्नुथ के लेख द्वारा चुनौती दी गई थी। डॉ. स्टील के टेलनेट गीत ने घातीय पुनरावृत्ति पर आधारित एक पूरी तरह से अलग एल्गोरिथ्म का उपयोग किया, जो टेलनेट के कुछ कार्यान्वयनों पर एक पैरोडी है। दर्रा चावे ने सुझाव दिया कि मानव गीतों का जटिलता विश्लेषण छात्रों को जटिलता सिद्धांत सिखाने के लिए एक उपयोगी शैक्षणिक उपकरण हो सकता है। प्रो. एलन शेरमन का लेख "ऑन सुपरपोलिलोगैरिथमिक सबएक्सपोनेंशियल फंक्शंस" लिखते हैं कि क्नुथ का लेख कार्यों के एक विशेष वर्ग के विश्लेषण के लिए मौलिक था। संदर्भ बाहरी लिंक "गीतों की जटिलता", क्नुथ, डोनाल्ड ई. (1984)। कम्प्यूटेशनल जटिलता सिद्धांत संगीत का गणित इन-जॉक्स कंप्यूटर हास्य डोनाल्ड क्नुथ 1977 दस्तावेज़ कंप्यूटर विज्ञान के पेपर संगीत और हास्य