Материал: Интеллектуальные информационные системы. труды международной научно-практической конференции. И73
ИНТЕЛЛЕКТУАЛЬНЫЕ
ИНФОРМАЦИОННЫЕ
СИСТЕМЫ
Труды Международной научно-практической конференции
В двух частях
Часть 1
Воронеж 2021
1
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования «Воронежский государственный технический университет»
ИНТЕЛЛЕКТУАЛЬНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ
Труды Международной научно-практической конференции
(г. Воронеж, 2-4 декабря 2020 г.)
В двух частях Часть 1
Воронеж 2021
1
УДК 681.518(06)
ББК 32.97:74.58-26.253я4 И73
Интеллектуальные информационные системы: труды Международной И73 научно-практической конференции: в 2 ч.; ФГБОУ ВО «Воронежский государственный технический университет». – Воронеж: Изд-во ВГТУ, 2021. Ч.1. – 152 с.
ISBN 978-5-7731-0939-6 (Ч.1) ISBN 978-5-7731-0938-9
Рассматриваются вопросы моделирования, оптимизации проектирования интеллектуальных информационных систем, использования информационных технологий в образовании, экономике, технике, биомедицинских системах, здравоохранении и экологии.
Материалы сборника соответствуют научному направлению «Интеллектуальные информационные системы» и перечню критических технологий Российской Федерации, утвержденному Президентом Российской Федерации.
Сборник будет полезен специалистам, аспирантам, студентам, деятельность которых связана с решением практических задач в области информатики, кибернетики, применением информационных систем и технологий в технике, образовании, экономике и медицине.
|
УДК 681.518(06) |
|
ББК 32.97:74.58-26.253я4 |
|
Редакционная коллегия: |
Я. Е. Львович |
– заслуженный деятель науки РФ, д-р техн. наук, проф. |
|
(Воронеж) – ответственный редактор; |
С. Л. Подвальный |
– заслуженный деятель науки РФ, |
|
– д-р техн. наук, проф. (Воронеж); |
О. В. Родионов |
– д-р техн. наук, проф. (Воронеж); |
В. А. Зернов |
– д-р техн. наук, проф. (Москва); |
И. Я. Львович |
– д-р техн. наук, проф. (Воронеж); |
М. В. Фролов |
– д-р мед. наук, проф. (Воронеж); |
Б. Я. Советов |
– заслуженный деятель науки и техники РФ, д-р техн. |
|
наук, проф. (Санкт-Петербург); |
Ю. С. Сахаров |
– д-р техн. наук, проф. (Москва); |
Е. Н. Коровин |
– д-р техн. наук, проф. (Воронеж); |
Б. Н. Тишуков |
– канд. техн. наук, ответственный секретарь (Воронеж) |
Рецензенты: кафедра вычислительной техники и информационных систем
Воронежского государственного лесотехнического университета им. Г. Ф. Морозова (зав. кафедрой д-р техн. наук, проф. В. К. Зольников); В. М. Курейчик, д-р техн. наук, проф., ФГАОУ ВО «Южный
федеральный университет»
Печатается по решению редакционно-издательского совета Воронежского государственного технического университета
ISBN 978-5-7731-0939-6 (Ч.1) |
© ФГБОУ ВО «Воронежский государственный |
ISBN 978-5-7731-0938-9 |
технический университет», 2021 |
2
ВВЕДЕНИЕ
Всовременных условиях развитие информационных технологий и систем все в большей степени определяется их интеллектуализацией. Интеллектуальные информационные технологии — одна из наиболее перспективных и быстро развивающихся научных и прикладных областей информатики, в рамках которой разрабатываются модели и методы решения слабо формализуемых задач.
Втрудах представлены материалы, затрагивающие вопросы повышения эффективности производственных, экономических, образовательных, биомедицинских систем на основе использования современных технологий, интеллектуальной поддержки принятия решений, формализации экспертной информации, создания учебно-исследовательских систем, теории моделирования и оптимизации.
Сборник полезен специалистам, аспирантам, студентам, деятельность которых связана с решением практических задач в области информатики, кибернетики, применением информационных систем и технологий в технике, образовании, экономике и медицине.
3
УДК 004.67
Ю. Н. Артамонов, К. А. Смирнова
НОВЫЙ АЛГОРИТМ ВЫБОРА НА ОСНОВЕ ПОРОЖДАЮЩИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Алгоритм выбора является фундаментальной задачей теоретической информатики и находит широкие применения при обработке численных данных: нахождение элементов заданного ранга в выборке, алгоритмы сортировки, нахождение ближайших соседей в числовой последовательности, задача нахождения выпуклых оболочек множества. Формулировка данной задачи восходит к Ч. Э. Р. Хоару и заключается в следующем [1]: дано
множество X ={xj}, X = n, отношение порядка на X и целое число 1≤ k ≤ n.
Требуется найти k -й наименьший элемент, т.е. элемент x X , для которого существует по крайней мере k −1 элементов j =1, ,(k −1): xj x и не менее k
элементов j =1, ,k : xj x xj = x.
Введем следующее обозначение: x = Q(X,k). В частных случаях
получаем: |
Q(X,1) |
n |
|
|
= min(X),Q(X,n) = max(X),Q(X, |
2 |
) = median(X). Обычно для |
||
|
|
|
|
|
удобства анализа рассматривают X как множество (без повторения элементов). Первая реализация алгоритма, названного в статье [1] - FIND, предложена самим Ч. Э. Р. Хоаром, как модификация его алгоритма сортировки quicksort. Алгоритм FIND также часто называют quickselect. Для данного алгоритма
доказана следующая оценка количества сравнений [2]:
C(n,k) = 2 ((n+1) Hn −(n−k +3) Hn−k+1 −(k +2) Hk +n+3),
k
где Hk = ∑i=1 1i - частные гармонические суммы.
Для граничных случаев имеем:
C(n,1) = C(n,n) = 2n+o(n),
C(n,median) = 3.39n+o(n).
Как отмечено в статье [3], на практике алгоритм FIND популярен, поскольку многие другие алгоритмы гораздо медленнее в среднем.
В цикле статей [3, 4, 5] рассматривается алгоритм SELECT, который обеспечивает на текущий момент лучший в среднем результат:
C(n,k) = n+min(n−k,k)+o(n).
При этом в статье [3] проведен сравнительный анализ SELECT и FIND. По сравнению с FIND, SELECT требует лишь небольшого дополнительного стекового пространства для рекурсии. Было показано, что SELECT превосходит довольно сложные реализации FIND.
4