बाइनरी संख्या

Question

के सेट को अलग करने के लिए न्यूनतम संख्या में बिट्स खोजने के लिए एल्गोरिदम का कहना है कि हमारे पास के बाइनरी संख्याएं हैं (प्रत्येक लंबाई में से प्रत्येक)। हमें इन के बाइनरी संख्याओं को विशिष्ट रूप से पहचानने के लिए आवश्यक न्यूनतम बिट्स (निरंतर रहने की आवश्यकता नहीं) की आवश्यकता है। उदाहरण के लिए 100, 110 को 1 बिट (दूसरी स्थिति में) से अलग किया जा सकता है। 111, 110, 101 को 2 बिट्स को प्रतिष्ठित करने की आवश्यकता है।

Answer 1

Minimum Set Cover एक सेट यू, और एक सेट के सबसेट यू के एस के संदर्भ में परिभाषित किया गया है। यू में प्रत्येक तत्व एस में सेटों में से एक (कम से कम) द्वारा कवर किया जाना चाहिए।

यदि आप सेट कवर को हल कर सकते हैं, तो आप इस समस्या को भी हल कर सकते हैं। आप एक सेट यू जिसका प्रत्येक प्रविष्टि, यू _{i, j} (जहां मैं < जे), जोड़े से मेल खाती है (i, j) और (जे, i) का निर्माण मान लीजिए कि आपकी के संख्याएं (इसलिए | यू | = के (के -1)/2)। अब n सेट, एस निर्माण , ..., एस _n, n संभव बिट पदों के लिए इसी। एस _जे जोड़ों की स्थिति जे भिन्नता से संबंधित सभी तत्वों का सबसेट है। यही कारण है, अगर संख्या कश्मीर, एल स्थिति जे में अलग हैं, तो यू _{कश्मीर, एल} ∈ एस _जे निर्धारित किया है।

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

Answer 2

हम उन बाइनरी को रैखिक समीकरणों के सेट के रूप में देख सकते हैं। तो, उदाहरण के के लिए, अगर हम इन द्विआधारी है: 1111, 1100, 1001, हम उन्हें इस प्रकार का प्रतिनिधित्व कर सकते हैं:

x1 + x2 + x3 + x4 = y1 
x1 + x2 + 0 + 0 = y2 
x1 + 0 + 0 + x4 = y3 

यहाँ से, हम महसूस करते हैं कि, हम Gaussian elimination उपयोग कर सकते हैं अतिरिक्त खत्म करने के लिए उन समीकरणों को कम करने चर (उपरोक्त उदाहरण में, यह x1 है)। कमी का परिणाम के विशिष्ट चर के सेट होगा, और हम मूल प्रश्न के परिणाम प्राप्त करने के लिए एक अतिरिक्त चर हटा देंगे।