Resumen
El bloqueo económico, político y social impuesto a Cuba limita la adquisición del software legal necesario para el desarrollo de la industria cubana del software, por tal motivo el Software Libre se abre como solución a esta problemática. Actualmente la Universidad de las Ciencias Informáticas lleva a cabo un significativo proceso de migración hacia el Software Libre y juega un papel importantísimo en la producción de software para las diferentes instituciones y empresas; en la misma se utilizan junto con las tecnologías y herramientas, diferentes tipos de estructuras de datos (ED). En la carrera se estudian las ED pero en su versión más simple, lo cual sirve para sumergirse en esta importante materia.
El desarrollo en una plataforma de Software Libre de una Biblioteca de Estructuras de Datos Avanzadas, permitirá reducir en costo y tiempo la solución de diversos problemas, facilitará además la gestión y aprovechamiento de la memoria del sistema y brindará una mayor flexibilidad frente a los cambios que puedan existir.
El producto final tendría gran utilidad en la esfera productiva y docente de la universidad así como en cualquier parte del mundo, ya que nunca se ha logrado agrupar a las variantes de implementación de estas estructuras de datos en una biblioteca.
El hecho de que la Biblioteca de Estructuras de Datos Avanzadas estará implementada para una plataforma de Software Libre, anotará un punto más a favor en su desarrollo, y contará para su mejoramiento y perfección con la colaboración de todos los interesados.
Palabras clave: biblioteca, estructura de datos avanzadas, software libre.
DEVELOPMENT OF A LIBRARY OF ADVANCED DATA STRUCTURE
ABSTRACT
The economic, social and political limits imposed on Cuba for the purchase of legal software required for the development of Cuban software industry, for this reason free software is opened as a solution to this problem. Currently, the University of Information Sciences conducts a significant process of migration to Free Software and plays an important role in the production of software for different institutions and companies, in the same are used in conjunction with the technologies and tools, different types data structures (ED). In the race we study the ED but in its simplest version, which serves to immerse them selves in this important area.
Developing a platform for a Free Software Library Advanced Data Structures, will reduce cost and time in solving various problems, will also facilitate the management and use of system memory and provide greater flexibility for changes may exist. The final product would be useful in the production sphere and teacher at the university as well as anywhere in the world, has never been able to group variants of implementation of these data structures in a library.
The fact that the library of advanced data structures will be implemented for a free software platform, will score one point for their development, and will have for its improvement and perfection with the collaboration of all stakeholders.
Keywords: library, advanced data structure, free software.
Introducción
El desarrollo del software es considerado como uno de los problemas técnicos cruciales en la actualidad y desde su aparición ha ganado gran complejidad. El bloqueo económico, político y social impuesto a Cuba limita, entorpece y encarece la adquisición del software legal necesario para el desarrollo de la industria cubana del software, por tal motivo el Software Libre se abre como solución a esta problemática. Sin duda alguna el Software Libre es sustentable para Cuba, por esto su aplicación como plataforma informática de trabajo adquiere una relevante importancia que puede verse reflejada en el ámbito económico, político y tecnológico.
Actualmente la Universidad de las Ciencias Informáticas lleva a cabo un significativo proceso de migración hacia el Software Libre, ya que muchas de las herramientas que se utilizan son propietarias y hay que pagar grandes sumas de dinero por la adquisición de sus licencias. La universidad juega un papel importantísimo en la producción de software para las diferentes instituciones y empresas, ya sean nacionales o extranjeras, como es el caso de PDVSA; en la misma se utilizan junto con las tecnologías y herramientas, diferentes tipos de estructuras de datos para el manejo con grandes cantidades de información.
A nivel mundial existen bibliotecas de estructuras de datos implementadas en lenguajes de programación como C++, C# y Java que poseen estructuras básicas, tal es el caso de los registros que además son estructuras de datos estáticas, las cuales tienen como marcada limitación que el espacio ocupado en la memoria de la computadora se define en tiempo de compilación y no puede ser modificado durante la ejecución del programa. Para solucionar este problema están las estructuras de datos dinámicas, como las listas, las pilas, las colas, etc., que pueden almacenar grandes cantidades de elementos de diferentes tipos.
En la carrera de Ingeniería Informática o similares, debido a su importancia, es prácticamente obligatorio el estudio de las estructuras de datos pero en su versión más simple (listas, pilas, colas, árboles y grafos sencillos), lo cual sirve para sumergirse en esta importante materia y darle solución a determinados problemas. Para las estructuras de datos se han realizado varios trabajos en el mundo y en Cuba, principalmente en la Universidad de las Ciencias Informáticas, pero lo que se ha desarrollado respecto a este tema en la universidad es para contribuir con el desarrollo de los diversos proyectos productivos o para resolver los problemas puntuales de la docencia, por ejemplo, que sirvan de apoyo en las clases y en las tareas finales de la asignatura de Programación o en la pruebas de nivel de la misma asignatura.
Pero desafortunadamente, según las investigaciones realizadas, no se ha implementado aún una biblioteca que contenga agrupada una gran variedad de estructuras de datos y cuando hace falta utilizarlas hay que implementarlas por separado o usar las que se encuentran aisladas. Por tal motivo el problema científico es precisamente: "la poca disponibilidad de bibliotecas que contengan agrupadas una gran variedad de estructuras de datos avanzadas", con el fin de ser usadas en cualquier solución que lo requiera. El desarrollo en una plataforma de Software Libre de una Biblioteca de Estructuras de Datos Avanzadas, permitirá reducir en costo y tiempo la solución de diversos problemas, facilitará además la gestión y aprovechamiento de la memoria del sistema y brindará una mayor flexibilidad frente a los cambios que puedan existir.
El producto final tendría gran utilidad principalmente en la esfera productiva y docente de la universidad así como en cualquier parte del mundo, ya que como se ha planteado anteriormente, nunca se ha logrado agrupar a las variantes de implementación de estas estructuras de datos en una biblioteca, además la documentación que la acompaña puede emplearse como una herramienta independiente para el estudio de estas estructuras de datos avanzadas. El hecho de que la Biblioteca de Estructuras de Datos Avanzadas estará implementada para una plataforma de Software Libre, anotará un punto más a favor en su desarrollo, y contará para su mejoramiento y perfección con la colaboración de todos los interesados.
Materiales y métodos
Lenguaje Unificado de Modelado (UML)
Es la notación de modelado que se utilizará como soporte para la modelación de la solución propuesta y lograr así un mayor entendimiento de la misma. UML ayuda al usuario a entender la realidad desde el punto de vista de la tecnología y les da la posibilidad de que reflexionen antes de invertir y gastar grandes cantidades de dinero en proyectos que no estén seguros en su desarrollo y de esta forma reducir el coste y el tiempo empleado en la construcción de las piezas que conformarán el modelo. Desde el punto de vista puramente tecnológico, UML tiene una gran variedad de propiedades que han sido las que realmente han contribuido a hacer de este, el estándar de la industria que es en realidad. [Booch, Rumbaugh, Jacobson, 2000]
Metodología de desarrollo de software
La metodología a utilizar como base para el desarrollo de la solución propuesta es el Proceso Unificado de Desarrollo de Software (RUP). Dado que este es un proceso general que cubre todas las posibles expectativas tanto del cliente como del equipo de desarrollo. Es el resultado de la evolución e integración de diferentes metodologías de desarrollo de software. Permite sacar el máximo provecho de los conceptos asociados a la orientación de objetos y al modelado visual. Cuenta con las mejoras prácticas en el desarrollo del software. Además este proceso de desarrollo de software junto con el Lenguaje Unificado de Modelado UML, constituye la metodología estándar más utilizada para el análisis, implementación y documentación de los sistemas orientados a objetos. Permite la mitigación temprana de los posibles riesgos, lo cual es un proceso visible en las primeras etapas del desarrollo del software. [Jacobson, Booch y Rumbaugh, 2000]
Herramienta CASE de Desarrollo de Software
La herramienta a utilizar para un buen desarrollo ingenieril de esta investigación es el Visual Paradigm porque es una herramienta de modelado multiplataforma. A continuación se muestran algunas de sus características fundamentales. Unifica el formato de todos los diagramas, brinda soporte para toda la notación UML, presenta diagramas de capas sofisticados así como análisis de textos. Proporciona características tales como la ingeniería inversa y la generación de código y de informes. Permite invertir el código fuente de los programas, archivos ejecutables y binarios en modelos UML al instante, creando de manera simple toda la documentación. Otra de las ventajas que ofrece es la navegación intuitiva entre el modelo visual y el código, además de permitir la sincronización entre el código fuente y el modelo en tiempo real o bajo demanda. [Paradigm, 2011]
Lenguaje de programación
El lenguaje de programación que se utilizará para la programación de las estructuras de datos avanzadas que conformarán a la biblioteca es Python, el cual es un lenguaje de programación potente y fácil de aprender. Para fundamentar esta decisión se mencionan a continuación algunas características y ventajas que lo hacen muy atractivo.
Es un lenguaje de propósito general, debido a que toda aplicación programable con C# o Java también puede ser programada en Python. Posee múltiples compiladores en diversas plataformas como: Unix/Linux, MS Windows, Macintosh y otros. Es un lenguaje Orientado a Objetos donde se destaca la herencia múltiple como uno de sus principales logros y ofrece una manera sencilla de crear programas con componentes reutilizables. Es multi-paradigma ya que permite varios estilos de programación por ejemplo: Programación Orientada a Objetos, Programación Estructurada o Procedural y Programación Funcional. Posee una sintaxis elegante y clara que se acerca al lenguaje natural, garantizando que todos los programadores tengan un mismo estilo de organizar el código y a su vez permite un fácil entendimiento a los que lo consulten. Las peculiaridades sintácticas de Python traen consigo una reducción de los caracteres utilizados y de líneas de códigos. Es Open Source, razón por la cual la biblioteca de módulos de Python contiene un sin fin de módulos de utilidad y sigue en constante perfeccionamiento y crecimiento.
El entorno de ejecución de Python detecta mucho de los errores de programación que se escapan del control de los compiladores y proporciona información muy rica para detectarlos y corregirlos. Otra ventaja fundamental de Python es la gratuidad de su intérprete y tiene versiones para prácticamente cualquier plataforma en uso: sistemas PC bajo Linux, sistemas PC bajo Microsoft Windows, sistemas Macintosh de Apple, etc. Como nota positiva comentar que la mayoría de las palabras claves utilizadas por Python coinciden con las usadas en C o Java. [Ipiña, Diego, 2010]
IDLE Python 2.5 y PyScripter como Entorno de Desarrollo Integrado (IDE) para la programación de la biblioteca
Desde el surgimiento de Python han sido muchos los Entorno de Desarrollo Integrado que se han desarrollado para este lenguaje, incluso la consola de Linux soporta sus instrucciones y comandos. Entre los más utilizados se encuentran IDLE Python en sus distintas versiones, que es proporcionado por la organización Python.org.
Para la programación de todas las estructuras de datos avanzadas se utilizó el IDLE Python 2.5 por ser la última versión del IDE que proporciona la organización creadora del lenguaje Python.org. El PyScripter es un IDE cómodo ya que brinda opciones de completamiento de código y traceo. Además como Python es un lenguaje interpretado, el bytecode que genera es entendible al mismo tiempo por todos los sistemas operativos que lo soportan.
Resultados y discusión
Como resultado de la presente investigación se obtiene el desarrollo en una plataforma de Software Libre de una Biblioteca de Estructuras de Datos Avanzadas, específicamente con las estructuras de datos: Listas, Pilas, Colas, Tablas Hash y DCEL, en algunas de sus variantes de implementación; conjuntamente se elaboró un documento de ayuda que puede ser utilizado como guía de estudio, aún cuando no se utilicen las implementaciones de la misma, ya que en el documento se detallan diversos aspectos de interés de cada una de las estructuras de datos avanzadas. Lo mencionado anteriormente permite tener un mejor conocimiento de estas estructuras y saber en un problema determinado cual es la más óptima para darle solución al mismo. Sin duda alguna, la Biblioteca de Estructura de Datos Avanzadas desarrollada en una plataforma de Software Libre es sustentable en nuestro país, por este motivo su aplicación adquiere una relevante importancia.
Conceptos asociados al dominio del problema:
Biblioteca de Estructuras de Datos Avanzadas (BEDA): es una abstracción de lo que va a ser la Biblioteca de Estructuras de Datos Avanzadas, es decir, va a ser el fichero que contendrá el conjunto de estructuras de datos que se implementarán.
Nodo: Un nodo se compone por un campo que contiene el tipo de dato de los elementos y por uno o más campos que son referencias a otros nodos.
Lista: Una lista se define como una n-tupla de elementos (donde li es el i-ésimo elemento de la lista) ordenados de forma consecutiva, o sea, el elemento li precede al elemento li +1: L= (l1, l2,…, Ln). [Gregory, 2009]
Pila: Una pila es una estructura sencilla que se puede definir como una colección ordenada S = (S1, S2,…, Sn) donde los elementos se insertan y eliminan por un mismo extremo conocido como tope. [Gregory, 2009]
Cola: Una cola es una estructura de datos caracterizada por ser una lista ordenada de elementos C = (C1, C2,…, Cn), donde la operación de Apilar se realiza por un extremo llamado cola y la operación de extracción Desapilar por el otro llamado cabeza. [Gregory, 2009]
Tabla Hash: Una tabla hash es una estructura de datos que está formada por combinaciones de llaves o claves con valores organizados en sectores de almacenamiento para permitir realizar una búsqueda rápida. [Mictlan, 2008]
DCEL: son las siglas inglesas de lista de lados doblemente enlazados. La estructura DCEL está formada por tres colecciones de registros: Lista de vértices, Lista de aristas y Lista de caras. [Ferrera, 2008]
A continuación se presentan los requisitos funcionales correspondientes a la Biblioteca de Estructuras de Datos Avanzadas agrupados por funcionalidades. El sistema debe permitir:
RF 1. Calcular la longitud.
RF 1.1 Devolver la cantidad de elementos de la lista.
RF 1.2 Devolver la cantidad de elementos de la pila.
RF 1.3 Devolver la cantidad de elementos de la cola.
RF 2. Determinar si la estructura está vacía.
RF 2.1 Determinar si la lista está vacía.
RF 2.2 Determinar si la pila está vacía.
RF 2.3 Determinar si la cola está vacía.
RF 3. Determinar si la estructura está llena.
RF 3.1 Determinar si la lista con arreglo está llena.
RF 3.2 Determinar si la pila con arreglo está llena.
RF 3.3 Determinar si la cola con arreglo está llena.
RF 4. Buscar elementos.
RF 4.1 Buscar elementos en la tabla hash dada una clave.
RF 5. Obtener elementos.
RF 5.1 Obtener el elemento que está en una posición determinada de la lista.
RF 5.2 Obtener el elemento que se encuentra en el tope de la pila.
RF 5.3 Obtener el elemento que se encuentra en la primera posición de la cola.
RF 5.4 Obtener el elemento que se encuentra en la última posición de la cola.
RF 5.5 Obtener las aristas que pertenecen a una cara en la DCEL.
RF 5.6 Obtener las aristas salientes de un vértice en la DCEL.
RF 5.7 Obtener la cara correspondiente dado una arista en la DCEL.
RF 5.8 Obtener los vértices correspondientes a una cara en la DCEL.
RF 6. Adicionar elementos.
RF 6.1 Adicionar un elemento al final de la lista.
RF 6.2 Apilar un elemento en el tope de la pila.
RF 6.3 Adicionar un elemento al final de la cola.
RF 6.4 Adicionar una arista en la DCEL.
RF 7. Insertar elementos.
RF 7.1 Insertar un nuevo elemento en una posición determinada de la lista.
RF 7.2 Insertar un nuevo elemento en un índice determinado de la tabla hash.
RF 8. Eliminar elementos.
RF 8.1 Eliminar el elemento que está en una posición determinada de la lista.
RF 8.2 Desapilar el elemento que se encuentra en el tope de la pila.
RF 8.3 Extraer el elemento que se encuentra en la cabeza de la cola.
RF 8.4 Eliminar el elemento que está en un índice determinado de la tabla hash.
A continuación se muestra el modelo general organizado por paquetes de manera que se pueda entender mejor la lógica del problema. Ver Figura 1.
Fig. 1. Diagrama general del diseño organizado en paquetes de la Biblioteca de Estructura de Datos Avanzadas.
En la implementación se empieza con el resultado del diseño y se implementa el sistema en términos de componentes, es decir, ficheros de código fuente, scripts, ficheros de código binario, ejecutables y similares, describe también como se organizan y se relacionan unos con otros. Los diagramas de componentes se utilizan para mostrar las dependencias de compilación de los ficheros de código, relaciones de derivación entre ficheros de código fuente y ficheros que son resultados de la compilación, dependencias entre los elementos de implementación y los elementos correspondientes del diseño que son implementados. [Jacobson, Booch y Rumbaugh, 2000]. Una biblioteca es una combinación de estos ficheros, y al mostrar las dependencias entre ellos, se obtiene una visión de las partes necesarias para la creación de la biblioteca. En la Figura 2 se observan los componentes que conforman la BEDA.
Fig. 2. Diagrama de Componentes de la Biblioteca de Estructura de Datos Avanzadas.
Las pruebas del software son un elemento crítico para garantizar la calidad del mismo y representa una revisión final de las especificaciones del diseño y de la codificación. Para la validación de las funcionalidades de la BEDA se realizaron Pruebas de Caja Blanca, las cuales se basan en un minucioso examen de los detalles procedimentales del código a evaluar, por lo que es necesario conocer la lógica del programa. [Jacobson, Booch y Rumbaugh, 2000]
Conclusiones
Durante el desarrollo de este trabajo se realizó una investigación exhaustiva del estudio del estado del arte de las diferentes estructuras de datos que conforman a la biblioteca. Se demostró la eficiencia de las tendencias y las tecnologías actuales utilizadas para el desarrollo de la Biblioteca de Estructuras de Datos Avanzadas cubriéndose los pasos propuestos por RUP como metodología de desarrollo de software la cual le dio soporte al lenguaje de modelado UML que se empleó para la modelación de los diferentes diagramas, se utilizó además al Visual Paradigm como herramienta CASE y como lenguaje de programación a Python para la implementación de las diferentes estructuras de datos. Finalmente se concluye que durante la realización del presente trabajo se cumplió con el objetivo general propuesto: "desarrollar en una plataforma de Software Libre una Biblioteca de Estructuras de Datos Avanzadas", específicamente con las estructuras de datos: Listas, Pilas, Colas, Tablas Hash y DCEL, en algunas de sus variantes de implementación; conjuntamente se elaboró un documento que servirá de ayuda a los usuarios de la biblioteca, reafirmando así la utilidad y validez de emplear las tecnologías informáticas para apoyar las labores que se desarrollan en cualquier esfera del desarrollo social.
Referencias
1. Booch, G., Rumbaugh, J. y Jacobson I. "El Lenguaje Unificado de Modelado". 2000.
2. Jacobson, I., Booch G. y Rumbaugh J. "El Proceso Unificado de Desarrollo de Software". 2000, nº [Consultado el: 2011]. Disponible en: http://bibliodoc.uci.cu/pdf/reg00060.pdf.
3. Paradigm, V. 2011. Build Quality Applications Faster, Better and Cheaper [Consultado: 2011 Disponible en: http://www.visual-paradigm.com/product/vpuml/index.jsp.
4. Ipiña, G. D. A., Diego Lz,. Profesor del Departamento de Ingeniería de Software. "Pensando en Python (I):3 en raya en modo texto". Facultad de Ingeniería (ESIDE) de la Universidad de Deusto. 2010
5. Gregory, H. Estructuras de datos, algoritmos y programación orientada a objetos. La Habana: Félix Varela, 2009.
6. Mictlan. Página de entrenamiento para el ACM ICPC de la Universidad Tecnológica de la Mixteca. Diccionarios, de 2008]. Disponible en: http://mictlan.utm.mx/html/jaws/html/index.php?page/diccionarios.
7. Ferrera, J. C. Diagramas de Voronoi Facultad de Informática. Universidad Politécnica de Madrid: 2008. Disponible en: http://www.dma.fi.upm.es/mabellanas/voronoi/voronoi/voronoi.html.
Autor:
Yulaine Arias Guerra1,
Yusel Arias Guerra2
1UCI -Facultad Regional de Granma, Ave. Camilo Cienfuegos, Manzanillo, Granma, Cuba
2 DESOFT, Prolongación de General García, S/N, Bayamo, Granma, Cuba