फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या: Difference between revisions
(Created page with "{{Short description|Computer science problem}} File:FiringSquadProblem.svg|right|thumb|15 अवस्थाओं और समय की 3एन इकाइयों क...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Computer science problem}} | {{Short description|Computer science problem}} | ||
[[File:FiringSquadProblem.svg|right|thumb|15 अवस्थाओं और समय की 3एन इकाइयों का उपयोग करके एफएसएसपी का | [[File:FiringSquadProblem.svg|right|thumb|15 अवस्थाओं और समय की 3एन इकाइयों का उपयोग करके एफएसएसपी का समाधान। समय ऊपर से नीचे बढ़ता जाता है।]] | ||
[[File:FSSP 1d1.svg|right|thumb|समय की 2n-2 इकाइयों का उपयोग करके | [[File:FSSP 1d1.svg|right|thumb|समय की 2n-2 इकाइयों का उपयोग करके समाधान। समय नीचे से ऊपर की ओर बढ़ता जाता है।]]फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या [[कंप्यूटर विज्ञान]] और [[सेलुलर ऑटोमेटन]] में समस्या है जिसमें लक्ष्य सेलुलर ऑटोमेटन को डिजाइन करना है, जो सक्रिय सेल से शुरू होकर अंततः ऐसी स्थिति तक पहुंचता है जिसमें सभी कोशिकाएं साथ सक्रिय होती हैं। इसे पहली बार 1957 में [[जॉन माइहिल]] द्वारा प्रस्तावित किया गया था और 1962 में एडवर्ड एफ. मूर द्वारा ([[जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक)]] और [[मार्विन मिंस्की]] द्वारा समाधान के साथ) प्रकाशित किया गया था। | ||
==समस्या कथन== | ==समस्या कथन== | ||
समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है: लक्ष्य नियमों की | समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है: लक्ष्य नियमों की प्रणाली तैयार करना है जिसके अनुसार अधिकारी निष्पादन विवरण को फायर करने का आदेश दे सकता है ताकि उसके सदस्य अपनी राइफलों को साथ फायर कर सकें। | ||
अधिक औपचारिक रूप से, समस्या [[सेल्यूलर आटोमेटा]] से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें | अधिक औपचारिक रूप से, समस्या [[सेल्यूलर आटोमेटा]] से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें पंक्ति में व्यवस्थित कोशिकाएं कहा जाता है, जैसे कि प्रत्येक चरण में प्रत्येक मशीन अपने पिछले राज्य और अपने दो पड़ोसियों के राज्यों के कार्य के रूप में नए राज्य में संक्रमण करती है। पंक्ति। [[ अग्निशमक दल ]] समस्या के लिए, लाइन में कोशिकाओं की सीमित संख्या होती है, और नियम जिसके अनुसार प्रत्येक मशीन अगले राज्य में संक्रमण करती है, लाइन के आंतरिक सभी कोशिकाओं के लिए समान होनी चाहिए, लेकिन दो के संक्रमण कार्य रेखा के अंतिम बिंदुओं को अलग-अलग होने की अनुमति है, क्योंकि इन दोनों कोशिकाओं में से प्रत्येक के दोनों किनारों पर पड़ोसी गायब है। | ||
प्रत्येक कोशिका की अवस्थाओं में तीन अलग-अलग अवस्थाएँ शामिल होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए कि | प्रत्येक कोशिका की अवस्थाओं में तीन अलग-अलग अवस्थाएँ शामिल होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए कि कोशिका जो शांत है और जिसके पड़ोसी शांत हैं वह शांत बनी रहे। प्रारंभ में, समय पर {{math|1=''t'' = 0}}, सबसे बाईं ओर (सामान्य) सेल को छोड़कर, जो सक्रिय है, सभी अवस्थाएँ शांत हैं। लक्ष्य राज्यों का सेट और संक्रमण फ़ंक्शन को इस तरह डिज़ाइन करना है कि, कोशिकाओं की रेखा कितनी भी लंबी क्यों न हो, समय मौजूद हो {{mvar|t}} ऐसा कि प्रत्येक कोशिका समय पर फायरिंग अवस्था में परिवर्तित हो जाती है {{mvar|t}}, और ऐसा कि कोई भी सेल समय से पहले फायरिंग स्थिति से संबंधित नहीं है {{mvar|t}}. | ||
==समाधान== | ==समाधान== | ||
एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: | एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: तेज़ लहर और धीमी लहर जो तीन गुना धीमी गति से चलती है। तेज़ लहर रेखा के दूसरे छोर से उछलती है और केंद्र में धीमी लहर से मिलती है। फिर दोनों तरंगें चार तरंगों में विभाजित हो गईं, तेज़ और धीमी तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक जारी रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है। | ||
न्यूनतम समय (जो है) का उपयोग करके | न्यूनतम समय (जो है) का उपयोग करके समाधान {{math|2''n'' − 2}}समय की इकाइयों के लिए {{mvar|n}} सैनिक), सबसे पहले किसके द्वारा पाया गया था {{harvs|first=Eiichi|last=Goto|authorlink=Eiichi Goto|year=1962|txt}}, लेकिन उसके समाधान में हजारों राज्यों का उपयोग किया गया। {{harvtxt|Waksman|1966}}इसे 16 राज्यों तक सुधारा, और {{harvtxt|Balzer|1967}} ने इसे आठ राज्यों तक और सुधार दिया, जबकि यह साबित करने का दावा किया कि कोई चार-राज्य समाधान मौजूद नहीं है। [[पीटर सैंडर्स (कंप्यूटर वैज्ञानिक)]] ने बाद में पाया कि बाल्ज़र की खोज प्रक्रिया अधूरी थी, लेकिन सही खोज प्रक्रिया के माध्यम से चार-राज्य गैर-अस्तित्व परिणाम की फिर से पुष्टि करने में कामयाब रहे। वर्तमान में सबसे अच्छा ज्ञात समाधान, छह राज्यों का उपयोग करते हुए, द्वारा पेश किया गया था {{harvs|first=Jacques|last=Mazoyer|year=1987|txt}}. यह अभी भी अज्ञात है कि क्या पाँच-राज्य समाधान मौजूद है। | ||
न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ..., ''S''<sub>''i''</sub>}} गति से {{math|1, 1/3, 1/7, ..., 1/(2<sup> ''i''−1</sup> − 1)}}. सिग्नल {{math|''S''<sub>1</sub>}} लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है {{math|''S''<sub>''i''</sub>}} (के लिए {{math|''i'' ≥ 2}}) सेल पर {{math|''n''/2<sup> ''i''−1</sup>}}. कब {{math|''S''<sub>1</sub>}} प्रतिबिंबित करता है, यह सही छोर पर | न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>, ''S''<sub>3</sub>, ..., ''S''<sub>''i''</sub>}} गति से {{math|1, 1/3, 1/7, ..., 1/(2<sup> ''i''−1</sup> − 1)}}. सिग्नल {{math|''S''<sub>1</sub>}} लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है {{math|''S''<sub>''i''</sub>}} (के लिए {{math|''i'' ≥ 2}}) सेल पर {{math|''n''/2<sup> ''i''−1</sup>}}. कब {{math|''S''<sub>1</sub>}} प्रतिबिंबित करता है, यह सही छोर पर नया जनरल भी बनाता है। सिग्नल {{math|''S''<sub>''i''</sub>}} का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर फैलता है। हर दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। {{math|''S''<sub>1</sub>}} गति 1 से अपने आप चलता है जबकि प्रत्येक धीमा सिग्नल केवल तभी चलता है जब उसे कोई सहायक सिग्नल मिलता है। | ||
==सामान्यीकरण== | ==सामान्यीकरण== | ||
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या को कई अन्य प्रकार के सेलुलर ऑटोमेटन के लिए सामान्यीकृत किया गया है, जिसमें कोशिकाओं के उच्च-आयामी सरणी भी शामिल हैं {{harv|Shinahr|1974}}. विभिन्न प्रारंभिक स्थितियों वाली समस्या के विभिन्न प्रकारों पर भी विचार किया गया है {{harv|Kobayashi|Goldstein|2005}}. | फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या को कई अन्य प्रकार के सेलुलर ऑटोमेटन के लिए सामान्यीकृत किया गया है, जिसमें कोशिकाओं के उच्च-आयामी सरणी भी शामिल हैं {{harv|Shinahr|1974}}. विभिन्न प्रारंभिक स्थितियों वाली समस्या के विभिन्न प्रकारों पर भी विचार किया गया है {{harv|Kobayashi|Goldstein|2005}}. | ||
फायरिंग स्क्वाड समस्या के समाधान को अन्य समस्याओं के लिए भी अपनाया जा सकता है। उदाहरण के लिए, {{harvs|first=Patrick|last=Fischer|authorlink=Patrick C. Fischer|year=1965|txt}} ने फायरिंग स्क्वाड सिंक्रोनाइज़ेशन समस्या के पहले समाधान के आधार पर [[अभाज्य संख्या]]एँ उत्पन्न करने के लिए | फायरिंग स्क्वाड समस्या के समाधान को अन्य समस्याओं के लिए भी अपनाया जा सकता है। उदाहरण के लिए, {{harvs|first=Patrick|last=Fischer|authorlink=Patrick C. Fischer|year=1965|txt}} ने फायरिंग स्क्वाड सिंक्रोनाइज़ेशन समस्या के पहले समाधान के आधार पर [[अभाज्य संख्या]]एँ उत्पन्न करने के लिए सेलुलर ऑटोमेटन एल्गोरिदम डिज़ाइन किया। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 17:53, 10 August 2023
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या कंप्यूटर विज्ञान और सेलुलर ऑटोमेटन में समस्या है जिसमें लक्ष्य सेलुलर ऑटोमेटन को डिजाइन करना है, जो सक्रिय सेल से शुरू होकर अंततः ऐसी स्थिति तक पहुंचता है जिसमें सभी कोशिकाएं साथ सक्रिय होती हैं। इसे पहली बार 1957 में जॉन माइहिल द्वारा प्रस्तावित किया गया था और 1962 में एडवर्ड एफ. मूर द्वारा (जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिंस्की द्वारा समाधान के साथ) प्रकाशित किया गया था।
समस्या कथन
समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है: लक्ष्य नियमों की प्रणाली तैयार करना है जिसके अनुसार अधिकारी निष्पादन विवरण को फायर करने का आदेश दे सकता है ताकि उसके सदस्य अपनी राइफलों को साथ फायर कर सकें।
अधिक औपचारिक रूप से, समस्या सेल्यूलर आटोमेटा से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें पंक्ति में व्यवस्थित कोशिकाएं कहा जाता है, जैसे कि प्रत्येक चरण में प्रत्येक मशीन अपने पिछले राज्य और अपने दो पड़ोसियों के राज्यों के कार्य के रूप में नए राज्य में संक्रमण करती है। पंक्ति। अग्निशमक दल समस्या के लिए, लाइन में कोशिकाओं की सीमित संख्या होती है, और नियम जिसके अनुसार प्रत्येक मशीन अगले राज्य में संक्रमण करती है, लाइन के आंतरिक सभी कोशिकाओं के लिए समान होनी चाहिए, लेकिन दो के संक्रमण कार्य रेखा के अंतिम बिंदुओं को अलग-अलग होने की अनुमति है, क्योंकि इन दोनों कोशिकाओं में से प्रत्येक के दोनों किनारों पर पड़ोसी गायब है।
प्रत्येक कोशिका की अवस्थाओं में तीन अलग-अलग अवस्थाएँ शामिल होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए कि कोशिका जो शांत है और जिसके पड़ोसी शांत हैं वह शांत बनी रहे। प्रारंभ में, समय पर t = 0, सबसे बाईं ओर (सामान्य) सेल को छोड़कर, जो सक्रिय है, सभी अवस्थाएँ शांत हैं। लक्ष्य राज्यों का सेट और संक्रमण फ़ंक्शन को इस तरह डिज़ाइन करना है कि, कोशिकाओं की रेखा कितनी भी लंबी क्यों न हो, समय मौजूद हो t ऐसा कि प्रत्येक कोशिका समय पर फायरिंग अवस्था में परिवर्तित हो जाती है t, और ऐसा कि कोई भी सेल समय से पहले फायरिंग स्थिति से संबंधित नहीं है t.
समाधान
एफएसएसपी का पहला समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार शामिल है: तेज़ लहर और धीमी लहर जो तीन गुना धीमी गति से चलती है। तेज़ लहर रेखा के दूसरे छोर से उछलती है और केंद्र में धीमी लहर से मिलती है। फिर दोनों तरंगें चार तरंगों में विभाजित हो गईं, तेज़ और धीमी तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक जारी रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है।
न्यूनतम समय (जो है) का उपयोग करके समाधान 2n − 2समय की इकाइयों के लिए n सैनिक), सबसे पहले किसके द्वारा पाया गया था Eiichi Goto (1962), लेकिन उसके समाधान में हजारों राज्यों का उपयोग किया गया। Waksman (1966)इसे 16 राज्यों तक सुधारा, और Balzer (1967) ने इसे आठ राज्यों तक और सुधार दिया, जबकि यह साबित करने का दावा किया कि कोई चार-राज्य समाधान मौजूद नहीं है। पीटर सैंडर्स (कंप्यूटर वैज्ञानिक) ने बाद में पाया कि बाल्ज़र की खोज प्रक्रिया अधूरी थी, लेकिन सही खोज प्रक्रिया के माध्यम से चार-राज्य गैर-अस्तित्व परिणाम की फिर से पुष्टि करने में कामयाब रहे। वर्तमान में सबसे अच्छा ज्ञात समाधान, छह राज्यों का उपयोग करते हुए, द्वारा पेश किया गया था Jacques Mazoyer (1987). यह अभी भी अज्ञात है कि क्या पाँच-राज्य समाधान मौजूद है।
न्यूनतम समय वाले समाधानों में, सामान्य सही संकेत भेजता है S1, S2, S3, ..., Si गति से 1, 1/3, 1/7, ..., 1/(2 i−1 − 1). सिग्नल S1 लाइन के दाहिने छोर पर प्रतिबिंबित होता है, और सिग्नल से मिलता है Si (के लिए i ≥ 2) सेल पर n/2 i−1. कब S1 प्रतिबिंबित करता है, यह सही छोर पर नया जनरल भी बनाता है। सिग्नल Si का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर फैलता है। हर दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। S1 गति 1 से अपने आप चलता है जबकि प्रत्येक धीमा सिग्नल केवल तभी चलता है जब उसे कोई सहायक सिग्नल मिलता है।
सामान्यीकरण
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या को कई अन्य प्रकार के सेलुलर ऑटोमेटन के लिए सामान्यीकृत किया गया है, जिसमें कोशिकाओं के उच्च-आयामी सरणी भी शामिल हैं (Shinahr 1974). विभिन्न प्रारंभिक स्थितियों वाली समस्या के विभिन्न प्रकारों पर भी विचार किया गया है (Kobayashi & Goldstein 2005).
फायरिंग स्क्वाड समस्या के समाधान को अन्य समस्याओं के लिए भी अपनाया जा सकता है। उदाहरण के लिए, Patrick Fischer (1965) ने फायरिंग स्क्वाड सिंक्रोनाइज़ेशन समस्या के पहले समाधान के आधार पर अभाज्य संख्याएँ उत्पन्न करने के लिए सेलुलर ऑटोमेटन एल्गोरिदम डिज़ाइन किया।
संदर्भ
- Balzer, Robert (1967), "An 8-state minimal time solution to the firing squad synchronization problem", Information and Control, 10 (1): 22–42, doi:10.1016/S0019-9958(67)90032-0.
- Fischer, Patrick C. (1965), "Generation of primes by a one-dimensional real-time iterative array", Journal of the ACM, 12 (3): 388–394, doi:10.1145/321281.321290.
- Goto, Eiichi (1962), A minimal time solution of the firing squad problem, Dittoed course notes for Applied Mathematics 298, Cambridge, MA: Harvard University, pp. 52–59. As cited by Waksman (1966).
- Kobayashi, Kojiro; Goldstein, Darin (2005), "On formulations of firing squad synchronization problems", Unconventional Computation (PDF), Lecture Notes in Computer Science, vol. 3699, Springer-Verlag, pp. 157–168, doi:10.1007/11560319_15.
- Mazoyer, Jacques (1987), "A six-state minimal time solution to the firing squad synchronization problem", Theoretical Computer Science, 50 (2): 183–238, doi:10.1016/0304-3975(87)90124-1.
- Moore, F. R.; Langdon, G. G. (1968), "A generalized firing squad problem", Information and Control, 12 (3): 212–220, doi:10.1016/S0019-9958(68)90309-4.
- Shinahr, Ilka (1974), "Two- and three-dimensional firing-squad synchronization problem", Information and Control, 24 (2): 163–180, doi:10.1016/S0019-9958(74)80055-0.
- Waksman, Abraham (1966), "An optimum solution to the firing squad synchronization problem", Information and Control, 9 (1): 66–78, doi:10.1016/S0019-9958(66)90110-0.
