113 Прикладна математика
Permanent URI for this collection
Освітньо-професійна програма / Освітньо-наукова програма: Прикладна математика
Browse
Browsing 113 Прикладна математика by Author "Олійник, Богдана"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Алгоритми і коди над силовськими 2-підгрупами симетричних груп S2n : дисертація на здобуття наукового ступеня доктора філософії(2023) Ольшевська, Віта; Олійник, БогданаДисертація на здобуття наукового ступеня доктора філософії в галузі знань 11 "Математика та статистика" за спеціальністю 113 "Прикладна математика" — Національний університет "Києво-Могилянська академія", Київ, 2023. Дисертаційна робота присвячена побудові і аналізу алгоритмів над силовськими 2-підгрупами симетричних груп та дослідженню властивостей кодів на цих групах. Силовські p-підгрупи є класичними об’єктами в теорії груп, опис таких підгруп допомагає зрозуміти структуру самої групи. Зокрема, словські р-підгрупи симетричної групи досліджувалися професором Л. Калужніним та описані в його працях за допомогою вінцевих добутків циклічних груп. Він запропонував зображати елементи таких груп у вигляді спеціальних таблиць, а саме - впорядкованих наборів многочленів певного вигляду. Ю. Дмитрук у своїй праці описав алгебраїчні структури силовських 2-підгруп симетричних груп. Основою для створення означення та отриманих головних результатів послугували саме статті Л. Калужніна. Елементи силовських підгруп симетричних груп можна розглядати як портери автоморфізмів кореневих дерев, які наведені в роботі В. Некрашевича. Мінімальна система твірних та графи Келлі на силовських р-підгрупах симетричних груп S2n описані А. Слупік та В. Сущанським. Нехай маємо ціле та додатнє число п > 1. Силовську 2-підгрупу симетричної групи S2n позначимо S2n as Syl2(S2n). Група Syl2(S2n) ізоморфна кінцевому добутуку р-циклічних груп, що мають порядок 2, а саме: Sylr2 (S2n ) = Z 2 I . . . I Z2 n разів. Б. Павлик використав поліноміальне представлення елементів групи Syl2(S2n). Він описав дії над Syl2(S2n) на множині мінімальних систем твірних цієї групи. Нижній центральний ряд силовських підгруп симетричних груп Sn було досліджено А. Віером. Оскільки такі структури досить зручні та ефективні в обчисленнях, природним продовженням є дослідження алгоритмічних властивостей та створення алгоритмів для обрахунків у силовських 2-підгрупах симетричних груп, елементи яких представлені саме деревами. Враховуючи характеристику порядку групи, особливої уваги заслуговує випадок, коли р = 2. У дисертаційній роботі дослідження ґрунтується на властивостях бінарних кореневих p-рівневих дерев з мітками. У тому числі розглянуті алгоритми основних групових операцій для таких структур, алгоритми зв’язку між деревами та підстановками з силовських 2-підгруп симетричних груп. Окрім того, для кожного алгоритму доведено коректність та досліджено часову складність. Використовуючи зв’язок підстановок з бінарними кореневими деревами з мітками, в дисертаційній роботі побудовано алгоритм пошуку кількості рухомих точок підстановок та відстані Хеммінга між елементами групи Syl2(S2n). Логічним продовженням роботи стало дослідження кодів над підстановками із силовських 2-підгруп симетричних груп. Починаючи із 1970-х років коди, побудовані на підстановках, та їх властивості широко досліджуються у різних сферах. Так І. Блейк у своїй роботі коротко розглянув та узагальнив відомі того часу результати про перестановочні масиви. Метою статті Дж. Денеса було показати, як використовувати перестановочне кодування для голосових операцій та паралельних обчислень. П. Камероном було отримано низку результатів про групи перестановок і перестановочні коди та зроблено огляд про відомі результати. Описано декілька відкритих проблем. Під кодом на групі підстановок розуміють множину елементів із групи Sn, де довільна пара із множини має відстань не меншу від заданої. При цьому можуть використовувати як різні підгрупи симетричної групи, так і різні метрики, наприклад, Хеммінга, Улама, Левенштейна тощо. Перестановочні коди використовуються як коди корекції помилок в каналах комунікацій з малою пропускною здатністю. Одним з напрямків є дослідження кодів на алгебраїчних структурах. Р. Бейлі у своїй роботі наводить ефективні алгоритми декодування, коли перестановочні коди є підмножинами з Sn. У дисертації розглядаються властивості кодів, які визначені на підстановках із силовської 2-підгрупи Syl2(S2n). симетричної групи Syl2 з відстанню Хеммінга dH над ними. Для їх дослідження також використано зв’язок групи Syl2(S2n) із групою бінарних кореневих n-рівневих дерев з мітками. Досліджено метричні властивості кодів на підстановках. Також описано властивості відстані Хеммінга на підстановках із силовської 2-підгрупи Syl2(S2n) симетричної групи S2n та побудовано алгоритм пошуку відстані Хеммінга для підстановок групи, що має складність 0 (2 n). Окрім того, досліджено метричні властивості кодів на підстановках із Syl2(S2n) та знайдено розміри і кількість кодів для максимальної та мінімальної ненульової відстані Хеммінга. Таким чином, у дисертаційній роботі містяться наступні нові наукові результати: 1. Запропоновано алгоритми перетворення підстановки із силовської 2-підгрупи симетричної групи у кореневе бінарне n-рівневе дерево з мітками та обернений перехід від дерева з LT2,n до підстановки із Syl2(S2n). Доведено їхню коректність і обчислено часову складність. 2. Запропоновано алгоритм множення підстановок силовської 2-підгрупи симетричної групи, що використовує зображення груп бінарними деревами з мітками, та обчислено його часову складність. Описано алгоритм знаходження оберненого елемента. Доведено його коректність та обчислено часову складність. 3. Описано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп симетричних груп з часовою складністю 0 (2n). Пораховано, що в середньому алгоритм виконує т кроків для групи Syl2(S2n). 4. Запропоновано формулу, за якою можна визначити кількість підстановок із Syl2(S2n), що мають задану, зокрема максимальну, кількість рухомих точок. 5. Наведено алгоритм пошуку відстані Хеммінга для підстановок із силовських 2-підгруп симетричних груп з часовою складністю O(2n). Оцінено, що в середньому алгоритм виконує n кроків для групи Syl2(S2n). 6. Запропоновано рекурсивну формулу для обчислення кількості підстановочних кодів CH over Syl2(S2n) з максимальною відстанню Хеммінга та обчислено кількість таких кодів. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії кодування, теорії груп підстановок. Дисертація може бути використана для читання спеціалізованих курсів з теорії алгоритмів та теорії кодування для студентів математичних спеціальностей.Item Метрична розмірність метричних та ультраметричних просторів з умовами скінченності : дисертація на здобуття наукового ступеня доктора філософії(2021) Пономарчук, Богдан; Олійник, БогданаУ дисертаційній роботі розглянуто задачу пошуку метричної розмірності для скінченних ультраметричних просторів, а також описано метричну розмірність для деяких конструкцій метричних просторів з умовами скінченності. Визначення метричної розмірності метричного простору було запропоноване Блюменталем в 1953 році. 20 років потому Харарі та Мелтер у своїй роботі застосували це визначення до метричних просторів визначених графами. Після чого, концепт метричної розмірності знайшов широке коло застосувань: комбінаторний аналіз, робототехніка, біологія, хімія та інші. У 2013 році С. Бау та Ф. Беардон продовжили ідеї Блюменталя щодо дослідження метричної розмірності метричних просторів. Вони вивчали метричну розмірність підпросторів Евклідового простору. Пізніше, М. Хейдарпур та С. Магсауді підрахували метричну розмірність геометричних просторів. Відомо що, пошук метричної розмірності метричного простору є NP-складною задачею. Є декілька шляхів дослідження метричної розмірності. Один з них — дослідження метричної розмірності для певних родин метричних просторів чи графів. Другим підходом є дослідження метричної розмірності конструкцій метричних просторів, що побудовані на основі метричних просторів, метрична розмірність яких вже відома. У дисертаційній роботі дослідження здійснюються в обох описаних вище напрямках. А саме повністю охарактеризовано метричну розмірність скінченних ультраметричних або неархімедових просторів. Показано, що для довільного скінченного ультраметричного простору його метрична розмірність може бути знайдена за поліноміальний час. Наведено поліноміальний алгоритм знаходження метричної розмірності для довільного ультраметричного простору. Для побудови цього алгоритму було використано ізометричне зображення ультраметричних просторів деревами. Показано, що складність побудови такого зображення дорівнює O(n5), де n — кількіств точок ультраметричного простору. Також доведено, що метрична розмірність ультраметричного простору, який визначається на кореневому дереві, або дорівнює метричній розмірності цього дерева як графа, або на одиницю менше. В роботі також повністю описано ультраметричні простори метрична розмірність яких дорівнює одиниці. Окрім ультраметричних просторів в дисертаційній роботі розглянуто метричну розмірність різних конструкцій метричних просторів. Зокрема показано, що для довільної шкали трансформації метрична розмірність метричного простору дорівнює метричній розмірності його трансформації. Наведено формулу для підрахунку метричної розмірності вінцевого добутку скінченного метричного простору і рівномірно дискретного метричного простору. У випадку коли метрична розмірність рівномірно дискретно метричного простору дорівнює нескінченності, метрична розмірність конструкції також дорівнює нескінченності. Крім того, для прямої суми метричних просторів скінченого діаметра показано, що її метрична розмірність дорівнюватиме сумі метричних розмірностей цих просторів. Показано, що для довільних метричних просторів скінченного діаметра метрична розмірність їх прямої суми дорівнює двом тоді і тільки тоді коли метрична розмірність кожного з просторів дорівнює 1. В останньому розділі також розглянуто метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, та dTO. Показано, що хоча ці метрики є топологічно еквівалентними, відповідні метричні простори мають різну метричну розмірність. Таким чином, в дисертаційній роботі містяться наступні нові наукові результати: 1. Наведено алгоритм зображення ультраметричного простору кореневим деревом, часова складність якого O(n5). 2. Для довільного скінченного ультраметричного простору показано, що існує поліноміальний алгоритм обчислення його метричної розмірності. 3. Охарактеризовано всі ультраметричні простори розмірність яких дорівнює одиниці. 4. Отримано формулу для обчислення метричної розмірності вінцевого добутку скінченного метричного та рівномірно дискретного метричного просторів. 5. Охарактеризовано метричну розмірність прямої суми метричних просторів скінченного діаметра. 6. Описано метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, d2 та dTO. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії графів, робототехніці, теорії метричних просторів. Дисертація може бути використана для читання спецкурсів з теорії графів для студентів математичних спеціальностей.