Search academic texts

Information × Registration Number 0420U100673, Candidate dissertation Status Кандидат фізико-математичних наук Date 11-06-2020 popup.evolution o 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. Description Дисертацію присвячено дослідженню алгоритмів, що реалізують операції перетину, об’єднання та різниці у табличних алгебрах. Для кожної теоретико-множинної операції розглянуто алгоритми, що їх реалізують на таблицях: спочатку викладено базові, найбільш природні алгоритми, що їх реалізують, далі розглядаються знайдені модифікації базових алгоритмів, які дозволяють суттєво зменшити кількість обчислень. Знайдено точну часову складність у найгіршому випадку та в середньому, причому обчислюється як загальна кількість обчислювальних дій, так і складність кожної з трьох маніпуляцій даних (додавання, видалення та порівняння) окремо. На основі знайдених теоретичних оцінок для кожної операції визначено найбільш швидкий алгоритм, що її реалізує. Розроблено програмну систему, яка обчислює фактичну кількість виконаних обчислень для кожного запропонованого алгоритму та порівнює їх зі знайденими теоретичними оцінками складності в середньому. Програмна система підтвердила точність знайдених теоретичних оцінок. Досліджено алгоритми, що реалізують теоретико-множинні операції на мультитаблицях. Розглянуто базові алгоритми, знайдено модифікації цих алгоритмів, що можуть дозволити зменшити кількість обчислень; для усіх алгоритмів знайдено складність у найгіршому випадку. За допомогою обчислювальних експериментів було визначено найбільш швидкі алгоритми, що реалізують кожну теоретико-множинну операцію для мультитаблиць. Для перетину, різниці, проекції, селекції, з’єднання, активного доповнення, ділення наведено необхідні та достатні умови, за яких ці операції зберігають активний домен. Registration Date 2020-06-11 popup.nrat_date 2020-07-03 Close