ОЦЕНКА СЛОЖНОСТИ ЭФФЕКТИВНЫХ АЛГОРИТМОВ ПРОВЕРКИ НАЛИЧИЯ СОВМЕСТНОГО ДЕЙСТВИЯ БИНАРНЫХ ФАКТОРОВ
Аннотация и ключевые слова
Аннотация (русский):
Приведены эффективные алгоритмы проверки наличия совместного действия k факторов в данном отклике, зависящем от n факторов, а также вычисления степеней этого совместного действия для любого k. Показано, что асимптотическая временнáя сложность предлагаемых алгоритмов не превосходит квадрата от размера входных данных, представляющих отклик f.

Ключевые слова:
булева функция, булев куб, эффективный алгоритм, временная сложность алгоритма, бинарная теория достаточных причин, отклик.
Текст

Введение. Булева модель теории достаточных причин, предложенная в работах [1-8], позволяет рассматривать эту эпидемиологическую концепцию как приложения общей теории конечных булевых алгебр и булевых функций [9, 10]. При этом помимо прояснения и формализации основных понятий этой концепции возникает необходимость разработки эффективных алгоритмов [11, 12], вычисляющих различные величины обсуждаемой теории. При этом важно не только предложить эти алгоритмы, но и оценить их вычислительную сложность [11, 12], поскольку размер входных данных для этих алгоритмов в булевом формализме теории достаточных причин достаточно высок.

Ниже мы рассмотрим оценки асимптотической временнóй вычислительной сложности проверки наличия совместного действия факторов в отклике и нахождения степени этого совместного действия [5, 6, 8], применяемых в задаче классификации совместного действия факторов в бинарной теории достаточных причин. 

Предварительно заметим, что речь будет идти только об асимптотической сложности, которая обычно используется в теории сложности алгоритмов [11, 12], что связано с размером входных данных обсуждаемой задачи, зависящим от числа факторов экспоненциально. Действительно, булев куб  имеет 2n вершин, а любой двухуровневый отклик f  от n (булевых) переменных полностью определятся своим носителем , причем [7]. Так как вершина булева куба определяется бинарным вектором длины n, то размер входных данных, задающих отклик f, в худшем случае равен N = n·2n. Следовательно, уже при сравнительно небольшом числе факторов объем исходных данных становится слишком большим, что делает необходимым построение эффективных алгоритмов вычисления различных конструкций этой теории, причем один из параметров оценки алгоритма как эффективного является минимизация его вычислительной сложности. Кроме того, следует отметить, что имеющиеся модели теории достаточных причин как в формальном [1-8], так и в полуформальном изложении [14-16] допускают произвольное число факторов. Поэтому уже с точки зрения полноты этой теории рассмотрение всех вопросов, возникающих в контексте того или иного формализма, совершенно естественно и необходимо.

Одно из важных общих понятий булевой модели теории достаточных причин – понятие совместного действия n факторов в отклике, зависящем от всех этих n факторов, введено в работах [5,7]. В работе [7] также был приведён эффективный алгоритм проверки по данному отклику наличия в нём совместного действия всех его факторов, а также приведена оценка сверху временнóй сложности этого алгоритма величиной .

Основные результаты

В работах [6, 8] было предложено понятие взаимодействия k факторов в отклике, зависящем от n факторов, которое обобщает понятия взаимодействия n факторов в отклике, зависящем от n факторов. С помощью критерия совместного действия k факторов, предложенного в [6], можно доказать аналогичную оценку временнóй сложности эффективного алгоритма проверки наличия этого действия в данном отклике. Формулировка этого критерия (см. Теорему 1 ниже) использует представления отклика f в виде неориентированного графа , который является подграфом булева куба с вершинами из носителя Cf.  

Теорема 1 [6]. В отклике f , зависящем от n факторов, имеется взаимодействие k факторов тогда и только тогда, когда минимальная степень вершин в графе  не превосходит nk.

Теорема 2. Для любого k  существует эффективный алгоритм, проверяющий наличие совместного действия k факторов в отклике, зависящем от n факторов, причем временнáя сложность этого алгоритма имеет порядок не более чем .

Доказательство. Каждый  автоморфизм  булева куба может быть продолжен на  свободную булеву алгебру всех булевых функций от переменных . При этом булевой функции f соответствует булева функция  чей носитель  равен образу  носителя  функции f. Пусть  - произвольная вершина графа . Рассмотрим автоморфизм  булева куба , определяемый равенством  где сложение по модулю 2. Любой автоморфизм булева куба является изометрией этого куба как метрического пространства с метрикой-расстоянием Хэмминга. Поэтому степень вершины γ в графе  равна степени вершины 0 в графе , вершинно-порожденном множеством . Степень вершины 0 в графе  равна числу вершин единичного веса Хэмминга в множестве  Получение списка таких вершин и подсчёт их числа имеют сложность не более чем . Следовательно, вычисление степени любой вершины в графе  имеет  временнýю сложность не более чем , а вычисление минимальной степени вершин в этом графе – не более чем .

Таким образом, оценка  экспоненциальна по числу факторов n, но менее чем квадратична по наибольшему размеру входных данных

Для исследования совместного действия факторов в данном отклике в работах [5,7] было введено понятие степени  совместного действия n факторов в отклике f. В работе [7] также предложен эффективный алгоритм нахождения  и показано, что верхняя оценка сложности этого алгоритма равна .

В работе [6] было введено обобщение этого понятия – степень  совместного действия k факторов в отклике f, зависящем от n факторов, а в работе [8] рассмотрена зависимость степени  от k. Следующее утверждение даёт оценку сложности вычисления набора  степеней совместного действия для данного отклика f.

Теорема 3. Существует эффективный алгоритм вычисления набора  степеней совместного действия данного отклика f, причем сложность этого алгоритма оценивается сверху величиной порядка  где N, как и раньше, максимальный размер входных данных, .

Доказательство. Рассмотрим булев куб  как решёточно-упорядоченное множество  относительно покомпонентного сравнения ‘≤’ бинарных векторов [10], которое можно представить ориентированным графом R. В графе R для каждого  выделены списки Uk лексикографически упорядоченных вершин веса k. На формирование графа R потребуется времени (элементарных шагов вычислительных операций) не более чем . Далее для каждого набора  производим следующие шаги:

  1.  формируем список лексикографически упорядоченных вершин множества Cg, где из списка вершин множества Cf.
  2.  полученный список распределяем по спискам Vk, , вершин веса k, для которых сохраняется лексикографическое упорядочение;
  3.  при помощи списков Vk из графа R получаем помеченный ориентированный граф Rg, в котором каждая вершина  из списка Uk помечается числом если  и  в противном случае. Таким образом, граф Rg представляет частично упорядоченное множество .

Шаги (1)-(3) в целом займут времени не более чем .

  1.  для каждой вершины  графа из списка Uk вычисляем метку с помощью метки  и меток  для k вершин  из списка Uk-1, покрываемых вершиной  в  (считая, что m(0)=0);
  2.  для каждого находим mk максимальное значение  среди всех вершин  графа из списка Uk.

На этапы (4)-(5) потребуется время не более чем  Шаги (1)-(5) повторяются для каждого набора  и поэтому в целом выполняемые действия потребуют времени не более чем , что не превосходит

На последнем шаге для каждого k находим максимальное значение среди всех тех mk, которые вычисляются на этапе (5) для всех вершин  Можно доказать, что полученное значение равно степени .

Таким образом, в целом, описанный динамический алгоритм имеет временнýю сложность не более чем

Список литературы

1. Панов В. Г., Нагребецкая Ю. В. Алгебраическая трактовка двухфакторной теории достаточных причин // Труды СПИИРАН. 2013. Т. 3(26). С. 277–296.

2. Панов В. Г., Нагребецкая Ю. В. Алгебраическая классификация совместного действия n бинарных факторов // Материалы IX междунар. конф. «Системный анализ в медицине». Благовещенск. 2015. С. 31–34.

3. Panov V.G. and Nagrebetskaya J.V. Boolean algebras and classification of interactions in sufficient-component cause model // Int. J. Pure Appl. Math. 2015. V. 98(2). P. 239–259.

4. VanderWeele T.J., Robins J.M. A theory of sufficient cause interactions // COBRA Preprint Series. 2006. Paper 13.

5. Нагребецкая Ю.В., Панов В.Г. Степень взаимодействия бинарных факторов в теории достаточных причин // Материалы XIII междунар. конф. "Системный анализ в медицине". Благовещенск, 2019. C. 31–34.

6. Нагребецкая Ю. В., Панов В. Г. Обобщение понятия взаимодействия n факторов в теории достаточных причин и его свойства // Материалы XIII междунар. конф. "Системный анализ в медицине". Благовещенск, 2019. C. 35–38.

7. Nagrebetskaya J.V., Panov V.G. Joint action of binary factors in the sufficient causes theory and its classification // Int. J Innov. Tech.&Exploring Eng. V.9(1), 2019. P. 2146–2153.

8. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

9. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. Екатеринбург: Изд-во Уральского ун-та, 1996.

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. M.: Мир, 1982.

11. Ахо. А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. M.: Мир, 1979.

12. Rothman K. Causes // Am. J. Epidemiology. 1976. V. 104(6). P. 587–592.

13. Miettinen O. S. Causal and preventive interdependence: Elementary principles // Scand. J. Work. Environ. Health. 1982. V. 8. P. 159–168.

14. VanderWeele T. J., Robins J. M. The identification of synergism in the sufficient-component-cause framework // Epidemiology. 2007. V. 18(3). P. 329–339.

15. VanderWeele T. J., Richardson T. S. General theory for interactions in sufficient cause models with dichotomous exposures // Ann. Statistics. 2012. V. 40. P. 2128–2161.

Войти или Создать
* Забыли пароль?