हम आपके हस्ताक्षर को एक कुंडा तंत्र के साथ नकली करते हैं। केम्पे का प्रमेय

इस पोस्ट में मैं एक ऐसे प्रोग्राम के बारे में बात करूँगा जो किसी काज तंत्र का उपयोग करके कोई हस्ताक्षर करता है। कार्यक्रम केम्पे के प्रमेय पर आधारित है, जो 19 वीं शताब्दी के मध्य में सिद्ध हुआ।

केम्पे का प्रमेय

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

कई गणितज्ञों का मानना ​​था कि एक आदर्श सीधी रेखा खींचने वाली एक काज तंत्र बनाने की समस्या सिद्धांत रूप में अघुलनशील है, जब तक कि एक सरल रेखा खींचने वाला लिपिंक-पॉसेलियर तंत्र 19 वीं शताब्दी के मध्य में खोजा नहीं गया था:

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

प्रक्रिया है

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

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





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





इस तरह के घटता के साथ कपोविच-मिल्सन के एक लेख से घटता के साथ हमारे हस्ताक्षर (फूरियर श्रृंखला सिद्धांत) को अनुमानित करना और भी आसान है। दरअसल, यह फूरियर श्रृंखला के सिद्धांत से चलता है जो एक खंड पर है कार्यों और कोसाइन में विस्तारित किया जा सकता है। सन्निकटन सटीकता के लिए हमारे पास है:


गुणांक और खोजने में आसान है। आपको बस बाएं और दाएं की समानता को गुणा करना होगा और से एकीकृत को , फिर दाईं ओर लगभग सभी इंटीग्रल शून्य पर रीसेट हो जाते हैं, शब्द के साथ एक को छोड़कर पहली समानता में और शब्द के साथ दूसरे में। परिणाम है:

मैंने बहुत लंबे समय तक सोचा कि क्या इस पोस्ट में इन त्रिकोणमितीय वक्रों का निर्माण करने वाले टिका के निर्माण के लिए एक एल्गोरिदम रखा जाए। तब मुझे एहसास हुआ कि इससे पाठ में गणितीय नीरसता आ जाएगी। लोग आमतौर पर इस तरह के ग्रंथों में लंबे सबूत पढ़ना पसंद नहीं करते हैं। इसलिए, मुझे सिर्फ एक लिंक (अपडेट: दर्पण ) के साथ मिलेगा। जिज्ञासु लोग देख सकते हैं।
और यहाँ, वास्तव में, वह आवेदन ही है जो आपके हस्ताक्षर को गलत बताता है : david.wf/linkage । (upd: दर्पण ) कृपया ध्यान दें कि आप माउस के साथ डिजाइन को स्थानांतरित कर सकते हैं, और अंदर और बाहर ज़ूम करने के लिए स्कोरर का उपयोग कर सकते हैं (अपडेट: विशेष "सन्निकटन" स्लाइडर के साथ सन्निकटन की डिग्री को भी बदला जा सकता है)। आवेदन आधुनिक ब्राउज़रों पर काम करता है, मैंने पुराने पर परीक्षण नहीं किया। क्रोम पर सभी धीमा हो जाता है, क्योंकि केवल क्रोम अन्य ब्राउज़रों ( प्रोफाइल ) की तुलना में बहुत तेजी से सीधी रेखाएं खींचता है। सच कहूं, मैंने अनुकूलन पर बहुत प्रयास किया, ताकि कमजोर कंप्यूटर पर कुछ भी धीमा न हो, लेकिन, स्पष्ट रूप से, मुझे बहुत सफलता नहीं मिली। मैं एक बार फिर से जोर देता हूं कि कार्यक्रम का निर्माण करने वाला काज आपके हस्ताक्षर के अलावा कुछ भी नहीं खींच सकता है। काज एक कताई नीले त्रिकोण द्वारा संचालित है - "इंजन"।