Оптимізація алгоритму субекспоненціальної складності для розв’язання SAT задачі
DOI:
https://doi.org/10.18664/ikszt.v0i3.140329Ключові слова:
SAT задача, булева функція, субекспоненціальна складністьАнотація
При модернізації і створенні сучасних систем управління на залізничному транспорті створюються оптоелектронні аналоги електромагнітних реле. При їх побудові виникає необхідність розв’язання в реальному часі задачі здійсненності бу́левих фо́рмул (SAT задача). В даній роботі для SAT задачі запропоновано алгоритм субекспоненціальної складності, який визначає, чи здійсненна функція, а також процедура, що дозволяє перерахувати всі набори змінних, на яких булева функція здійсненна за субекспоненціальний час.
Посилання
Бутенко, В. М. Компьютерная система управления движением поездов [Текст] / В. М. Бутенко, В. И. Мойсеєнко, Д. М. Кузьменко // Залізничний транспорт України. – 2000. – № 5–6. – С. 80–82.
Комутаційний пристрій-оптоелектронний аналог електромагнітного реле струму [Текст] : пат. UA № 116449, МПК9 H03K 17/60 (2006.01) / Бутенко В. М., Головко О. В., Зайченко О. Б., Мелешко В. В., Мірошник М. А., Мойсеєнко В. І., Чуб І. М., Чуб С. Г.; заявник і власник Український державний університет залізничного транспорту. – № u 2016 11255 від 07.11.2016; опубл. 25.05.2017, Бюл. № 10. – 8 с.
Пристрій підвищення точності обліку і контролю електроенергії вимірювальним комплексом [Текст] : пат. UA № 102949, МПК9 Н 01F 38/00; Н 01F 38/20; Н 01F 38/28; G01R 21/00; G01R 21/06; G01R 22/00 / Бутенко В. М., Білоусов О. Ф., Бриксін В. О., Головко О. В., Махота А. О., Приходько Ю. С., Терьошин В. М.; Скарговській А. О., Терьошин О. В.; заявник і власник Українська державна академія залізничного транспорту. - № а 2012 08136 від 03.07.2012; опубл. 27.08.2013, Бюл. № 16. – 6 с.
Математичне моделювання в розподілених інформаційно-керуючих системах залізничного транспорту [Текст] : монографія / С. В. Лістровий, С. В. Панченко, В. І. Мойсеєнко, В. М. Бутенко – Харків : ФОП Бровін О.В., 2017. – 220 с.
Development of method of definition maximum clique in a non-oriented graph [Text] / S. V. Listrovoy, V. M. Butenko, V. O. Bryksin, O. V. Golovko // EasternEuropean Journal of Enterprise Technologies. – 2017. – Vol. 5, №4 (89). – P. 12 – 17.
DOІ: 10.15587/1729-4061.2017.111056
Signal flow graph models and alternative gain formula for multiprobe microwave multimeter [Text] / Zaichenko O.B., Butenko V.M., Miroshnyk M.A. // Інформаційно-керуючі системи на залізничному транспорті. – 2016. – №12 (98). – С. 12–17.
Бутенко, В. М. Оптимізація моделей розподілених інформаційно-вимірювальних систем залізничного транспорту [Текст] / В. М. Бутенко // Прикладні науково-технічні дослідження: матеріали Міжнар. наук.-практ. конф. (5-7 квітня 2017). –
Івано-Франківськ : «Симфонія форте», 2017. – С. 88–89.
Скатов, А. В. Аппаратное ускорение решения задач выполнимости для построения тестов цифровых схем [Текст] / А. В. Скатов, А. В. Борисевич // Информатика, электроника, связь: сб. науч. тр. – Севастополь : Изд-во Сев. НТУ, 2008. – С. 9–15.
Kheterpal V., Rovner V. V., Hersan T. G., Motiani D., Takegawa Y., Strojwas A. J., and Pileggi L. Design Methodology for IC Manufacturability Based on Regular Logic Bricks. In Proceedings of the 42nd Conference on Design Automation, pages 353–358, 2005.
Taylor B., Pileggi L. Exact Combinatorial Optimization Methods for Physical Design of Regular Logic Bricks. In Proceedings of the 44th Conference on Design Automation, Р. 344–349, 2007.
Cheremisinova L., Novikov D. SAT-Based Approach to Verification of Logical Descriptions with Functional Indeterminacy // 8th International Workshop on Boolean Problems. Freiberg: September 18 – 19, 2008. – P. 59–66.
Дулькейт, В. И. Непрерывные аппроксимации решения задачи «выполнимость» применительно к криптографическому анализу асиммет-ричных шифров [Текст] / В. И. Дулькейт, Р. Т. Файзуллин , И. Г. Хныкин // Компьютерная оптика. – 2009. – №1, Т. 33. – С. 86–90.
Listrovoy, S.V. On Correlation of P And NP Classes [Text] / S.V. Listrovoy // I. J. Modern Education and Computer Science. – 2012. – № 3. – P. 21–27.
Спосіб вимірювання параметрів сигналів і трактів НВЧ [Текст] : пат. UA № 113161, Україна, МПК G01R 21/04; G01R 27/06 / Зайченко О. Б., Ключник І. І., Мірошник М. А., Бутенко В. М.; заявник і патентовласник Харківський національний ун-т радіоелектроніки; заявл. – № u 2016 08483 від 01.08.2016; опубл. 10.01.2017, Бюл. № 1. – 5 с.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2018 А. Б. БОЙНІК, В. М. БУТЕНКО, О. В. ГОЛОВКО, М. В. УШАКОВ
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
