Durante los últimos días he publicado una serie de cinco artículos sobre el problema de la minimización de funciones lógicas, y en concreto sobre el algoritmo de Quine-McClusky, reputado en la profesión como el procedimiento de referencia para resolver este tipo de problemas: dada una expresión lógica, encontrar la expresión equivalente, o sea, con su misma tabla de verdad, que sea mínima, es decir, que contenga el menor número posible de variables individuales.
Tratándose de un algoritmo publicado en 1956, ha sido estudiado y utilizado profusamente durante sus casi setenta años de vida. Y sin embargo, todavía es posible encontrar formas de mejorar este algoritmo para reducir los recursos informáticos que requiere o simplemente para que efectivamente encuentre la función lógica mínima equivalente a una dada, lo que no siempre hace.
En esos artículos fui paulatinamente describiendo el algoritmo en su diferentes pasos, alguno de ellos nuevo en el sentido de que no he encontrado referencias sobre ellos en la Red, otros idénticos a lo expresado en la literatura, y otros, por fin, con modificaciones sobre lo expresado en dicha literatura sobre el algoritmo.
En este artículo final de la serie presento un único documento con el compendio de los cinco artículos; he retocado algunas frases para eliminar el estilo derivado de estar publicados en una serie de artículos en la web, pero el documento sigue las mismas pautas y el mismo orden de exposición seguido en los artículos de la serie.
He aquí el documento completo.
Espero que os sirva.
Disfrutad de la vida mientras podáis.
The Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado. El documento completo. by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.
{ 4 } Comentarios
Muchas gracias por la serie y el documento con la información completa
De nada, Rafael. Ha sido un placer
Voy leyéndome el artículo poco a poco, esta súper bien explicado y se hace hasta ameno seguir la lógica (estamos locos los informáticos.
Lo que me sorprende de verdad es el potencial de esto. Si realmente los pasos extras y las optimizaciones que describes no están en la literatura y por lo tanto no están implementadas en las librerías habituales… esto tiene el potencial de mejorar todos los compiladores existentes ¿no? (al menos los que las usen que seguro que son casi todos)
Si los compiladores son capaces de mejorar las expresiones lógicas escritas por los programadores, implica que los programas se ejecutarán más rápido y eso no es una tontería. En caso de que el resultado final sea el mismo (el programa final no cambie) aún se ganaría en el tiempo de ejecución de la compilación en sí misma y aunque no es tan importante si que ahorra tiempo de programador y eso también es importante. De hecho, puede que muchas de las optimizaciones que se desactivan por los programadores porque tarda mucho en compilar… no se desactivarían y eso vuelve al principio, mejores programas.
¿Has comprobado si las librerías que comentas incluyen estas optimizaciones o algo similar? Si no es así… a lo mejor algún día cojo el guante y hasta me pongo a ello
Hola, César. Gracias por tu comentario.
Yo no digo que “no estén en la literatura” los procesos y trucos que he encontrado; lo que yo digo es que “no he encontrado referencia alguna” en la Red. Es decir, en la Red GRATUITA. Porque desde luego que no he puesto ni un euro para investigar en las bases de datos de pago.
Pero sí, es posible que nadie haya “descubierto” alguno o todos esos trucos que permiten mejorar en más o en menos el ancestral algoritmo de Quine-McClusky.
Yo soy un informático jubilado un poco loco, que disfruta trasteando con las cosas que le gustan, pero ni voy a gastar una pasta en publicar nada en ninguna revista, ni voy a hacer el esfuerzo de traducir nada a la lingua franca sajona, ni voy a comprobar si hay algo parecido en los optimizadores de los compiladores… y tampoco voy a reclamar la autoría de nada.
Me he divertido investigando y escribiendo el documento, y luego dándolo a conocer a la comunidad de la mejor forma que puedo, que es en estas páginas. Usadlo como mejor os parezca, citándolo o no.
Es decir, lo cedo al dominio público, a la comunidad de esos informáticos un poco pirados (o mucho) a los que nos gusta meternos al barro a buscar la pepita de oro. Vuestro es.
Un saludo Mac
Escribe un comentario