Реєстраційний номер
0420U100673, Кандидатська дисертація
На здобуття
Кандидат фізико-математичних наук
Дата захисту
11-06-2020
Статус
Захищена
Назва роботи
Теоретико-множинні табличні операції та їх складність
Здобувач
Канарська Ірина Сергіївна,
Керівник Редько Володимир Никифорович
Опонент Кахута Надія Дмитрівна
Опонент Гупал Анатолій Михайлович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Київський національний університет імені Тараса Шевченка
Опис
Дисертацію присвячено дослідженню алгоритмів, що реалізують операції перетину, об’єднання та різниці у табличних алгебрах.
Для кожної теоретико-множинної операції розглянуто алгоритми, що їх реалізують на таблицях: спочатку викладено базові, найбільш природні алгоритми, що їх реалізують, далі розглядаються знайдені модифікації базових алгоритмів, які дозволяють суттєво зменшити кількість обчислень. Знайдено точну часову складність у найгіршому випадку та в середньому, причому обчислюється як загальна кількість обчислювальних дій, так і складність кожної з трьох маніпуляцій даних (додавання, видалення та порівняння) окремо. На основі знайдених теоретичних оцінок для кожної операції визначено найбільш швидкий алгоритм, що її реалізує. Розроблено програмну систему, яка обчислює фактичну кількість виконаних обчислень для кожного запропонованого алгоритму та порівнює їх зі знайденими теоретичними оцінками складності в середньому. Програмна система підтвердила точність знайдених теоретичних оцінок.
Досліджено алгоритми, що реалізують теоретико-множинні операції на мультитаблицях. Розглянуто базові алгоритми, знайдено модифікації цих алгоритмів, що можуть дозволити зменшити кількість обчислень; для усіх алгоритмів знайдено складність у найгіршому випадку. За допомогою обчислювальних експериментів було визначено найбільш швидкі алгоритми, що реалізують кожну теоретико-множинну операцію для мультитаблиць.
Для перетину, різниці, проекції, селекції, з’єднання, активного доповнення, ділення наведено необхідні та достатні умови, за яких ці операції зберігають активний домен.
Дата реєстрації
2020-06-24
Додано/оновлено в НРАТ
2020-07-03 / 2026-06-30
