सैद्धांतिक कंप्यूटर विज्ञान में मास्टर, अकादमिक विश्वविद्यालय (आरएएस)

सेंट पीटर्सबर्ग में, एक अद्भुत जगह है जहां कंप्यूटर वैज्ञानिक कंप्यूटर विज्ञान के सिद्धांतकार बनाते हैं। यह रूसी विज्ञान अकादमी (एयू आरएएस) का अकादमिक विश्वविद्यालय है।

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

लेकिन मैं अपने उदाहरण से बताना चाहता हूं कि सैद्धांतिक विभाग में एक छात्र बनने पर क्या दिलचस्प और गहन समस्याओं की जांच की जा सकती है और कितनी दिलचस्प है।

एयू में मेरा शोध कार्य

एयू के सैद्धांतिक विभाग में, एक मास्टर के काम को लिखने के लिए एक गंभीर अध्ययन की आवश्यकता होती है। एक ही समय में एक प्रकाशन पाने के लिए नेता बहुत कोशिश कर रहे हैं - जो पहले से ही बहुत लुभावना है।

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

प्रेरणा

आइए कुछ एनपी- संपूर्ण समस्या को देखें, उदाहरण के लिए, निष्पादन योग्य सूत्रों की भाषा। हम एल्गोरिदम पर विचार करेंगे जो किसी भी फॉर्मूले पर रुकते हैं और एक जवाब के रूप में एक बिट लौटाते हैं - यह फॉर्मूला संभव है या नहीं। अब 40 वर्षों के लिए, यह सवाल पूछा गया है कि क्या एल्गोरिदम के इस सेट के बीच एक बहुपद है, और कोई भी अभी तक इसका जवाब देने में सक्षम नहीं है। हालांकि, हम खुद से एक और, शायद सरल सवाल पूछ सकते हैं, क्या इस समस्या का एक इष्टतम एल्गोरिदम है - एक एल्गोरिथ्म जो एक बहुपद तक सभी दूसरों की तुलना में तेजी से काम करता है (क्योंकि हम केवल एल्गोरिदम के बहुपद में रुचि रखते हैं)। मान लीजिए कि इस तरह का एक इष्टतम एल्गोरिथ्म मौजूद है (आइए हम इसे ए कहते हैं), तो एनपी पी के बराबर नहीं है अगर और केवल अगर ए बहुपद नहीं है। यह पहले से ही कुछ है, क्योंकि हमें अपनी समस्या को हल करने वाले सभी संभव एल्गोरिदम के लिए ऐसा करने के बजाय एक विशेष एल्गोरिथ्म की गैर-बहुपदता साबित करने की आवश्यकता है।

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

इसलिए, इन दोनों प्रश्नों ने मेरे गुरु की थीसिस के लिए इष्टतम एल्गोरिदम का अध्ययन करने की प्रेरणा के रूप में कार्य किया और हमें वास्तव में इस दिशा में कुछ दिलचस्प मिला।

पिछला शोध

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

• अर्ध-एल्गोरिथ्म - संकल्प एल्गोरिथ्म का आधा - एक एल्गोरिथ्म जो भाषा से 1 इनपुट पर जवाब देता है और अन्य इनपुट पर नहीं रुकता है
• संभाव्य - एल्गोरिथ्म में यादृच्छिक बिट्स तक पहुंच है (एक ईमानदार सिक्का टॉस कर सकते हैं)
• हेयुरिस्टिक - एल्गोरिथ्म एक छोटी (सीमित) त्रुटि कर सकता है, और ऑपरेटिंग समय को बढ़ाकर इस त्रुटि को मनमाने ढंग से छोटा किया जा सकता है।

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

परिणाम

यादृच्छिक बिट्स का उपयोग करने के बजाय, आपको इनपुट से यादृच्छिकता (एन्ट्रॉपी) निकालने की कोशिश करनी चाहिए (क्योंकि अब और कहीं नहीं जाना है)। यह एक द्विदलीय "मिक्सिंग" ग्राफ (एक लुकअप टेबल की तरह कुछ) का उपयोग करके किया जा सकता है, जहां बाएं लोब में हम इनपुट द्वारा अनुक्रमित करेंगे, और दाएं लोब से कई आसन्न कोने हमें कई छद्म यादृच्छिक बिट्स देंगे।

ग्राफ के लिए आवश्यक शर्तों को तैयार करने के पहले प्रयास के बाद, हमने महसूस किया कि यह आमतौर पर ऐसा करना संभव नहीं था, इसलिए हमने एक सरल मामले पर विचार करने का फैसला किया - एक इंजेक्शन फ़ंक्शन की छवियों के सेट की भाषा जो इसके इनपुट को एक बिट से बढ़ाती है। यहाँ पाठक (यदि ऐसे पाठक हैं जो यहाँ मिले हैं) को एक वैध आक्रोश होना चाहिए: "जो इस तरह की भाषाओं की परवाह करता है"? हालांकि, मान लें कि हम एक छद्म यादृच्छिक जनरेटर (काफी विश्वसनीय इंजेक्शन जनरेटर के अस्तित्व में रुचि रखते हैं जो अपने इनपुट को एक बिट से बढ़ाते हैं एक खुला प्रश्न है)। तब हम इष्टतम एल्गोरिथ्म प्राप्त करेंगे जो कहेंगे: "क्या यह सच है कि हमारे जनरेटर द्वारा दी गई (उसे) संख्या उत्पन्न हुई थी"? यदि यह इष्टतम एल्गोरिथ्म बहुपद हो, तो हम जनरेटर को "तोड़" देंगे, अर्थात्। हम उन संख्याओं को भेद करते हैं जो इसे वास्तव में यादृच्छिक से उत्पन्न करती हैं! यह वास्तव में बहुत अच्छा होगा, क्योंकि हम लगभग सभी मौजूदा क्रिप्टोकरंसी पर हमले पाएंगे।

तो, इस मामले में, व्युत्पन्नता सफल हुई, और इसके अलावा, हमने न केवल इष्टतम अनुमानी अर्ध-एल्गोरिदम बनाया, बल्कि इसे पूर्ण एल्गोरिथ्म के साथ पूरक किया।

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

ग्रेजुएट स्कूल एयू में जाने के पांच कारण ...

... यदि आप सैद्धांतिक कंप्यूटर विज्ञान करना चाहते हैं:

1. एयू सेंट पीटर्सबर्ग में एकमात्र जगह है और रूस में कुछ में से एक है जहां आप अपने आप को सैद्धांतिक कंप्यूटर विज्ञान के अध्ययन के लिए समर्पित कर सकते हैं।
2. ऊर्जावान और निर्विवाद रूप से प्रतिभाशाली वैज्ञानिक एयू में काम करते हैं।
3. एयू में, छात्र पाठ्यक्रम को प्रभावित कर सकते हैं और अपनी इच्छानुसार पाठ्यक्रमों का हिस्सा चुन सकते हैं।
4. एयू विदेशी लोगों सहित स्कूलों की यात्राएं प्रायोजित करता है।
5. एयू में आपको एक अद्भुत एस्प्रेसो मशीन से मुफ्त कॉफी मिलेगी! (ताकि प्रमेयों में कुछ संसाधित किया जा सके)।

एयू से स्नातक होने के बाद मैं क्या करूं?

मैं स्टैनफोर्ड में सैद्धांतिक कंप्यूटर विज्ञान करना जारी रखता हूं। पिछली तिमाही में, मैं डैन बोन के साथ एन्क्रिप्टेड डेटा पर गणना कर रहा था, और अब मैं रयान विलियम्स के साथ सर्किट जटिलता से निपटूंगा।

तो, मेरी सलाह - इसके लिए जाओ, यह एक कोशिश के काबिल है! अभी आवेदन जमा किया जा सकता है।