Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах

Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах

Исследованы алгоритмы реализации пересечения, объединения и разности таблиц в табличных алгебрах: сначала рассматриваются наиболее естественные алгоритмы, а затем предлагаются их модификации, позволяющие уменьшить количество вычислений. Для всех предложенных алгоритмов найдены точные оценки сложно...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Доповіді НАН України
Datum:2016
1. Verfasser: Канарская, И.С.
Format: Artikel
Sprache:Russian
Veröffentlicht: Видавничий дім "Академперіодика" НАН України 2016
Schlagworte:
Інформатика
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/125911
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:Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах / И.С. Канарская // Доповіді Національної академії наук України. — 2016. — № 11. — С. 17-23. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-125911
record_format dspace
spelling Канарская, И.С.
2017-11-09T16:15:41Z
2017-11-09T16:15:41Z
2016
Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах / И.С. Канарская // Доповіді Національної академії наук України. — 2016. — № 11. — С. 17-23. — Бібліогр.: 10 назв. — рос.
1025-6415
DOI: doi.org/10.15407/dopovidi2016.11.017
https://nasplib.isofts.kiev.ua/handle/123456789/125911
004.655
Исследованы алгоритмы реализации пересечения, объединения и разности таблиц в табличных алгебрах: сначала рассматриваются наиболее естественные алгоритмы, а затем предлагаются их модификации, позволяющие уменьшить количество вычислений. Для всех предложенных алгоритмов найдены точные оценки сложности в худшем случае и в среднем, на основе которых были найдены наиболее быстрые алгоритмы для каждой операции. Проведены численные эксперименты, которые подтверждают теоретические оценки.
Досліджено алгоритми реалізації перетину, об’єднання та різниць таблиць в табличних алгебрах: спочатку розглядаються найбільш природні алгоритми, а потім пропонуютъся їх модифікації, які дозволяють зменшити кількість обчислень. Для 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.
ru
Видавничий дім "Академперіодика" НАН України
Доповіді НАН України
Інформатика
Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
Оцінки складності алгоритмів реалізації теоретико-множинних операцій в табличних алгебрах
Estimates of the complexity of algorithms of implementation of set-theoretic operations in table algebras
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
spellingShingle Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
Канарская, И.С.
Інформатика
title_short Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
title_full Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
title_fullStr Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
title_full_unstemmed Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
title_sort оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах
author Канарская, И.С.
author_facet Канарская, И.С.
topic Інформатика
topic_facet Інформатика
publishDate 2016
language Russian
container_title Доповіді НАН України
publisher Видавничий дім "Академперіодика" НАН України
format Article
title_alt Оцінки складності алгоритмів реалізації теоретико-множинних операцій в табличних алгебрах
Estimates of the complexity of algorithms of implementation of set-theoretic operations in table algebras
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.
issn 1025-6415
url https://nasplib.isofts.kiev.ua/handle/123456789/125911
citation_txt Оценки сложности алгоритмов реализации теоретико-множественных операций в табличных алгебрах / И.С. Канарская // Доповіді Національної академії наук України. — 2016. — № 11. — С. 17-23. — Бібліогр.: 10 назв. — рос.
work_keys_str_mv AT kanarskaâis ocenkisložnostialgoritmovrealizaciiteoretikomnožestvennyhoperaciivtabličnyhalgebrah
AT kanarskaâis ocínkiskladnostíalgoritmívrealízacííteoretikomnožinnihoperacíivtabličnihalgebrah
AT kanarskaâis estimatesofthecomplexityofalgorithmsofimplementationofsettheoreticoperationsintablealgebras
first_indexed 2025-12-07T18:19:48Z
last_indexed 2025-12-07T18:19:48Z
_version_ 1850874620234694656

Ähnliche Einträge