परिमित बीजगणित, ज्यामितीय और कोड। यैंडेक्स में ग्रिगोरी कबाट्यान्स्की द्वारा व्याख्यान

हालाँकि हमारे आस-पास की दुनिया में लगभग सब कुछ, हाल ही में, गणित में अनंत वस्तुओं का वर्चस्व है। परिमित गणित में एक गंभीर रुचि केवल आधी सदी पहले पैदा हुई - पहले कंप्यूटरों के आगमन के साथ। और अनंत (निरंतर) गणित हमारे लिए बहुत अधिक परिचित और समझने योग्य है।

यह व्याख्यान इतिहास के एक अद्भुत मोड़ के लिए समर्पित है जब परिमित क्षेत्र (गाल्वा क्षेत्र), पहले से ही कई पेशेवर गणितज्ञों के लिए भी अपरिचित, अचानक इंजीनियरों द्वारा मांग में बन गए, और इसने परिमित क्षेत्रों और संबंधित वस्तुओं के सिद्धांत के बारे में हमारे ज्ञान को बदल दिया।



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

निम्नलिखित कार्यों को एक ही वर्ग के लिए जिम्मेदार ठहराया जा सकता है:

• कितने को n- आयामी आकार के आकार के q × q ... × q पर रखा जा सकता है ताकि कोई भी क्षेत्र एक से अधिक बार न धड़कें?
• किस प्रकार के n और q में रूक की ऐसी व्यवस्था n- आयामी आकार के आकार के q × q ... × q पर मौजूद है जैसे कि प्रत्येक क्षेत्र एक बार धड़कता है?

मकड़ियों के बारे में

त्रि-आयामी अंतरिक्ष में, सब कुछ काफी स्पष्ट है: Sp (3) = 2 ? चूंकि अगर हम तीन-आयामी घन के कोने पर दो मकड़ियों को रखते हैं, तो वे आवश्यक रूप से विपरीत हैं, और उनके पंजे के साथ तीन आउटगोइंग कोने पर कब्जा कर लेते हैं। तीसरा मकड़ी डालने के लिए कहीं नहीं है।
मकड़ियों की अधिकतम संख्या कब ज्ञात की जाती है?
Sp (3) = 2, Sp (4) = 2, Sp (5) = 4, Sp (6) = 8, Sp (7) = 16 ... ?
Sp (15) = 2 ¹¹ , Sp (14) = 2 ¹⁰ , Sp (13) = 2 ⁹ , Sp (12) = 2 ⁸
लेकिन Sp (8) = 20, Sp (9) = 40, Sp (10) = 72, Sp (11) = 144
वह Sp (10) ≥ 72; Sp (11) ≥ 144 एक लंबे समय के लिए जाना जाता था, लेकिन यह केवल 1999 में समानता साबित करना संभव था।

हम बताते हैं कि यदि Sp (2 ^r -1) = 2 ^{2 r -1-r है} , तो यह मकड़ियों (या q = 2 के साथ बदमाशों) की सही व्यवस्था है। प्रत्येक मकड़ी शीर्ष पर रहती है, जहां वह बैठती है, और n = 2 ^r - 1 अधिक कोने, जहां उसके पंजे पहुंचते हैं। कुल n + 1 = 2 ^r शीर्ष पर एक मकड़ी का कब्जा होता है, और उनके Sp (2 ^r -1) = 2 ^{2 r -1-r} = 2 ^{nr होते हैं} । इसलिए, क्यूब के सभी कोने पर कब्जा कर लिया गया है - यह सही व्यवस्था है।

हम सी कोने के सेट को परिभाषित करते हैं जहां मकड़ियों तीन रैखिक समीकरणों की एक प्रणाली द्वारा n = 7 के लिए बैठते हैं।
x _{1 7} x _{3 5} x ₅ = x ₇ = 0; x _{2 7} x _{3 6} x ₆ = x ₇ = 0; x _{4 7} x _{5 6} x ₆ = x ₇ = 0 , जहाँ a2 b mod2 में जोड़ है , अर्थात। 1 mod1 = 0 ( mod2 ), और बाकी - हमेशा की तरह।

आइए हम रैखिक समीकरणों की इस प्रणाली के गुणांक मैट्रिक्स को निरूपित करते हैं:



तब इस प्रणाली को Hx ^T = 0. के रूप में फिर से लिखा जा सकता है। ध्यान दें कि ith कॉलम संख्या i का द्विआधारी प्रतिनिधित्व है।

हमें यह साबित करने की जरूरत है कि कोई भी द्विआधारी 7-आयामी वेक्टर y "बिल्कुल" एक मकड़ी के समान है, या, जो समान है, वह क्षेत्र y बिल्कुल एक किश्ती को मारता है।

हम s = Hy ^{T की} गणना करते हैं ^। यदि s = (0, 0, 0) , तो y kind C किसी प्रकार का मकड़ी वहां बैठता है। यदि s then (0, 0, 0) है , तो s = h _i कुछ i के लिए मैट्रिक्स H का i कॉलम है, और इसलिए c = y _i e _i , C , जहां e _मैं सभी शून्य का वेक्टर है, 1 को छोड़कर, i- वें समन्वय में खड़ा है। तब शीर्ष पर बैठे मकड़ी c = y reaches e _i अपने पंजे के साथ वेक्टर y के ith निर्देशांक अक्ष तक पहुँचता है। यदि अन्य शीर्ष c पर बैठा हुआ मकड़ी cth के अक्ष अक्ष के साथ अपने पंजे द्वारा वेक्टर y तक पहुंच जाएगा , तो y = c ' _j e _j और Hy ^T = Hc' ^T + He _j ^T = h _j , जो विरोधाभास की ओर जाता है चूंकि h _i h h _j - मैट्रिक्स H के सभी कॉलम अलग - अलग हैं। अगर मैं = जे , तो सी '= सी ।

त्रुटि सुधार कोड

कल्पना कीजिए कि हमारे पास शून्य और लोगों का एक क्रम है जिसे हम एक ऐसे चैनल पर प्रसारित करना चाहते हैं जिसमें संचरण संबंधी त्रुटियां दुर्लभ मामलों में हो सकती हैं। सात बिट्स को प्रेषित करते समय, हमारे पास या तो कोई त्रुटि नहीं हो सकती है, या एक त्रुटि: प्रेषित पदों में से एक को विपरीत स्थिति में स्वीकार किया जाएगा। यह माना जाता है कि हमने 7 बिट्स की लंबाई के साथ 16 शब्दों की एक सूची तैयार की है। शब्दों को लंबाई के बाइनरी वैक्टर के साथ गिना जा सकता है 4. और फिर यह पता चलता है कि रिसीवर को 7 बिट्स का उपयोग करके 4 बिट्स की जानकारी भेजी जाएगी। यह बेशक ओवरहेड है। एक आसान तरीका है: हम प्रत्येक बिट को तीन बार प्रसारित कर सकते हैं। यदि ट्रांसमिशन को एक से अधिक त्रुटि की अनुमति नहीं है, तो गलत तरीके से प्रसारित बिट को बहाल किया जाएगा। लेकिन इसलिए हम बारह की मदद से चार बिट्स को संचारित करेंगे। तदनुसार, सात के माध्यम से चार बिट्स को प्रसारित करना अधिक किफायती है। सात बिट्स में से चार सूचना प्रसारित करेंगे, और शेष तीन बिट्स सत्यापन के रूप में कार्य करेंगे।

तो, शून्य और लोगों का एक वेक्टर प्रसारित होता है। सोलह में से एक ने अनुमति दी। हम यह सुनिश्चित करने के लिए नहीं जानते हैं कि ट्रांसमिशन त्रुटि हुई है या नहीं। रिसीवर में, हमें यह जानना होगा कि क्या बिट्स में से एक विपरीत स्थिति में चला गया है। ऐसा करने के लिए, हम वेक्टर को चैनल से बाहर ले जाते हैं और इसे रैखिक समीकरणों के हमारे सिस्टम में डालते हैं। यदि सब कुछ संतुष्ट है, तो यह एक कोड वेक्टर है, अनुमत सोलह में से एक, ट्रांसमिशन त्रुटियां नहीं हुईं। और अगर तीन समीकरणों में से कुछ पूरे हो गए हैं, लेकिन कुछ नहीं हैं, तो हम 1 के रूप में अधूरा लिखते हैं, और 0. के रूप में अधूरा है। हमें वही बात मिलेगी जो हमने ऊपर माना था: एक वेक्टर द्वारा मैट्रिक्स को गुणा करना। यदि s 0 के बराबर है, तो संचरण त्रुटियों के बिना पारित हो गया, अन्यथा स्थिति i पर एक त्रुटि हुई।

व्याख्यान को अंत तक देखने के बाद, आप सीखेंगे कि हामिंग त्रुटि सुधार कोड, परिमित क्षेत्र और यह सब कैसे साधारण गणित से जुड़ा है, के बारे में ठीक-ठीक निर्धारण करना है।