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

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=128776’