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

From Vigyanwiki

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

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


विषय क्षेत्र द्वारा प्रमुख कलनविधि

कलनविधीय के 3-बहुरूपता सिद्धांत

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

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

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


रूपांतरण कलनविधि

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

कलनविधि गाँठ सिद्धांत

  • यह निर्धारित करना कि गाँठ साधारण है या नहीं, जटिलता वर्ग एनपी में जाना जाता है[11]
  • गाँठ के प्रकार को निर्धारित करने की समस्या को जटिलता वर्ग पीस्पेस के रूप में जाना जाता है।
  • एक गांठ के अलेक्जेंडर बहुपद की गणना के लिए कलनविधि हैं।[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=128784’