РОЗРОБКА АСОЦІАТИВНОГО МАСИВУ ДЛЯ ЗБЕРІГАННЯ РОЗРІДЖЕНИХ ОРІЄНТОВАНИХ ГРАФІВ НА ОСНОВІ БІНАРНИХ ДІАГРАМ РІШЕНЬ З ПОДАВЛЕННЯМ НУЛІВ

Володимир Володимирович Міхав

Анотація


Ефективне представлення розріджених орієнтованих графів у пам’яті комп’ютера дає можливість будувати моделі складних мереж із великою кількістю об’єктів, у тому числі – соціальних мереж. У статті описується спосіб представлення розріджених орієнтованих графів за допомогою асоціативного масиву на основі бінарних діаграм рішень, який дає можливість ефективно зберігати графи великої розмірності, але вимагає значної кількості обчислень для внесення змін. Для оптимізації використання обчислювальних ресурсів використовується додаткове сховище, у якому будуть накопичуватися зміни. Також у статті запропоновано алгоритм управління пам’яттю при роботі з бінарними діаграмами рішень.

Повний текст:

PDF

Посилання


Ахо А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман; пер. с англ. А. Минько. – М.: ООО "И. Д. Вильямс", 2000. – 384 с.

Карпов Ю. Г. MODEL СHECKING. Верификация параллельных и распределенных программных систем / Юрий Глебович Карпов. – СПб.: БХВ-Петербург, 2010. – С. 295–366

Кнут Д. Э. Искусство программирования, том 4, А. Комбинаторные алгоритмы, часть 1 / Дональд Эрвин Кнут; пер. с англ. И. В. Красикова. – М.: ООО "И. Д. Вильямс", 2013. – 960 с.

Introduction to Algorithms / T.Cormen, C. Leiserson, R. Rivest, C. Stein; 3 rd edition – The MIT Press, 2009. – 1292 p.

Loekito E. A Binary decision diagram based approach for mining frequent subsequences / E. Loekito, J. Bailey, J Pei – Knowledge and Information Systems, 2009. – Volume 24. – Issue 2. – P. 235-268

Rudell R. Dynamic Variable Ordering for Ordered Binary Decision Diagrams / Richard Rudell. // Proceedings of the 1993 IEEE/ACM International Conference on Computer-aided Design. – 1993. – P. 42–47.


Посилання

  • Поки немає зовнішніх посилань.