Topología computacional
La topología algorítmica, o topología computacional, és un subcampo de la topología que se superpon en àrees de l'informàtica, en particular, la geometria computacional i la teoria de la complexitat computacional.
Una preocupació principal de la topología algorítmica, com el seu nom ho sugerix, és desenrollar algoritmes eficients per a resoldre problemes que sorgixen naturalment en camps com la geometria computacional, els gràfics, la robòtica, les ciències socials, la biologia estructural i la química, utilisant métodos de la topología computable.[1][2][3]
Principals algoritmes per àrea temàtica
[editar | editar còdic]Teoria algorítmica de 3 varietats
[editar | editar còdic]Una gran família d'algoritmes relacionats en les 3-varietats giren entorn a la teoria de superfícies normals, que és una frase que engloba vàries tècniques per a convertir problemes de la teoria de 3-varietats en problemes de programació llineal sancera.
- Algoritme de reconeiximent de tres esferes de Rubinstein i Thompson. Est és un algoritme que pren com a entrada una varietat triangulada de 3 dimensions i determina si la varietat és homeomorfa o no a la varietat de 3 dimensions. Té un temps d'eixecució exponencial en el número de símplex tetraèdrics en la varietat 3 inicial i també un perfil de memòria exponencial. Ademés, està implementat en el paquet de software Regina. [4] Saul Schleimer va continuar demostrant que el problema radica en la classe de complexitat NP. [5] Ademés, Raphael Zentner va demostrar que el problema residix en la classe de complexitat coNP, [6] sempre que es complixca l'hipòtesis de Riemann generalisada. Utilisa la teoria de calibre instantàneu, la teorema de geometrización de 3 varietats i el treball posterior de Greg Kuperberg [7] sobre la complexitat de la detecció de nucs.
- La descomposició de suma conexa de 3-varietats també està implementada en Regina, té un temps d'eixecució exponencial i es basa en un algoritme similar a l'algoritme de reconeiximent de 3-esferes.
- Burton, Rubinstein i Tillmann [8] han determinat algorítmicamente que la 3-varietat de Seifert-Weber no conté cap superfície incompresible, basant-se en la teoria de superfícies normals.
- El algoritme de Manning és un algoritme per a trobar estructures hiperbòliques en 3-varietats que el seu grup fonamental té una solució al problema verbal.[9]
Actualment, la descomposició JSJ no s'ha implementat algorítmicamente en software de computadora. Tampoc la descomposició del cos per compressió. Hi ha algunes heurístiques molt populars i exitoses, com SnapPea, que té molt èxit en calcular estructures hiperbòliques aproximades en varietats trianguladas de 3 elements. Se sap que la classificació completa de 3-varietats es pot fer algorítmicamente,[10] de fet, se sap que decidir si dos 3-varietats tancades i orientades donades per triangulacions (complexos simpliciales) són equivalents (homeomórficas) és recursivo elemental.[11] Açò generalisa el resultat del reconeiximent de 3 esferes.
Algoritmes de conversió
[editar | editar còdic]- SnapPea implementa un algoritme per a convertir un nuc pla o un diagrama d'enllaç en una triangulació cuspide. Este algoritme té un temps d'eixecució aproximadament llineal en el número de creus en el diagrama i un perfil de memòria baix. L'algoritme és similar a l'algoritme de Wirthinger per a construir representacions del grup fonamental de complements d'enllaç donats per diagrames planars. De manera similar, SnapPea pot convertir presentacions quirúrgiques de 3 varietats en triangulacions de les 3 varietats presentades.
- D. Thurston i F. Costantino tenen un procediment per a construir una varietat 4-triangulada a partir d'una varietat 3-triangulada. De manera similar, es pot utilisar per a construir presentacions quirúrgiques de 3-varietats trianguladas, encara que el procediment no està escrit explícitament com un algoritme; en principi, deuria tindre un temps d'eixecució polinomial en el número de tetraedres de la triangulació de 3-varietats donada. [12]
- S. Schleimer té un algoritme que produïx una varietat triangulada de 3 dimensions, donada com a entrada una paraula (en generadors de torsió Dehn ) per al grup de classes de mapage d'una superfície. La varietat 3 és la que utilisa la paraula com a mapa d'unió per a una divisió de Heegaard de la varietat 3. L'algoritme es basa en el concepte de triangulació en capes.
Teoria de nucs algorítmics
[editar | editar còdic]Se sap que la determinació de si un nuc és trivial o no es realisa en les classes de complexitat NP [13] aixina com també en les co-NP. [14] Se sap que el problema de determinar el gènero d'un nuc té la classe de complexitat PSPACE. [13]
Homotopía computacional
[editar | editar còdic]- Métodos computacionals para grups de homotopía d'esferes.
- Métodos computacionals per a resoldre sistemes d'equacions polinòmiques.
- Brown té un algoritme per a calcular els grups de homotopía d'espais que són complexos de Postnikov finitos, [15] encara que no es considera àmpliament implementable.
Homologia computacional
[editar | editar còdic]El càlcul dels grups d'homologia dels complexos celulars es reduïx a dur les matrius llímit a la forma normal de Smith. Encara que este és un problema completament resolt algorítmicamente, existixen varis obstàculs tècnics per al càlcul eficient de complexos grans. Hi ha dos obstàculs centrals: En primer lloc, l'algoritme bàsic de forma Smith té una complexitat cúbica en el tamany de la matriu involucrada, ya que utilisa operacions de fila i columna, lo que ho fa inadequat per a complexos de celes grans. En segon lloc, les matrius intermiges que resulten de l'aplicació de l'algoritme de la forma Smith es completen inclús si un comença i termina en matrius disperses.
- Algoritmes de forma normal de Smith eficients i provabilístics, com els que es troben en la biblioteca LinBox.
- Reduccions homotópicas simples per a preprocesar càlculs d'homologia, com en el paquet de software Perseus.
- Algoritmes per a calcular la homologia persistent de complexos filtrats, com en el paquet R TDAstats. [16]
- En algunes aplicacions, com en TDA, és útil tindre representants de classes d'homologia que siguen lo més "menuts" possible. Açò es coneix com el problema de la localisació d'homologia. En varietats trianguladas, donada una cadena que representa una classe d'homologia, en general és NP-difícil aproximar la cadena homòloga de soport mínim. [17]No obstant, l'entorn particular d'aproximació de la localisació d'1-cohomología en 2-varietats trianguladas és un dels tres únics problemes coneguts la dificultat dels quals és equivalent a la Conjectura de Joc Únic. [18]
Llibres
[editar | editar còdic]- Tomasz Kaczynski; Konstantin Mischaikow, {{{nom2}}}; Marian Mrozek, {{{nom3}}} (2004). Computational Homology, Springer. ISBN 0-387-40853-3.
- Afra J. Zomorodian (2005). Topology for Computing, Cambridge. ISBN 0-521-83666-2.
- Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5.
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Chiou. «Topologists Tackle the Trouble With Poll Placement». Quanta Magazine. Consultat el 2024-04-01.
- ↑ Zomorodian, Afra J. (2005-01-10). Topology for Computing (en en), Cambridge University Press. ISBN 978-1-139-44263-3.
- ↑ Experimental Mathematics.13(3)
- 267–272.doi:10.1080/10586458.2004.10504538.
- ↑ Schleimer. «Sphere Recognition Lies in NP».
- ↑ (2018).Duke Mathematical Journal.167(9)
- 1643–1712.doi:10.1215/00127094-2018-0004.
- ↑ (2014).Advances in Mathematics.256
- 493–506.doi:10.1016/j.aim.2014.01.007.
- ↑ (2009).Transactions of the American Mathematical Society.364(2)
- 911–932.doi:10.1090/S0002-9947-2011-05419-X.
- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Algorithms and Computation in Mathematics.ISSN 1431-1550.doi:10.1007/978-3-662-05102-3.Consultat el 2025-01-27.
- ↑ Pacific Journal of Mathematics.301
- 189–241.doi:10.2140/pjm.2019.301.189.
- ↑ (2008).Journal of Topology.1(3)
- 703–745.doi:10.1112/jtopol/jtn017.
- ↑ 13,0 13,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Journal of Open Source Software.3(28)
- 860.doi:10.21105/joss.00860.
- ↑ Discrete & Computational Geometry.45(3)
- 425–448.doi:10.1007/s00454-010-9322-8. Preliminary version appeared at SODA 2010.
- ↑ .
- Este artícul conté una traducció derivada de «Topología computacional» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.