Eficiencia algorítmica en aplicaciones de grafos orientadas a redes GMPLS

Efficiency Graphs fllgorithmic’s applications oriented to GMPLS networks

Los algoritmos utilizados en el desarrollo y aplicación de grafos hacen uso de recursos medibles en tiempo y espacio; al estudio de estos costos se le conoce como complejidad algorítmica; frecuentemente se hace uso de cualquier algoritmo al azar sin realizar un análisis de ellos en el ambiente en que se ejecutarán; el objetivo del presente artículo es hacer un análisis algorítmico en ambientes comunes, con el fin de generar estadísticas que evidencien la conveniencia del uso de algoritmos específicos.

I. INTRODUCCIÓN

Para trabajar con algoritmos relacionados con grafos y sus aplicaciones es necesario tomar en cuenta las ramas de las ciencias de la computación que prestan herramientas para realizar análisis detallado, describiendo medidas en tiempo y espacio, para evaluar la eficiencia de éstos.

II. ANÁLISIS ALGORÍTMICO

El análisis algorítmico se puede definir como el estudio que se realiza sobre un algoritmo para determinar si su rendimiento y comportamiento cumple con los requerimientos [15]; adicionalmente, permite tomar en cuenta esta información para determinar la eficiencia del algoritmo. El objetivo del análisis de algoritmos es cuantificar las medidas físicas: "tiempo de ejecución y espacio de memoria" y comparar distintos algoritmos que resuelven un mismo problema [2]. En el análisis de algoritmos es necesario tener en cuenta, inicialmente, que los algoritmos construidos deben ser correctos, es decir, deben producir un resultado deseado en tiempo finito. Los criterios para realizar esta evaluación pueden ser eficiencia, portabilidad, eficacia, robustez, etc. [3]. El concepto de eficiencia de un algoritmo es relativo, dado que ante dos algoritmos que resuelven el mismo problema, uno es más eficiente que otro si consume menos recursos, presentándose que algunos dan una eficiencia en tiempo, pero con un consumo alto de recursos, o, por el contrario, un uso óptimo de recursos, pero con un tiempo un poco más largo. De acuerdo con esto, en muchas ocasiones es bastante útil predecir cómo se comportará un algoritmo sin llegar a su implementación, es decir, analizar el algoritmo matemáticamente.

III. COMPLEJIDAD ALGORÍTMICA

La teoria de la complejidad computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema [16]. Dado que en las ciencias de la computación los algoritmos son la herramienta más importante que se presenta, deben dar solución a diferentes problemas, con pasos concretos, claros y finitos. Cada algoritmo arroja un cálculo correcto a través de la recepción de datos de entrada y de la generación de información de salida [5].