अभिकलनात्मक सांस्थिति

From Vigyanwiki

कलनविधीय टोपोलॉजी, या अभिकलनात्मक टोपोलॉजी, कंप्यूटर विज्ञान के क्षेत्र अतिव्यापन के साथ टोपोलॉजी का एक उपक्षेत्र है, विशेष रूप से, अभिकलनात्मक ज्यामिति और अभिकलनात्मक जटिलता सिद्धांत।

कलनविधीय टोपोलॉजी का एक प्राथमिक संबंध, जैसा कि इसके नाम से पता चलता है, अभिकलनात्मक ज्यामिति,आरेखी , यंत्रमानवशास्त्र, संरचनात्मक जीवविज्ञान औररसायन विज्ञान जैसे क्षेत्रों में स्वाभाविक रूप से उत्पन्न होने वाली समस्याओं को हल करने के लिए कुशल एल्गोरिदम विकसित करना है।[1][2]


विषय क्षेत्र द्वारा प्रमुख एल्गोरिदम

एल्गोरिदमिक 3-कई गुना सिद्धांत

3-कई गुना से संबंधित एल्गोरिदम का एक बड़ा परिवार सामान्य सतह सिद्धांत के चारों ओर घूमता है, जो एक वाक्यांश है जिसमें 3-कई गुना सिद्धांत में पूर्णांक रैखिक प्रोग्रामिंग समस्याओं में समस्याओं को बदलने के लिए कई तकनीकों को शामिल किया गया है।

  • रुबिनस्टीन और थॉम्पसन का 3-क्षेत्रीय पहचान एल्गोरिथम। यह एक एल्गोरिथ्म है जो इनपुट के रूप में एक त्रिभुज (टोपोलॉजी) 3-कई गुना लेता है और यह निर्धारित करता है कि कई गुना 3-क्षेत्र के लिए होमियोमोर्फिज्म है या नहीं। प्रारंभिक 3-कई गुना में टेट्राहेड्रल सिम्प्लेक्स की संख्या में इसकी घातीय रन-टाइम है, और एक घातीय स्मृति प्रोफ़ाइल भी है। इसके अलावा, इसे सॉफ्टवेयर पैकेज रेजिना (कार्यक्रम) में लागू किया गया है।[3] शाऊल श्लेमर ने जटिलता वर्ग एनपी (जटिलता) में समस्या को दिखाने के लिए चला गया।[4] इसके अलावा, राफेल ज़ेंटनर ने दिखाया कि समस्या जटिलता वर्ग coNP में निहित है,[5] बशर्ते कि सामान्यीकृत रीमैन परिकल्पना मान्य हो। वह इंस्टेंटन गेज सिद्धांत, 3-कई गुना के ज्यामितीय प्रमेय और ग्रेग कुपरबर्ग के बाद के काम का उपयोग करता है [6] गाँठ का पता लगाने की जटिलता पर।
  • जुड़ा योग | 3-मैनिफोल्ड्स का कनेक्ट-सम अपघटन भी रेजिना (प्रोग्राम) में लागू किया गया है, इसमें एक्सपोनेंशियल रन-टाइम है और यह 3-स्फीयर रिकग्निशन एल्गोरिदम के समान एल्गोरिदम पर आधारित है।
  • यह निर्धारित करते हुए कि सीफर्ट-वेबर 3-मैनीफोल्ड में कोई असंपीड्य सतह नहीं है, बर्टन, रुबिनस्टीन और टिलमैन द्वारा एल्गोरिथम रूप से लागू किया गया है[7] और सामान्य सतह सिद्धांत पर आधारित है।
  • मैनिंग एल्गोरिथम 3-मैनिफोल्ड्स पर हाइपरबॉलिक संरचनाओं को खोजने के लिए एक एल्गोरिदम है जिसका मौलिक समूह समूहों के लिए शब्द समस्या का समाधान करता है।[8]

वर्तमान में JSJ अपघटन को कंप्यूटर सॉफ्टवेयर में एल्गोरिदमिक रूप से लागू नहीं किया गया है। न ही कम्प्रेशन-बॉडी अपघटन है। कुछ बहुत ही लोकप्रिय और सफल अनुमान हैं, जैसे कि SnapPea, जिसने त्रिभुजित 3-कई गुना पर अनुमानित अतिपरवलयिक संरचनाओं की गणना करने में बहुत सफलता प्राप्त की है। यह ज्ञात है कि 3-कई गुना का पूर्ण वर्गीकरण एल्गोरिदमिक रूप से किया जा सकता है।[9]


रूपांतरण एल्गोरिदम

  • SnapPea प्लानर नॉट (गणित) या नॉट (गणित)#नॉट डायग्राम को पुच्छल त्रिकोणासन में बदलने के लिए एक एल्गोरिथम लागू करता है। इस एल्गोरिथ्म में आरेख में क्रॉसिंग की संख्या और कम मेमोरी प्रोफ़ाइल में मोटे तौर पर रैखिक रन-टाइम है। एल्गोरिथम प्लेनर आरेखों द्वारा दिए गए लिंक पूरक के मौलिक समूह की प्रस्तुतियों के निर्माण के लिए विर्थिंगर एल्गोरिथम के समान है। इसी तरह, SnapPea 3-मैनिफोल्ड की शल्य चिकित्सा सिद्धांत प्रेजेंटेशन को प्रस्तुत 3-मैनिफोल्ड के त्रिकोणासन में बदल सकता है।
  • डी. थर्स्टन और एफ. कॉस्टेंटिनो के पास त्रिकोणीय 3-कई गुना से त्रिकोणीय 4-कई गुना बनाने की प्रक्रिया है। इसी तरह, इसका उपयोग त्रिकोणीय 3-कई गुना की शल्य चिकित्सा प्रस्तुतियों के निर्माण के लिए किया जा सकता है, हालांकि सिद्धांत रूप में प्रक्रिया को स्पष्ट रूप से एल्गोरिदम के रूप में नहीं लिखा गया है, इसमें दिए गए 3-कई गुना त्रिभुज के टेट्राहेड्रा की संख्या में बहुपद रन-टाइम होना चाहिए।[10]
  • एस. श्लीमर के पास एक एल्गोरिद्म है जो एक सतह के मानचित्रण वर्ग समूह के लिए एक शब्द (स्ट्रेच ट्विस्ट जेनरेटर में) दिए जाने पर त्रिकोणीय 3-कई गुना उत्पन्न करता है। 3-कई गुना वह है जो 3-कई गुना के हेगार्ड विभाजन के लिए संलग्न मानचित्र के रूप में शब्द का उपयोग करता है। एल्गोरिथ्म एक स्तरित त्रिकोणासन की अवधारणा पर आधारित है।

एल्गोरिथम गाँठ सिद्धांत

  • यह निर्धारित करना कि गाँठ तुच्छ है या नहीं, जटिलता वर्ग एनपी (जटिलता) में जाना जाता है[11]
  • गाँठ के जीनस को निर्धारित करने की समस्या को जटिलता वर्ग PSPACE के रूप में जाना जाता है।
  • एक गांठ के अलेक्जेंडर बहुपद की गणना के लिए बहुपद-समय एल्गोरिदम हैं।[12]


कम्प्यूटेशनल समरूपता

  • गोले के होमोटॉपी समूहों के लिए कम्प्यूटेशनल तरीके # कम्प्यूटेशनल तरीके।
  • बहुपद समीकरणों की प्रणालियों को हल करने के लिए कम्प्यूटेशनल तरीके#होमोटॉपी निरंतरता विधि।
  • ब्राउन के पास रिक्त स्थान के होमोटॉपी समूहों की गणना करने के लिए एक एल्गोरिथ्म है जो परिमित पोस्टनिक की प्रणाली हैं,[13] हालांकि इसे व्यापक रूप से लागू करने योग्य नहीं माना जाता है।

कम्प्यूटेशनल होमोलॉजी

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

  • LinBox लाइब्रेरी में पाया गया कुशल और संभाव्य स्मिथ सामान्य फॉर्म एल्गोरिदम।
  • Perseus सॉफ्टवेयर पैकेज के रूप में प्री-प्रोसेसिंग होमोलॉजी कंप्यूटेशंस के लिए सरल होमोटोपिक कटौती।
  • TDAstats आर पैकेज के रूप में, निस्पंदन (गणित) परिसरों की लगातार होमोलॉजी की गणना करने के लिए एल्गोरिदम।[14]


यह भी देखें

संदर्भ

  1. ↑ Afra J. Zomorodian, Topology for Computing, Cambridge, 2005, xi
  2. ↑ Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences (in English), Cham: Springer International Publishing, pp. 1–23, doi:10.1007/978-3-319-70658-0_87-1, ISBN 978-3-319-70658-0
  3. ↑ Burton, Benjamin A. (2004). "Introducing Regina, the 3-manifold topology software" (PDF). Experimental Mathematics. 13: 267–272. doi:10.1080/10586458.2004.10504538.
  4. ↑ Schleimer, Saul (2011). "क्षेत्र की पहचान एनपी में निहित है" (PDF) – via University of Warwick.
  5. ↑ Zentner, Raphael (2018). "Integer homology 3-spheres admit irreducible representations in SL(2,C)". Duke Mathematical Journal. 167 (9): 1643–1712. arXiv:1605.08530. doi:10.1215/00127094-2018-0004. S2CID 119275434.
  6. ↑ Kuperberg, Greg (2014). "गाँठ एनपी, मोडुलो जीआरएच में है". Advances in Mathematics. 256: 493–506. arXiv:1112.0845. doi:10.1016/j.aim.2014.01.007. S2CID 12634367.
  7. ↑ Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). "वेबर-सीफर्ट डोडेकाहेड्रल स्पेस नॉन-हेकेन है". Transactions of the American Mathematical Society. 364 (2). arXiv:0909.4625. doi:10.1090/S0002-9947-2011-05419-X.
  8. ↑ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
  9. ↑ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
  10. ↑ Costantino, Francesco; Thurston, Dylan (2008). "3-manifolds efficiently bound 4-manifolds". Journal of Topology. 1 (3): 703–745. arXiv:math/0506577. doi:10.1112/jtopol/jtn017. S2CID 15119190.
  11. ↑ Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM, 46 (2): 185–211, arXiv:math/9807016, doi:10.1145/301970.301971, S2CID 125854.
  12. ↑ "Main_Page", The Knot Atlas.
  13. ↑ Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65: 1–20, doi:10.2307/1969664
  14. ↑ Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). "TDAstats: R pipeline for computing persistent homology in topological data analysis". Journal of Open Source Software. 3 (28): 860. Bibcode:2018JOSS....3..860R. doi:10.21105/joss.00860. PMID 33381678.


बाहरी संबंध


किताबें


श्रेणी:कम्प्यूटेशनल टोपोलॉजी श्रेणी:अनुप्रयुक्त गणित श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत श्रेणी:कम्प्यूटेशनल विज्ञान श्रेणी:अध्ययन के कम्प्यूटेशनल क्षेत्र

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अभिकलनात्मक_सांस्थिति&oldid=128764’