डिस्पेंसर: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
डिस्पेंसर | डिस्पेंसर एकपक्षीय [[यादृच्छिकता निकालने वाला|एक्सट्रैक्टर]] है।<ref>{{cite journal|first=Ronen|last=Shaltiel|title=एक्सट्रैक्टर्स के स्पष्ट निर्माण में हालिया विकास|journal=Bulletin of the EATCS|year=2002|volume=77|pages=67–95|url=https://cs.haifa.ac.il/~ronen/online_papers/survey.ps|access-date=2018-04-10}}</ref> जहां एक एक्सट्रैक्टर के लिए आवश्यक है कि प्रत्येक घटना को समान वितरण और निकाले गए वितरण के अनुसार समान संभावना मिले, एक डिस्पर्सर के लिए केवल उत्तरार्द्ध की आवश्यकता होती है। इस प्रकार एक डिस्पर्सर के लिए, एक घटना <math>A \subseteq \{0,1\}^{m}</math> हमारे पास है: <math>Pr_{U_{m}}[A] > 1 - \epsilon</math> | ||
<math>Pr_{U_{m}}[A] > 1 - \epsilon</math> | |||
परिभाषा ( | |||
परिभाषा (डिस्पर्सर): A <math>(k, \epsilon)</math>-डिस्पर्सर एक फलन है | |||
<math>Dis: \{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}</math> | <math>Dis: \{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}</math> | ||
ऐसा कि प्रत्येक वितरण के लिए <math>X</math> पर <math>\{0,1\}^{n}</math> साथ | |||
ऐसा कि प्रत्येक वितरण <math>X</math> के लिए <math>H_{\infty}(X) \geq k</math> पर <math>\{0,1\}^{n}</math> के साथ वितरण का समर्थन <math>Dis(X,U_{d})</math> कम से कम <math>(1-\epsilon)2^{m}</math> आकार होता है | |||
==ग्राफ़ सिद्धांत== | ==ग्राफ़ सिद्धांत== | ||
एक ('' | एक ('''''N'', ''M'', ''D'', ''K'', ''e''''')-डिस्पर्सर [[द्विदलीय ग्राफ|द्विपक्षीय ग्राफ]] है जिसमें बायीं ओर ''N'' शीर्ष हैं, प्रत्येक डिग्री ''D'' और दाहिनी ओर ''M'' शीर्ष है, जैसे कि बायीं ओर ''K'' शीर्षों का प्रत्येक उपसमुच्चय दाईं ओर (1 − '''''e''''')''M'' से अधिक शीर्षों से जुड़ा है। | ||
[[एक्सट्रैक्टर (गणित)]] संबंधित प्रकार का ग्राफ है जो और भी | [[एक्सट्रैक्टर (गणित)]] संबंधित प्रकार का ग्राफ है जो और भी सशक्त प्रोपर्टी की गारंटी देता है; इस प्रकार प्रत्येक ('''''N'', ''M'', ''D'', ''K'', ''e''''')-एक्सट्रैक्टर भी ('''''N'', ''M'', ''D'', ''K'', ''e)'''''-डिस्पर्सर है। | ||
==अन्य अर्थ== | ==अन्य अर्थ== | ||
डिस्पेंसर उच्च गति वाला मिश्रण उपकरण है जिसका उपयोग पिगमेंट और अन्य ठोस पदार्थों को तरल में | डिस्पेंसर उच्च गति वाला मिश्रण उपकरण है जिसका उपयोग पिगमेंट और अन्य ठोस पदार्थों को तरल में डिस्पर्सर या घोलने के लिए किया जाता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[विस्तारक ग्राफ]] | *[[विस्तारक ग्राफ]] | ||
==संदर्भ== | ==संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
[[Category: ग्राफ़ परिवार]] | [[Category: ग्राफ़ परिवार]] | ||
Revision as of 11:06, 3 August 2023
डिस्पेंसर एकपक्षीय एक्सट्रैक्टर है।[1] जहां एक एक्सट्रैक्टर के लिए आवश्यक है कि प्रत्येक घटना को समान वितरण और निकाले गए वितरण के अनुसार समान संभावना मिले, एक डिस्पर्सर के लिए केवल उत्तरार्द्ध की आवश्यकता होती है। इस प्रकार एक डिस्पर्सर के लिए, एक घटना हमारे पास है:
परिभाषा (डिस्पर्सर): A -डिस्पर्सर एक फलन है
ऐसा कि प्रत्येक वितरण के लिए पर के साथ वितरण का समर्थन कम से कम आकार होता है
ग्राफ़ सिद्धांत
एक (N, M, D, K, e)-डिस्पर्सर द्विपक्षीय ग्राफ है जिसमें बायीं ओर N शीर्ष हैं, प्रत्येक डिग्री D और दाहिनी ओर M शीर्ष है, जैसे कि बायीं ओर K शीर्षों का प्रत्येक उपसमुच्चय दाईं ओर (1 − e)M से अधिक शीर्षों से जुड़ा है।
एक्सट्रैक्टर (गणित) संबंधित प्रकार का ग्राफ है जो और भी सशक्त प्रोपर्टी की गारंटी देता है; इस प्रकार प्रत्येक (N, M, D, K, e)-एक्सट्रैक्टर भी (N, M, D, K, e)-डिस्पर्सर है।
अन्य अर्थ
डिस्पेंसर उच्च गति वाला मिश्रण उपकरण है जिसका उपयोग पिगमेंट और अन्य ठोस पदार्थों को तरल में डिस्पर्सर या घोलने के लिए किया जाता है।
यह भी देखें
संदर्भ
- ↑ Shaltiel, Ronen (2002). "एक्सट्रैक्टर्स के स्पष्ट निर्माण में हालिया विकास". Bulletin of the EATCS. 77: 67–95. Retrieved 2018-04-10.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |
