Primero que nada antes de empezar este tema aquí están algunos conceptos , que es BDD o en español diagrama de decisión binario.
En ciencias de la computación, un diagrama de decisión binario (DDB), es una estructura de datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en los DDB, sin necesidad de descomprimirlos.
Y una funcion boolena se puede representarse como un grafo acíclico dirigido con raíz, el cual posee nodos de decisión y dos nodos terminales llamados terminal -0 y terminal-1. Cada nodo de decisión está etiquetado por una variable booleana (0 o 1) y tiene dos nodos hijos, llamados hijo menor e hijo mayor. La arista que une un nodo con un hijo menor (mayor) representa una asignación de la variable con el valor 0 (1).
Un DDB está ordenado si las distintas variables aparecen en el mismo orden para todos los caminos desde la raíz. Un DDB es reducido si se han aplicado las siguientes dos reglas a su grafo:
Unir los isomorfismos de subgrafos.
Eliminar los nodos cuyos dos hijos sean isomorfos.
En el uso popular, el término DDB también se refiere a Diagrama de decisión binario reducido ordenado (DDBRO, mejor conocido en la literatura en inglés como ROBDD: Reduced Ordered Binary Decision Diagram). Una ventaja de un DDBRO es que es canónico (único) para una función particular y un orden de variables.Esta propiedad es útil por ejemplo en la verificación de funciones de equivalencia.
Un camino desde el nodo raíz al terminal-1 representa una asignación de variables (posiblemente parcial) para la cual la función booleana es verdadera. Si el camino desciende desde un nodo hasta un hijo menor (mayor), la variable del nodo adquiere el valor 0 (1).
Para la tarea 4 se pidio lo siguiente:
Inventar una función booleana, usando por mínimo 3 variables y 4 conectivos básicos.
* Construyan y dibujen su BDD. Diagrama binario de Decisión creo asi se llama
* Reduzcan el BDD resultante a un ROBDD.
* Dibujen el ROBDD resultante
Esta es mi expresión booleana :
(X v Y)
^ ( Y v X) v ¬ Z
Ahora genero mi arbol binario.
Reducir a ROBDD
Para reducir un árbol binario de decisión a un Diagrama Binario de Decisión se tienen que considerar dos reglas:
- Unir los isomorfismos (de igual forma) de subgrafos
- Eliminar los nodos que sus dos hijos sean isomorfos.
REFERENCIAS :
Ojo con los acentos. Está bien, 10 pts.
ResponderEliminar