Канарська І. С. Теоретико-множинні табличні операції та їх складність

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