Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах
Исследованы алгоритмы, реализующие пересечение, объединение и разность в табличных алгебрах. Предложены модификации наиболее распространенных алгоритмов, позволяющие сократить количество вычислений. На основе оценки сложности в худшем случае и в среднем для модифицированных алгоритмов найден наиболе...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2017 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/144680 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах / В.Н. Редько, Д.Б. Буй, И.С. Канарская, А.С. Сенченко // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 3-15. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862743917328334848 |
|---|---|
| author | Редько, В.Н. Буй, Д.Б. Канарская, И.С. Сенченко, А.С. |
| author_facet | Редько, В.Н. Буй, Д.Б. Канарская, И.С. Сенченко, А.С. |
| citation_txt | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах / В.Н. Редько, Д.Б. Буй, И.С. Канарская, А.С. Сенченко // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 3-15. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Исследованы алгоритмы, реализующие пересечение, объединение и разность в табличных алгебрах. Предложены модификации наиболее распространенных алгоритмов, позволяющие сократить количество вычислений. На основе оценки сложности в худшем случае и в среднем для модифицированных алгоритмов найден наиболее быстрый алгоритм для каждой операции. Разработана программная система, экспериментально подтверждающая теоретические оценки.
Досліджено алгоритми, що реалізують операції перетину, об’єднання і різниці в табличних алгебрах. Запропоновано модифікації найбільш поширених алгоритмів, які дозволяють скоротити кількість обчислень. На основі оцінки складності в гіршому випадку і в середньому для модифікованих алгоритмів знайдено найбільш швидкий алгоритм для кожної операції. Розроблено програмну систему, що експериментально підтверджує теоретичні оцінки.
The algorithms implementing intersection, union, and difference in table algebras are investigated. Modifications of the most common algorithms reducing the amount of computation are proposed. Based on the evaluated complexities in the worst case and in the average for the modified algorithms, the fastest algorithm for each operation is found. The program experimentally confirming the theoretical estimates is developed.
|
| first_indexed | 2025-12-07T20:32:49Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-144680 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T20:32:49Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Редько, В.Н. Буй, Д.Б. Канарская, И.С. Сенченко, А.С. 2019-01-01T20:09:11Z 2019-01-01T20:09:11Z 2017 Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах / В.Н. Редько, Д.Б. Буй, И.С. Канарская, А.С. Сенченко // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 3-15. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144680 004.655 Исследованы алгоритмы, реализующие пересечение, объединение и разность в табличных алгебрах. Предложены модификации наиболее распространенных алгоритмов, позволяющие сократить количество вычислений. На основе оценки сложности в худшем случае и в среднем для модифицированных алгоритмов найден наиболее быстрый алгоритм для каждой операции. Разработана программная система, экспериментально подтверждающая теоретические оценки. Досліджено алгоритми, що реалізують операції перетину, об’єднання і різниці в табличних алгебрах. Запропоновано модифікації найбільш поширених алгоритмів, які дозволяють скоротити кількість обчислень. На основі оцінки складності в гіршому випадку і в середньому для модифікованих алгоритмів знайдено найбільш швидкий алгоритм для кожної операції. Розроблено програмну систему, що експериментально підтверджує теоретичні оцінки. The algorithms implementing intersection, union, and difference in table algebras are investigated. Modifications of the most common algorithms reducing the amount of computation are proposed. Based on the evaluated complexities in the worst case and in the average for the modified algorithms, the fastest algorithm for each operation is found. The program experimentally confirming the theoretical estimates is developed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах Точні оцінки часової складності реалізації алгоритмів теоретико-множинних операцій в табличних алгебрах Precise estimates of the time complexity of implementing the algorithms of set-theoretic operations in table algebra Article published earlier |
| spellingShingle | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах Редько, В.Н. Буй, Д.Б. Канарская, И.С. Сенченко, А.С. Кібернетика |
| title | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| title_alt | Точні оцінки часової складності реалізації алгоритмів теоретико-множинних операцій в табличних алгебрах Precise estimates of the time complexity of implementing the algorithms of set-theoretic operations in table algebra |
| title_full | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| title_fullStr | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| title_full_unstemmed | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| title_short | Точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| title_sort | точные оценки временной сложности реализации алгоритмов теоретико-множественных операций в табличных алгебрах |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144680 |
| work_keys_str_mv | AT redʹkovn točnyeocenkivremennoisložnostirealizaciialgoritmovteoretikomnožestvennyhoperaciivtabličnyhalgebrah AT buidb točnyeocenkivremennoisložnostirealizaciialgoritmovteoretikomnožestvennyhoperaciivtabličnyhalgebrah AT kanarskaâis točnyeocenkivremennoisložnostirealizaciialgoritmovteoretikomnožestvennyhoperaciivtabličnyhalgebrah AT senčenkoas točnyeocenkivremennoisložnostirealizaciialgoritmovteoretikomnožestvennyhoperaciivtabličnyhalgebrah AT redʹkovn točníocínkičasovoískladnostírealízacííalgoritmívteoretikomnožinnihoperacíivtabličnihalgebrah AT buidb točníocínkičasovoískladnostírealízacííalgoritmívteoretikomnožinnihoperacíivtabličnihalgebrah AT kanarskaâis točníocínkičasovoískladnostírealízacííalgoritmívteoretikomnožinnihoperacíivtabličnihalgebrah AT senčenkoas točníocínkičasovoískladnostírealízacííalgoritmívteoretikomnožinnihoperacíivtabličnihalgebrah AT redʹkovn preciseestimatesofthetimecomplexityofimplementingthealgorithmsofsettheoreticoperationsintablealgebra AT buidb preciseestimatesofthetimecomplexityofimplementingthealgorithmsofsettheoreticoperationsintablealgebra AT kanarskaâis preciseestimatesofthetimecomplexityofimplementingthealgorithmsofsettheoreticoperationsintablealgebra AT senčenkoas preciseestimatesofthetimecomplexityofimplementingthealgorithmsofsettheoreticoperationsintablealgebra |