Ольшевська В. А. Алгоритми i коди над силовськими 2-пiдгрупами симетричних груп S2n . – Квалiфiкацiйна наукова праця на правах рукопису.
Дисертацiя на здобуття наукового ступеня доктора фiлософiї в галузi знань 11 “Математика та статистика” за спецiальнiстю 113 “Прикладна математика” — Нацiональний унiверситет «Києво-Могилянська академiя», Київ, 2023.
Дисертацiйна робота присвячена побудовi i аналiзу алгоритмiв над силовськими 2-пiдгрупами симетричних груп та дослiдженню властивостей кодiв на цих групах.
Силовськi p-пiдгрупи є класичними об’єктами в теорiї груп, опис таких пiдгруп допомагає зрозумiти структуру самої групи. Зокрема, силовськi p-пiдгрупи симетричної групи дослiджувалися професором Л.Калужнiним та описанi в його працях за допомогою вiнцевих добуткiв циклiчних груп. Вiн запропонував зображати елементи таких груп у виглядi спецiальних таблиць, а саме – впорядкованих наборiв многочленiв певного вигляду. Ю.Дмитрук у своїй працi описав алгебраїчнi структури силовських 2-пiдгруп симетричних груп. Основою для створення означення та отриманих головних результатiв послугували саме статтi Л.Калужнiна.
Елементи силовських пiдгруп симетричних груп можна розглядати як портери автоморфiзмiв кореневих дерев, якi наведенi в роботi В.Некрашевича. Мiнiмальна система твiрних та графи Келлi на силовських p-пiдгрупах симетричних груп S_(p^n ) описанi А.Слупiк та В.Сущанським. Б.Павлик використав полiномiальне представлення елементiв групи 〖Syl〗_2 (S_(2^n ) ). Вiн описав дiї над 〖Syl〗_2 (S_(2^n ) ) на множинi мiнiмальних систем твiрних цiєї групи. Нижнiй центральний ряд силовських пiдгруп симетричних груп S_n було дослiджено А.Вiером.
Оскiльки такi структури досить зручнi та ефективнi в обчисленнях, природним продовженням є дослiдження алгоритмiчних властивостей та створення алгоритмiв для обрахункiв у силовських 2-пiдгрупах симетричних груп, елементи яких представленi саме деревами. Враховуючи характеристику порядку групи, особливої уваги заслуговує випадок, коли p = 2.
У дисертацiйнiй роботi дослiдження ґрунтується на властивостях бiнарних кореневих n-рiвневих дерев з мiтками. У тому числi розглянутi алгоритми основних групових операцiй для таких структур, алгоритми зв’язку мiж деревами та пiдстановками з силовських 2-пiдгруп симетричних груп. Окрiм того, для кожного алгоритму доведено коректнiсть та дослiджено часову складнiсть.
Використовуючи зв’язок пiдстановок з бiнарними кореневими деревами з мiтками, в дисертацiйнiй роботi побудовано алгоритм пошуку кiлькостi рухомих точок пiдстановок та вiдстанi Хеммiнга мiж елементами групи 〖Syl〗_2 (S_(2^n ) ). Логiчним продовженням роботи стало дослiдження кодiв над пiдстановками iз силовських 2-пiдгруп симетричних груп.
Починаючи iз 1970-х рокiв коди, побудованi на пiдстановках, та їх властивостi широко дослiджуються у рiзних сферах. I.Блейк у своїй роботi коротко розглянув та узагальнив вiдомi того часу результати про перестановочнi масиви. Дж.Денесом було показано, як використовувати перестановочне кодування для голосових операцiй та паралельних обчислень. П.Камероном було отримано низку результатiв про групи перестановок i перестановочнi коди.
Пiд кодом на групi пiдстановок розумiють множину елементiв iз групи S_n, де довiльна пара iз множини має вiдстань не меншу вiд заданої. При цьому можуть використовувати як рiзнi пiдгрупи симетричної групи, так i рiзнi метрики, наприклад, Хеммiнга, Улама, Левенштейна тощо. Перестановочнi коди використовуються як коди корекцiї помилок в каналах комунiкацiй з малою пропускною здатнiстю. Р.Бейлi у своїй роботi наводить ефективнi алгоритми декодування, коли перестановочнi коди є пiдмножинами з S_n.
У дисертацiї розглядаються властивостi кодiв, якi визначенi на пiдстановках iз
силовської 2-пiдгрупи 〖Syl〗_2 (S_(2^n ) ) симетричної групи S_(2^n ) з вiдстанню Хеммiнга d_H над ними. Дослiджено метричнi властивостi кодiв на пiдстановках. Також описано властивостi вiдстанi Хеммiнга на пiдстановках iз силовської 2 пiдгрупи 〖Syl〗_2 (S_(2^n ) ) симетричної групи S_(2^n ) та побудовано алгоритм пошуку вiдстанi Хеммiнга для пiдстановок групи.
Ключовi слова: група пiдстановок, силовськi 2-пiдгрупи симетричних груп, алгоритми, часова складнiсть, дерево, вiдстань Хеммiнга, коди на групах пiдстановок.
