Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
Исследованы алгоритмы реализации пересечения, объединения и разности таблиц в табличных
 алгебрах: сначала рассматриваются наиболее естественные алгоритмы, а затем предлагаются их модификации, позволяющие уменьшить количество вычислений. Для всех предложенных
 алгоритмов найдены точн...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2016 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/125911 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах / И.С. Канарская // Доповіді Національної академії наук України. — 2016. — № 11. — С. 17-23. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | Исследованы алгоритмы реализации пересечения, объединения и разности таблиц в табличных
алгебрах: сначала рассматриваются наиболее естественные алгоритмы, а затем предлагаются их модификации, позволяющие уменьшить количество вычислений. Для всех предложенных
алгоритмов найдены точные оценки сложности в худшем случае и в среднем, на основе которых
были найдены наиболее быстрые алгоритмы для каждой операции. Проведены численные эксперименты, которые подтверждают теоретические оценки.
Досліджено алгоритми реалізації перетину, об’єднання та різниць таблиць в табличних алгебрах: спочатку
розглядаються найбільш природні алгоритми, а потім пропонуютъся їх модифікації, які дозволяють зменшити кількість обчислень. Для 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.
|
|---|---|
| ISSN: | 1025-6415 |