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.

JEG Plaza, MAR Nuñez., (2017), Formación en competencias específicas para la industria del software colombiano. Experiencias del uso del aprendizaje basado en proyectos. RCTA.

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.

L Tangarife, M Sánchez, M Rojas., (2017), Modelo de interventoría de tecnologías de información en el área de conocimiento de la gestión del alcance de PMBOK® y alineado con ISO 21500 y COBIT®. RCTA.

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

O Suarez, C Vega, E Sánchez, A Pardo., (2018), Degradación anormal de p53 e inducción de apoptosis en la red P53-mdm2 usando la estrategia de control tipo pin. RCTA.

Omran, M. T., Sack, J. R., &Zarrabi-Zadeh, H. (2013). Findingpathswithminimumsharededges (Vol. 24). JournalofCombinatorialOptimization.

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. RCTA, 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.v35.n35.2020.3926

Enlaces refback

  • No hay ningún enlace refback.