Оптимальный метод решения специальных классов системы нелинейных уравнений второй степени
DOI:
https://doi.org/10.26577/JMMCS.2023.v118.i2.02Ключевые слова:
многочлен Жегалкина, линейные булевы функции, однородно-единичные матрицы, полиномиальная длина, дизъюнктивные нормальные формыАннотация
Предложен оптимальный метод решения специального класса системы нелинейных логических уравнений второго порядка с целью упрощения определений и сокращения времени решения систем логических уравнений. В исследуемом классе систем нелинейных логических уравнений логические формулы полностью или частично разбиваются на некоторые линейные комбинации. В результате логические формулы сводятся к умножению линейных многочленов, на основании чего получается система линейных логических уравнений, порядок величины которой решить проще, чем систему логических уравнений второго порядка, рассмотрены некоторые задачи минимизации специальных дизъюнктивных нормальных форм, полученных из полиномов Жегалкина второго порядка специального класса.
Библиографические ссылки
[1] A. Kabulov, I. Yarashov and A. Otakhonov, "Algorithmic Analysis of the System Based on the Functioning Table and Information Security,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795746
[2] A. Kabulov, I. Saymanov, I. Yarashov and A. Karimov, "Using Algorithmic Modeling to Control User Access Based on Functioning Table,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795850
[3] E. Navruzov and A. Kabulov, "Detection and analysis types of DDoS attack,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-7, doi: 10.1109/IEMTRONICS55184.2022.9795729.
[4] A. Kabulov, I. Saymanov, I. Yarashov and F. Muxammadiev, "Algorithmic method of security of the Internet of Things based on steganographic coding,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-5, doi: 10.1109/IEMTRONICS52119.2021.9422588.
[5] A. Kabulov, I. Normatov, E. Urunbaev and F. Muhammadiev, "Invariant Continuation of Discrete Multi-Valued Functions and Their Implementation,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-6, doi: 10.1109/IEMTRONICS52119.2021.9422486.
[6] A.Kabulov, I. Normatov, A.Seytov and A.Kudaybergenov, "Optimal Management of Water Resources in Large Main Canals with Cascade Pumping Stations,"2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Vancouver, BC, Canada, 2020, pp. 1-4, doi: 10.1109/IEMTRONICS51293.2020.9216402.
[7] Kabulov, A.V., Normatov, I.H. (2019). About problems of decoding and searching for the maximum upper zero of discrete monotone functions. Journal of Physics: Conference Series, 1260(10), 102006. doi:10.1088/1742-6596/1260/10/102006
[8] Kabulov, A.V., Normatov, I.H. Ashurov A.O. (2019). Computational methods of minimization of multiple functions. Journal of Physics: Conference Series, 1260(10), 10200. doi:10.1088/1742-6596/1260/10/102007
[9] Yablonskii S.V. Vvedenie v diskretnuyumatematiku: Ucheb. posobiedlyavuzov. -2e izd., pererab. idop. -M.:Nauka. Glavnayaredaksiyafiziko-matematicheskoy literature, -384 s.
[10] Djukova, E.V., Zhuravlev, Y.I. Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions. Comput. Math. and Math. Phys. 58, 2064–2077 (2018). https://doi.org/10.1134/S0965542518120102
[11] Leont’ev, V.K. Symmetric boolean polynomials. Comput. Math. and Math. Phys. 50, 1447–1458 (2010). https://doi.org/10.1134/S0965542510080142
[12] Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
[13] RamamohanPaturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing (STOC ’92). Association for Computing Machinery, New York, NY, USA, 468–474. https://doi.org/10.1145/129712.129758.
[14] Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satisfiability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19–152.
[15] Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P. 142–149.
[2] A. Kabulov, I. Saymanov, I. Yarashov and A. Karimov, "Using Algorithmic Modeling to Control User Access Based on Functioning Table,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795850
[3] E. Navruzov and A. Kabulov, "Detection and analysis types of DDoS attack,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-7, doi: 10.1109/IEMTRONICS55184.2022.9795729.
[4] A. Kabulov, I. Saymanov, I. Yarashov and F. Muxammadiev, "Algorithmic method of security of the Internet of Things based on steganographic coding,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-5, doi: 10.1109/IEMTRONICS52119.2021.9422588.
[5] A. Kabulov, I. Normatov, E. Urunbaev and F. Muhammadiev, "Invariant Continuation of Discrete Multi-Valued Functions and Their Implementation,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-6, doi: 10.1109/IEMTRONICS52119.2021.9422486.
[6] A.Kabulov, I. Normatov, A.Seytov and A.Kudaybergenov, "Optimal Management of Water Resources in Large Main Canals with Cascade Pumping Stations,"2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Vancouver, BC, Canada, 2020, pp. 1-4, doi: 10.1109/IEMTRONICS51293.2020.9216402.
[7] Kabulov, A.V., Normatov, I.H. (2019). About problems of decoding and searching for the maximum upper zero of discrete monotone functions. Journal of Physics: Conference Series, 1260(10), 102006. doi:10.1088/1742-6596/1260/10/102006
[8] Kabulov, A.V., Normatov, I.H. Ashurov A.O. (2019). Computational methods of minimization of multiple functions. Journal of Physics: Conference Series, 1260(10), 10200. doi:10.1088/1742-6596/1260/10/102007
[9] Yablonskii S.V. Vvedenie v diskretnuyumatematiku: Ucheb. posobiedlyavuzov. -2e izd., pererab. idop. -M.:Nauka. Glavnayaredaksiyafiziko-matematicheskoy literature, -384 s.
[10] Djukova, E.V., Zhuravlev, Y.I. Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions. Comput. Math. and Math. Phys. 58, 2064–2077 (2018). https://doi.org/10.1134/S0965542518120102
[11] Leont’ev, V.K. Symmetric boolean polynomials. Comput. Math. and Math. Phys. 50, 1447–1458 (2010). https://doi.org/10.1134/S0965542510080142
[12] Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
[13] RamamohanPaturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing (STOC ’92). Association for Computing Machinery, New York, NY, USA, 468–474. https://doi.org/10.1145/129712.129758.
[14] Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satisfiability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19–152.
[15] Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P. 142–149.
Загрузки
Как цитировать
Bayzhumanov, A. A. (2023). Оптимальный метод решения специальных классов системы нелинейных уравнений второй степени. Вестник КазНУ. Серия математика, механика, информатика, 118(2), 11–20. https://doi.org/10.26577/JMMCS.2023.v118.i2.02
Выпуск
Раздел
Математика
