ANÁLISIS DE COMPLEJIDAD EN ALGORITMOS: CASOS DE APLICACIÓN

Efrén Romero Riaño, Gabriel Mauricio Martínez Toro, Dewar Rico Bautista

Resumen


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.

Texto completo:

PDF

Referencias


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. Rev. Col. Tec. De Avan.

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. Rev. Col. Tec. De Avan., p.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.




DOI: https://doi.org/10.24054/16927257.v36.n36.2020.4021

Enlaces refback

  • No hay ningún enlace refback.