ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 3, с. 538-546
УДК 519.712
О ПОСТРОЕНИИ ТУПИКОВЫХ ПОКРЫТИЙ ЦЕЛОЧИСЛЕННОЙ МАТРИЦЫ1)
© 2007 г. Е. А. Демьянов*, Е. В. Дюкова**
(* 119421 Москва, ул. Обручева, 26, корп. 2, Фонд "Общественное мнение";
** 119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: egor_d13@mail.ru; djukova@ccas.ru Поступила в редакцию 26.06.2006 г.
Получены новые оценки вычислительной сложности задачи построения тупиковых покрытий целочисленной матрицы (поиска максимальных конъюнкций логической функции специального вида). Библ. 7. Табл. 1.
Ключевые слова: дискретные процедуры распознавания и классификации, тупиковое покрытие целочисленной матрицы, асимптотически оптимальный алгоритм, метрические свойства множества покрытий, метрические свойства дизъюнктивных нормальных форм.
Комбинаторный (логический) анализ данных в задачах распознавания и классификации основан на использовании аппарата дискретной математики, в частности методов построения покрытий булевых и целочисленных матриц (нормальных форм логических функций), что оказывается сложным в силу чисто вычислительных трудностей переборного характера. При этом особую сложность представляет построение тупиковых покрытий целочисленной матрицы (специальной нормальной формы двузначной логической функции, заданной перечислением нулей). Поиски эффективных алгоритмов построения тупиковых покрытий ведутся с середины 1960-х годов.
В [1]-[4] рассмотрен случай, когда число строк m в матрице имеет более низкий порядок роста, чем число столбцов n, при условии, что n —► га. Для этого случая построен асимптотически оптимальный алгоритм поиска тупиковых покрытий. Алгоритм работает с полиномиальной задержкой относительно m и n (число элементарных операций, выполняемых алгоритмом на каждом шаге, ограничено сверху полиномом от m и n) и число его шагов при n —»- ^ почти всегда (для почти всех матриц данного размера) асимптотически равно числу тупиковых покрытий.
В настоящей работе рассмотрен случай, когда n < m. Построен алгоритм поиска тупиковых покрытий целочисленной матрицы c элементами из {0, 1, ..., k- 1}, k > 2, с полиномиальной задержкой на каждом шаге и такой, что логарифм по основанию k числа его шагов при n —► ^ почти всегда асимптотически равен логарифму по основанию k числа тупиковых покрытий. Обоснование алгоритма базируется на изучении метрических (количественных) свойств множества тупиковых покрытий и так называемых с-подматриц целочисленной матрицы. Получены новые асимптотические оценки типичных значений числа тупиковых покрытий и длины тупикового покрытия и такие же оценки для количественных характеристик множества с-подматриц. Аналогичные результаты приведены для задач построения нормальных форм двузначной логической функции, заданной перечислением нулевых точек.
1. МЕТРИЧЕСКИЕ СВОЙСТВА ТУПИКОВЫХ ПОКРЫТИЙ И с-ПОДМАТРИЦ
в
В СЛУЧАЕ n < m < kn , в < 1/2
Пусть Mkmn - множество всех матриц размера m х n с элементами из {0, 1, ..., k- 1}, k> 2; Erk, k > 2, r < n, - множество всех наборов вида (сх, ..., сг), где ci е {0, 1, ..., k- 1}.
Работа выполнена при частичной финансовой поддержке РФФИ (код проекта 04-01-00795), гранта президента РФ по поддержке ведущих научных школ НШ < 5833.2006.1 и программы ОМН РАН "Алгебраические и комбинаторные методы математической кибернетики".
Рассмотрим а е Егк, а = (аь ..., аг). Через Qp(а),р е {1, 2, ..., г}, обозначим множество всех наборов (Р1, ..., вг) в Егк таких, что вр ф ар и в/ = а,- при / е {1, 2, ..., г}\{р}.
Пусть Ь е Мктп. Тупиковым а-покрытием матрицы Ь называется набор столбцов Н этой матрицы такой, что подматрица ЬН матрицы Ь, образованная столбцами набора Н, обладает следующими двумя свойствами: 1) ЬН не содержит строку а; 2) еслир е {1, 2, ..., г}, то ЬН содержит хотя бы одну строку из множества Qp(а). Подматрица матрицы Ь, имеющая с точностью до перестановки строк вид
в1 а2 аз • • аг-1 аг
а1 в2 аз • • аг-1 аг
а1 а2 аз • • аг-1 в.
где вр ф ар дляр = 1, 2, ..., г, называется а-подматрицей.
Таким образом, Н является тупиковым а-покрытием тогда и только тогда, когда ЬН не содержит строку а и содержит а-подматрицу.
Понятие тупикового (0, ..., 0)-покрытия булевой матрицы совпадает с хорошо известным понятием неприводимого покрытия булевой матрицы. Отметим, что (0, ..., 0)-подматрица булевой матрицы является единичной подматрицей.
Положим, что £(Ь, а) - множество всех а-подматриц матрицы Ь, В(Ь, а) - множество всех тупиковых а-покрытий матрицы Ь. Пусть, далее,
Бг(Ь) = и Ь, а), Вг(Ь) = и В(Ь, а),
5( Ь) = и Sr( Ь), В (Ь) = и Sr( Ь),
г1 = [^кт - - 1], | V] - мощность множества V.
в
Пусть п < т < к" , в < 1/2. В рассматриваемом случае получена асимптотика логарифма типичного числа подматриц из £(Ь) с порядком не меньшим г1 (при п —«- Показано, что эта асимптотика совпадает с асимптотикой логарифма типичного числа покрытий из В(Ь) и совпадает с асимптотикой логарифма типичного числа тех покрытий из В(Ь), у которых длины не меньше г1. Получена оценка типичной длины покрытия из В(Ь). Указанные оценки приведены в сформулированных ниже теоремах 1-3.
Замечание 1. Если в матрице Ь из Мтп есть две одинаковые строки, то, очевидно, при удалении одной из них множество В(Ь) не меняется. Следовательно, при подсчете числа тупиковых покрытий матрицы Ь
пв
имеет смысл рассматривать случай, когда в Ь нет одинаковых строк. При т < к , в < 1/2, требуемым
свойством обладают почти все матрицы Мтп (см. ниже утверждение 4, разд. 3).
пв к Теорема 1. Если п < т < к" , в < 1/2, то при п —► ^ для почти всех матриц Ь из Мтп логарифм по основанию к числа всех подматриц из Б(Ь) с порядком не меньшим г1 асимптотически равен при п —► ^ логарифму по основанию к числа всех покрытий из В(Ь) с длиной не меньшей
г1 и асимптотически равен 1о%кСп + г1.
Теорема 2. Если п < т < к" , в < 1/2, то при п —^ для почти всех матриц Ь из Мтп логарифм по основанию к числа всех покрытий из В(Ь) с длиной не меньшей г1 асимптотически равен логарифму по основанию к числа всех покрытий из В(Ь) и асимптотически равен ^^С^ + г1.
ае Е,,
ае Е
к
к
г = 1 г = 1
Теорема 3. Если n < m < k" , ß < 1/2, то при n —► га у почти всех матриц L из Mmn длины почти всех покрытий из B(L) принадлежат интервалу [rx, logkmn].
Доказательства теорем 1-3 опираются на леммы 1-6, приведенные далее. При доказательстве лемм 1-6 использовались результаты работ [5] и [6].
Будем считать Mkmn = {L} пространством элементарных событий, в котором каждое событие L происходит с вероятностью 1/|Mmn |. Математическое ожидание случайной величины X(L), определенной на множестве Mmn, будем обозначать через MX(L), дисперсию - через DX(L).
Легко доказывается
Лемма 1. ПустьX(L) > 0, 0 > 0, v0(n) - доля тех матриц L из Mmn, для которыхX(L) > OMX(L). Тогда справедливо неравенство v0(n) < 1/0.
Далее записи an ~ bn, n —► га, и an <n bn, n —► га, соответственно означают, что limajbn = 1, n —► га, и limajbn < 1, n —► ra.
2
Пусть ar = CrnCrm r!(k - 1)rkr-r . Так как ar_ 1 = 0 (ar) при n < m, r < rb то справедлива
Лемма 2. При n < m имеет место соотношение
X crnemr\( k -i )rkr - r«cn cm r,i (k -1)n
2
Г t Г - r,
r > ri
,nß
Лемма 3. При m < k , в < 1/2, имеет место соотношение
2
logk(Crmri!(k_ 1)rik ri) = o(logk(enkr)), n —► га.
Доказательство. В справедливости леммы можно убедиться непосредственной проверкой. Действительно, из очевидного неравенства ern > ((n - r)/r)r следует, что
logс" >n (1- в)rilogkn, n—► га. (1)
С другой стороны,
_ 2 r b = ex! (k _1 )rikri <( mk)ri/kri <(k2lnlog km) \
Следовательно, имеем
logkb <n rilogklnn, n —► га. (2)
Из (1) и (2) следует утверждение леммы 3.
На Mmn = {L} рассмотрим случайные величины nr(L) = |Br(L)|, Zr(L) = |<S"r(L)|. Нетрудно подсчитать (см. [5]), что имеет место формула
м Zr ( l ) = enemr!( k _i )rkr _r2.
в
Лемма 4. При n < m < k" , в < 1/2, имеет место соотношениее
logkХПг(L)< logkXZr(L) <n logkerm + ri, n—► га.
r > ri r > ri
Доказательство. Из лемм 2 и 3 сразу следует, что
logkX мПг(l) < logkX мZr(l) - logkern + ri, n га.
r > r, r > r,
Отсюда, применяя лемму 1 с 0 = \ogfr ^¿л, получаем утверждение леммы 4.
оо
в
Лемма 5. При m < к" , в < 1/2, имеет место соотношение
log к X Zr (L) > log к X П (L) >" log кС" + ri, " —
r > ri r > ri
Доказательство. В [6] показано, что
nri(L)« C"'2ri( 1- к ri)m, ~.
Оценим (1 - к^ )m:
(i - к ri) > exp (-2m/krl) > (logкт)-2к.
Отсюда, учитывая, что logklogkm = o (logkC"1), получаем утверждение леммы.
Из лемм 4 и 5 следует утверждение теоремы 1.
"в
Лемма 6. При " < m < к" , в < 1/2, имеет место соотношение
í \
" —«. тс.
Хпг(L) = o Xnr(L)
= o
r < ri Vr > ri У
"в
Доказательство. В [6] показано, что при т < к , в < 1/2,
ХПг (Ь) = о (Сг: к"1), п —
г < г^
С другой стороны, согласно теореме 1, имеем
VI; ги1 + ®(п)
Xnr (L) = (С" к" )
r
r > r
где 5(") > 0, 5(") —► 0 при " —»- тс. Следовательно,
/ л
ХПг(L) = o ХПг(L)
r < "i Vr > "i /
" —► тс.
Отсюда получаем утверждение доказываемой леммы.
Из теоремы 1 и леммы 6 следует утверждение теоремы 2. Из леммы 6 следует утверждение теоремы 3.
Замечание 2. Оценка для |В(Ь)|, приведенная в теореме 2, ранее была получена более сложным способом в [7].
2. ПОСТРОЕНИЕ ТУПИКОВЫХ ПОКРЫТИЙ В СЛУЧАЕ п < т < кп , у < 1/(2к + 1)
Пусть G(Ь) - конечная совокупность наборов столбцов матрицы Ь, содержащая В(Ь). Предполагается, что каждый набор из G(Ь) не содержит одинаковых столбцов и некоторые наборы столбцов в G(Ь) могут встречаться более одного раза.
Пусть алгоритм А строит покрытия из В(Ь) путем последовательного просмотра всех наборов из G(Ь). При этом каждый набор из G(Ь) просматривается столько раз, сколько раз он встречается в G(Ь). Таким образом, на каждом шаге алгоритма А строится некоторый набор столбцов Н из G(L) и проверяется принадлежность Н к В(Ь). Число шагов алгоритма А обозначим через ЫА(Ь).
Нас будет интересовать вычислительная сложность алгоритма А в типичном случае (для почти всех булевых матриц размера т х п при п —► тс).
Будем говорить, что алгоритм А строит G(Ь) с полиноми
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.