Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
|
|
| Creator |
Канарская, И.С.
|
|
| Subject |
Інформатика
|
|
| Description |
Исследованы алгоритмы реализации пересечения, объединения и разности таблиц в табличных алгебрах: сначала рассматриваются наиболее естественные алгоритмы, а затем предлагаются их модификации, позволяющие уменьшить количество вычислений. Для всех предложенных алгоритмов найдены точные оценки сложности в худшем случае и в среднем, на основе которых были найдены наиболее быстрые алгоритмы для каждой операции. Проведены численные эксперименты, которые подтверждают теоретические оценки. Досліджено алгоритми реалізації перетину, об’єднання та різниць таблиць в табличних алгебрах: спочатку розглядаються найбільш природні алгоритми, а потім пропонуютъся їх модифікації, які дозволяють зменшити кількість обчислень. Для ycіx запропонованих алгоритмів знайдено точні оцінки складності в найгіршому випадку та у середньому, на основі яких було знайдено найбільш швидкі алгоритми для кожної операції. Проведені обчислювальні експерименти, які підтверджують теоретичні оцінки. The algorithms of implementation of the intersection, union, and difference of tables in the table algebras are investigated. A modification of the most common algorithms reducing the amount of computation is proposed. Based on the evaluated complexities in the worst case and on the average for the modified algorithms, the fastest algorithms for each operation are found. The experiments, which confirm the theoretical estimates, are executed. |
|
| Date |
2017-11-09T16:15:41Z
2017-11-09T16:15:41Z 2016 |
|
| Type |
Article
|
|
| Identifier |
Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах / И.С. Канарская // Доповіді Національної академії наук України. — 2016. — № 11. — С. 17-23. — Бібліогр.: 10 назв. — рос.
1025-6415 DOI: doi.org/10.15407/dopovidi2016.11.017 http://dspace.nbuv.gov.ua/handle/123456789/125911 004.655 |
|
| Language |
ru
|
|
| Relation |
Доповіді НАН України
|
|
| Publisher |
Видавничий дім "Академперіодика" НАН України
|
|