Investigación y Posgrado

Sitios de Interés

Logo Uncoma UNCOMA
Logo Pedco PEDCO
Logo SIU SIU Guaraní
Logo Correo Correo electrónico FAI
Logo facebook FAI en Facebook
Logo Twitter FAI en Twitter  
boton telegram FAI en Telegram

En caso de emergencia médica dentro del Campus llamar a

sien

Teléfono: 107

Título: "Layout Automático de Grafos con Inteligencia Artificial para la Visualización de Modelos Conceptuales

Tesista: Giuliano Marinelli

Directores: Dra. Laura Cecchi - Dr. Germán Braun

Carrera: Licenciatura en Ciencias de la Computación

Día: 29 de abril de 2020

 

Resumen

Los algoritmos de layout automático son una herramienta de gran utilidad para el diseño de modelos conceptuales, diagramas o grafos, en cualquier lenguaje de modelado como UML, ER, ORM, entre otros. En este sentido, para lograr un algoritmo de layout es necesario estudiar varias características que conforman un layout correctamente visualizado. Hemos considerado de mayor importancia, entre estas características, que el grafo (diagrama) resultante posea una mínima cantidad de cruzamientos entre sus arcos. Este problema se conoce como Crossing Number, y es NP-Completo.

En este trabajo se introduce el diseño y la implementación de ArcGen, un nuevo algoritmo genético, que minimiza la cantidad de cruces de un grafo. ArcGen involucra un preprocesamiento del grafo original, transformando su representación gráfica a un Diagrama de Arcos. Se describen todos los detalles del diseño y de la implementación con la que se validó el algoritmo.

Finalmente, dada la motivación del desarrollo de ArcGen y la complejidad temporal del problema Crossing Number, se realizaron experimentos circunscritos a grafos de tamaño proporcional al de los diagramas que se generan en la práctica real de modelado conceptual.

Se presentan los resultados de estos experimentos, mostrando que el algoritmo reduce el número de cruces sobre el grafo original en hasta cuatro veces. Se muestra también la integración de tal algoritmo con otros de layout, como el algoritmo Dirigido por Fuerzas de Tunkelang que permite dar una visualización diferente sobre el grafo. Finalmente, se evalúan y comparan los resultados en conjunto e individualmente.

Foto del día de la defensa con sus tutores, el tribunal integrado por los docentes Mg. Gerardo Parra, Dra. Gabriela Aranda y Lic.Christian Giménez, y representantes de la Secretaría Academica FAI

Foto del dia de la defensa de tesis  

Ver otras tesis FaI ]