Головна

Бінарні діаграми рішень (БДР)

  1. Activity diagram (діаграми активності).
  2. Collaboration diagram (діаграми співробітництва)
  3. Use case diagram (діаграми прецедентів).
  4. Z. ХАРАКТЕРИСТИКА ОРГАНІЗАЦІЇ ухвалення управлінських рішень 379
  5. Адміністративне оскарження рішень податкових органів.
  6. Адміністративне оскарження рішень податкових органів.
  7. Аналітика у процесі прийняття державних рішень

Бінарна діаграма рішень (Binary Decision Diagrams, BDD) - це граф, що є модифікацією семантичного дерева. У БДР вузли з одним і тим же значенням функції об'єднані. Якщо на кожному рівні БДР все вершини мають одну і ту ж мітку (однакові змінні), то така БДР називається впорядкованою (в англомовній літературі таке уявлення називається Ordinary Binary Decision Diagrams, або скорочено OBDD). Будемо називати таке уявлення УБДР. Вершини УБДР розташовані за рівнями, кожному рівню відповідає одна змінна, що позначає вершини, що знаходяться на цьому рівні. З кожної вершини виходять два ребра: одне відповідає нульовому значенню відповідної змінної (будемо його зображувати штриховою лінією), а інше - одиничному значенню цієї змінної (воно зображується суцільною лінією).

На рис. 4 показані всі чотири форми представлення функції .

Бінарні діаграми рішень використовуються як компактна форма подання булевої функції. Таке уявлення корисно в багатьох випадках, наприклад, коли потрібно багато разів обчислювати значення функції при різних наборах значень її аргументів. Для того щоб отримати значення функції f, Наприклад, на мові С, замість зберігання громіздкою таблиці істинності можна обчислити оператор: f = q? (R? 0: 1): (р? 0: 1), Який побудований на підставі БДР (див. Рис. 4). У цьому прикладі використання УБДР дозволяє обчислити значення булевої функції, виконавши всього дві операції, в той час як при її обчисленні щодо аналітичного подання потрібно не менше 5 операцій.


Мал. 4. Чотири форми подання двійковій функції

 f (p, q, r)  Таблиця істинності  семантичне дерево  Бінарна діаграма рішень
p q r f

Складність представлення функції за допомогою УБДР істотно залежить від порядку змінних. Так, наприклад, УБДР для іншого порядку змінних, ніж на рис. 4, містить чотири вершини, а не три (рис. 5). Цікавою проблемою теоретичної інформатики є знаходження алгоритму, що дає оптимальний порядок змінних булевої функції з точки зору представлення цієї функції впорядкованої БДР.

Мал. 5. УБДР для функції  з порядком змінних [p, q, r]

 



Попередня   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   Наступна

Дискретна математика | Введення в алгебру логіки | Основні функції алгебри логіки | Формули алгебри логіки | Закони алгебри логіки і наслідки з них | Логічні функції багатьох змінних | Побудова формул алгебри логіки по заданій таблиці істинності | Деякі замкнуті класи (класи Посту). поняття базису | Алгебра Жегалкина і лінійні функції | Методи мінімізації логічних функцій |

© um.co.ua - учбові матеріали та реферати