Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел
Анотація
У роботі наведена оптимізаційні перетворення алгоритму побудови мінімальної генеруючої множини розв’язків системи лінійних однорідних рівнянь в множині натуральних чисел, які покращують часові характеристики цього алгоритму з обгрунтуванням та ілюстрацією роботи на прикладах.
Посилання
Gordan P. Ueber die Auflösung linearen Gleidungen mit reallen Coefficienten. Mathematische Annalen, 1873, № 6, P. 23–28.
Hilbert D. Ueber die Theorie der algebraischen Formen. Mathematische Annalen, 1890, № 36, – P. 473–534.
Clausen M., Fortenbacher A. Efficient solution of linear diophantine equations. Journ. Symbolic Computation, 1989, v.8. № 1,2. – P. 201–216.
Contenjean E., Devie H. An efficient algorithm for solving systems of Diophantine equations, Inform. Comput, 1994, № 113, v. 1. – P. 143–172.
Domenjoud E. Outils pour la deduction automatique dans les theories associatives-commutatives. Thesis de Doctorat d'Universite: Universite de Nancy I, 1991.
Pottier L. Minimal solution of linear diophantine systems: bounds and algorithms. In Proceed. of the 4-th Intern. Conf. on Rewriting Techniques and Applications, Como, Italy, 1991, – P.162–173.
Kryvyi S. Calculation of the minimal set of Petri net’s invariants. J. Artificial intelligence. 2001, № 3. pp. 199-206.
Kryvyi S. Linear Diophantine constraints and their applications. Kyiv: Interservis. 2021. – 260 p.
Hermann M., Juban L., Kolaitis P. G. On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System. Springer Verlag, LNCS, 1999, № 1705. – P. 13–32.
Авторське право (c) 2023 Сергій Кривий, Олексій Чугаєнко (Автор)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
