Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью | ПДМ. 2013. № 2(20).

Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью

Рассматривается система линейных булевых уравнений с искажённой правой частью, истинное решение которой имеет заданный вес, не зависящий от числа неизвестных в системе. Предлагается вероятностный алгоритм нахождения этого решения, имеющий меньшую временную сложность по сравнению с методом максимума правдоподобия. В отличие от известных алгоритмов, обладающих указанным свойством, предложенный алгоритм использует только операции сравнения и (поразрядного и арифметического) сложения двоичных целых чисел, что позволяет применять его на практике в случае, когда другие алгоритмы оказываются менее эффективными.

Fast algorithm for recovering the true solution with fixed weight of a system of linear Boolean equations with noised right-hand side.pdf Рассмотрим систему булевых уравнений (1) Ax = b = Ax0 0 £, где A — случайная равновероятная матрица размера m х k над полем из двух элемен- Система уравнений (СУ) (1) называется системой линейных булевых уравнений с искажённой правой частью, а вектор x0 — её истинным решением [1]. Предположим, что вес (количество ненулевых координат) вектора x0 равен фиксированному числу р ^ 3. Требуется восстановить этот вектор по известным значениям A, b, p и р. Как правило, данную задачу решают в предположении, что число неизвестных k в системе (1) принимает любые достаточно большие натуральные значения, а вероятность искажения p не зависит от k. При этом требуется разработать алгоритм, позволяющий для любых наперёд заданных p Е (0,1/2) и р Е {3, 4,...} находить истинное решение этой системы уравнений с любой наперёд заданной надёжностью при всех достаточно больших значениях k и m [1-3]. Назовём алгоритм A восстановления истинных решений СУ (1) состоятельным, если существует функция mo : Nx (0,1/2) х (0,1/2) х{3, 4,...} —у N, удовлетворяющая следующему условию: для любыхp, 8 Е (0,1/2), р Е {3, 4,...} существует число k0 Е N, такое, что для любого натурального k ^ k0 и произвольного вектора x0 Е {0,1}k веса р вероятность правильного восстановления этого вектора с помощью алгоритма A по известной реализации случайной системы (1), состоящей из m = m0(k,p, 8, р) уравнений, больше либо равна 1 — 8. В дальнейшем рассматриваются только состоятельные алгоритмы. Трудоёмкость (или временная сложность в худшем случае) каждого из них является функцией четырёх параметров: T = T(k,p, 8, р), где m = m0(k,p, 8, р); k ^ k0; p, 8 Е (0,1/2); р Е {3, 4,...}. Обычно интересуются асимптотическим поведением этой функции при k м то для каждого набора значений (p, 8, р). Наибольший интерес представляют алгоритмы, трудоёмкость которых полиномиально зависит от k, (1 — 2p)-1 и 8-1. Уточним понятие элементарной операции, необходимое для оценки трудоёмкости алгоритмов. Отметим, что в большинстве работ, посвящённых алгоритмам решения систем булевых уравнений с искажёнными правыми частями, тип используемых операций не оговаривается явно. Как правило, это операции над целыми числами или двоичными векторами произвольной длины. В настоящей работе элементарной называется любая двоичная операция (булева функция двух переменных), а также операция i м- i + 1, где i — произвольное целое число. Любые (не обязательно элементарные) операции называются условными. Остановимся подробнее на известных алгоритмах восстановления истинных решений систем уравнений (1). Наиболее естественный из них состоит в применении метода максимума правдоподобия и сводится к перебору всех k-мерных векторов веса р. Известно [1, теорема5.1], что для любых p Е (0,1/2), р Е {3,4,...} и m = (1 + ) log (k)/(1 — h(p)), где h(p) = —plogp — (1 — p) log(1 — p), lim > 0, метод максимума правдоподобия позволяет восстанавливать истинное решение СУ (1) с вероятностью, стремящейся к 1 при k м то. Нетрудно убедиться, что в этом случае трудоёмкость метода составляет O((1 — 2p)-2kklog k) элементарных операций, где O зависит только от р. В [2] предложен асимптотически более эффективный алгоритм, основная идея которого заключается в том, чтобы построить таблицы D и D', состоящие из векторов Ay и Az ф b соответственно, где y и z пробегают все k-мерные булевы векторы веса |_р/2] и |~р/2] соответственно, и применить к этим таблицам алгоритм решения задачи о ближайшей окрестности (approximate nearest neighbor problem), описанный в [4]. Последний позволяет с некоторой высокой вероятностью найти в таблицах векторы Ay0 и Az0 ф b, расположенные на определённом (не слишком большом) расстоянии Хэмминга. В [2] показано, что для любой последовательности положительных чисел ш1,ш2,..., сходящейся к +то, и произвольных p, 8 Е (0,1/2), р Е {3, 4,...} при всех достаточно больших k и m = |~р(1 — 2p)-2 log(k8-1)wk] истинное решение СУ (1) равно y0 ф z0 с вероятностью не менее 1 — 8. При этом для нахождения этого решения требуется O((1 — 2p)-2krp/2K1+4p2+ak(p)) log(k8-1 )wfc) условных операций, где lim (p) = 0 для любого p Е (0,1/2), а O зависит только от р (отметим, что в формулировках этого результата, приведённых в [2] (см. теорему 5 и следствие 1), имеются неточности и опечатки). Обратим внимание, что в [4] отсутствуют явные оценки надёжности алгоритма решения задачи о ближайшей окрестности, а в [2] ошибочно предполагается, что этот алгоритм всегда завершается успешно. Поэтому вопрос о том, с какой вероятностью алгоритм из [2] восстановит вектор x0, выполняя указанное выше количество операций, остаётся открытым. Отметим также, что алгоритм из [4] предназначен для решения задачи о ближайшей окрестности в евклидовом пространстве, а не в пространстве Хэмминга. В результате (при стандартном вложении второго пространства в первое) основная доля вычислений приходится на операции над вещественными числами. Последнее обстоятельство существенно усложняет программную реализацию алгоритма, который становится трудноприменимым на практике, если число неизвестных k заключено в пределах от нескольких сотен до нескольких тысяч, а вероятность p является величиной порядка 10-3. (Отметим, что к решению систем уравнений с такими параметрами приводит задача восстановления некоторых линейных кодов по наборам случайных кодовых слов, искажённых в двоичном симметричном канале связи [5].) В [3] предложен другой алгоритм восстановления вектора x0, основанный на быстром умножении некоторых целочисленных матриц, трудоёмкость которого для любых p Е (0,1/2), р Е {3, 4,...} и всех достаточно больших k, m (зависящих от p и р) ограничена сверху величиной po/y((1 — 2p)-1)k°'8p условных операций, где po/y — некоторый полином, не зависящий от параметров. Этот алгоритм интересен тем, что в оценке его трудоёмкости отсутствует зависимость от p в показателе степени числа k. Однако при указанных выше значениях k и p алгоритм из [3] практически не превосходит по эффективности метод максимума правдоподобия. При этом для его применения требуется существенно больший объём памяти. Целью настоящей работы является разработка алгоритма, имеющего меньшую трудоёмкость по сравнению с методом максимума правдоподобия, допускающего простую программную реализацию и позволяющего на практике восстанавливать истинные решения систем уравнений (1) от нескольких сотен или тысяч неизвестных, по крайней мере, при малых значениях p и р. Представленный ниже алгоритм базируется на той же идее, что и алгоритм из [2], но использует только операции сравнения и (поразрядного и арифметического) сложения двоичных целых чисел. Вместо решения задачи о ближайшей окрестности предложено проводить быстрый поиск пары близких векторов в таблицах D и D' по критерию совпадения их фрагментов в случайно выбранном множестве координат. Отметим, что эта идея используется в [6-8] и ряде других работ по теории информационного поиска. Получены оценки надёжности и трудоёмкости предложенного алгоритма. Приведены результаты вычислительных экспериментов, показывающие, что средняя трудоёмкость алгоритма заметно меньше её верхней границы в худшем случае. 1. Теоретические результаты В дальнейшем, если не оговорено противное, символ O обозначает некоторую положительную постоянную, не зависящую от каких-либо параметров. В частности, для любых функций ^ и —, определённых на некотором множестве X и принимающих вещественные значения, формула t ^ 1, получим отсюда, что ^ ^ . , , (1 — e)m — А Л ( / (1 — e)m — t4 * Рг(^) ^ 1 - (-)- ^ ex^ -/ ' ( ) mm -1\tl = exp{-/(1 - e - tm-1)*} . Покажем, наконец, что Рг(П4) ^ 2-tN. (10) Зафиксируем векторы y0 Е V(1), zo Е V(2), такие, что xo = yo 0 z0. Обозначим Uj(£, M) событие, состоящее в том, что i — наименьшее натуральное число от 1 до / со свойством Mj С N(£); V(A, Mj) — событие, состоящее в том, что случайный вектор a_my0 встречается в наборе (AMiy : y Е V(1)) не менее двух раз. Справедливо равенство Рг(О0 = Е Рг(^4 П Uj(£, М)). (11) j=1 Пусть происходит событие П4 П Uj(^, М). Тогда = 0 и вектор AMiz0 0 b_M = = a_my0 присутствует среди вторых компонент пар, записанных в таблице Dj. С другой стороны, поскольку алгоритм возвращает значение Out = «НЕТ», на i-м шаге в результате выполнения процедуры 2 определяется вектор y Е V(1), отличный от y0. Следовательно, происходит событие V(A, Mj). Итак, Рг(^4 П Uj(f,М)) ^ Рг(^4 П V(A,Mj)),i Е U (12) Далее, для любого фиксированного t-множества M С 1,m вероятность события V(A, M) = V(A, Mj) П {Mj = M} не превосходит среднего числа появлений нулевого вектора в наборе (AM(y ф y0) : y Е V(1)\{y0}), которое равно 2-t(N - 1). Отсюда на основании формул (11), (12) и независимости случайных элементов A,£ и M следует, что Pr(O0 ^ Е Е Pr(U*(£, M) П V(A, Мг) П {Mi = M}) = i=Z MC1,m: |M |=t = E Е Pr(Ui(£, M) П {Mi = M})Pr(V(A, M)) ^ i=Z MC1,m: |M | = t ^ 2-tN E ^ Pr(Ui(f, M) П {Mi = M}) = 2-tN E Pr(Ui(f, M)) ^ 2-tN. i=1 MC1,m: i=i |M | = t Итак, справедливо неравенство (10), что и требовалось доказать. Из оценок (6)-(10) непосредственно следует неравенство (5). ■ Исследуем асимптотическое поведение трудоёмкости алгоритма при k ^ то для каждого набора значений (p, 5, р). Теорема 2. Пусть 5, 5^ 52, 53, 54 —положительные числа, такие, что р положим t = max {[log(N51-1)] , [(1/2 - p)-1J + 1} ,e = p + t-1; (14) m = max{ [1/2 ■ t2 ln^-1)] , [1/2 ■ (1/2 - e)-2 1п(Ж25з-1)] , [t(1 - e)-1J + 1} ; (15) (1 - e - tm-1) * ln(54-1) 16) I Тогда предложенный алгоритм восстанавливает истинное решение СУ (1) с вероятностью не менее 1 - 5, а его трудоёмкость при k ^ то составляет T = O ((1 - 2p)-2krp/2l(1+log( 1-Р^logW2!) (17) элементарных операций, где O зависит только от 5j (j Е 1,4). Доказательство. Из соотношений (14), (15) следует, что параметры e и t удовлетворяют ограничениям, указанным в условии теоремы 1. Неравенство Рош ^ 5 вытекает непосредственно из формул (5) и (13)-(16). Убедимся в справедливости равенства (17) (на протяжении оставшейся части доказательства символ O обозначает некоторую постоянную, зависящую разве что от параметров 5j, j Е 1,4). Обозначим р = e + tm-1, C = 1 + 2/ln(52-1) и зафиксируем число k0 Е N, такое, что 1/2 ■ log k0 > max{C, 1 + (1/2 - p)-1}. Из определения параметров N и t вытекает, что для любого k ^ k0 справедливы следующие соотношения: 2(1+ (1/2 - p)-1) < log N ^ t = [log(N51-1)] ^ log(2N51-1). (18) Кроме того, согласно формуле (15), tm-1 ^ 2/(tln(52-1)), откуда следует, что для любого k ^ k0 р = p + t-1 + tm-1 ^ p + t-1 ( 1 + i /r2_ 1 ) ^ p + C ln(52-1^" log N Оценим сверху значение (1 - ц) * при k ^ k0. Заметим, что поскольку p < 1/2 и 1/2 ■ log N > C, то 1 - ц ^ 1 - p - c/log N ^ (1 - p) (1 - 2C/log N) > 0. Отсюда, используя верхнюю оценку параметра t из формулы (18), получим (1 - ц)- ^ (1 - p)-t ^ 1 - ^^ * = 2*!°g(1-p)-12*M1-2C/logN)-1 ^ ^ (2N^1-1)log(1-p)-1 (2N^1-1)log(1-2C/logN)-1 ^ ^ Nlog(1-p)-1 (2^1-1)(2N^1-1)log(1-2C/logN)-1. Наконец, применяя известное неравенство ln(1-x) ^ -x(1-x)-1, x Е (0,1), получим ln ((2N^1-1)log(1-2C/logN) ) = ln ( Г1 - j ^ 2C / 2C \-1 ^ log(2N^1-1^-2^— 1 -r^ = O(1), k —У то. 61 1 logNV logNJ V Итак, / = O ((1 - ц)-4) = O (nlog(1-p)-1) , k — то. (19) Далее, на основании соотношений (18) для любого k ^ k0 справедливы неравенства t(1/2 - p) > 2(1 + (1/2 - p)-1)(1/2 - p) > 2, из которых следует, что 1/2 - e =1/2 - p - t-1 = (1/2 - p)(1 - t-1(1/2 - p)-1) > 1/2 ■ (1/2 - p). Отсюда на основании формулы (15) получаем m = O((1/2 - p)-2 log2 N), k — то. (20) Кроме того, согласно формуле (14), t = log N + O(1),k — то. (21) Подставляя выражения в правых частях равенств (19)-(21) в формулу (3) и принимая во внимание соотношения N ^ N ^ k^2!, р^У ^ 1/2 ■ k^2, р Е 3, k - 1, получаем T = O(/N(t log N + рш)) = O ^N 1+log(1-p)-1 (1/2 - p)-2 log2 Nv) = = O ((1 - 2p)-2krP/2l(1+log(1-p)-1)log2krP/2l) , k — то. Итак, равенство (17), а вместе с ним и теорема полностью доказаны. ■ Замечание 1. Как видно из доказательства теоремы 2, при выполнении равенств (14)-(16) и = = = = 0,25$ трудоёмкость описанного алгоритма ограничена сверху полиномиальной функцией от —величины, обратной к верхней границе вероятности ошибки алгоритма. Вопрос о том, обладают ли указанным свойством алгоритмы, изложенные в [2, 3], в этих публикациях не обсуждается. Замечание 2. Трудоёмкость описанного алгоритма можно уменьшить, если при выполнении процедуры 1 хранить таблицу Di в «распределённом» виде, записывая по адресу A. У номер вектора y Е V(1) (в случае многократного обращения по одному и тому же адресу сохраняется последняя запись). При выполнении процедуры 2 для нахождения вектора y Е V(1) со свойством A.У = b(z).Mi достаточно обратиться в память по адресу ^(z). , z Е V(2) , i Е 1, / . Нетрудно видеть, что вероятность ошибки модифицированного таким образом алгоритма оценивается сверху по формуле (5). При этом его трудоёмкость составляет T = O(NV/pm) (22) элементарных операций, а объём используемой памяти — S = O(2*t + km) бит. (23) 2. Вычислительные эксперименты Описанный алгоритм (в модифицированном виде; см. замечание 2) реализован программно и применён к решению ряда систем уравнений с искажёнными правыми частями. Вычислительные эксперименты проводились на ЭВМ с процессором Intel Core i5-2450 (2,5 ГГц) и объёмом оперативной памяти 6 Гб RAM (DDR3) на базе Windows 7. При этом использовалась среда разработки Microsoft Visual C++ Studio 2008. В табл. 1 и 2 показаны типичные результаты, полученные в двух сериях экспериментов. Слева в таблицах приведены теоретические значения параметров t, e, / и m, logТ, log Т, рассчитанные при 51 = 52 = 53 = 54 = 0,255 по формулам (14)-(16) и (22), (23). Справа указаны значения параметров t', e', m', выбранные для проведения экспериментов, а также результаты, полученные в ходе их выполнения. Таблица 1 Сравнение теоретических и экспериментальных результатов (k = 200, р = 4, 5 = 0,1) p Теория Эксперимент t £ / m log T log Т t' £ 1ср max m' T с ср 0,005 20 0,055 21 738 30,20 24,33 20 0,055 1,15 3 600 0,0056 0,008 20 0,058 22 738 30,27 24,33 20 0,058 1,20 6 600 0,0082 0,010 20 0,060 23 738 30,33 24,33 20 0,060 1,27 6 600 0,0089 0,020 20 0,070 29 738 30,67 24,33 20 0,070 1,59 12 600 0,0215 0,050 20 0,100 57 738 31,64 24,33 20 0,100 2,66 20 600 0,0604 Для каждой пары значений (p, m'), приведённых в табл. 1 и 2, 225раз выполнялась следующая процедура: независимо друг от друга, случайно равновероятно генерировались m' х k -матрица A и вектор x0 веса р, по которым формировалась СУ вида (1) с искажениями в правой части, распределёнными по закону (2). Затем к полученной СУ применялся описанный выше (модифицированный) алгоритм с параметрами /, e' и t', значения которых приведены в таблицах. В результате выполнения алгоритма для каждой из 225 систем уравнений определялось фактическое число шагов (выбираемых множеств M, i Е 1, /) до нахождения оценки истинного решения этой системы. Таблица 2 Сравнение теоретических и экспериментальных результатов (k = 2000, р = 4, 5 = 0,1) p Теория Эксперимент t £ / m log T log S t' £' 1ср max m' ^с 0,005 27 0,042 21 1345 37,72 31,76 26 0,042 1,17 4 1000 19,516 0,008 27 0,045 23 1345 37,85 31,76 26 0,045 1,20 4 1000 21,312 0,010 27 0,047 25 1345 37,97 31,76 26 0,047 1,39 7 1000 30,572 0,020 27 0,057 33 1345 38,39 31,76 26 0,057 1,56 5 1000 43,866 0,050 27 0,087 79 1345 39,63 31,76 26 0,087 4,15 31 1000 153,721 Параметры /£р и /^ах в таблицах равны соответственно среднему арифметическому и наибольшему из этих чисел. В последней колонке табл. 1 и 2 приведено среднее время выполнения алгоритма в секундах (при этом надёжность восстановления истинных решений сгененированных СУ составляет 100%). Как видно из таблиц, значения /£р и /^ах заметно меньше теоретической верхней границы / количества шагов, выполняемых до нахождения оценки истинного решения СУ. Например, согласно табл. 2, истинное решение веса 4 системы из 1000 уравнений от 2000 неизвестных с вероятностью искажения в правой части p = 0,050 находится в среднем не более чем на пятом (а в худшем случае — на тридцать первом) шаге со 100 %-й надёжностью, в то время как теоретическое значение числа шагов / = 79 (при большем количестве уравнений m = 1345 и нижней границе надёжности алгоритма 90%). Среднее время восстановления решения такой СУ составляет около 2,5 мин. Экспериментально установлено, что параметры алгоритма могут быть выбраны в широком диапазоне в зависимости от ограничений относительно трудоёмкости и количества уравнений в системе. При этом на практике значения указанных параметров заметно меньше теоретических (при той же нижней границе надёжности). В табл. 3-5 приведены результаты сравнения предложенного алгоритма с методом максимума правдоподобия. Данные в табл. 3 получены следующим образом. Сначала экспериментальным путём для каждого значения p, указанного в таблице, были получены оценки m1 (p) и m2(p) наименьшего числа уравнений в (случайно сгенерированной) системе (1), при котором вероятность правильного восстановления её истинного решения с помощью метода максимума правдоподобия и соответственно предложенного алгоритма составляет не менее 90 %. Затем для каждого p 225 раз выполнялась процедура, в ходе которой к случайно сгенерированной СУ (1), состоящей из m2(p) уравнений, применялся предложенный алгоритм. Потом из этой СУ удалялись последние m2 (p) - m1 (p) уравнений и полученная система решалась методом максимума правдоподобия. Данные в табл. 4 и 5 получены аналогично, с тем отличием, что для каждого исходного значения p вместо 225 запусков процедуры выполнялось только 10. Последнее обстоятельство обусловлено заметным увеличением времени решения СУ методом максимума правдоподобия. Таблица 3 Сравнение алгоритмов решения систем с искажёнными правыми частями (k = 128, р = 4) p Метод максимума правдоподобия Предложенный алгоритм Среднее время выполнения, с Количество уравнений, mi(p) Среднее время выполнения, с Количество уравнений, m2(p) 0,005 3,6795 40 0,0008 56 0,008 3,6923 40 0,0027 56 0,010 3,8418 40 0,0072 56 0,020 3,9712 48 0,0113 160 0,050 5,8443 72 0,0453 200 Таблица 4 Сравнение алгоритмов решения систем с искажёнными правыми частями (k = 128, р = 5) p Метод максимума правдоподобия Предложенный алгоритм Среднее время выполнения, с Количество уравнений, mi(p) Среднее время выполнения, с Количество уравнений, m2(p) 0,005 94,48 40 0,0732 56 0,008 99,73 40 0,0899 56 0,010 105,96 40 0,0995 56 0,020 106,16 48 0,3466 72 0,050 136,60 72 1,4910 160 Таблица 5 Сравнение алгоритмов решения систем с искажёнными правыми частями (k = 128, р = 6) p Метод максимума правдоподобия Предложенный алгоритм Среднее время выполнения, с Количество уравнений, mi(p) Среднее время выполнения, с Количество уравнений, m2(p) 0,005 2056,94 40 0,4013 56 0,008 2154,86 40 0,4551 64 0,010 2138,73 40 0,4278 64 0,020 2197,63 48 0,7418 120 0,050 3691,22 72 2,7181 200 Как видно из таблиц, предложенный алгоритм в сотни (а в ряде случаев — в тысячи) раз превосходит по эффективности метод максимума правдоподобия, причём с ростом значения р это различие становится всё более заметным. В целом, предложенный алгоритм представляется более простым и эффективным с точки зрения программной реализации по сравнению с алгоритмами, описанными в [2, 3], и может быть применён на практике для восстановления истинных решений малого веса слабоискажённых систем линейных булевых уравнений от нескольких сотен или тысяч неизвестных. Авторы благодарны рецензенту за критические замечания, учёт которых позволил существенно улучшить качество работы, избежать неточностей в формулировках и усилить первоначальную версию теоремы 2.

Ключевые слова

система булевых уравнений с искаженной правой частью, вероятностный алгоритм. Введение, system of Boolean linear equations with noised right-hand side, probabilistic algorithm

Авторы

ФИООрганизацияДополнительноE-mail
Алексейчук Антон НиколаевичНациональный технический университет Украины (г. Киев)доктор технических наук, профессор Института специальной связи и защиты информацииalex-crypto@mail.ru. x67mail@gmail.com
Грязнухин Александр ЮрьевичНациональный технический университет Украины (г. Киев)аспирант Института специальной связи и защиты информацииx67mail@gmail.com
Всего: 2

Ссылки

Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике. М.: ТВП, 1997. T. 1. C. 1-18.
Grigorescu E., Reysin L., and Vempala S. On noise-tolerant learning of sparse parities and related problems // Proc. 22nd Intern. Conf. of Algorithmic Learning Theory. Berlin, Heidelberg: Springer Verlag, 2011. P. 413-424.
Valiant G. Finding correlations in subquadratic time, with applications to learning parities and juntas // Proc. 53rd Annual IEEE Symp. on the Foundations of Computer Science, New Brunswick, New Jersey, October 2-23, 2012. P. 11-20.
Andoni А. and Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimension // Proc. 47th Symp. on Foundations of Computer Science, Berkeley, California, October 21-24, 2006. P. 459-468.
Алексейчук А. Н., Грязнухин А. Ю. Метод восстановления систематических линейных кодов по наборам искаженных кодовых слов // Прикладная радиоэлектроника. 2013. T. 12. №2. С. 128-132.
Greene D., Parnas M., and Yao F. Multi-index hashing for information retrieval // Proc. 35th Annual IEEE Symp. on the Foundations of Computer Science, Santa Fe, New Mexico, November 20-22, 1994. P. 722-731.
Dolev D., Harari Y., and Parnas M. Finding the neighborhood of a query in a dictionary // Proc. 2nd Israel Symp. on Theory and Computing Systems, Natanya, Israel, June 7-9, 1993. P. 33-42.
Indyk P. and Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proc. Symp. on Theory of Computing. New York, NY, USA: ACM, 1998. P. 604-613.
Де Брёйн Н. Г. Асимптотические методы в анализе: пер. с англ. М.: ИЛ, 1961. 247 с.
Babbage S. H. Improved "exhaustive search" attacks on stream ciphers // European Convention on Security and Detection, Brighton, May 16-18, 1995. P. 161-166.
GolicJ. Cryptanalysis of alleged A5 stream cipher // Advances in Cryptology. Proc. EUROCRYPT'97. Springer Verlag, 1997. P. 239-255.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. М.: Мир, 1980. 476 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 535 с.
Ширяев А. Н. Вероятность: учеб. пособие для вузов. М.: Наука, 1989. 640 с.
 Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью | ПДМ. 2013. № 2(20).

Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью | ПДМ. 2013. № 2(20).

Полнотекстовая версия