Бинарни дијаграми одлуке

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

У пољу рачунарских наука, бинарни диаграм одлуке(БДД) или програм гранања, представља Структуру података које представљају Булова функција као сто су негацијска нормална форма или као исказни усмерени ациклични граф, ПДАГ . Такође на вишем апстрактном ниво, БДД се може разматрати као компресовано представљање скупова и релација. За разлику од осталих компресованих представљања, операције се директно примењују на компресовну репрезентацију без потребе за декомпресовање.

Дефиниција уреди

Булове функције се могу представити као коренски, усмерени, ацикличани графови, који садрже одлучујуће и крајње (чворови који немају синова) чворове. Постоје две врсте крајњих чворова који имају вредност или 0 или 1. Сваком чвору $N$ се додељује једна Буловска променљива $V_{N}$ која има два сина и који се називају нижи(лоw) и виши(хигх). Од крајњег чвора $V_{N}$ до нижег(вишег) сина предстаља вредност од $V_{N}$ до 0(1). БДД се такође може назвати и уређен уколико се различите променљиве појављују у свакој путањи од корена у истом поретку. БДД може да буде упрошћен уколико се примене два текућа правила на граф:

Спојити изоморфне подграфове;
Избрисати чворове чија су деца изоморфна.

У свкодневној употреби, термин БДД скоро увек се односи на Редуцед Ордеред Бинарy Децисион Диаграм (РОБДД у литератури, користе се када би аспекти уређивања и упросћавања требало да буду наглашени). Предност РОБДД дијаграма је да може бити канонски (јединствен) представник за одређене функције и променљивог редоследа .^[1] Ово својство је корисно у функционалном проверавању еквиваленције и других операција као што су функционалне технологије мапирања.

Путања од корена до крајњег чвора са вредношћу 1 представља (могуће делимичну) вредности променљиве за коју је Булова функција тачна. Како се спуштамо до нижег( или вишег) сина из чвора тада вредност променљиве тог чвора је 0(или 1).

Пример уреди

Лева слика представља бинарно стабло одлуке(без примена правила за упрошћавање), и таблица истинитости, оба представљају функцију ф(x1, x2, x3). У стаблу, са леве стране, вредност функције може бити одређен за дате вредности променљивих пратећи путању од корена ка крајњим чворовима. У фигури испод, испрекидане линије представљају путању ка нижим синовима, док неиспрекидане предстаљају путање ка вишим синовима. Дакле, да би нашли вредност функције за вредности x1=0, x2=1, x3=1, крећемо из првог чвора(корена) x1, прелазимо испрекиданом линијом до чвора x2 (пошто x1 има вредност 0), након тога прелазимо неиспрекиданом линијемо два пута (пошто вредности променљивих x2 и x3 су једнаки 1) што води до крајњег чвора са вредношћу један, што представља вредност функције ф(x1, x2, x3).

Бинарно "стабло" одлуке са леве стране може бити трансформисан у бинарни диаграм одлуке максималним упрошћавањем према два правила за упрошћавање. Резултат је БДД приказан на десној слици.

Бинарно стабло одлуке и табела истинитости за функцију

f(x_{1},x_{2},x_{3})={\bar {x_{1}}}{\bar {x_{2}}}{\bar {x_{3}}}+x_{1}x_{2}+x_{2}x_{3}

БДД за функцију ф

Историја уреди

Основна идеја ове структуре података потиче од "Сханнон еxпансион". Пребацивање функција је подељена у две подфункције(кофактора) додељујући једну променљиву(иф-тхен-елсе нормална форма). Уколико се таква подфункција може посматрати као подстабло онда се може представити као бинарно стабло одлуке. Бинарни диаграм одлуке (БДД) је увео C. Y. Лее,^[2] и даљим истраживањем Схелдон Б. Акерс^[3] и Раyмонд Т. Боуте.^[4] Док потпуни потенцијал за ефикасне алогаритме базиране на овој структури података је истраживао "Рандал Брyант" на "Царнегие Меллон Университy": он је користио фиксиран редослед променљивих(за канонску репрезентацију) и дељене подграфове (за компресију). Примена ова два концепта доводи до ефикасне структуре података и алогаритама за представљање скупова и релација.^[5] ^[6] Проширујући на неколико дијаграма, тј. један подграф коришћен за неколико дијаграма, дефинисана је структура података Схаред Редуцед Ордеред Бинарy Децисион Диаграм.^[7] Појам БДД се сада углавном користи да означи ту структуру података. У овој видео лекцији Фун Wитх Бинарy Децисион Диаграмс (БДДс),^[8]"Доналд Кнутх" назива ову структуру као једну од бољих фундаменталниних структура која је дефинисана у последњих двадесетпет година и поменуо да је Брyант-ов цланак из 1986. године једно време био један од најзначајнијх цитираних радова у рачунарству.

Апликације уреди

БДД се интезивно користи у ЦАД софтверу за ситезу кола (логичка синтеза) и на формалну верификацију. Постоје неколико мање познатих примена БДД, укључујуци Фаулт трее анализе, Баyесиан образлжењу, конфигурације производа, и приватно претраживање информација^[9] ^[10]. Сваки произвољан БДД (чак и ако није упрошћен или уређен) могу се директно имплементирати заменом сваког чвора са 2-1 мултиплексер. Сваки мултиплексер може да се директно имплементира помоцу 4-ЛУТ у ФПГА. То није тако једноставно да се конвертује из произвољне логичке мреже у БДД(за разлику од анд-инвертер грапх).

Уређивање променљивих уреди

Величина БДД је одређена и функцијом којом је репрезентована и изабраног уређивања променљивих. Постоје Булове функције $f(x_{1},\ldots ,x_{n})$ за које од избора уређивања променљивих зависи да ли ће број чворова бити линеаран (ин н) у најбољем случају или експоненцијалан у најгорем случају. Приметимо Булову функцију $f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.$ Користећи уређење $x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}$ , за БДД је потребно 2^н+1 чворова за представљање функције. Користећи уређење $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}$ , потребно је 2н+2 чворова.

БДД за функцију ƒ(x₁, ..., x₈) = x₁x₂ + x₃x₄ + x₅x₆ + x₇x₈ користећи лоше уређење променљивих

Користећи добро урешење променљивих

У пракси, за примену ове структуре података, је од кљчног значаја да се изабере најбољи начин за уређење променљивих. Проблем проналажења најбољег начина за уређење припада класи "НП-тешких" проблема. Редослед променљивих доводи до ОБДД која је ц пута веца од оптималне.^[11] Међутим постоје ефикасне хеуристике које се баве овим проблемом.^[12] Постоје функције којима је граф увек експоненцијалне величине - независно од уређења променљивих. Ово важи за нпр. функцију множења.

Логичке операције уреди

Многе логичке операције на БДД могу се имплементирати у полиномијалном времену.

Коњукција
Дисјукција
Негација
Егзистенцијална апстракција
Универзална апстракција

Међутим понављањем ових операција више пута нпр. формирање коњукцију или дисјукцију од скупа диаграма, у најгорем случају се може резултирати експоненцијално велики БДД. То је зато што свака од претходних операција за два БДД може да доведе у БДД са величином сразмерно производу та два диаграма, самим тим и до експоненцијалне величине.

Види још уреди

Булова задовљивост проблема
L/поли, тј. Сложеност класа која обухвата комплексне проблеме у полиномијалној величини БДД
Модел цхецкинг
Радикс стабло
Бинарy кеy – метод индетификације врста у биологији помоћу бинарних стабла
Баррингтон'с теорема

Референце уреди

^ Грапх-Басед Алгоритхмс фор Боолеан Фунцтион Манипулатион, Рандал Е. Брyант, 1986
^ C. Y. Лее. "Репресентатион оф Сwитцхинг Цирцуитс бy Бинарy-Децисион Програмс". Белл Сyстемс Тецхницал Јоурнал,. . 38. 1959: 985—999. Недостаје или је празан параметар |титле= (помоћ).
^ Схелдон Б. Акерс. Бинарy Децисион Диаграмс, ИЕЕЕ Трансацтионс он Цомпутерс, C- . 27 (6): 509—516. Недостаје или је празан параметар |титле= (помоћ), Јуне 1978.
^ Раyмонд Т. Боуте. „Тхе Бинарy Децисион Мацхине ас а программабле цонтроллер”. ЕУРОМИЦРО Неwслеттер, Вол. 1 (2): 16—22. , Јануарy 1976.
^ Рандал Е. Брyант. "Грапх-Басед Алгоритхмс фор Боолеан Фунцтион Манипулатион Архивирано на сајту Wayback Machine (23. септембар 2015)". IEEE Transactions on Computers, C- . 35 (8): 677—691. Недостаје или је празан параметар |title= (помоћ), 1986.
^ R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys,. . 24 (3) http://www.cs.cmu.edu/~bryant/pubdir/acmcs92.ps. Недостаје или је празан параметар |title= (помоћ) (September). 1992. pp. 293-318.
^ Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "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.
^ „Stanford Center for Professional Development[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 04. 06. 2014. г. Приступљено 18. 04. 2014. Сукоб URL—викивеза (помоћ)
^ R.M. Jensen. "CLab: A C+ + library for fast backtrack-free interactive product configuration". Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, 2004.
^ H.L. Lipmaa. "First CPIR Protocol with Data-Dependent Computation". ICISC 2009.
^ Detlef Sieling. "The nonapproximability of OBDD minimization." Information and Computation 172, 103–138. 2002.
^ Rice, Michael. „A Survey of Static Variable Ordering Heuristics for E?cient BDD/MDD Construction” (PDF).

Литература уреди

R. Ubar, "Test Generation for Digital Circuits Using Alternative Graphs (in Russian)", in Proc. Tallinn Technical University, 1976, No.409, Tallinn Technical University, Tallinn, Estonia. pp. 75–81.

Dodatna literatura уреди

D. E. Knuth, "The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison–Wesley Professional, March 27, 2009) viii+260pp. Knuth, Donald Ervin (1997). The Art of Computer Programming: Fasc. 0. Introduction to combinatorial algorithms and boolean functions. Addison-Wesley. ISBN 978-0-321-58050-4. Архивирано из оригинала 12. 03. 2016. г. Приступљено 18. 04. 2014.
H. R. Andersen "An Introduction to Binary Decision Diagrams," Lecture Notes, 1999, IT University of Copenhagen.
Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: OBDD – Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
Ebendt, Rüdiger; Fey, Görschwin; Drechsler, Rolf (2005). Advanced BDD optimization. Springer. ISBN 978-0-387-25453-1.
Becker, Bernd; Drechsler, Rolf (1998). Binary Decision Diagrams: Theory and Implementation. Springer. ISBN 978-1-4419-5047-5.

Spoljašnji linkovi уреди

Dosupni BDD paketi

ABCD: ABCD paketi Armin Biere, Johannes Kepler Universität, Linz.
CMU BDD, BDD paket, Carnegie Mellon University, Pittsburgh
BuDDy: A BDD paket by Jørn Lind-Nielsen
Biddy:Akademska multiplatforma BDD paketa, University of Maribor
CUDD: BDD paket, University of Colorado, Boulder
JavaBDD: Java biblioteka za manipulaciju BDD
JDD java implementcaija BDD i ZBDD.
JBDD od istog autora koji ima slican API, ali je Java interfejs od BuDDy i CUDD
The Berkeley CAL paketi za manipulacijom u sirinu
DDD: C++ biblioteka koja dodatno sadrzi celobrojnu vrednot i hijerarhijske dijagrame odluke
JINC: C++ biblioteka razvijena na University of Bonn, Germany, podrzava nekoliko BDD varijanti i visenitnio
Fun With Binary Decision Diagrams (BDDs), lecture by Donald Knuth

[1] Грапх-Басед Алгоритхмс фор Боолеан Фунцтион Манипулатион, Рандал Е. Брyант, 1986

[Lee-2] C. Y. Лее. "Репресентатион оф Сwитцхинг Цирцуитс бy Бинарy-Децисион Програмс". Белл Сyстемс Тецхницал Јоурнал,. . 38. 1959: 985—999. Недостаје или је празан параметар |титле= (помоћ).

[Akers-3] Схелдон Б. Акерс. Бинарy Децисион Диаграмс, ИЕЕЕ Трансацтионс он Цомпутерс, C- . 27 (6): 509—516. Недостаје или је празан параметар |титле= (помоћ), Јуне 1978.

[4] Раyмонд Т. Боуте. „Тхе Бинарy Децисион Мацхине ас а программабле цонтроллер”. ЕУРОМИЦРО Неwслеттер, Вол. 1 (2): 16—22. , Јануарy 1976.

[Bryant-1986-5] Рандал Е. Брyант. "Грапх-Басед Алгоритхмс фор Боолеан Фунцтион Манипулатион Архивирано на сајту Wayback Machine (23. септембар 2015)". IEEE Transactions on Computers, C- . 35 (8): 677—691. Недостаје или је празан параметар |title= (помоћ), 1986.

[Bryant-1992-6] R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys,. . 24 (3) http://www.cs.cmu.edu/~bryant/pubdir/acmcs92.ps. Недостаје или је празан параметар |title= (помоћ) (September). 1992. pp. 293-318.

[Brace-7] Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "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.

[8] „Stanford Center for Professional Development[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 04. 06. 2014. г. Приступљено 18. 04. 2014. Сукоб URL—викивеза (помоћ)

[Jensen-9] R.M. Jensen. "CLab: A C+ + library for fast backtrack-free interactive product configuration". Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, 2004.

[Lipmaa-10] H.L. Lipmaa. "First CPIR Protocol with Data-Dependent Computation". ICISC 2009.

[Sieling-11] Detlef Sieling. "The nonapproximability of OBDD minimization." Information and Computation 172, 103–138. 2002.

[12] Rice, Michael. „A Survey of Static Variable Ordering Heuristics for E?cient BDD/MDD Construction” (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]