Análisis de complejidad en algoritmos: casos de aplicación
DOI:
https://doi.org/10.24054/rcta.v2i36.28Keywords:
Algoritmos, Complejidad computacional, NP-HARDAbstract
La complejidad computacional desde el enfoque de tiempo y espacio ha sido un tema de investigación que ha sido abordado por diversos investigadores. La creación de mecanismos capaces de resolver problemas en tiempo razonable y de algoritmos que minimizan el uso de memoria computacional, tema de discusión relevante para los investigadores en el ámbito de la computación. El objetivo del artículo es dar a conocer el análisis de casos de aplicación de complejidad de algoritmos. Casos seleccionados, especialmente problemas de conectividad, en los cuales se clasifican algunos problemas según su complejidad en tiempo y espacio, así como la descripción de los algoritmos usados para solucionar estos problemas.
Downloads
References
Angel, O., Benjamini, I., Ofek, E., &Wieder, U. (2008). Routingcomplexityoffaultynetworks. RandomStructures and Algorithms, 32(1), 71–87. https://doi.org/10.1002/rsa.20163
Ariganello, E. (2014). Redes Cisco. Guía de estudio para la certificación. CCNA Routing y switching (Primera ed.). México D.F., México: Alfaomega. Recuperado el 15 de Mayo de 2017
Arora, S., &Boaz, B. (Enero de 2007). ComputationalComplexity: A Modern Approach,Draftof a book. Princeton University.
Barbehenn, M. (1998). A note onthecomplexityofDijkstra’salgorithmforgraphswithweightedvertices. IEEE TransactionsonComputers, 47(2), 263. https://doi.org/10.1109/12.663776
Bisbal Riera, J. (2009). Manual de algorítmica: recursividad, complejidad y diseño de algoritmos. Barcelona: Editorial UOC.
Bock, M., & Borges Hernandez, C. E. (5 de Febrero de 2005). Un problema en el espacio PSPACE. Recuperado el 24 de 05 de 2017, de http://paginaspersonales.deusto.es/cruz.borges/Papers/05AlgComp.pdf
Bollobás, B., & Riordan, O. (1993). Dijkstra ’ s Algorithm. Network, 69(1959), 036114. Retrievedfrom http://www.ncbi.nlm.nih.gov/pubmed/21282851
CCNA. (2014). Introducción al enrutamiento y reenvío de paquetes. Retrievedfrom https://sites.google.com/site/uvmredes2/1-introduccion-al-enrutamiento-y-reenvio-de-paquetes/1-3-construccion-de-la-tabla-de-enrutamiento
Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introductiontothealgorithns. Secondedition. London: The MIT Press. Recuperado el 23 de 05 de 2017, de http://is.ptithcm.edu.vn/~tdhuy/Programming/Introduction.to.Algorithms.pdf
Eugenio, S., &Rhadamés, C. (09 de 2001). Análisis de Algoritmos y Complejidad. Obtenido de http://ccg.ciens.ucv.ve/~esmitt/ayed/II-2011/ND200105.pdf
Feamster, N., Balakrishnan, H., Rexford, J., Shaikh, A., & van derMerwe, J. (2004). Thecase forseparatingroutingfromrouters. In Proceedingsofthe ACM SIGCOMM workshop on Future directions in networkarchitecture - FDNA ’04 (p. 5). https://doi.org/10.1145/1016707.1016709
Hopcroft, Motwani, & Ullman. (2001). Introductiontoautomatatheory, languajes and computation. Segunda edición. Pearson Education.
Laporte, G., & Osman, I. H. (1995). Routingproblems: A bibliography. AnnalsofOperationsResearch, 61(1), 227–262. https://doi.org/10.1007/BF02098290
Lavalle, J. (2012). El concepto de computabilidad de Alan Turing. Revista de la vicerrectoría de Investigación y estudios de posgrado , 1-16.
MathematicalSocietyofJapan. (1987). EncyclopedicDictionaryofMathematics. KiyosiIto.
Méndez, L., Rodriguez-Colina, E., & Medina, C. (2014). Toma de Decisiones Basadas en el Algoritmo de DIJKSTRA. Redes de Ingeniería, 4(2), 2013. Retrievedfrom http://revistas.udistrital.edu.co/ojs/index.php/REDES/article/view/6357/7872
Omran, M. T., Sack, J. R., &Zarrabi-Zadeh, H. (2013). Findingpathswithminimumsharededges (Vol. 24). JournalofCombinatorialOptimization.
Plaza J, Ruiz M, Rosero C, Zapata L. (2017). Formación en competencias específicas para la industria del software colombiano. Experiencias del uso del aprendizaje basado en proyectos. Revista Tecnologías de Avanzada, ISSN: 1692-7257
Revista digital para profesionales de la enseñanza. (10 de 09 de 2010). Enigma: las matemáticas ganaron la segunda guerra mundial. Obtenido de https://www.feandalucia.ccoo.es/docu/p5sd7422.pdf
Riaño, E., Rico-Bautista, D., & Martínez, M. (2018). ÁRBOL DE CAMINOS MÍNIMOS: ENRUTAMIENTO, ALGORITMOS APROXIMADOS Y COMPLEJIDAD. Revista Colombiana de Tecnologías de Avanzada, 1(31), 11–21. https://doi.org/https://doi.org/10.24054/16927257.v31.n31.2018.2780
Rosenfeld, D. R., & Irazábal, j. (2013). Computabilidad, complejidad computacional y verificación de programas. La Plata: Editorial de la Universidad Nacional de La Plata.
Sanchis, A., Ledezma, A., Iglesias, J., García, B., & Alonso, J. (22 de 05 de 2012). Universidad Carlos III de Madrid. Obtenido de http://ocw.uc3m.es/ingenieria-informatica/teoria-de-automatas-y-lenguajes-formales/material-de-clase-1/tema-8-complejidad-computacional
Scopus. (2017). Análisis de búsquedas con palabras clave . Scopus.
Skiena, S. (1982). Thealgorithmdesign manual. Chicago.
Takey, S. M., & Carvalho, M. M. (2016). Fuzzyfrontendofsystemicinnovations: A conceptual frameworkbasedon a systematicliteraturereview. TechnologicalForecasting and Social Change, 97-109.
Universidad de Huelva. (22 de 05 de 2016). Universidad de Huelva, Departamento de tecnologías de la información. Obtenido de http://www.uhu.es/francisco.moreno/gii_mac/docs/Tema_4.pdf
Yin, C., & Wang, H. (2010). Developed Dijkstra shortestpathsearchalgorithm and simulation. In 2010 International ConferenceonComputerDesign and Applications, ICCDA 2010 (Vol. 1). https://doi.org/10.1109/ICCDA.2010.5541129
Zhang, W., Wu, W., Lee, W., & Du, D.-Z. (2012). Complexity and approximationoftheconnected set-coverproblem. J GlobOptim, 53, 563-572.
Downloads
Published
Versions
- 2020-08-01 (4)
- 2020-08-01 (3)
- 2023-07-19 (2)
- 2020-10-02 (1)
How to Cite
Issue
Section
License
Copyright (c) 2020 REVISTA COLOMBIANA DE TECNOLOGIAS DE AVANZADA
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
