एक मनमाना प्राकृतिक संख्या को केवल दो की घातों के योग के रूप में दर्शाया जा सकता है, उदाहरण के लिए 23 = 16+4+2+1। इस योग में शामिल दो की शक्तियों को एक से और जो इसकी शक्तियों में शामिल नहीं हैं उन्हें शून्य से निरूपित करके, हम इस योग को एक बूलियन सेट (अन्य शब्दावली में, एक वेक्टर) (10111) 2 द्वारा संक्षेप में निरूपित कर सकते हैं। सूचकांक 2 आपको याद दिलाता है कि संख्या बाइनरी में लिखी गई है। सबसे कम महत्वपूर्ण (सबसे बाएं) अंक में एक का मतलब पद 1 है, बाएं से दूसरे अंक में एक का मतलब 2 है, तीसरे अंक में एक का मतलब 4 है, चौथे अंक में शून्य का मतलब पद 8 की अनुपस्थिति है, ए चौथे (सबसे महत्वपूर्ण) अंक में से एक का अर्थ है उपस्थिति पद 16 (ज्यादातर मामलों में बाइनरी सिस्टम में संख्याओं के केवल उन रिकॉर्डों पर विचार करना उचित है जिनमें सबसे महत्वपूर्ण अंक एक है)।

बाइनरी सिस्टम का मुख्य लाभ (इलेक्ट्रॉनिक डिजिटल प्रौद्योगिकी में इसके उपयोग की स्वाभाविकता के अलावा) इसमें अंकगणितीय संचालन के लिए एल्गोरिदम की असाधारण सादगी है। बाइनरी प्रणाली में गुणन सारणी को बिल्कुल भी याद रखने की आवश्यकता नहीं होती है: किसी भी संख्या को शून्य से गुणा करने पर शून्य मिलता है, और एक से गुणा करने पर वह स्वयं के बराबर होती है। विभाजन नियम को दो समानताओं 0/1 = 0, 1/1 =1 तक घटा दिया गया है, जिसके कारण बाइनरी सिस्टम में एक कॉलम द्वारा विभाजन दशमलव प्रणाली की तुलना में सरल है, और अनिवार्य रूप से बार-बार घटाव को कम करता है। बाइनरी सिस्टम में जोड़ तालिका गुणन तालिका (दशमलव प्रणाली के विपरीत) की तुलना में थोड़ी अधिक जटिल है, क्योंकि 1+1 = (10) 2 और अगले अंक तक ले जाना होता है।

बाइनरी सिस्टम में दो बिट जोड़ने का नियम सूत्र x+y = 2v+u, v = x&y, u = xÅy द्वारा दिया गया है। समरूपता के कारण, उन्हें जांचने के लिए चार नहीं, बल्कि तीन मामलों पर विचार करना पर्याप्त है: 0+0 = (00) 2, 1+0=0+1= (01) 2, 1+1 = (10) 2. जो सर्किट यह जोड़ करता है उसे आधा योजक (अंग्रेजी साहित्य में: आधा योजक) कहा जाता है और आमतौर पर इसे HA या FA2 नामित किया जाता है। यह सर्किट (आधार (AND, XOR) में) चित्र में दिखाया गया है।

मल्टी-बिट बाइनरी संख्याओं पर अंकगणितीय संचालन के लिए सर्किट। दो एन-बिट बाइनरी संख्याओं (x n,....,x 1) 2 और (y n,....,y 1) 2 का योग, जैसा कि दशमलव प्रणाली में होता है, अगले की ओर ले जाता है अंक, जिसे गणना में ध्यान में रखा जाना चाहिए। ये कैरीज़ भी शून्य या एक के बराबर होती हैं (यदि कैरी शून्य है, तो मैन्युअल गणना में यह वास्तव में नहीं किया जाता है, लेकिन लॉजिक सर्किट को इस मामले में सही ढंग से काम करना चाहिए, क्योंकि यह "पता नहीं" है कि कौन सी कैरी आई है पिछला अंक)। आइए हम (i-1)वें अंक से अगले i-वें अंक में स्थानांतरण को w i (w 1 =0, क्योंकि इस मामले में कोई पिछला अंक नहीं है) से निरूपित करें। फिर z i (परिणाम का i-वां बिट) की गणना करने के लिए, आपको बिट्स x i और y i और कैरी बिट w i जोड़ना होगा। हम सूत्रों का उपयोग करके यह जोड़ करते हैं

x i + y i +w i = 2v i +u i , v i =m(x i ,y i ,w i), u i =l(x i ,y i ,w i)

FA3 सर्किट का उपयोग करना। फिर z i =u i =l(x i,y i,w i), और अगला कैरी बिट w i +1 = v i =m(x i,y i,w i)। एन-बिट संख्याओं को जोड़ने पर, आम तौर पर बोलते हुए, एक एन+1-बिट संख्या प्राप्त होती है। इसका सबसे महत्वपूर्ण बिट z n +1 = w n +1 अंतिम कैरी के बराबर है।

तीन अंकों की संख्याओं को जोड़ने का आरेख निम्नलिखित चित्र में दिखाया गया है। एन-बिट संख्याओं को जोड़ने की योजना समान दिखती है।

निर्दिष्ट एन-बिट योजक की जटिलता 5n-3 है। एन.पी. रेडकिन ने सिद्ध किया कि आधार (AND,OR,XOR,NOT) में कम जटिलता वाले n-बिट संख्याओं के लिए योजक मौजूद नहीं हैं। इसलिए निर्मित योजक एक न्यूनतम सर्किट है। लेकिन इस योजना में एक महत्वपूर्ण खामी है - इसमें बहुत गहराई है। किसी सर्किट की गहराई उसके तत्वों की अधिकतम संख्या है जो सर्किट के किसी भी इनपुट को उसके किसी आउटपुट से जोड़कर एक सर्किट बनाती है। उदाहरण के लिए, उपरोक्त FA3 सर्किट की गहराई 3 है।

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

सैद्धांतिक रूप से, वास्तविक सर्किट की विलंबता की गणना करना बहुत कठिन है। आमतौर पर सर्किट तत्वों के बहुत सारे सर्किट होते हैं जो इसके इनपुट को आउटपुट से जोड़ते हैं (इन सर्किट को पथ भी कहा जाता है), और सर्किट की देरी एक निश्चित अर्थ में सबसे खराब पथ के साथ देरी से निर्धारित होती है, जिसे महत्वपूर्ण कहा जाता है। उदाहरण के लिए, आरेख FA3 में, महत्वपूर्ण पथ संभवतः इनपुट X या Y को आउटपुट m से जोड़ता है। किसी भी पथ पर देरी न केवल इस पथ पर पड़े सभी तत्वों की देरी के योग से निर्धारित होती है (दिए गए उदाहरण में यह 3 के बराबर है, यदि हम प्रत्येक तत्व की देरी को एकल मानते हैं)। इन तत्वों को जोड़ने वाले तारों की देरी को भी ध्यान में रखा जाना चाहिए। किसी तत्व की देरी इस बात पर निर्भर करती है कि उसके कौन से इनपुट और उसके कौन से आउटपुट को मापा जाता है, साथ ही तत्व की विद्युत विशेषताओं और विचाराधीन सर्किट में सीधे उससे जुड़े तत्वों पर, यह तापमान पर निर्भर करता है सर्किट और यहां तक ​​​​कि विचाराधीन सर्किट को कौन से तार्किक मान प्रदान किए जाते हैं। इस तत्व के इनपुट पर पल और क्या (और किस दिशा में) इसके आउटपुट पर मूल्य बदलता है। हालाँकि, हालांकि बहुत सटीक रूप से नहीं, किसी पथ की देरी का अनुमान उसके तत्वों की देरी के योग के रूप में लगाया जा सकता है। यदि सभी तत्वों की देरी समान है, तो यह मान सर्किट की गहराई से निर्धारित होता है। बेशक, सर्किट की गहराई की अवधारणा को यह स्वीकार करके विस्तारित किया जा सकता है कि आधार के तत्वों में मनमाने ढंग से गैर-नकारात्मक देरी हो सकती है।

पहली नज़र में उपरोक्त एन-बिट योजक सर्किट की गहराई 3n-2 है। लेकिन संभावित महत्वपूर्ण पथों के सावधानीपूर्वक विश्लेषण से पता चलता है कि यह वास्तव में 2n-1 के बराबर है। यह अभी भी बहुत है और इस तरह से निर्मित वास्तविक सर्किट में काफी देरी होगी। व्यवहार में, ऐसे सर्किट का उपयोग किया जाता है जिनमें कम जटिलता होती है, जो Cn (जहां C एक छोटा स्थिरांक है) से अधिक नहीं होती है और कम गहराई होती है, जो लगभग 2log 2 n के बराबर होती है। वी.एम. 1970 में ख्रापचेंको ने कम जटिलता और गहराई की एक योजना बनाई, जो एसिम्प्टोटिक रूप से लॉग 2 एन के बराबर थी (यानी (1+ ई (एन)) लॉग 2 एन के बराबर, जहां एन बढ़ने पर ई (एन) शून्य हो जाता है)। उन्होंने हाल ही में साबित किया कि ऐडर की गहराई लॉग 2 एन + लॉग 2 एन (लॉग 2 (लॉग 2 एन))) से कम नहीं हो सकती। इसलिए, उनके द्वारा बनाई गई योजना में असम्बद्ध रूप से न्यूनतम गहराई है। हालाँकि, ख्रापचेंको की योजना केवल हजारों में से n के लिए पारंपरिक योजनाओं से बेहतर प्रदर्शन करती है। फिर भी, उनकी योजना में कुछ संशोधन किया गया है, जिसकी गहराई लगभग लॉग जे एन के बराबर है, जहां जे = (Ö5+1)/2 है, और इस योजना की गहराई मानक योजनाओं से कम है, जो पहले से ही एन = 8 से शुरू हो रही है। 2008 में, एम. आई. ग्रिंचुक ने लॉग 2 एन+लॉग 2 (लॉग 2 एन)+6 से अधिक गहराई का एक सर्किट बनाया, जिसमें छोटे एन के लिए भी सभी ज्ञात सर्किटों की तुलना में कम गहराई है।

एन-बिट संख्याओं को गुणा करने के लिए इष्टतम सर्किट बनाने की समस्या इष्टतम योजक के निर्माण की समस्या से भी अधिक कठिन साबित हुई। लगभग 6n 2 के बराबर जटिलता के आधार (OR,AND,XOR,NOT) में n-बिट संख्याओं को गुणा करने के लिए एक सर्किट बनाना आसान है। ऐसा करने के लिए, आप योजक के लिए उपरोक्त सर्किट का उपयोग कर सकते हैं। हालाँकि, इसकी गहराई काफी होगी. 60 के दशक की शुरुआत में, कई शोधकर्ताओं (यूएसएसआर में स्टोलारोव और ऑफमैन, यूएसए में एविसेनिस और वालेस) ने स्वतंत्र रूप से ऑर्डर एन 2 की जटिलता और ऑर्डर लॉग 2 एन की गहराई को गुणा करने के लिए एक योजना बनाई। गहराई के संदर्भ में, ये सर्किट क्रम में इष्टतम हैं, लेकिन एक स्पर्शोन्मुख रूप से न्यूनतम गहराई को गुणा करने के लिए एक सर्किट के निर्माण की समस्या अभी भी अनसुलझी है। जटिलता की दृष्टि से, ये योजनाएँ इष्टतम से बहुत दूर निकलीं। 1962 में, ए. ए. करात्सुबा ने एन 1.6 से अधिक की ऑर्डर जटिलता के साथ गुणन के लिए एक सर्किट बनाया, फिर ए. एल. टूम ने एन 1+ ई (एन) जटिलता के साथ एक सर्किट बनाया, जहां ई (एन) एन बढ़ने के साथ शून्य हो जाता है। एक निश्चित अर्थ में, यह परिणाम अंतिम है, हालांकि, इसे 70 के दशक के अंत में जर्मन गणितज्ञ ए. शॉनहेज और एफ. स्ट्रैसन द्वारा परिष्कृत किया गया था, जिन्होंने गुणन सर्किट के लिए एन से अधिक नहीं होने वाले ऑर्डर की जटिलता के लिए एक ऊपरी सीमा प्राप्त की थी। लॉग 2 एन लॉग 2 (लॉग 2 एन), और 2008 में इस अनुमान में अमेरिकी गणितज्ञ एम. फ्यूहरर द्वारा सुधार किया गया था, जिन्होंने डबल लॉगरिदम को बेहद धीमी गति से बढ़ने वाले फ़ंक्शन के साथ बदल दिया था। एक धारणा है कि गुणन सर्किट की ऑर्डर जटिलता एन लॉग 2 एन से कम नहीं है, लेकिन यह साबित नहीं हुआ है।

अमेरिकी गणितज्ञ एस. कुक ने साबित किया कि 2n-बिट संख्या को n-बिट संख्या से विभाजित करने के लिए एक सर्किट का निर्माण करना संभव है, जिसकी क्रम जटिलता n-बिट संख्याओं को गुणा करने की जटिलता से अधिक नहीं है। यह भी ज्ञात है कि ऑर्डर विभाजन के लिए सर्किट की जटिलता की निचली सीमा गुणन की जटिलता के लिए निचली सीमा से कम नहीं है। इसलिए, जटिलता अनुमान के संदर्भ में, गुणा की तुलना में विभाजन कोई नई बात नहीं है। हालाँकि, लंबे समय तक क्रम से विभाजन की गहराई का सबसे अच्छा अनुमान (लॉग 2 एन) 2 था।

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

अनुशंसित पाठ

1. के बारे में। लुपानोव "नियंत्रण प्रणालियों की जटिलता के स्पर्शोन्मुख अनुमान" एड। मॉस्को स्टेट यूनिवर्सिटी, 1984।
2. के बारे में। लुपनोव "गणितीय तर्क पर व्याख्यान नोट्स" एड। मॉस्को स्टेट यूनिवर्सिटी, 2009।
3. जे. सैवेज "कम्प्यूटेशनल जटिलता" एम. एड. फैक्टोरियल, 1998.
4. डी. नुथ "द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग", खंड 2, संस्करण। विलियम्स, 2000.
5. एस.बी. गशकोव "संख्या प्रणाली और उनके अनुप्रयोग", एम. एड. एमसीएनएमओ, 2004.
6. एस.बी. गशकोव, वी.एन. चुबारिकोव “अंकगणित। एल्गोरिदम. कम्प्यूटेशनल जटिलता,'संपादित करें। बस्टर्ड, 2005.

इस साइट से सामग्री का उपयोग करते समय - और बैनर लगाना अनिवार्य है!!!

बाइनरी अंकगणित

जिन संख्याओं का हम उपयोग करते हैं उन्हें दशमलव कहा जाता है और जिस अंकगणित का हम उपयोग करते हैं उसे दशमलव भी कहा जाता है। ऐसा इसलिए है क्योंकि प्रत्येक संख्या को 10 वर्णों वाले संख्याओं के समूह से बनाया जा सकता है - संख्याएँ - "0123456789"।

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

उदाहरण के लिए, संख्या 246 लें। इस अंकन का अर्थ है कि संख्या में दो सैकड़ों, चार दहाई और छह इकाई हैं। इसलिए, हम निम्नलिखित समानता लिख ​​सकते हैं:

246 = 200 + 40 + 6 = 2 * 10 2 + 4 * 10 1 + 6 * 10 0

यहां, समान चिह्न एक ही संख्या को लिखने के तीन तरीकों को अलग करते हैं। अंकन का तीसरा रूप अब हमारे लिए सबसे दिलचस्प है: 2 * 10 2 + 4 * 10 1 + 6 * 10 0। इसे इस प्रकार संरचित किया गया है:

हमारा नंबर तीन अंकों का है. अग्रणी अंक "2" संख्या 3 है। इसलिए इसे दूसरी घात से 10 से गुणा किया जाता है। अगले अंक "4" की क्रम संख्या 2 है और इसे पहले अंक में 10 से गुणा किया जाता है। यह पहले से ही स्पष्ट है कि अंकों को अंक की क्रम संख्या से एक की घात तक दस से गुणा किया जाता है। उपरोक्त को समझने के बाद, हम दशमलव संख्या को निरूपित करने का सामान्य सूत्र लिख सकते हैं। चलो N अंक वाला एक नंबर दिया जाए. हम i-वें अंक को i से निरूपित करेंगे। फिर संख्या को निम्नलिखित रूप में लिखा जा सकता है: a n a n-1 ....a 2 a 1 . यह पहला फॉर्म है, और तीसरा प्रवेश फॉर्म इस तरह दिखेगा:

ए एन ए एन-1 ….ए 2 ए 1 ​​= ए एन * 10 एन-1 + ए एन-1 * 10 एन-2 + …. + ए 2 * 10 1 + ए 1 * 10 0

जहां i "0123456789" सेट का एक पात्र है

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

ए एन ए एन-1 ….ए 2 ए 1 ​​= ए एन * 5 एन-1 + ए एन-1 * 5 एन-2 + …. + ए 2 * 5 1 + ए 1 * 5 0

जहां i सेट "01234" से एक अक्षर है

सामान्य तौर पर, हम 10 को किसी अन्य संख्या से बदल देते हैं और एक पूरी तरह से अलग संख्या प्रणाली और अलग अंकगणित प्राप्त करते हैं। यदि 10 को 2 से प्रतिस्थापित कर दिया जाए तो सबसे सरल अंकगणित प्राप्त होता है। परिणामी संख्या प्रणाली को बाइनरी कहा जाता है और इसमें संख्या को निम्नानुसार परिभाषित किया जाता है:

ए एन ए एन-1 ….ए 2 ए 1 ​​= ए एन * 2 एन-1 + ए एन-1 * 2 एन-2 + …. + ए 2 * 2 1 + ए 1 * 2 0

जहां i सेट "01" से एक अक्षर है

यह प्रणाली सबसे सरल है, क्योंकि इसमें कोई भी संख्या केवल दो अंकों 0 और 1 से बनती है। यह स्पष्ट है कि यह इससे सरल नहीं हो सकती। बाइनरी संख्याओं के उदाहरण: 10, 111, 101।

बहुत ही महत्वपूर्ण प्रश्न. क्या एक बाइनरी संख्या को दशमलव संख्या के रूप में दर्शाया जा सकता है और इसके विपरीत, क्या एक दशमलव संख्या को बाइनरी संख्या के रूप में दर्शाया जा सकता है।

बाइनरी से दशमलव. यह बहुत सरल है। ऐसे अनुवाद की विधि हमारी संख्या लिखने की विधि द्वारा दी जाती है। आइए, उदाहरण के लिए, निम्नलिखित बाइनरी संख्या 1011 लें। आइए इसे दो की घातों में विस्तारित करें। हमें निम्नलिखित मिलता है:

1011 = 1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0

आइए सभी रिकॉर्ड की गई क्रियाएं निष्पादित करें और प्राप्त करें:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. इस प्रकार, हमें प्राप्त होता है कि 1011 (बाइनरी) = 11 (दशमलव)। बाइनरी सिस्टम की थोड़ी सी असुविधा तुरंत दिखाई देती है। वही संख्या, जो दशमलव प्रणाली में बाइनरी सिस्टम में एक अंक के साथ लिखी जाती है, उसे रिकॉर्ड करने के लिए चार अंकों की आवश्यकता होती है। लेकिन यह सादगी की कीमत है (मुफ़्त में कुछ भी नहीं मिलता)। लेकिन बाइनरी प्रणाली अंकगणितीय संक्रियाओं में भारी लाभ देती है। और हम इसे बाद में देखेंगे.

निम्नलिखित बाइनरी संख्याओं को दशमलव के रूप में व्यक्त करें।

ए) 10010 बी) 11101 सी) 1010 सी) 1110 डी) 100011 ई) 1100111 एफ) 1001110

बाइनरी संख्याओं का जोड़.

कॉलम जोड़ने की विधि आम तौर पर दशमलव संख्या के समान ही होती है। अर्थात्, जोड़ बिटवाइज़ किया जाता है, सबसे कम महत्वपूर्ण अंक से शुरू करके। यदि, दो अंक जोड़ने पर, SUM नौ से अधिक है, तो अंक = SUM - 10 लिखा जाता है, और पूरे भाग (SUM / 10) को सबसे महत्वपूर्ण अंक में जोड़ा जाता है। (एक कॉलम में कुछ संख्याएँ जोड़ें, याद रखें कि यह कैसे किया जाता है।) बाइनरी संख्या के साथ भी ऐसा ही है। सबसे निचले अंक से शुरू करते हुए एक-एक करके जोड़ें। यदि परिणाम 1 से अधिक है, तो 1 लिख दिया जाता है और सबसे महत्वपूर्ण अंक में 1 जोड़ दिया जाता है (वे कहते हैं "मेरे सिर के ऊपर से")।

आइए उदाहरण लें: 10011 + 10001।

पहली श्रेणी: 1+1 = 2. हम 0 और 1 वैसे लिखते हैं जैसे मन में आता है।

दूसरी श्रेणी: 1+0+1(कठोर इकाई) =2. हम 0 और 1 लिखते हैं, यह मन में आया।

तीसरी श्रेणी: 0+0+1(याद की गई इकाई) = 1. लिखें 1.

चौथी श्रेणी 0+0=0. हम 0 लिखते हैं.

पांचवी श्रेणी 1+1=2. हम 0 लिखते हैं और छठे अंक में 1 जोड़ते हैं।

आइए तीनों संख्याओं को दशमलव प्रणाली में बदलें और जोड़ की शुद्धता की जांच करें।

10011 = 1*2 4 + 0*2 3 + 0*2 2 + 1*2 1 + 1*2 0 = 16 + 2 + 1 =19

10001 = 1*2 4 + 0*2 3 + 0*2 2 + 0*2 1 + 1*2 0 = 16 + 1 = 17

100100 = 1*2 5 + 0*2 4 + 0*2 3 + 1*2 2 + 0*2 1 + 0*2 0 =32+4=36

17 + 19 = 36 सही समानता

स्वतंत्र समाधान के उदाहरण:

ए) 11001 +101 =

बी) 11001 +11001 =

ग) 1001 + 111 =

ई) 10011 + 101 =

ई) 11011 + 1111 =

ई) 11111 + 10011 =

दशमलव संख्या को बाइनरी में कैसे बदलें। अगला ऑपरेशन घटाव है। लेकिन हम इस ऑपरेशन से थोड़ी देर बाद निपटेंगे, और अब हम दशमलव संख्या को बाइनरी में बदलने की विधि पर विचार करेंगे।

दशमलव संख्या को बाइनरी में बदलने के लिए, इसे दो की घातों तक विस्तारित किया जाना चाहिए। लेकिन यदि दस की शक्तियों में विस्तार तुरंत प्राप्त हो जाता है, तो दो की शक्तियों में विस्तार कैसे किया जाए, इस पर थोड़ा विचार करने की आवश्यकता है। सबसे पहले, आइए देखें कि चयन विधि का उपयोग करके इसे कैसे करें। आइए दशमलव संख्या 12 लें।

पहला कदम। 2 2 = 4, यह पर्याप्त नहीं है। इसके अलावा 2 3 = 8 पर्याप्त नहीं है, लेकिन 2 4 = 16 पहले से ही बहुत है। इसलिए, हम 2 3 =8 छोड़ते हैं। 12 - 8 = 4. अब आपको इसे दो 4 की घात के रूप में प्रस्तुत करने की आवश्यकता है।

दूसरा चरण। 4 = 2 2 .

तब हमारी संख्या 12 = 2 3 + 2 2 है। उच्चतम अंक की संख्या 4 है, उच्चतम घात = 3, इसलिए, दो 1 और 0 की घात वाले पद होने चाहिए। लेकिन हमें उनकी आवश्यकता नहीं है, इसलिए अनावश्यक डिग्रियों से छुटकारा पाने और आवश्यक डिग्रियों को छोड़ने के लिए , हम संख्या को इस प्रकार लिखते हैं: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - यह संख्या 12 का द्विआधारी प्रतिनिधित्व है। यह नोटिस करना आसान है कि प्रत्येक क्रमिक शक्ति है दो की सबसे बड़ी घात, जो विघटित संख्या से कम है। विधि को समेकित करने के लिए, आइए एक और उदाहरण देखें। संख्या 23.

चरण 1. दो की निकटतम घात 2 4 = 16. 23 -16 = 7 है।

चरण 2. दो की निकटतम शक्ति 2 2 = 4. 7 - 4 = 3

चरण 3. दो की निकटतम शक्ति 2 1 = 2. 3 - 2 = 1

चरण 4. दो की निकटतम शक्ति 2 0 =1 1 - 1 =0

हमें निम्नलिखित विस्तार मिलता है: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

और हमारी वांछित बाइनरी संख्या 10111 है

ऊपर चर्चा की गई विधि उसे सौंपी गई समस्या को अच्छी तरह से हल करती है, लेकिन एक ऐसी विधि भी है जो बहुत बेहतर तरीके से एल्गोरिथमीकृत है। इस विधि के लिए एल्गोरिदम नीचे लिखा गया है:

जब तक संख्या शून्य से अधिक है, तब तक ऐसा करें

अगला अंक = संख्या का शेषफल 2 से विभाजित करने पर

संख्या = संख्या का पूर्णांक भाग 2 से विभाजित

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

एल्गोरिथम प्रारंभ संख्या = 19

अगला अंक = 1

अगला अंक = 1

अगला अंक = 0

अगला अंक = 0

अगला अंक = 1

तो, परिणामस्वरूप, हमारे पास निम्नलिखित संख्या 10011 है। ध्यान दें कि चर्चा की गई दो विधियाँ अगले अंक प्राप्त करने के क्रम में भिन्न हैं। पहली विधि में, प्राप्त पहला अंक बाइनरी संख्या का सबसे महत्वपूर्ण अंक होता है, और दूसरी विधि में, इसके विपरीत, प्राप्त पहला अंक सबसे कम महत्वपूर्ण होता है।

दशमलव संख्याओं को दो तरीकों से बाइनरी में बदलें

ए) 14 बी) 29 सी) 134 डी) 158 एफ) 1190 ग्राम) 2019

भिन्न को दशमलव संख्या में कैसे बदलें।

यह ज्ञात है कि किसी भी परिमेय संख्या को दशमलव और साधारण भिन्न के रूप में दर्शाया जा सकता है। एक साधारण अंश, यानी, फॉर्म ए/बी का एक अंश, नियमित और अनुचित हो सकता है। एक भिन्न को उचित कहा जाता है यदि A<В и неправильной если А>में।

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

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

अब आइए अनुवाद नियम प्राप्त करने का प्रयास करें, और पहले उदाहरण 5,401 देखें

समाधान:

हम पहले से ज्ञात नियमों के अनुसार पूर्णांक भाग प्राप्त करेंगे, और यह बाइनरी संख्या 101 के बराबर है। और हम भिन्नात्मक भाग को 2 की शक्तियों में विस्तारित करेंगे।

स्टेप 1: 2 -2 = 0.25; 0.401 - 0.25 = 0.151. -यह शेषफल है.

चरण दो:अब हमें 0.151 को दो की घात के रूप में प्रस्तुत करने की आवश्यकता है। आइए ऐसा करें: 2 -3 = 0.125; 0.151 - 0.125 = 0.026

इस प्रकार, मूल भिन्नात्मक भाग को 2 -2 +2 -3 के रूप में दर्शाया जा सकता है। यही बात इस बाइनरी नंबर में भी लिखी जा सकती है: 0.011. पहला भिन्नात्मक अंक शून्य है, ऐसा इसलिए है क्योंकि हमारे विस्तार में 2 -1 की कोई शक्ति नहीं है।

पहले और दूसरे चरण से यह स्पष्ट है कि यह प्रतिनिधित्व सटीक नहीं है और विस्तार जारी रखना वांछनीय हो सकता है। आइये नियम पर नजर डालते हैं. इसमें कहा गया है कि हमें M के इतने चिह्नों की आवश्यकता है कि 10 3, 2 M से कम हो। यानी 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

चरण 3:अब हम संख्या 0.026 के साथ काम कर रहे हैं। इस संख्या के दो की निकटतम घात 2 -6 = 0.015625 है; 0.026 - 0.015625 = 0.010375 अब हमारी अधिक सटीक बाइनरी संख्या है: 0.011001। दशमलव बिंदु के बाद पहले से ही छह स्थान हैं, लेकिन यह अभी पर्याप्त नहीं है, इसलिए हम एक और कदम उठाते हैं।

चरण 4:अब हम 0.010375 नंबर के साथ काम कर रहे हैं। इस संख्या के दो की निकटतम घात 2 -7 = 0.0078125 है;

0,010375 - 0,0078125 = 0,0025625

चरण 5:अब हम 0.0025625 नंबर के साथ काम कर रहे हैं। इस संख्या के दो की निकटतम घात 2 -9 = 0.001953125 है;

0,0025625 - 0,001953125 = 0,000609375

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

0,401 = 0,011001101

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

अब आइए रूपांतरण एल्गोरिदम लिखें:

एल्गोरिथम का प्रारंभिक डेटा: ए के माध्यम से हम दशमलव रूप में लिखे गए मूल उचित दशमलव अंश को निरूपित करेंगे। माना कि इस भिन्न में N वर्ण हैं।

कलन विधि

क्रिया 1. असमानता 10 एन से आवश्यक बाइनरी अंक एम की संख्या निर्धारित करें< 2 M

क्रिया 2: बाइनरी प्रतिनिधित्व (शून्य के बाद के अंक) के अंकों की गणना के लिए चक्र। अंक संख्या को प्रतीक K द्वारा दर्शाया जाएगा।

1. अंक संख्या = 1
2. यदि 2 -K > A

फिर हम बाइनरी संख्या में शून्य जोड़ते हैं

• बाइनरी संख्या में 1 जोड़ें
• ए = ए - 2 -के

1. के = के + 1
2. यदि K > M

• तो एल्गोरिथ्म पूरा हो गया है
• अन्यथा, बिंदु 2 पर जाएँ.

दशमलव संख्याओं को बाइनरी में बदलें

ए) 3.6 बी) 12.0112 सी) 0.231 डी) 0.121 डी) 23.0091

बाइनरी संख्याओं को घटाना. हम एक कॉलम में संख्याओं को भी घटाएंगे और सामान्य नियम दशमलव संख्याओं के समान ही है, घटाव को थोड़ा-थोड़ा करके किया जाता है और यदि स्थान पर पर्याप्त संख्या नहीं है, तो इसे उच्चतम में किया जाता है। आइए निम्नलिखित उदाहरण को हल करें:

प्रथम श्रेणी. 1 - 0 =1. हम लिखते हैं 1.

दूसरी श्रेणी 0-1. एक लापता है. हम इसे वरिष्ठ वर्ग में रखते हैं। वरिष्ठ अंक से एक इकाई कनिष्ठ अंक में जाती है, जैसे दो इकाइयाँ (क्योंकि वरिष्ठ अंक को उच्च डिग्री के दो द्वारा दर्शाया जाता है) 2-1 = 1. हम लिखते हैं 1.

तीसरी श्रेणी. हमने इस रैंक की एक यूनिट पर कब्जा कर लिया था, इसलिए अब रैंक 0 में उच्चतम रैंक की एक यूनिट पर कब्जा करने की जरूरत है। 2-1 =1. हम लिखते हैं 1.

आइए दशमलव प्रणाली में परिणाम की जाँच करें

1101 - 110 = 13 - 6 = 7 (111) सही समानता।

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

दो के पूरक के माध्यम से घटाव का नियम बताता है कि घटाव को जोड़ द्वारा प्रतिस्थापित किया जा सकता है यदि घटाव को दो के पूरक में एक संख्या द्वारा प्रतिस्थापित किया जाता है।

उदाहरण: 34 - 22 = 12

आइए इस उदाहरण को बाइनरी फॉर्म में लिखें। 100010 - 10110 = 1100

नंबर 10110 का अतिरिक्त कोड इस प्रकार होगा

01001 + 00001 = 01010। फिर मूल उदाहरण को इस तरह जोड़कर बदला जा सकता है: 100010 + 01010 = 101100 इसके बाद, आपको सबसे महत्वपूर्ण अंक में एक इकाई को हटाने की आवश्यकता है। यदि हम ऐसा करते हैं, तो हमें 001100 मिलता है। आइए महत्वहीन शून्य को हटा दें और 1100 प्राप्त करें, यानी, उदाहरण सही ढंग से हल किया गया था

घटाव करना. सामान्य तरीके से और अतिरिक्त कोड में, पहले दशमलव संख्याओं को बाइनरी में परिवर्तित किया गया:

बाइनरी परिणाम को दशमलव संख्या प्रणाली में परिवर्तित करके जांचें।

द्विआधारी संख्या प्रणाली में गुणन.

सबसे पहले, निम्नलिखित दिलचस्प तथ्य पर विचार करें। किसी बाइनरी संख्या को 2 से गुणा करने के लिए (बाइनरी प्रणाली में दशमलव दो 10 है), गुणा की जाने वाली संख्या के बाईं ओर एक शून्य जोड़ना पर्याप्त है।

उदाहरण। 10101 * 10 = 101010

इंतिहान।

10101 = 1*2 4 + 0*2 3 + 1*2 2 + 0*2 1 +1*2 0 = 16 + 4 + 1 = 21

101010 =1*2 5 + 0*2 4 + 1*2 3 + 0*2 2 +1*2 1 +0*2 0 = 32 + 8 + 2 = 42

यदि हम याद रखें कि किसी भी बाइनरी संख्या को दो की घातों में विस्तारित किया जा सकता है, तो यह स्पष्ट हो जाता है कि बाइनरी संख्या प्रणाली में गुणन को घटाकर 10 (अर्थात दशमलव 2) से गुणा किया जाता है, और इसलिए, गुणन क्रमिक की एक श्रृंखला है बदलाव. सामान्य नियम यह है कि, दशमलव संख्याओं की तरह, बाइनरी गुणन बिटवाइज़ किया जाता है। और दूसरे गुणक के प्रत्येक अंक के लिए, पहले गुणक के दाईं ओर एक शून्य जोड़ा जाता है। उदाहरण (अभी तक किसी कॉलम में नहीं):

1011 * 101 इस गुणन को तीन अंकों के गुणन के योग तक घटाया जा सकता है:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 इसे एक कॉलम में इस तरह लिखा जा सकता है:

इंतिहान:

101 = 5 (दशमलव)

1011 = 11 (दशमलव)

110111 = 55 (दशमलव)

5*11 = 55 सही समानता

अपने लिए तय करें

ए) 1101 * 1110 =

बी) 1010 * 110 =

ई) 101011 * 1101 =

ई) 10010 * 1001 =

नोट: वैसे, बाइनरी सिस्टम में गुणन तालिका में केवल एक आइटम 1 * 1 = 1 होता है

द्विआधारी संख्या प्रणाली में विभाजन.

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

हम दाईं ओर (सबसे महत्वपूर्ण अंक से) अंकों की इतनी संख्या का चयन करते हैं कि परिणामी संख्या यथासंभव छोटी हो और साथ ही भाजक से बड़ी हो। 2, भाजक से कम है, इसलिए हमें जो संख्या चाहिए वह 23 है। फिर हम परिणामी संख्या को भाजक से शेषफल के साथ विभाजित करते हैं। हमें निम्नलिखित परिणाम मिलता है:

हम वर्णित ऑपरेशन को तब तक दोहराते हैं जब तक कि परिणामी शेष भाजक से कम न हो जाए। जब ऐसा होता है, तो रेखा के नीचे प्राप्त संख्या भागफल होती है, और अंतिम शेष संक्रिया का शेष होता है। अतः किसी बाइनरी संख्या को विभाजित करने की क्रिया ठीक उसी प्रकार की जाती है। आओ कोशिश करते हैं

उदाहरण: 10010111 / 101

हम एक ऐसी संख्या की तलाश कर रहे हैं जिसका पहला अंक भाजक से बड़ा हो। यह चार अंकों की संख्या 1001 है। यह मोटे अक्षरों में है। अब आपको चयनित संख्या के लिए एक भाजक खोजने की आवश्यकता है। और यहां हम दशमलव प्रणाली की तुलना में फिर से जीत गए। तथ्य यह है कि चयनित भाजक आवश्यक रूप से एक संख्या है, और हमारे पास केवल दो संख्याएँ हैं। चूँकि 1001 स्पष्ट रूप से 101 से बड़ा है, तो भाजक के साथ सब कुछ स्पष्ट है: 1. आइए ऑपरेशन चरण निष्पादित करें।

तो, पूर्ण किए गए ऑपरेशन का शेष भाग 100 है। यह 101 से कम है, इसलिए दूसरे डिवीजन चरण को पूरा करने के लिए, आपको अगला अंक 100 में जोड़ना होगा, यह अंक 0 है। अब हमारे पास निम्नलिखित संख्या है:

1000, 101 से बड़ा है, इसलिए दूसरे चरण में हम फिर से भागफल में संख्या 1 जोड़ेंगे और निम्नलिखित परिणाम प्राप्त करेंगे (स्थान बचाने के लिए, हम तुरंत अगला अंक हटा देंगे)।

तीसरा चरण। परिणामी संख्या 110, 101 से बड़ी है, इसलिए इस चरण में हम भागफल में 1 लिखेंगे। यह इस प्रकार निकलेगा:

परिणामी संख्या 11 101 से कम है, इसलिए हम भागफल में संख्या 0 लिखते हैं और अगली संख्या को नीचे कर देते हैं। यह इस प्रकार निकला:

परिणामी संख्या 101 से अधिक है, इसलिए हम संख्या 1 को भागफल में लिखते हैं और क्रियाएँ फिर से करते हैं। यह इस चित्र से पता चलता है:

परिणामी शेषफल 10, 101 से कम है, लेकिन हमारे पास लाभांश के अंक समाप्त हो गए हैं, इसलिए 10 अंतिम शेषफल है, और 1110 आवश्यक भागफल है।

आइए दशमलव संख्याओं में जाँच करें

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

कार्य 1: सभी नमूने पुनः प्राप्त करना

अक्सर ऐसी समस्याएं होती हैं जिनमें आपको वस्तुओं के दिए गए सेट से सभी संभावित संयोजन बनाने में सक्षम होने की आवश्यकता होती है। उदाहरण के लिए, यह कार्य:

पत्थरों के एक बड़े ढेर को देखते हुए, पत्थरों को दो ढेरों में व्यवस्थित करें ताकि इन दोनों ढेरों का द्रव्यमान यथासंभव बराबर हो।

यह कार्य इस प्रकार तैयार किया जा सकता है:

एक बड़े ढेर से पत्थरों का चयन इस प्रकार खोजें कि उसका कुल द्रव्यमान बड़े ढेर के आधे द्रव्यमान से जितना संभव हो उतना कम हो।

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

नमूने: (0, 0, 1); (0, 1, 0); (0, 1, 1); (100); (1, 0, 1); (1, 1, 0); (1, 1, 1);

यदि अगले नंबर के साथ स्थिति एक है, तो इसका मतलब है कि इस स्थिति के बराबर संख्या वाला एक तत्व चयन में मौजूद है, और यदि शून्य है, तो तत्व मौजूद नहीं है। उदाहरण के लिए, नमूना (0, 1, 0); संख्या 2 वाला एक तत्व शामिल है, और चयन (1, 1, 0) है; इसमें संख्या 1 और 2 वाले दो तत्व शामिल हैं।

यह उदाहरण स्पष्ट रूप से दिखाता है कि एक नमूने को बाइनरी संख्या के रूप में दर्शाया जा सकता है। इसके अलावा, यह देखना आसान है कि सभी संभावित एक, दो और तीन अंकों वाली बाइनरी संख्याएं ऊपर लिखी गई हैं। आइए उन्हें इस प्रकार पुनः लिखें:

001; 010; 011; 100; 101; 110; 111

1; 10; 11; 100; 101; 110; 111

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

एल्गोरिथम इनपुट डेटा

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

आइए इस बाइनरी संख्या को बड़े अक्षरों BINARY में निरूपित करने के लिए सहमत हों

कलन विधि

यदि किसी बाइनरी संख्या में पूरी तरह से इकाई शामिल है

फिर हम एल्गोरिथम बंद कर देते हैं

• हम बाइनरी अंकगणित के नियमों के अनुसार बाइनरी संख्या में एक जोड़ते हैं।
• परिणामी बाइनरी संख्या से हम अगला नमूना बनाते हैं, जैसा कि ऊपर वर्णित है।

समस्या 2: बड़ी अभाज्य संख्याएँ ढूँढना

आरंभ करने के लिए, आइए याद रखें कि अभाज्य संख्या एक प्राकृतिक संख्या है जो केवल 1 और स्वयं से विभाज्य होती है। अभाज्य संख्याओं के उदाहरण: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

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

टिप्पणी। एक मजबूत सिफर एक ऐसा सिफर होता है जिसे समझने में बहुत लंबा समय लगता है।

क्यों? एक अभाज्य संख्या एन्क्रिप्शन और डिक्रिप्शन के लिए एक कुंजी के रूप में कार्य करती है। इसके अलावा, हम जानते हैं कि अभाज्य संख्याएँ प्राकृतिक संख्याओं की श्रृंखला में बहुत बार दिखाई नहीं देती हैं। पहले हज़ार में इनकी संख्या काफी होती है, फिर इनकी संख्या तेजी से घटने लगती है। इसलिए, यदि हम एक बहुत बड़ी संख्या को कुंजी के रूप में नहीं लेते हैं, तो गूढ़लेखक, यहां तक ​​​​कि एक बहुत तेज़ कंप्यूटर का उपयोग करके, एक सीमित समय में (कुंजी के रूप में एक के बाद एक सभी सरल संख्याओं को आज़माकर) इसे प्राप्त करने में सक्षम होगा। समय।

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

मान लीजिए संख्या A में 150 अंक हैं। इसके वर्गमूल में कम से कम 75 अक्षर होंगे। इतनी संख्या में संभावित विभाजकों को सुलझाने के लिए, हमें एक बहुत शक्तिशाली कंप्यूटर और बहुत समय की आवश्यकता होती है, जिसका अर्थ है कि समस्या व्यावहारिक रूप से हल नहीं हो सकती है।

इससे कैसे निपटें.

सबसे पहले, आप एक संख्या की दूसरे से विभाज्यता की तुरंत जांच करना सीख सकते हैं, और दूसरी बात, आप संख्या ए को इस तरह से चुनने का प्रयास कर सकते हैं कि यह उच्च स्तर की संभावना के साथ अभाज्य हो। यह पता चला है कि यह संभव है. गणितज्ञ मेर्सन ने पाया कि संख्याएँ निम्नलिखित रूप में होती हैं

वे उच्च स्तर की संभावना के साथ सरल हैं।

ऊपर लिखे वाक्यांश को समझने के लिए, आइए गिनें कि पहले हजार में कितनी अभाज्य संख्याएँ हैं और उसी हजार में कितनी मेर्सन संख्याएँ अभाज्य हैं। तो, पहले हज़ार में मेर्सन संख्याएँ इस प्रकार हैं:

2 1 - 1 = 1 ; 2 2 -1 = 3 ; 2 3 - 1 = 7 ; 2 4 - 1 = 15; 2 5 - 1 = 31 ; 2 6 -1 = 63;

2 7 - 1 =127 ; 2 8 -1 = 255; 2 9 - 1 = 511;

अभाज्य संख्याएँ बोल्ड अक्षरों में अंकित हैं। 9 मेर्सन संख्याओं के लिए 5 अभाज्य संख्याएँ हैं। प्रतिशत के रूप में, यह 5/9*100 = 55.6% है। वहीं, प्रत्येक 1000 प्रथम प्राकृत संख्याओं के लिए केवल 169 अभाज्य संख्याएँ होती हैं। प्रतिशत के रूप में, यह 169/1000*100 = 16.9% है। अर्थात्, पहले हज़ार में, प्रतिशत के संदर्भ में, मेर्सन संख्याओं के बीच अभाज्य संख्याएं साधारण प्राकृतिक संख्याओं की तुलना में लगभग 4 गुना अधिक पाई जाती हैं

___________________________________________________________

अब आइए एक विशिष्ट मेर्सन संख्या लें, उदाहरण के लिए 2 4 - 1। आइए इसे एक बाइनरी संख्या के रूप में लिखें।

2 4 - 1 = 10000 - 1 = 1111

आइए निम्नलिखित मेर्सन संख्या 2 5 -1 लें और इसे बाइनरी संख्या के रूप में लिखें। हमें निम्नलिखित मिलता है:

2 5 -1 = 100000 - 1 = 11111

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

त्वरित दशमलव से बाइनरी रूपांतरण

बाइनरी संख्या प्रणाली का उपयोग करने में मुख्य समस्याओं में से एक दशमलव संख्या को बाइनरी में परिवर्तित करने में कठिनाई है। यह काफी श्रमसाध्य कार्य है. बेशक, तीन या चार अंकों की छोटी संख्याओं का अनुवाद करना बहुत मुश्किल नहीं है, लेकिन 5 या अधिक अंकों वाली दशमलव संख्याओं के लिए यह पहले से ही मुश्किल है। अर्थात्, हमें बड़ी दशमलव संख्याओं को शीघ्रता से बाइनरी में बदलने का एक तरीका चाहिए।

इस विधि का आविष्कार फ्रांसीसी गणितज्ञ लीजेंड्रे ने किया था। उदाहरण के लिए, संख्या 11183445 दी गई है। हम इसे 64 से विभाजित करते हैं, हमें शेषफल 21 मिलता है और भागफल 174741 होता है। हम इस संख्या को फिर से 64 से विभाजित करते हैं, हमें शेषफल 21 और भागफल 2730 प्राप्त होता है। अंत में , 2730 को 64 से विभाजित करने पर 42 शेषफल और 42 का भागफल प्राप्त होता है, लेकिन बाइनरी में 64 1000000 है, बाइनरी में 21 10101 है, और 42 101010 है, इसलिए, मूल संख्या बाइनरी में इस प्रकार लिखी जाती है:

101010 101010 010101 010101

इसे और अधिक स्पष्ट करने के लिए, यहां छोटी संख्या के साथ एक और उदाहरण दिया गया है। आइए संख्या 235 के द्विआधारी निरूपण को परिवर्तित करें। 235 को शेषफल के साथ 64 से विभाजित करें। हम पाते हैं:

क्वांटियेट = 3, बाइनरी 11 या 000011

शेष = 43, बाइनरी 101011

फिर 235 = 11101011। आइए इस परिणाम की जाँच करें:

11101011 = 2 7 + 2 6 + 2 5 + 2 3 + 2 1 + 2 0 = 128+64+32+8+2+1 = 235

टिप्पणियाँ:

1. यह देखना आसान है कि अंतिम बाइनरी संख्या में सभी शेषफल और अंतिम चरण में शेषफल और भागफल दोनों शामिल होते हैं।
2. भागफल को शेषफल से पहले लिखा जाता है।
3. यदि परिणामी भागफल या शेषफल में द्विआधारी प्रतिनिधित्व में 6 अंक से कम है (6 शून्य में संख्या 64 = 1000000 का द्विआधारी प्रतिनिधित्व होता है), तो इसमें महत्वहीन शून्य जोड़ दिए जाते हैं।

और एक और जटिल उदाहरण. नंबर है 25678425.

चरण 1: 25678425 को 64 से विभाजित किया गया

निजी = 401225

शेष = 25 = 011001

चरण 2: 401225 को 64 से विभाजित किया गया

भागफल = 6269

शेष = 9 = 001001

चरण 3: 6269 को 64 से विभाजित किया गया

भागफल = 97

शेष = 61 = 111101

चरण 4: 97 को 64 से विभाजित किया गया

भागफल = 1 = 000001

शेष = 33 = 100001

संख्या परिणाम = 1.100001.111101.001001.011001

इस संख्या में शामिल मध्यवर्ती परिणामों को एक बिंदु द्वारा अलग किया जाता है।

संख्याओं को बाइनरी प्रतिनिधित्व में बदलें:

परिशिष्ट: तालिका 1

किसी भी स्थितीय संख्या प्रणाली में अंकगणितीय संचालन उन्हीं नियमों के अनुसार किया जाता है जो दशमलव संख्या प्रणाली में उपयोग किए जाते हैं।

दशमलव संख्या प्रणाली की तरह, अंकगणितीय संक्रियाओं को करने के लिए आपको जोड़ (घटाव) और गुणन सारणी जानने की आवश्यकता होती है।

बाइनरी संख्या प्रणाली के लिए जोड़, घटाव और गुणन तालिका

बाइनरी संख्याएँ जोड़ना

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

उदाहरण: 1011,1 2 + 1010,11 2

स्थिति तब भी दिलचस्प होती है जब दो से अधिक संख्याएँ जोड़ी जाती हैं। इस मामले में, कई अंकों के माध्यम से स्थानांतरण संभव है।
उदाहरण: 111,1 2 + 111 2 + 101,1 2

इकाई के स्थान (बिट 0) में जोड़ने पर 4 इकाई होती हैं, जिन्हें मिलाने पर इकाई मिलती है 100 2 . अतः इसे शून्य अंक से प्रथम अंक तक स्थानांतरित कर दिया जाता है 0 , और दूसरे में - 1 .
इसी तरह की स्थिति दूसरे अंक में उत्पन्न होती है, जहां, दो स्थानांतरित इकाइयों को ध्यान में रखते हुए, संख्या प्राप्त की जाती है 5 = 101 2 . 1 दूसरी श्रेणी में रहता है, 0 तीसरे और में स्थानांतरित कर दिया गया 1 चौथे में स्थानांतरित कर दिया गया।

बाइनरी नंबर घटाना

ऐसे मामलों में जहां वरिष्ठ श्रेणी की एक इकाई लगी हुई है, यह कनिष्ठ श्रेणी की दो इकाइयां देती है। यदि किसी इकाई का अध्ययन कई श्रेणियों के बाद किया जाता है, तो यह सभी मध्यवर्ती शून्य श्रेणियों में एक इकाई और उस श्रेणी में दो इकाइयाँ देती है जिसके लिए इसका अध्ययन किया गया था।
उदाहरण: 10110,01 2 — 1001,1 2

सभी स्थितीय संख्या प्रणालियों में अंकगणितीय संक्रियाएं उन्हीं नियमों के अनुसार की जाती हैं जिनसे आप भलीभांति परिचित हैं।

जोड़ना।आइए बाइनरी संख्या प्रणाली में संख्याओं को जोड़ने पर विचार करें। यह एकल-अंकीय बाइनरी संख्याओं को जोड़ने के लिए एक तालिका पर आधारित है :

इस तथ्य पर ध्यान देना महत्वपूर्ण है कि दो को जोड़ने पर अंक ओवरफ्लो हो जाता है और सबसे महत्वपूर्ण अंक में स्थानांतरित हो जाता है। एक अंक अतिप्रवाह तब होता है जब उसमें मौजूद संख्या का मान आधार के बराबर या उससे अधिक हो जाता है।

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

उदाहरण के तौर पर, आइए बाइनरी नंबर 110 2 और 11 2 को एक कॉलम में जोड़ें :

आइए दशमलव संख्या प्रणाली में जोड़कर गणना की शुद्धता की जाँच करें। आइए बाइनरी संख्याओं को दशमलव संख्या प्रणाली में बदलें और फिर उन्हें जोड़ें:

110 2 =1*2 2 + 1*2 1 + 0*2 0 = 6 10 ;

11 2 = 1*2 1 + 1*2 0 = 3 10 ;

6 10 + 3 10 = 9 10 .

आइए अब बाइनरी जोड़ के परिणाम को दशमलव संख्या में बदलें:

1001 2 = 1*2 3 +0*2 2 + 0*2 1 + 1*2 0 = 9 10 /

आइए परिणामों की तुलना करें - जोड़ सही ढंग से किया गया था।

घटाव.आइए बाइनरी संख्याओं को घटाने पर नजर डालें। यह एकल-अंकीय बाइनरी संख्याओं को घटाने के लिए एक तालिका पर आधारित है। छोटी संख्या (0) में से बड़ी संख्या (1) घटाने पर उच्चतम अंक से ऋण बनता है। तालिका में, ऋण को एक पंक्ति के साथ 1 निर्दिष्ट किया गया है:

मल्टी-बिट बाइनरी संख्याओं का घटाव उपरोक्त घटाव तालिका के अनुसार होता है, सबसे महत्वपूर्ण बिट्स से संभावित उधार को ध्यान में रखते हुए। उदाहरण के तौर पर, आइए बाइनरी संख्या 110 2 और 11 2 घटाएं:

गुणन.गुणन एकल-अंकीय बाइनरी संख्याओं के लिए गुणन तालिका पर आधारित है:

बहु-अंकीय बाइनरी संख्याओं का गुणन गुणक के अंकों द्वारा गुणक के क्रमिक गुणन के साथ दशमलव संख्या प्रणाली में उपयोग की जाने वाली सामान्य योजना के अनुसार उपरोक्त गुणन तालिका के अनुसार होता है। उदाहरण के तौर पर, आइए बाइनरी संख्याओं को गुणा करें और:

विभाजन।दशमलव संख्या प्रणाली में विभाजन ऑपरेशन करने के लिए एल्गोरिदम के समान एक एल्गोरिदम का उपयोग करके विभाजन ऑपरेशन किया जाता है। उदाहरण के तौर पर, आइए बाइनरी संख्या 110 2 और 11 2 को विभाजित करें:

• छात्रों को बाइनरी नंबर सिस्टम से परिचित कराना, इसके नुकसान और कंप्यूटिंग में उपयोग के फायदे बताना;
• तार्किक सोच विकसित करें; बाइनरी संख्याओं के साथ अंकगणितीय परिचालन करने में कौशल विकसित करना;
• विषय में रुचि पैदा करें.

शिक्षण सॉफ्टवेयर: पीसी, कैलकुलेटर प्रोग्राम।

कक्षाओं के दौरान

मैं।आयोजन का समय

अभिवादन, अनुपस्थितों की जाँच।

1. पाठ लक्ष्य निर्धारित करना

- यह कितना होगा:

1000110 2 + 1010101 2 ; 100011110111 2 /101101 2;

1110001110 2 – 11010 2 ; 101101 2 * 100011 2

छात्रों के प्रस्तावित उत्तरों के बाद, मैं टिप्पणी करता हूं और समझाता हूं कि आज पाठ में हम सीखेंगे कि बाइनरी संख्या प्रणाली में अंकगणितीय संक्रियाओं को सही ढंग से कैसे करें।

2. एक व्यक्ति को बाइनरी सिस्टम में नहीं गिना जाता, क्योंकि... वह उसके लिए सुविधाजनक नहीं है. गिनती के लिए इसका उपयोग कौन या क्या करता है और क्यों?

द्वितीय.नई सामग्री की प्रस्तुति

बाइनरी नंबर प्रणाली

सभी स्थितीय संख्या प्रणालियों में से, द्विआधारी संख्या प्रणाली विशेष रूप से सरल है और इसलिए दिलचस्प है।

– बाइनरी संख्या प्रणाली का आधार क्या है? (क्यू = 2)

– बाइनरी नंबर लिखने का विस्तारित रूप क्या है? (ए 2 =ए एन-1 *2 एन-1 + …ए 0*2 0 + ए -1 *2 -1 +…ए -एम *2 -एम, जहां ए आई 1 या 0 है।)

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

बाइनरी अंकगणित.

बाइनरी संख्या प्रणाली में बेहतर महारत हासिल करने के लिए, बाइनरी संख्याओं पर अंकगणितीय परिचालन के प्रदर्शन में महारत हासिल करना आवश्यक है।

सभी स्थितीय प्रणालियाँ "समान" हैं, अर्थात्, उन सभी में अंकगणितीय संचालन समान नियमों के अनुसार किए जाते हैं:

• अंकगणित के समान नियम मान्य हैं: संचारी, साहचर्य, वितरणात्मक;
• जोड़, घटाव, गुणा और भाग के नियम मान्य हैं;
• अंकगणितीय संक्रियाएँ करने के नियम जोड़ और गुणन सारणी पर आधारित हैं।

जोड़ना।

बाइनरी संख्या जोड़ तालिका सरल है।

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
1 + 1 + 1 = 11

जब दो इकाइयाँ जोड़ी जाती हैं, तो अंक ओवरफ्लो हो जाता है और सबसे महत्वपूर्ण अंक में स्थानांतरित हो जाता है। एक अंक अतिप्रवाह तब होता है जब उसमें मौजूद संख्या का मान आधार के बराबर या उससे अधिक हो जाता है।

घटाव.

0 – 0 = 0
0 – 1 = 11
1 – 0 = 1
1 – 1 = 0

मल्टी-बिट बाइनरी संख्याओं का घटाव उपरोक्त घटाव तालिका के अनुसार होता है, उच्चतम अंकों से संभावित उधार को ध्यान में रखते हुए।

गुणन.

गुणन ऑपरेशन गुणक के अगले अंक द्वारा गुणक के क्रमिक गुणन के साथ सामान्य योजना (दशमलव संख्या प्रणाली में प्रयुक्त) के अनुसार गुणन तालिका का उपयोग करके किया जाता है।

किसी कॉलम से विभाजित करते समय, आपको मध्यवर्ती परिणामों के रूप में गुणा और घटाव करना होगा।

तृतीय. जो सीखा गया है उसका समेकन

समस्याओं का समाधान।

जोड़ प्रदर्शन करें:

1001001 + 10101 (उत्तर 1011110);
101101 + 1101101 (उत्तर 10011010)
11000,11 + 11010,11 (उत्तर 110011,1)

घटाव करें:

10001000 – 1110011 (उत्तर 10101)
1101100 – 10110110 (उत्तर – 1001010)
110101,101 – 1001,111 (101011,11)

गुणन करें:

100001*111,11 (उत्तर: 11111111,11)
10011*1111,01 (उत्तर: 100100001,11)

विभाजन करें:

1000000 / 1110 (उत्तर:100)
11101001000/111100 (उत्तर: 11111)

चतुर्थ. पाठ सारांश

छात्रों के काम का मूल्यांकन करना और पाठ में उत्कृष्ट प्रदर्शन करने वालों का नाम बताना।

वी. होमवर्क

बाइनरी संख्या प्रणाली में अंकगणितीय संचालन करने के नियमों के साथ-साथ बाइनरी संख्या प्रणाली में जोड़, घटाव और गुणा की तालिकाओं को जानें।

इन चरणों का पालन करें:

1. 110010 + 111,01;
2. 11110000111 – 110110001;
3. 10101,101 * 111;
4. 10101110/101.

टर्नरी और क्विनरी संख्या प्रणालियों में जोड़ और गुणन सारणी बनाएं।