Разработка математического, алгоритмического и программного обеспечения комбинаторной генерации для решения задач хранения и обработки больших объёмов данных

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-71-10052

НазваниеРазработка математического, алгоритмического и программного обеспечения комбинаторной генерации для решения задач хранения и обработки больших объёмов данных

Руководитель Кручинин Дмитрий Владимирович, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Томский государственный университет систем управления и радиоэлектроники" , Томская обл

Конкурс №71 - Конкурс 2022 года «Проведение исследований научными группами под руководством молодых ученых» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-114 - Дискретная математика и математическая кибернетика

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

Код ГРНТИ27.41.41

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Интенсивное развитие информационных технологий на фоне формирования цифровой экономики приводит к экспоненциальному росту объёмов различного рода данных, которые также носят распределённый характер. В связи с этим, возникает проблема эффективной организации процесса хранения, передачи и обработки большого объёма данных. Для оперативной работы с такими данными требуется инструментарий, который позволит структурировать и систематизировать информацию о различных объектах. Именно поэтому разработка соответствующих методов и алгоритмов для обработки таких данных становится важной и актуальной научной задачей. Предлагаемый проект посвящён решению указанной научной проблемы в части разработки математического, алгоритмического и программного обеспечения в рамках формирования методологии, направленной на улучшение способов хранения, поиска и генерации элементов множеств информационных объектов. Поскольку многим информационным объектам, в том числе характеризующимся большим объёмом данных, свойственна иерархическая или рекурсивная природа их описания, то становится возможным альтернативный способ представления множества таких информационных объектов в форме комбинаторного множества. В таком случае для заданного комбинаторного множества можно определить специализированные алгоритмы комбинаторной генерации, которые позволят эффективно организовать процесс хранения, поиска и генерации элементов данного множества. Анализ мировой научной литературы показывает, что комбинаторная генерация является актуальным направлением исследований в области дискретной математики и информатики. С каждым годом отмечается увеличение количества научных работ, посвящённых разработке новых и модернизации существующих алгоритмов комбинаторной генерации, которые находят своё применение при решении научных задач из самых разных областей науки. Предлагаемый проект направлен на развитие методологии построения и исследования алгоритмов комбинаторной генерации. В рамках проекта для множеств информационных объектов, представленных комбинаторными множествами, предлагается использовать биективное отображение на рекурсивные композиции деревьев И/ИЛИ. В таком случае применение рекурсивных композиций деревьев И/ИЛИ позволяет построить все классы алгоритмов комбинаторной генерации. В качестве апробации предлагается применить разработанную методологию по построению алгоритмов комбинаторной генерации для тестового набора комбинаторных множеств: получение функций мощности; построение алгоритмов ранжирования, генерации по рангу и последовательной генерации; определение вычислительной сложности алгоритмов; программная реализация полученных алгоритмов и проведение вычислительных экспериментов. В качестве базы знаний тестового набора комбинаторных множеств предлагается использовать онлайн-энциклопедию целочисленных последовательностей (www.oeis.org), в которой в настоящее время насчитывается более 300 тыс. записей, описывающих целочисленные последовательности, обладающих различного рода комбинаторными интерпретациями. Например, будет рассмотрено применение разработанных методов для построения комбинаторных алгоритмов для различного вида решётчатых путей (пути Деланнуа, пути Моцкина, пути Нараяны и др.). Разработанные в ходе выполнения исследований проекта алгоритмы комбинаторной генерации будут сопоставлены с существующими алгоритмами. Для определения эффективности разработанных алгоритмов комбинаторной генерации будут применены методы оценки вычислительной сложности алгоритмов. В качестве программной реализации разработанных алгоритмов предлагается применить возможности языков программирования (например, язык программирования Python) и математических пакетов (например, система компьютерной алгебры Maxima). Кроме того, в качестве апробации полученной методологии предлагается рассмотреть практическую задачу хранения и поиска среди больших объёмов данных на примере задачи хранения накопленной цифровой информации о ходе образовательного процесса университета за последние годы. Также предлагается рассмотреть практическую задачу генерации случайных дискретных структур на примере задачи тестирования программного обеспечения, обеспечивающего генерацию тестовых заданий образовательных электронных курсов.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Кручинин Д.В., Кручинин В.В. Development of an electronic encyclopedia of number pyramids based on the mathematical apparatus of compositae Proceedings book of the 5th Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, Том 1, стр. 70-72 (год публикации - 2022)

2. Денисов Н.М., Шабля Ю.В. Разработка алгоритмов комбинаторной генерации для множества помеченных деревьев с ограниченным количеством листьев Наука. Технологии. Инновации : сборник научных трудов Всероссийской научной конференции молодых ученых (5-8 декабря 2022 г., Новосибирск), Ч. 2. – С. 18-21. (год публикации - 2022)

3. Шабля Ю.В., Токарева А.В. Development of combinatorial generation algorithms for some lattice paths using the method based on AND/OR trees Proceedings book of the 5th Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, Том 1, стр. 228-231 (год публикации - 2022)

4. Токарева А.В. Системы прослеживаемости и идентификации продукции как основа менеджмента качества Сборник научных трудов XX Международной конференции студентов, аспирантов и молодых ученых "Перспективы развития фундаментальных наук" (25-28 апреля, г. Томск), Т. 5 "Экономика и управление", С. 35-37 (год публикации - 2023)

5. Полюга В.А. Representing combinatorial sets defined by the Fubini numbers in the form of AND/OR tree structures Сборник избранных статей XXVIII Международной научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР» (17 – 19 мая 2023, г. Томск), Ч. 3. - С. 313-316 (год публикации - 2023)

6. Токарева А.В. Автоматизация систем прослеживаемости и идентификации сложных технических изделий Сборник избранных статей XXVIII Международной научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР» (17 – 19 мая 2023, г. Томск), Ч. 2. - С. 143-146 (год публикации - 2023)

7. Полюга В.А., Шабля Ю.В. Разработка алгоритмов комбинаторной генерации для множеств, определяемых числами Фубини Сборник научных трудов XX Международной конференции студентов, аспирантов и молодых ученых "Перспективы развития фундаментальных наук" (25-28 апреля, г. Томск), Т. 3 "Математика". - С. 37-39 (год публикации - 2023)

8. Кручинин Д.В., Дарижапов А. An electronic encyclopedia of number pyramids for the generating functions Proceedings Book of the 13th Symposium on Generating Functions of Special Numbers and Polynomials and their Applications (GFSNP 2023), Том 1, с. 73-75 (год публикации - 2023)

9. Шабля Ю.В., Полюга В. Development of combinatorial generation algorithms for discrete structures associated with the Fubini numbers Proceedings Book of the 13th Symposium on Generating Functions of Special Numbers and Polynomials and their Applications (GFSNP 2023), Том 1, с. 293-296 (год публикации - 2023)

10. Кручинин В., Кручинин Д. Identities for the Harmonic numbers Proceedings Book of the 13th Symposium on Generating Functions of Special Numbers and Polynomials and their Applications (GFSNP 2023), Том 1, с. 275-276 (год публикации - 2023)

11. Перминова М.Ю., Кручинин Д.В. Development of an algorithm for decomposition generating functions Proceedings Book of the 13th Symposium on Generating Functions of Special Numbers and Polynomials and their Applications (GFSNP 2023), Том 1, с. 231-232 (год публикации - 2023)

12. Репьюк Н.С., Кручинин Д.В. Программное обеспечение для декомпозиции значений атрибута Описание журнала событий Moodle Сборник научных трудов XX Международной конференции студентов, аспирантов и молодых ученых "Перспективы развития фундаментальных наук" (25-28 апреля, г. Томск), Т. 7 "IT-технологии и электроника". - С. 124-126 (год публикации - 2023)

13. Кручинин Д.В., Кручинин В.В., Шабля Ю.В. Method for obtaining coefficients of powers of multivariate generating functions Mathematics, Vol. 11, no. 13. Article 2859 (год публикации - 2023)
10.3390/math11132859

14. Полюга В.А., Шабля Ю.В. Исследование быстродействия программной реализации алгоритмов комбинаторной генерации в зависимости от подхода к представлению данных Сборник материалов IX Международной научно-практической конференции молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук» (18-20 апреля 2023 г., Тольятти), С. 60-66 (год публикации - 2023)

15. Репьюк Н.С., Кручинин Д.В. Применение методов комбинаторной генерации на основе деревьев И/ИЛИ для хранения архивных данных Сборник материалов IX Международной научно-практической конференции молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук» (18-20 апреля 2023 г., Тольятти), С. 66-69 (год публикации - 2023)

16. Шабля Ю.В. Combinatorial generation algorithms for some lattice paths using the method based on AND/OR trees Algorithms, Vol. 16, no 6. – Article ID 266 (год публикации - 2023)
10.3390/a16060266

17. Шабля Ю.В. Метод сжатия данных журналов событий на основе теории комбинаторной генерации с применением структур деревьев И/ИЛИ Современные информационные технологии и ИТ-образование, Т. 19, № 3. - С. 564-574 (год публикации - 2023)
10.25559/SITITO.019.202303.564-574

18. Меринов А.А., Шабля Ю.В. Автоматизация процесса построения структур вариантов деревьев И/ИЛИ на основе их рекурсивной композиции Электронные средства и системы управления: материалы докладов XIX международной научно-практической конференции, Ч. 2. - С. 85-87 (год публикации - 2023)

19. Токарева А.В., Кручинин Д.В. О возможности применения алгоритмов комбинаторной генерации к процессу инвентаризации Решетневские чтения: материалы XXVII Междунар. науч.-практ. конф., посвящ. памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева, Ч. 2. - С. 171-173 (год публикации - 2023)

20. Полюга В.А., Шабля Ю.В. Сравнительный анализ скорости вычислений алгоритмов комбинаторной генерации для множеств, определяемых числами Фубини Наука. Технологии. Инновации: сборник научных трудов Всероссийской научной конференции молодых ученых, Ч. 2. – С. 163-167. (год публикации - 2024)

21. Токарева А.В., Кручинин Д.В. Модификация метода идентификации и прослеживаемости сложных технических изделий с применением алгоритмов комбинаторной генерации на основе деревьев И/ИЛИ Вестник СибГУТИ, Т. 18, № 3. - С. 73-85 (год публикации - 2024)
10.55648/1998-6920-2024-18-3-73-85

22. Токарева А.В. Применение модифицированного метода прослеживаемости и идентификации на основе деревьев И/ИЛИ для учёта комплексной техники Перспективы развития фундаментальных наук: сборник научных трудов XXI Международной конференции студентов, аспирантов и молодых ученых, Т. 3 "Математика". - С. 17-19 (год публикации - 2024)

23. Токарева А.В. Организация процесса хранения конструкторской документации с применением алгоритмов комбинаторной генерации Сборник избранных статей научной сессии ТУСУР, Ч. 2. - С. 214-216 (год публикации - 2024)

24. Меринов А.А., Шабля Ю.В. Сжатие изображений без потерь на основе методов комбинаторной генерации Перспективы развития фундаментальных наук: сборник научных трудов XXI Международной конференции студентов, аспирантов и молодых ученых, Т. 3 "Математика". - С. 11-13 (год публикации - 2024)

25. Полюга В.А. Способ представления текстовой информации в формате комбинаторного множества Сборник избранных статей научной сессии ТУСУР, Ч. 3. - С. 121-124 (год публикации - 2024)

26. Меринов А.А., Черявко Е.Е., Якутин В.Ю. Автоматизация процесса построения структур и вариантов деревьев И/ИЛИ и их графического представления в десктопном приложении Сборник избранных статей научной сессии ТУСУР, Ч. 3. - С. 84-86 (год публикации - 2024)

27. Шабля Ю.В., Меринов А.А., Кручинин Д.В. Combinatorial generation algorithms for directed lattice paths Mathematics, Vol. 12, no 8. – Article ID 1207 (год публикации - 2024)
10.3390/math12081207

28. Кручинин Д.В., Кручинин В.В. Some properties of the Faber polynomials Proceedings book of the 6th Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, P. 138-141. (год публикации - 2023)

29. Шабля Ю.В., Меринов А.А. Bijection between simple directed lattice paths and AND/OR tree structures Proceedings book of the 6th Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, P. 351-355. (год публикации - 2023)

30. Шабля Ю.В., Перминова М.Ю. Relationship between combinatorial sets, generating functions and combinatorial generation algorithms Proceedings book of the 6th Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, P. 356-359. (год публикации - 2023)

31. Шабля Ю.В., Полюга В.А., Кручинин Д.В. Combinatorial generation algorithms for discrete structures associated with the Fubini numbers Proceedings of the Jangjeon Mathematical Society (год публикации - 2024)

32. Шабля Ю.В., Полюга В.А. Method for designing encoding algorithms based on AND/OR trees Journal of Discrete Mathematical Sciences & Cryptography (год публикации - 2025)

33. Меринов А.А., Шабля Ю.В. Автоматизация кодирования изображений с помощью метода комбинаторной генерации на основе деревьев И/ИЛИ Электронные средства и системы управления: материалы докладов XХ Международной научно-практической конференции (год публикации - 2024)

34. Шабля Ю.В., Кручинин В.В., Кручинин Д.В. Enumeration of words derived from unambiguous context-free grammars based on powers of generating functions Proceedings of the Jangjeon Mathematical Society (год публикации - 2025)

35. Ражев К.С., Токарева А.В. Оценка эффективности способов хранения структур деревьев И/ИЛИ и их вариантов Наука. Технологии. Инновации: материалы всерос. науч. конф. молодых ученых (год публикации - 2024)

36. Шабля Ю.В., Кручинин Д.В. Algorithms for ranking and unranking the combinatorial set of RNA secondary structures Discrete Mathematics, Algorithms and Applications (год публикации - 2025)
10.1142/S1793830925500594

37. Токарева А.В. Анализ применимости модифицированного метода идентификации и прослеживаемости на основе деревьев И/ИЛИ в критической информационной инфраструктуре Сборник научных трудов XXII Международной конференции студентов, аспирантов и молодых ученых "Перспективы развития фундаментальных наук" (год публикации - 2025)

38. Шабля Ю.В., Кручинин В.В. Application of generating functions to calculate the number of words derived from unambiguous context-free grammars Proceedings Book of MICOPAM 2024 (год публикации - 2024)

39. Кручинин В.В., Кручинин Д.В., Шабля Ю.В. Some identities for harmonic numbers based on composition of generating functions Montes Taurus Journal of Pure and Applied Mathematics (год публикации - 2025)

40. Кручинин Д.В., Кручинин В.В., Перминова М.Ю. Fractals on compositae Proceedings Book of MICOPAM 2024 (год публикации - 2024)

41. Шабля Ю.В., Токарева А.В. Способы хранения структур деревьев И/ИЛИ и их вариантов в оперативной и постоянной компьютерной памяти Доклады ТУСУР, Т. 27, № 2. С. 44-50 (год публикации - 2024)
10.21293/1818-0442-2024-27-2-44-50

42. Полюга В.А. Применение алгоритма комбинаторной генерации в качестве примитива в структуре Меркла-Дамгора Сборник избранных статей научной сессии ТУСУР (год публикации - 2025)

43. Ражев К.С., Токарева А.В. Прототип системы идентификации и прослеживаемости с использованием алгоритмов комбинаторной генерации на основе деревьев И/ИЛИ Сборник избранных статей научной сессии ТУСУР (год публикации - 2025)

44. Шабля Ю.В. Сжатие информационных объектов с помощью методов комбинаторной генерации на основе деревьев И/ИЛИ Доклады ТУСУР, Т. 27, № 4. С. 74-79 (год публикации - 2024)
10.21293/1818-0442-2024-27-4-74-79

45. Шабля Ю.В. Метод построения алгоритмов комбинаторной генерации для контекстно-свободных языков на основе структур деревьев И/ИЛИ Информационные технологии (год публикации - 2025)

Публикации

40. Кручинин Д.В., Кручинин В.В., Перминова М.Ю. Fractals on compositae Proceedings Book of MICOPAM 2024 (год публикации - 2024)

Аннотация результатов, полученных в 2025 году
Структура многих информационных объектов может быть представлена в виде иерархической или рекурсивной зависимости. Для представления и кодирования таких информационных объектов достаточно хорошо подходит применение древовидных структур данных. Это приводит к возможности описания исследуемого информационного объекта с помощью формального комбинаторного множества, для которого применимы различного рода алгоритмы комбинаторной генерации. Целью третьего этапа проекта являлось применение разработанной методологии построения алгоритмов комбинаторной генерации для решения прикладных задач. В ходе проведения научно-исследовательских работ были получены следующие научные результаты: 1. Разработан графический редактор для визуального проектирования рекурсивных композиций структур деревьев И/ИЛИ. Кроме того, разработанное программное обеспечение дополнено функциональными возможностями по автоматизированному построению алгоритмов комбинаторной генерации (алгоритмы rank и unrank) в формате псевдокода для заданной пользователем рекурсивной композиции деревьев И/ИЛИ. Созданная инструментальная система построения алгоритмов комбинаторной генерации позволяет повысить скорость разработки новых комбинаторных алгоритмов для структур данных, связанных с деревьями И/ИЛИ. 2. Разработана в виде веб-приложения база алгоритмов комбинаторной генерации, систематизирующая знания о существующих алгоритмах комбинаторной генерации. Реализована структура и логика работы, где для каждого хранящегося в базе алгоритма комбинаторной генерации имеются информационные блоки и функциональный блок с возможностью выполнения выбранного алгоритма. Созданное веб-приложение является инструментом для систематизации информации об алгоритмах комбинаторной генерации, которая в дальнейшем может быть использована научным сообществом. 3. На основе разработанной методологии построения алгоритмов комбинаторной генерации, предложен подход к кодированию реляционной базы данных журнала событий системы управления обучением университета. Практическая значимость такого подхода заключается в эффекте сжатия хранимых данных в обрабатываемой базе данных. В качестве вычислительного эксперимента проведено сжатие основной таблицы реляционной базы данных журнала событий системы управления обучением университета. Результатом применения предложенного подхода к кодированию базы данных журнала событий стало увеличение на 30% коэффициента сжатия для алгоритма сжатия LZMA. 4. Разработаны генераторы тестовых задач, основанные на структурах деревьев И/ИЛИ, с фиксированным диапазоном значений генерируемых параметров задач. В сравнении с встроенными в систему управления обучением Moodle инструментами для формирования тестовых заданий, разработанные генераторы позволяют повысить вариативность образовательного контента. 5. С целью развития методологии построения алгоритмов комбинаторной генерации за счет применения теории производящих функций, разработан метод нахождения явных и рекуррентных выражений коэффициентов степеней производящей функции. На основе полученных рекуррентных выражений построены алгоритмы комбинаторной генерации для комбинаторных объектов, описываемых числами Моцкина и Каталана. 6. Исследованы возможности применения разработанной методологии построения алгоритмов комбинаторной генерации для создания новых способов представления сложных дискретных структур в междисциплинарных областях. Сформулированы следующие научно-технические предложения: - В области кодирования текстовой информации: предложены правила биективного отображения текстовой информации на структуры деревьев И/ИЛИ, разработан метод кодирования текстовой информации с возможностью применения различных выражений функции мощности комбинаторного множества текстов заданной длины. Разработанный метод кодирования может быть использован в качестве этапа предварительной обработки для алгоритмов сжатия данных, так как позволяет сократить избыточность хранимой в тексте информации; - В области кодирования растровых изображений: предложены правила биективного отображения растровых изображений на структуры деревьев И/ИЛИ, разработан метод кодирования растровых изображений с эффектом сжатия без потерь. Статистические тесты для последовательностей чисел, формируемых из содержимого бинарных файлов с вычисленными значениями рангов для растровых изображений, подтвердили соответствие генерируемых чисел критериям случайности. Следовательно, возможна разработка генератора псевдослучайных чисел с использованием методов комбинаторной генерации, где источником энтропии является растровое изображение; - В области кодирования сложных дискретных структур: предложена общая схема кодирования информационных объектов с помощью алгоритмов комбинаторной генерации с использованием промежуточной формы представления в виде вариантов дерева И/ИЛИ. Используя предложенную схему кодирования, можно решать задачу сжатия данных без потерь для информационных объектов, представляющих собой сложные дискретные структуры с биективным отображением на деревья И/ИЛИ; - В области идентификации и прослеживаемости сложных технических изделий: разработан прототип системы, автоматизирующей процесс идентификации и внутреннего учета комплексной техники на предприятиях, который позволяет решать ряд управленческих задач, связанных с обеспечением доступа к информации о технике; - В области генерации выражений формальных языков, заданных контекстно-свободными грамматиками: разработан метод построения алгоритмов ранжирования и генерации по рангу для контекстно-свободных языков, разработан метод получения явных/рекуррентных выражений для вычисления количества деревьев вывода слов заданной длины из нетерминальных символов контекстно-свободной грамматики. Получаемые с помощью предложенного метода алгоритмы комбинаторной генерации могут найти применение при решении задач сжатия данных и моделирования объектов, описываемых словами формальных языков.

Публикации

40. Кручинин Д.В., Кручинин В.В., Перминова М.Ю. Fractals on compositae Proceedings Book of MICOPAM 2024 (год публикации - 2024)

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