| TAZ-PFC-2017-018 |
Una aproximación a la optimización de algoritmos mediante el uso de minimización de funciones booleanas
Escartín Aparicio, Rubén Alejandro
Campos Laclaustra, Javier (dir.) ; Viñals Yufera, Víctor (dir.)
Universidad de Zaragoza,
EINA,
2017
Departamento de Informática e Ingeniería de Sistemas, Área de Lenguajes y Sistemas Informáticos
Ingeniero en Informática
Resumen: Este proyecto explora la posibilidad de optimizar algoritmos utilizando técnicas de minimización de funciones booleanas. La idea de partida es que expresar un programa a muy bajo nivel permitirá localizar y eliminar redundancia. Para ello se trabaja con operaciones bit a bit de lógica booleana. Usamos únicamente la función NAND para expresar cualquier otra función gracias a su propiedad de completitud funcional. Expresar un algoritmo de esta forma nos permite, por un lado, tener una medida del coste del algoritmo en funciones NAND y, por otro, paralelizarlo. Mediante minimización, se puede optimizar un circuito lógico equivalente a un fragmento de código secuencial, que no tenga bucles ni recursividad. Para ello se ha desarrollado una técnica propia de minimización rápida. Se han desarrollado técnicas para este proyecto que permiten aplicar la minimización a algoritmos recursivos. De este modo se eliminan, por ejemplo, operaciones repetidas en diferentes iteraciones de un bucle. Para llevar a cabo este trabajo se ha desarrollado una notación propia, parecida a un lenguaje ensamblador, que permite trabajar con funciones lógicas y recursividad. Se ha creado una base de datos dónde se definen las funciones recursivas, que pueden representar desde una puerta lógica hasta un algoritmo como el de la suma. Se han implementado los métodos de optimización de estas funciones recursivas y un método de evaluación, mediante el que se ejecutan para comprobar que son correctas. También se han implementado una serie de utilidades para, por ejemplo, traducir entre diferentes notaciones. Finalmente se han comparado los resultados con el algoritmo sin optimizar y con la solución que nos ofrecerían otras herramientas.
Tipo de Trabajo Académico: Proyecto Fin de Carrera
Enlace permanente:
El registro pertenece a las siguientes colecciones:
Trabajos académicos > Trabajos Académicos por Centro > Escuela de Ingeniería y Arquitectura
Trabajos académicos > Proyectos fin de carrera