DOI
10.34229/KCA2522-9664.25.6.2
УДК 61.681.3
С.Л. КРИВИЙ
Київський національний університет імені Тараса Шевченка, Київ, Україна,
krivoi@i.com.ua
О.В. ЧУГАЄНКО
ТОВ «Самсунг РнД інститут Україна», Київ, Україна, firestream_13@yahoo.com
С.М. КРАСНИТСЬКИЙ
Київський національний університет технологій та дизайну, Київ, Україна,
krasnits.sm@ukr.net
АЛГОРИТМИ РОЗВ’ЯЗАННЯ ЛІНІЙНИХ
ОБМЕЖЕНЬ У МНОЖИНІ {0, 1}
Анотація. Представлено три алгоритми розв’язання систем лінійних обмежень із цілими коефіцієнтами
у множині {0, 1}. Перший алгоритм має експоненціальну оцінку часової складності, але розпаралелюється. Другий алгоритм знаходить розв’язки шляхом зведення розв’язання системи обмежень до розв’язання одного лінійного рівняння. Третій алгоритм є паралельною комбінацією першого та другого алгоритмів. Наведено екпериментальні результати реалізованих алгоритмів.
Ключові слова: лінійні обмеження, 01-розв’язок, алгоритми.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 1. Bockmayr A., Weispfenning V. Solving numerical constraints. In: Handbook of Automated Reasoning. Robinson J.A., Voronkov A. (Eds.). Vol. 1. Elsevier Science Publishers B.V., 2001. P. 753–842. https://doi.org/10.1016/B978-044450813-3/50014-X.
- 2. Kryvyi S.L. Algorithms of solution of systems of linear Diophantine constraints over the set {0, 1}. Cybernetics and Systems Analysis. 2003. Vol. 39, N 5. P. 676–685. https://doi.org/10.1023/B:CASA.0000012088.53339.a7.
- 3. Кривий С.Л. Лінійні Діофантові обмеження та їх застосування. Київ: Iнтерсервіс, 2021. 257 с.
- 4. Clausen M., Fortenbacher A. Efficient solution of linear diophantine equations. Journal of Symbolic Computation. 1989. Vol. 8, Iss. 1–2. P. 201–216. https://doi.org/10.1016/S0747-7171(89)80025-2.
- 5. Cohen D., Jeavons P. The complexity of constraint languages. In: Handbook of Constraint Programming. Rossi F., van Beek P., Walsh T. (Eds.). Elsevier, 2006. P. 245–280. https://doi.org/10.1016/S1574-6526(06)80012-X
- 6. Contenjean E., Devie H. An efficient algorithm for solving systems of Diophantine equations. Information and Computation. 1994. Vol. 113, Iss. 1. P. 143–172. https://doi.org/10.1006/inco.1994.1067.
- 7. Contejean E., Ajili F. Avoiding slack variables in the solving of linear Diophantine equations and inequations. Theoretical Computer Science. 1997. Vol. 173, Iss. 1. P. 183–208. https://doi.org/10.1016/S0304-3975(96)00195-8
- 8. Papadimitriou Ch.H. Zlozonosc obliczeniowa. Warszawa: Wydawnictwo Naukowo-Techniczne, 2002. 539 s.
