Diferencia entre revisiones de «Diagrama de decisión binario»

El máximo potencial de esta estructura de datos para ser utilizada en la implementación de algoritmos eficientes fue investigada por [[Randal Bryant]] en la [[Universidad Carnegie Mellon]]: su aporte clave fue el utilizar una ordenación fija de variables (para lograr una representación canónica) y sub-grafos compartidos (para mayor compresión). Aplicando ambos conceptos logró una estructura de datos y algoritmos eficientes para la representación de conjuntos y relaciones.<ref name="Bryant-1986">Randal E. Bryant. "[http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.ps Graph-Based Algorithms for Boolean Function Manipulation]". IEEE Transactions on Computers, C-35(8):677–691, 1986.</ref><ref name="Bryant-1992">R. E. Bryant, "[http://www.cs.cmu.edu/~bryant/pubdir/acmcs92.ps Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams"], ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293–318.</ref> Así se definió la estructura de datos ''Diagrama de decisión binario reducido ordenado y compartido'' (en inglés ''«Shared Reduced Ordered Binary Decision Diagram»''), que permite que un sub-grafo sea utilizado por varios DDBs.<ref name="Brace">Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "[http://portal.acm.org/citation.cfm?id=123222&coll=portal&dl=ACM Efficient Implementation of a BDD Package"]. In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), pages 40–45. IEEE Computer Society Press, 1990.</ref> Actualmente, la noción de DDB se utiliza generalmente para referirse a esta estructura de datos particular.

 

 

== Véase también ==