Registration Number
0420U100673, Candidate dissertation
Status
Кандидат фізико-математичних наук
Date
11-06-2020
popup.evolution
.
Title
Set-theoretic table operations and its complexity
Author
Kanarska Iryna Serhiivna,
popup.head Redko Volodymyr Nykyforovych
popup.opponent Kakhuta Nadiia Dmytrivna
popup.opponent Gupal Anatoliy M.
popup.rada
Taras Shevchenko National University of Kyiv
Description
Дисертацію присвячено дослідженню алгоритмів, що реалізують операції перетину, об’єднання та різниці у табличних алгебрах.
Для кожної теоретико-множинної операції розглянуто алгоритми, що їх реалізують на таблицях: спочатку викладено базові, найбільш природні алгоритми, що їх реалізують, далі розглядаються знайдені модифікації базових алгоритмів, які дозволяють суттєво зменшити кількість обчислень. Знайдено точну часову складність у найгіршому випадку та в середньому, причому обчислюється як загальна кількість обчислювальних дій, так і складність кожної з трьох маніпуляцій даних (додавання, видалення та порівняння) окремо. На основі знайдених теоретичних оцінок для кожної операції визначено найбільш швидкий алгоритм, що її реалізує. Розроблено програмну систему, яка обчислює фактичну кількість виконаних обчислень для кожного запропонованого алгоритму та порівнює їх зі знайденими теоретичними оцінками складності в середньому. Програмна система підтвердила точність знайдених теоретичних оцінок.
Досліджено алгоритми, що реалізують теоретико-множинні операції на мультитаблицях. Розглянуто базові алгоритми, знайдено модифікації цих алгоритмів, що можуть дозволити зменшити кількість обчислень; для усіх алгоритмів знайдено складність у найгіршому випадку. За допомогою обчислювальних експериментів було визначено найбільш швидкі алгоритми, що реалізують кожну теоретико-множинну операцію для мультитаблиць.
Для перетину, різниці, проекції, селекції, з’єднання, активного доповнення, ділення наведено необхідні та достатні умови, за яких ці операції зберігають активний домен.
Registration Date
2020-06-24
popup.nrat_date
2020-07-03 / 2026-06-30
