Análisis de complejidad en algoritmos: casos de aplicación

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

doi:10.24054/rcta.v2i36.28

Autores/as

Efrén Romero Riaño Universidad Industrial de Santander
Gabriel Mauricio Martínez Toro Universidad Autónoma de Bucaramanga
Dewar Rico Bautista Universidad Francisco de Paula Santander

DOI:

https://doi.org/10.24054/rcta.v2i36.28

Palabras clave:

Algoritmos, Complejidad computacional, NP-HARD

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.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

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.