Задача про математичний сейф та її розв'язання (частина 2)

• Видавець: Інститут кібернетики ім. В.М. Глушкова НАН України
• Дата: 2021
• Автори: Кривий, С.Л., Гогерчак, Г.І.
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2021
• Назва видання: Кібернетика та комп’ютерні технології
• Теми: Методи оптимізації та екстремальні задачі
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/179350
• Цитувати: Задача про математичний сейф та її розв'язання (частина 2) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 16-28. — Бібліогр.: 3 назв. — укр.

Мета статті. Представлення методів розв’язання задачі про математичний сейф (в матричному та графовому виглядах) для різноманітних її варіацій, які пов’язані як з областю, над якою розглядається задача, так і зі структурою систем лінійних рівнянь над цими областями. Розглянуто розв’язання відповідних систем у скінченних простих полях, скінченних полях, примарних кільцях лишків та скінченних кільцях. Всі наведені алгоритми мають оцінки часової складності. Результати. Наведено приклади розв’язання задачі про математичний сейф, умови існування розв’язків в різних областях, над якими ця задача розглядається (скінченні прості поля, скінченні поля, примарні кільця, і асоціативно-комутативні кільця з одиницею). Вибір відповідної області над якою розглядається задача про математичний сейф, та відповідного алгоритму розв’язання залежить від кількості позицій засувів сейфа. Всі наведені алгоритми супроводжуються оцінками їх часової складності, які розглядалися в першій частині даної роботи..