3 सम - Revision history

Manidh at 03:52, 4 August 2023

2023-08-04T03:52:35Z

@@ Line 191: / Line 191: @@
   | url = http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
   | year = 2004}}.
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 10/07/2023]]
-[[Category:Vigyan Ready]]
+[[Category:Lua-based templates]]

Indicwiki: 10 revisions imported from :alpha:3_सम

2023-08-04T03:34:35Z

10 revisions imported from alpha:3_सम

← Older revision	Revision as of 09:04, 4 August 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-08-03T11:45:47Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 17:15, 3 August 2023
Line 197:		Line 197:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 10/07/2023]]		[[Category:Created On 10/07/2023]]
			[[Category:Vigyan Ready]]

alpha>Neeraja: Neeraja moved page आसुम to 3 सम without leaving a redirect

2023-08-03T11:44:32Z

Neeraja moved page आसुम to 3 सम without leaving a redirect

← Older revision	Revision as of 17:14, 3 August 2023
(No difference)

alpha>Neetua08 at 12:15, 17 July 2023

2023-07-17T12:15:44Z

← Older revision		Revision as of 17:45, 17 July 2023
Line 3:		Line 3:

	{{unsolved\|कंप्यूटर विज्ञान\|क्या 3सम समस्या को समय पर हल करने के लिए कोई एल्गोरिदम है? <math>O(n^{2-\epsilon})</math>, कुछ के लिए <math>\epsilon>0</math>?}}		{{unsolved\|कंप्यूटर विज्ञान\|क्या 3सम समस्या को समय पर हल करने के लिए कोई एल्गोरिदम है? <math>O(n^{2-\epsilon})</math>, कुछ के लिए <math>\epsilon>0</math>?}}
	[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3सम समस्या पूछती है कि क्या दिया गया समुच्चय <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv\|एरिक्सन\|1999}}.		[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''3सम''' समस्या पूछती है कि क्या दिया गया समुच्चय <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv\|एरिक्सन\|1999}}.

	यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम <math> \Omega(n^2) </math> समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय {{sfn\|Grønlund\|Pettie\|2014}} इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता <math> O(n^{3/2}\sqrt{\log n}) </math> है इसके पश्चात् इन सीमाओं में सुधार किया गया था।{{sfn\|Freund\|2017}}{{sfn\|Gold\|Sharir\|2017}}{{sfn\|Chan\|2018}}		यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम <math> \Omega(n^2) </math> समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय {{sfn\|Grønlund\|Pettie\|2014}} इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता <math> O(n^{3/2}\sqrt{\log n}) </math> है इसके पश्चात् इन सीमाओं में सुधार किया गया था।{{sfn\|Freund\|2017}}{{sfn\|Gold\|Sharir\|2017}}{{sfn\|Chan\|2018}}
Line 9:		Line 9:
	3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> चलता है {{sfn\|Chan\|2018}} केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री <math>O(n{\log^2 n})</math> जटिलता है {{sfn\|Kane\|Lovett\|Moran\|2018}} पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान <math>O(n^{2-\Omega(1)})</math> नहीं हो सका है।<ref name="kpp14" />		3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> चलता है {{sfn\|Chan\|2018}} केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री <math>O(n{\log^2 n})</math> जटिलता है {{sfn\|Kane\|Lovett\|Moran\|2018}} पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान <math>O(n^{2-\Omega(1)})</math> नहीं हो सका है।<ref name="kpp14" />

	जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>		जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>
	== द्विघात एल्गोरिथ्म ==		== द्विघात एल्गोरिथ्म ==
	मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है		मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है

alpha>Neetua08 at 11:49, 17 July 2023

2023-07-17T11:49:22Z

← Older revision		Revision as of 17:19, 17 July 2023
Line 10:		Line 10:

	जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>		जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>



	== द्विघात एल्गोरिथ्म ==		== द्विघात एल्गोरिथ्म ==
	मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है		मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है
Line 70:		Line 67:
	* वापस करना {{tmath\|a \gets (a'-1)/10,\ b \gets (b'-2)/10,\ c \gets (c'+3)/10}}.		* वापस करना {{tmath\|a \gets (a'-1)/10,\ b \gets (b'-2)/10,\ c \gets (c'+3)/10}}.
	जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी {{math\|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}} है .<ref>For a reduction in the other direction, see [https://cs.stackexchange.com/q/37888 Variants of the 3-sum problem].</ref>		जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी {{math\|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}} है .<ref>For a reduction in the other direction, see [https://cs.stackexchange.com/q/37888 Variants of the 3-sum problem].</ref>


	=== कनवल्शन योग ===		=== कनवल्शन योग ===
	सरणी के इच्छानुसार तत्वों की खोज करने के अतिरिक्त:		सरणी के इच्छानुसार तत्वों की खोज करने के अतिरिक्त:
Line 77:		Line 72:
	कनवल्शन 3सम समस्या (कन्व3सम) विशिष्ट स्थानों में तत्वों की खोज करती है:<ref name=patrascu10>{{Cite conference \| doi = 10.1145/1806689.1806772\| title = गतिशील समस्याओं के लिए बहुपद निचली सीमा की ओर\| conference = Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10\| pages = 603\| year = 2010\| last1 = Patrascu \| first1 = M. \| isbn = 9781450300506}}</ref>		कनवल्शन 3सम समस्या (कन्व3सम) विशिष्ट स्थानों में तत्वों की खोज करती है:<ref name=patrascu10>{{Cite conference \| doi = 10.1145/1806689.1806772\| title = गतिशील समस्याओं के लिए बहुपद निचली सीमा की ओर\| conference = Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10\| pages = 603\| year = 2010\| last1 = Patrascu \| first1 = M. \| isbn = 9781450300506}}</ref>
	:<math>S[i+j]=S[i]+S[j]</math>		:<math>S[i+j]=S[i]+S[j]</math>


	==== कन्व3सम से 3सम तक कमी ====		==== कन्व3सम से 3सम तक कमी ====
	3सम के लिए सॉल्वर दिए जाने पर, कन्व3सम समस्या को निम्नलिखित विधि से हल किया जा सकता है।<ref name=patrascu10/>		3सम के लिए सॉल्वर दिए जाने पर, कन्व3सम समस्या को निम्नलिखित विधि से हल किया जा सकता है।<ref name=patrascu10/>
Line 120:		Line 113:

	अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी उपस्थित हैं। उदाहरण [[एक्स + वाई छँटाई\|x + y]] का निर्णय संस्करण है: संख्याओं के दिए गए समुच्चय {{mvar\|X}} और {{mvar\|Y}} का {{mvar\|n}} तत्व प्रत्येक वहाँ {{mvar\|''n''²}} हैं <ref>{{cite web \|first1=Erik \|last1=Demaine \|author-link1=Erik Demaine \|first2=Jeff \|last2=Erickson \|first3=Joseph \|last3=O'Rourke \|title=Problem 41: Sorting X + Y (Pairwise Sums) \|date=20 August 2006 \|access-date=23 September 2014 \|website=The Open Problems Project \|url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>		अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी उपस्थित हैं। उदाहरण [[एक्स + वाई छँटाई\|x + y]] का निर्णय संस्करण है: संख्याओं के दिए गए समुच्चय {{mvar\|X}} और {{mvar\|Y}} का {{mvar\|n}} तत्व प्रत्येक वहाँ {{mvar\|''n''²}} हैं <ref>{{cite web \|first1=Erik \|last1=Demaine \|author-link1=Erik Demaine \|first2=Jeff \|last2=Erickson \|first3=Joseph \|last3=O'Rourke \|title=Problem 41: Sorting X + Y (Pairwise Sums) \|date=20 August 2006 \|access-date=23 September 2014 \|website=The Open Problems Project \|url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>


	== यह भी देखें ==		== यह भी देखें ==
	* उपसमुच्चय योग समस्या		* उपसमुच्चय योग समस्या
Line 127:		Line 118:
	== टिप्पणियाँ ==		== टिप्पणियाँ ==
	{{Reflist}}		{{Reflist}}


	== संदर्भ ==		== संदर्भ ==
	*{{cite journal \|last1=Kane \|first1=Daniel M. \|last2=Lovett \|first2=Shachar \|last3=Moran \|first3=Shay \|title=Near-optimal linear decision trees for k-SUM and related problems \|journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) \|year=2018 \|pages=554–563 \|doi=10.1145/3188745.3188770 \|arxiv=1705.01720 \|isbn=9781450355599 \|s2cid=30368541 }}		*{{cite journal \|last1=Kane \|first1=Daniel M. \|last2=Lovett \|first2=Shachar \|last3=Moran \|first3=Shay \|title=Near-optimal linear decision trees for k-SUM and related problems \|journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) \|year=2018 \|pages=554–563 \|doi=10.1145/3188745.3188770 \|arxiv=1705.01720 \|isbn=9781450355599 \|s2cid=30368541 }}

alpha>Neetua08 at 11:48, 17 July 2023

2023-07-17T11:48:39Z

← Older revision		Revision as of 17:18, 17 July 2023
Line 2:		Line 2:
	{{redirects\|3सम\|माल्ट पेय\|एल्कोपॉप्स की तुलना#बीयर-आधारित}}		{{redirects\|3सम\|माल्ट पेय\|एल्कोपॉप्स की तुलना#बीयर-आधारित}}

	{{unsolved\|~~computer science~~\|~~Is there an algorithm to solve the 3SUM problem in time~~ <math>O(n^{2-\epsilon})</math>, ~~for some~~ <math>\epsilon>0</math>?}}		{{unsolved\|कंप्यूटर विज्ञान\|क्या 3सम समस्या को समय पर हल करने के लिए कोई एल्गोरिदम है? <math>O(n^{2-\epsilon})</math>, कुछ के लिए <math>\epsilon>0</math>?}}
	[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3सम समस्या पूछती है कि क्या दिया गया समुच्चय <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv\|एरिक्सन\|1999}}.		[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3सम समस्या पूछती है कि क्या दिया गया समुच्चय <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv\|एरिक्सन\|1999}}.

	यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम <math> \Omega(n^2) </math> समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय {{sfn\|Grønlund\|Pettie\|2014}} इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता <math> O(n^{3/2}\sqrt{\log n}) </math> है इसके पश्चात् इन सीमाओं में सुधार किया गया था।{{sfn\|Freund\|2017}}{{sfn\|Gold\|Sharir\|2017}}{{sfn\|Chan\|2018}}		यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम <math> \Omega(n^2) </math> समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय {{sfn\|Grønlund\|Pettie\|2014}} इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता <math> O(n^{3/2}\sqrt{\log n}) </math> है इसके पश्चात् इन सीमाओं में सुधार किया गया था।{{sfn\|Freund\|2017}}{{sfn\|Gold\|Sharir\|2017}}{{sfn\|Chan\|2018}}

	3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> चलता है {{sfn\|Chan\|2018}} केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री <math>O(n{\log^2 n})</math> जटिलता है {{sfn\|Kane\|Lovett\|Moran\|2018}} पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान <math>O(n^{2-\Omega(1)})</math> नहीं हो सका है।<ref name="kpp14" />		3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> चलता है {{sfn\|Chan\|2018}} केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री <math>O(n{\log^2 n})</math> जटिलता है {{sfn\|Kane\|Lovett\|Moran\|2018}} पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान <math>O(n^{2-\Omega(1)})</math> नहीं हो सका है।<ref name="kpp14" />

	जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>		जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <math>O(n + N\log N)</math> किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, समुच्चय की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय <math>S</math> की तुलना की गई थी <ref>{{Introduction to Algorithms\|edition=3}} Ex. 30.1–7, p. 906.</ref>



	== द्विघात एल्गोरिथ्म ==		== द्विघात एल्गोरिथ्म ==
	मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है		मान लीजिए कि इनपुट ऐरे <math>S[0..n-1]</math> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <math>O(n^2)</math> को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math> है

	कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)\|कंप्यूटर प्रोग्रामिंग]] आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार <math>O(n^2)</math> है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>		कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)\|कंप्यूटर प्रोग्रामिंग]] आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार <math>O(n^2)</math> है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>

	सॉर्ट(s);<syntaxhighlight lang="abl">		सॉर्ट(s);<syntaxhighlight lang="abl">
Line 105:		Line 105:
	:<math>h(x+y)=h(x)+h(y)</math> या		:<math>h(x+y)=h(x)+h(y)</math> या
	:<math>h(x+y)=h(x)+h(y)+1</math>		:<math>h(x+y)=h(x)+h(y)+1</math>
	इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, अर्थात, प्रत्येक तत्व को रखना होता है इस प्रकार <math>x\in S</math> में दोनों <math>T[h(x)]</math> और अंदर <math>T[h(x)]-1</math>. इसलिए प्रत्येक सेल में 2R तत्व होते है, और हमें कन्व3सम चलाना <math>(2R)^3</math> होता है .		इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, अर्थात, प्रत्येक तत्व को रखना होता है इस प्रकार <math>x\in S</math> में दोनों <math>T[h(x)]</math> और अंदर <math>T[h(x)]-1</math>. इसलिए प्रत्येक सेल में 2R तत्व होते है, और हमें कन्व3सम चलाना <math>(2R)^3</math> होता है .

	== 3सम-कठोरता ==		== 3सम-कठोरता ==
Line 119:		Line 119:
	** विमान में गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंड बाधाओं के समुच्चय को देखते हुए, क्या किसी दिए गए रॉड को बाधाओं से टकराए बिना प्रारंभ और समाप्ति स्थितियों के बीच अनुवाद और घुमाव द्वारा स्थानांतरित किया जा सकता है?		** विमान में गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंड बाधाओं के समुच्चय को देखते हुए, क्या किसी दिए गए रॉड को बाधाओं से टकराए बिना प्रारंभ और समाप्ति स्थितियों के बीच अनुवाद और घुमाव द्वारा स्थानांतरित किया जा सकता है?

	अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी उपस्थित हैं। उदाहरण [[एक्स + वाई छँटाई\|x + y]] का निर्णय संस्करण है: संख्याओं के दिए गए समुच्चय {{mvar\|X}} और {{mvar\|Y}} का {{mvar\|n}} तत्व प्रत्येक वहाँ {{mvar\|''n''²}} हैं <ref>{{cite web \|first1=Erik \|last1=Demaine \|author-link1=Erik Demaine \|first2=Jeff \|last2=Erickson \|first3=Joseph \|last3=O'Rourke \|title=Problem 41: Sorting X + Y (Pairwise Sums) \|date=20 August 2006 \|access-date=23 September 2014 \|website=The Open Problems Project \|url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>		अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी उपस्थित हैं। उदाहरण [[एक्स + वाई छँटाई\|x + y]] का निर्णय संस्करण है: संख्याओं के दिए गए समुच्चय {{mvar\|X}} और {{mvar\|Y}} का {{mvar\|n}} तत्व प्रत्येक वहाँ {{mvar\|''n''²}} हैं <ref>{{cite web \|first1=Erik \|last1=Demaine \|author-link1=Erik Demaine \|first2=Jeff \|last2=Erickson \|first3=Joseph \|last3=O'Rourke \|title=Problem 41: Sorting X + Y (Pairwise Sums) \|date=20 August 2006 \|access-date=23 September 2014 \|website=The Open Problems Project \|url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>


	== यह भी देखें ==		== यह भी देखें ==
	* उपसमुच्चय योग समस्या		* उपसमुच्चय योग समस्या

alpha>Neetua08 at 11:46, 17 July 2023

2023-07-17T11:46:11Z

Show changes

alpha>Neetua08 at 11:32, 17 July 2023

2023-07-17T11:32:38Z

← Older revision		Revision as of 17:02, 17 July 2023
Line 18:		Line 18:
	कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)\|कंप्यूटर प्रोग्रामिंग]] आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार <math>O(n^2)</math> है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>		कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)\|कंप्यूटर प्रोग्रामिंग]] आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार <math>O(n^2)</math> है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>

	सॉर्ट(एस);		सॉर्ट(एस);<syntaxhighlight lang="abl">
			sort(S);
	i = 0 से n - 2 ~~के लिए करें~~		for i = 0 to n - 2 do
	ए = एस[आई];		a = S[i];
	~~प्रारंभ~~ = ~~मैं~~ + 1;		start = i + 1;
	~~अंत~~ = एन - 1;		end = n - 1;
	~~जबकि~~ (~~प्रारंभ~~ <~~अंत~~) ~~करते हैं~~		while (start < end) do
	बी = एस[~~प्रारंभ~~]		b = S[start]
	सी = एस[~~अंत~~];		c = S[end];
	~~यदि~~ (ए + बी + सी == 0) तो		if (a + b + c == 0) then
	~~आउटपुट ए~~, बी, सी;		output a, b, c;
	// ~~शून्य के योग वाले सभी त्रिक संयोजनों की खोज जारी रखें।~~		// Continue search for all triplet combinations summing to zero.
	// हमें अंत और प्रारंभ दोनों को साथ अपडेट करने की आवश्यकता है क्योंकि सरणी मान अलग-अलग हैं।		// We need to update both end and start together since the array values are distinct.
	~~प्रारंभ~~ = ~~प्रारंभ~~ + 1;		start = start + 1;
	~~अंत~~ = ~~अंत~~ - 1;		end = end - 1;
	~~अन्यथा यदि~~ (ए + बी + सी > 0) तो		else if (a + b + c > 0) then
	~~अंत~~ = ~~अंत~~ - 1;		end = end - 1;
	~~अन्य~~		else
	~~प्रारंभ~~ = ~~प्रारंभ~~ + 1;		start = start + 1;
	~~अंत~~		end
	~~अंत~~		end
			</syntaxhighlight>निम्नलिखित उदाहरण छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। a के वर्तमान मान लाल रंग में दिखाए गए हैं, b और c के मान मैजेंटा में दिखाए गए हैं।<syntaxhighlight>
	निम्नलिखित उदाहरण छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। ए के वर्तमान मान लाल रंग में दिखाए गए हैं, बी और सी के मान मैजेंटा में दिखाए गए हैं।		-25 -10 -7 -3 2 4 8 10 (a+b+c==-25)
	<~~span style= color:red~~ >-25~~</span> <span style= color:magenta >~~-10~~</span>~~ -7 -3 2 4 8 ~~<span style= color:magenta >~~10~~</span>~~ (a +बी+सी==-25)		-25 -10 -7 -3 2 4 8 10 (a+b+c==-22)
	~~<span style= color:red >~~-25~~</span>~~ -10 ~~<span style= color:magenta >~~-7~~</span>~~ -3 2 4 8 ~~<span style= color:magenta >~~10~~</span>~~ (ए +बी+सी==-22)		. . .
	. . .		-25 -10 -7 -3 2 4 8 10 (a+b+c==-7)
	~~<span style= color:red >~~-25~~</span>~~ -10 -7 -3 2 4 ~~<span style= color:magenta >~~8~~</span> <span style= color:magenta >~~10~~</span>~~ (a +बी+सी==-7)		-25 -10 -7 -3 2 4 8 10 (a+b+c==-7)
	-25 ~~<span style= color:red >~~-10~~</span> <span style= color:magenta >~~-7~~</span>~~ -3 2 4 8 ~~<span style= color:magenta >~~10~~</span>~~ (ए +बी+सी==-7)		-25 -10 -7 -3 2 4 8 10 (a+b+c==-3)
	-25 ~~<span style= color:red >~~-10~~</span>~~ -7 ~~<span style= color:magenta >~~-3~~</span>~~ 2 4 8 ~~<span style= color:magenta >~~10~~</span>~~ (ए +बी+सी==-3)		-25 -10 -7 -3 2 4 8 10 (a+b+c==2)
	-25 ~~<span style= color:red >~~-10~~</span>~~ -7 -3 ~~<span style= color:magenta >~~2~~</span>~~ 4 8 ~~<span style= color:magenta >~~10~~</span>~~ (a +बी+सी==2)		-25 -10 -7 -3 2 4 8 10 (a+b+c==0)
	-25 ~~<span style= color:red >~~-10~~</span>~~ -7 -3 ~~<span style= color:magenta >~~2~~</span>~~ 4 ~~<span style= color:magenta >~~8~~</span>~~ 10 (a +बी+सी==0)		</syntaxhighlight>एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास समाधान है a + b + c = 0. चूंकि सूचक केवल ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।

	एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास समाधान है a + b + c = 0. चूंकि सूचक केवल ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।

	== वेरिएंट ==		== वेरिएंट ==

alpha>Neetua08 at 11:29, 17 July 2023

2023-07-17T11:29:52Z

Show changes