Number of Solutions for Some Special Logical Analysis Problems of Integer Data
- Authors: Djukova A.P.1, Djukova E.V.1
-
Affiliations:
- Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 119333, Moscow, Russia
- Issue: No 5 (2023)
- Pages: 57-66
- Section: КОМПЬЮТЕРНЫЕ МЕТОДЫ
- URL: https://journals.rcsi.science/0002-3388/article/view/140342
- DOI: https://doi.org/10.31857/S0002338823050050
- EDN: https://elibrary.ru/OHCWCE
- ID: 140342
Cite item
Abstract
In the class of discrete enumeration problems, an important place belongs to the problems of searching for frequently and infrequently occurring elements in integer data. Questions on the effectiveness of such a search are directly related to the study of the metric (quantitative) properties of sets of frequent and infrequent elements. It is assumed that the initial data are presented in the form of an integer matrix, whose rows are descriptions of the studied objects in the given system of the numerical characteristics of these objects, called attributes. The case is considered when each attribute takes values from the set {0,1,...k-1}, k>2. Asymptotic estimates for the typical number of special, frequent fragments of object descriptions, called correct fragments, and estimates for the typical length of such a fragment are given. We also present new results concerning the study of the metric properties of the minimal infrequent fragments of descriptions of objects.
About the authors
A. P. Djukova
Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 119333, Moscow, Russia
Email: edjukova@mail.ru
Россия, Москва
E. V. Djukova
Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 119333, Moscow, Russia
Author for correspondence.
Email: edjukova@mail.ru
Россия, Москва
References
- Баскакова Л.В., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // ЖВМ и МФ. 1981. Т. 21. № 5. С. 1264–1275.
- Hammer P.L. Partially Defined Boolean Functions and Cause-effect Relationships // Lecture at the Intern. Conf. on Multi-Attrubute Decision Making Via ORBased Expert Systems. Passau, Germany: University of Passau, 1986.
- Дюкова Е.В., Журавлев Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // ЖВМ и МФ. 2000. Т. 40. № 8. С. 1264–1278.
- Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // ЖВМ и МФ. 2002. Т. 42. № 5. С. 741–753.
- Журавлев Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. М.: ФАЗИС, 2006. 159 с.
- Dragunov N., Djukova E. and Djukova A. Supervised Classification and Finding Frequent Elements in Data // VIII Intern. Conf. on Information Technology and Nanotechnology (ITNT-2022). Samara, Russian Federation: IEEE, 2022. P. 1–5.
- Дюкова Е.В., Дюкова А.П. О сложности обучения логических процедур классификации // Информатика и ее применения. 2022. Т. 16. Вып. 4. С. 57–62.
- Андреев А.Е. Об асимптотическом поведении числа тупиковых тестов и длины минимального теста для почти всех таблиц // Пробл. кибернетики. 1984. Вып. 41. С. 117–142.
- Дюкова Е.В., Сотнезов Р.М. Асимптотические оценки числа решений задачи дуализации и ее обобщений // ЖВМ и МФ. 2011. Т. 51. № 8. С. 1431–1440.
- Носков В.Н., Слепян В.А. О числе тупиковых тестов для одного класса таблиц // Кибернетика. 1972. № 1. С. 60–65.
- Aggarwal Charu C. Frequent Pattern Mining. N. Y.: Springer International Publishing, 2014. 469 p. (https://www.charuaggarwal.net/freqbook.pdf).
![](/img/style/loading.gif)