WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«А. В. Быстрыгова В работе рассматривается задача параметроэффективной расшифровки линейных функций k-значной логики в рамках модели точной расшифровки. Получены точные значения сложности расшифровки ...»

Параметро-эффективная расшифровка

линейных функций k-значной логики

А. В. Быстрыгова

В работе рассматривается задача параметроэффективной расшифровки линейных функций k-значной

логики в рамках модели точной расшифровки. Получены

точные значения сложности расшифровки для малого

количества существенных переменных. Получены верхние

и нижние оценки для общего случая для двух типов

запросов: на значение и на сравнение. При стремлении

числа переменных к бесконечности получен порядок сложности расшифровки для обоих типов запросов .

Ключевые слова: точная расшифровка функций, линейные функции k-значной логики, запросы на значение, запросы на сравнение .

Введение На практике часто может возникнуть ситуация, когда нам дано некоторое устройство — “черный ящик”, про которое мы знаем некоторую частичную информацию, например, что оно принадлежит некоторому классу устройств, и нам хочется понять, что за устройство перед нами. При этом мы можем подавать на вход устройства некоторые сигналы и снимать с выходов устройства результат. Если такое устройство является конечным автоматом [1–11], то раздел науки, занимающийся анализом таких устройств называется эксперименты с автоматами [12–16]. При этом если у нас есть только одно такое А. В. Быстрыгова устройство, то эксперимент называется простым, и мы, подавая на вход устройства входные воздействия, понимаем, что его состояние меняется каждый такт. Если у нас имеются несколько копий устройства, то эксперимент называется кратным. Если исследуемое устройство является устройством без памяти, то необходимость в нескольких копиях отпадает. Раздел науки, занимающийся анализом устройств без памяти называется расшифровкой функций, а в зарубежной литературе Machine Learning (машинное обучение) .



Расшифровка функции — это игра между “учеником” (алгоритмом расшифровки) и “учителем”, в которой “учитель” загадывает функцию из класса, известного “ученику”, и тот должен за наименьшее количество запросов разрешенного вида разгадать функцию .

Наиболее известны две модели расшифровки функций: модель точной расшифровки (exact learning) [17–30] и модель вероятно примерно точной расшифровки (probably approximately correct leaning, PAC) [30–35] .

В модели точной расшифровки “ученик” должен точно расшифровать загаданную “учителем” функцию, то есть полностью восстановить таблицу значений функции, или если эта функция не дискретная, то восстанавливать ее с некоторой точностью (в этом случае этот процесс называется интерполяцией функции [36]). При вероятно примерно точной расшифровке “ученик” не может выбирать набор, значение функции на котором он хочет узнать. Он делает запрос к функции, а “учитель”, руководствуясь заранее определенным распределением вероятности на области определения функции, выбирает набор значений аргументов и выдает “ученику” пару: набор и значение функции на этом наборе. Цель “ученика” — восстановить вектор значений загаданной функции так, чтобы вероятность ошибки была небольшой .

Одной из первых рассматривалась задача расшифровки монотонных булевых функций. Эта же задача является наиболее полно решенной [18–21]. В работах [22–25] получено решение задачи расшифровки функции разбиения булевого куба на под

<

Параметро-эффективная расшифровка линейных функций k-значной логики

кубы. В работе [26] предлагается общий подход к параллельной параметро-эффективной расшифровке интервально-постоянных функций. Этот класс функций включает в себя, в частности, и монотонные функции и функции разбиения булевого куба на подкубы .



В работе [27] рассматривалась задача расшифровки пороговых функций, а в работах [28, 29] исследовалась задача расшифровки арифметических сумм монотонных конъюнкций. И, наконец, в работах [30–32] изучалась задача расшифровки линейных булевых функций .

О параметро-эффективной расшифровке говорят, если функции из загадываемого класса зависят от большого числа переменных, но известно, что загаданная функция зависит существенно от малого числа переменных, и сложность расшифровки зависит от числа существенных переменных (даже если это число неизвестно “ученику”) и слабо зависит от общего числа переменных (это число всегда известно “ученику”) .

В данной работе рассматривается задача параметроэффективной расшифровки линейных функций k-значной логики в рамках модели точной расшифровки. Задача рассматривается в двух вариантах:

1) “ученик” может задавать “учителю” запросы на значение:

подать “учителю” один набор, ответ на запрос: значение функции на этом наборе 2) “ученик” может задавать “учителю” запросы на сравнение:

подать “учителю” два набора, ответ на запрос: вернуть на каком наборе значение больше или сказать, что значения на обоих наборах равны .

В работах [37, 38] рассматривалась расшифровка функций ранжирования интернет поисковиков запросами на сравнение .

В работе [30] было получено, что сложность расшифровки линейных булевых функции f, существенно зависящей от p переменных, равна сложности расшифровки функции f, существенно зависящей от np переменных, а также в рамках модели точной расшифровки запросами на значение получены верх

<

А. В. Быстрыгова

ние оценки: ] log n[ для p = 1, 3] log n[2 для p = 2, 4] log n[3 для p = 3 .

В работах [30], [31], [32] была рассмотрена эта задача для произвольного p в рамках модели вероятно примерно точной расшифровки PAC. Для этой модели в работе [30] получена оценка O(p log n/p). В работе [31] получена оценка O(n1 p log n), если известно, что загаданная функция зависит от не более чем p переменных .

В работе [40] была рассмотрена задача расшифровки линейных булевых функций в рамках модели точной расшифровки запросами на значение, получена верхняя оценка сложности p log n + p .

В настоящей работе в рамках модели точной расшифровки получены оценки сложности расшифровки запросами на значение линейных булевых функций для случаев p = 2 и p = 3, отличающиеся от точного значения не более чем на 2, получены верхние и нижние оценки сложности параметро-эффективной расшифровки запросами на значение и запросами на сравнение линейных функций k-значной логики с нулевым свободным членом. При стремлении числа переменных к бесконечности получен порядок сложности расшифровки для обоих типов запросов .

Автор выражает благодарность д.ф.-м.н. профессору Э.Э.Гасанову за научное руководство и помощь в работе .





Основные понятия и формулировка результатов .

Пусть (k) — некоторый класс функций k-значной лоТогда n (k) (k) есть подкласс, состоягики (k щий из функций, зависящих от n переменных x0, x1,..., xn1 ;

p,n (k) n (k) есть подкласс, состоящий из функций от n переменных x0,..., xn1, существенно зависящих ровно от p переменных .

Под запросом на значение к функции f (k) будем понимать вектор (набор) a E n, E = {0, 1,..., k 1}. Под ответом на запрос на значение будем понимать значение f (a) .

Параметро-эффективная расшифровка линейных функций k-значной логики

–  –  –

Если в дальнейшем будем рассматривать задачу расшифровки запросами на значение, то будем в обозначениях дописывать индекс V, если запросами на сравнение, то C .

Под алгоритмом расшифровки будем понимать условный эксперимент, который последовательно генерирует запросы к функции в зависимости от ответов на предыдущие запросы .

Будем говорить, что алгоритм расшифровывает функцию f из n (k), если значения функции на наборах, сгенерированных условным экспериментом, однозначно определяют таблицу значений функции f при условии, что f n (k). Скажем, что алгоритм расшифровывает класс функций (k), если для любого n N он расшифровывает любую функцию из n (k) при условии, что он получает n в виде входного параметра. Обозначим множество алгоритмов расшифровки класса (k) через A((k)). Любой элемент множества A((k)) можно понимать и как единичный алгоритм, получающий n на вход, и как последовательность алгоритмов, такую что n-й алгоритм последовательности расшифровывает функции из n (k) .

Пусть A A((k)), f (k), тогда обозначим через (A, f ) число запросов на значение функции, требуемое алгоритму A для расшифровки функции f. Будем называть (A, f ) сложностью алгоритма A на функции f .

Положим

–  –  –

Алгоритм расшифровки, на котором достигается минимум — это такой алгоритм, который работает лучше других алгоритмов на самой плохой функции из класса .

–  –  –

Предложенные алгоритмы расшифровки заключаются в

1) нахождении существенных переменных xi, то есть при которых ci = 0

2) нахождении значений ненулевых коээфициентов ci .

Будем говорить, что алгоритм находит существенную переменную и коэффициент перед ней функции f из (k, n, p), если по значениям функции на наборах, сгенерированных алгоритмом, мы хотя бы для одной переменной функции f однозначно можем сказать, что она является существенной и знаем значение коэффициента перед ней. Обозначим множество алгоритмов, находящих существенную переменную и коэффициент перед ней для класса (k, n, p) через G((k, n, p)) .

Пусть A G((k, n, p)), f (k, n, p), тогда обозначим через µ(A, f ) число запросов на значение функции, требуемое алгоритму A для нахождения какой-либо существенной переменной и коэффициента перед ней функции f .

Положим

–  –  –

Если a — вещественное число, то через ]a[ или ceil(a) обозначим наименьшее целое не меньшее a, через [a] обозначим Параметро-эффективная расшифровка линейных функций k-значной логики

–  –  –

Теорема 1. Для любого натурального n, n 2, справедливы неравенства 2] log n[2 V (2, n, 2) 2] log n[1, причем если log n [log n] {0} (1/2, 1), то V (2, n, 2) = 2] log n[1 .

Теорема 2. Для любого натурального n, n 5, справедливы соотношения

–  –  –

Теорема 5. Для любых натуральных n, k, p (n 2, 1 p n/2, k 2) имеет место следующее неравенство V (k, n, p) p log2 (k 1) + p · log2 (n p + 1) log2 p .

Теорема 6. Для любых натуральных n, k, p (n 2, 1 p n/2, k 2) имеет место следующее неравенство C (k, n, p) p log2 (k 1) + p · log2 (n p + 1) log2 p .

–  –  –

Оценки сложности расшифровки запросами на значение линейных булевых функций от двух переменных Приведем сначала классическую мощностную нижнюю оценку .

Лемма 1 (мощностная нижняя оценка). Для любого класса функций (k), любого алгоритма A, расшифровывающего класс (k), для любого натурального n существует такая функция f из n (k), что V (A, f ) ] log2 |n (k)|[ .

Параметро-эффективная расшифровка линейных функций k-значной логики Доказательство. Любой запрос a = (a0, a1,..., an1 ) на значение функции разбивает множество функций (k)n на два подмножества: те функции, которые на наборе a принимают значение f (a), и те — которые на этом наборе принимают значение не f (a) .

Чтобы найти функцию, которую произвольным фиксированным алгоритмом трудно расшифровать, нам достаточно “прятать” искомую функцию в множестве большей мощности. В этом случае каждый запрос будет сокращать множество потенциальных функций в лучшем случае в 2 раза. И, значит, если число запросов будет меньше чем ] log |n |[, то расшифровываемая функция будет находиться в множестве мощности не менее 2, а, значит, еще не определена однозначно .

Лемма доказана .

Лемма 2. Для любого натурального n, n 2, справедлиlog n[2, причем если log n во неравенство V (2, n, 2) [log n] {0} (1/2, 1), то V (2, n, 2) 2] log n[1 .

Доказательство. Множество (2, n, 2) имеет мощность Cn = n(n 1)/2 = n /2 n/2. Так как при n 2 справедливо неравенство n2 /2 n/2 n2 /4, то с учетом леммы 1 имеем

–  –  –

Пусть B — некоторое подмножество множества переменных {x0, x1,..., xn1 }. Под запросом на множестве B будем понимать запрос значения функции f на наборе, в котором все переменные из B установлены в 1, а остальные в 0. Будем обозначать его f (B) .

Лемма 3. Если B {x0, x1, .

.., xn1 } и в B содержится нечетное число существенных переменных функции f из (2, n, p), то одну из существенных переменных множества B можно найти за не более ] log |B|[ запросов .

Доказательство. Разделим B произвольным образом на два непересекающихся множества B1 и B2, отличающиеся по мощности не более чем на 1. Запросим значение на B1. Если оно равно 0 (то есть в B1 четное число существенных переменных, а значит во множестве B2 нечетное), положим B = B2, иначе, положим B = B1. Затем опять разделим B на два множества и т.д, до тех пор пока B состоит из более чем одной переменной .

Получившееся в итоге множество B состоит из одной переменной, которая и является существенной. Поскольку каждый раз множество B делится надвое, то для нахождения существенной переменной потребуется не более ] log |B|[ запросов .

Лемма доказана .

Как следствие получаем следующий результат, ранее опубликованный в [30] .

Следствие 2. Для любого натурального n имеет место равенство V (2, n, 1) =] log n[ .

Доказательство. Согласно мощностной нижней оценке V (2, n, 1) ] log |(2, n, 1)|[=] log n[. С другой стороны, поскольку любая функция из (2, n, 1) имеет одну существенную переменную, то согласно лемме 3 ее можно найти не более чем за ] log n[ запросов .

Введем B i — подмножество переменных множества B, у которых в двоичном представлении номера переменной i-й бит Параметро-эффективная расшифровка линейных функций k-значной логики равен 1 (нумерация идет от младших значимых битов, начиная с 0) .

Например, пусть n = 8, B = {x1, x3,, x4 }. Тогда B 0 = {x1, x3 }, B = {x3 }, B 2 = {x4 } .

Лемма 4. Для любого натурального n, n 2, справедливо неравенство V (2, n, 2) 2] log n[1 .

Доказательство. Пусть B = {x0, x1,..., xn1 }. Запросим значение искомой функции f на множествах B i, i = 0, 1,..., ] log n[1, т.е. сделаем ] log n[ запросов .

Если на B i функция f равна 0, то в B i содержится четное число существенных переменных, т.е. в нашем случае либо 0, либо 2, и, значит, i-й бит в номерах обоих существенных переменных одинаков .

Если f (B i ) = 1, то в B i содержится нечетное число существенных переменных, что в нашем случае означает, что в B i содержится ровно одна существенная переменная. Следовательно, номера существенных переменных по i-му биту отличаются .

Поскольку номера существенных переменных отличны, то обязательно существует хотя бы один бит, на котором они отличаются. Пусть эти номера отличаются в p-м бите. Тогда f (B p ) = 1, и в B p содержится ровно одна существенная переменная. Согласно лемме 3 мы можем найти эту переменную за ] log |B p |[ запросов. Учитывая, что |B p | 2] log n[1, имеем, что на нахождение этой переменной мы потратим не более ] log n[1 запросов .

Остается заметить, что поскольку мы опросили значение функции f на каждом из запросов B i, то мы для каждого i {0, 1,..., ] log n[1} знаем совпадают ли i-е биты номеров существенных переменных. Тем самым, зная одну переменную, мы автоматически узнаем и вторую существенную переменную .

Таким образом, задав не более чем 2] log n[1 запросов, мы узнаем обе существенные переменные функции. Лемма доказана .

Теорема 1 является простым следствием лемм 2 и 4 .

–  –  –

Оценки сложности расшифровки запросами на значение линейных булевых функций от трех переменных Лемма 5. Для любого натурального n, n 5, справедливо неравенство V (2, n, 3) 3] log n[4, причем

1) если log n [log n] (1/3, 2/3], то V (2, n, 3) 3] log n[3;

2) если log n [log n] {0} (2/3, 1), то V (2, n, 3) 3] log n[2 .

Доказательство. Множество (2, n, 3) имеет мощность Cn = n(n 1)(n 2)/6 = n3 /6 n2 /2 + n/3. Так как при n 5 справедливо неравенство n3 /6n2 /2+n/3 n3 /8, то с учетом леммы 1 имеем ] log Cn [] log(n3 /8)[=]3 log n[3, V (2, n, 3) т.е .

V (2, n, 3) ]3 log n[2 .

Обозначим [log n] = m, c = log n m, c [0, 1), т.е. log n = m + c .

Если c = 0, то 3] log n[= 3m =]3 log n[ .

Если c (0, 1/3], то 3] log n[= 3m + 3, а ]3 log n[=]3m + 3c[= 3m + 1, т.е. ]3 log n[= 3] log n[2 .

Если c (1/3, 2/3], то 3] log n[= 3m + 3, а ]3 log n[=]3m + 3c[= 3m + 2, т.е. ]3 log n[= 3] log n[1 .

Если c (2/3, 1), то 3] log n[= 3m + 3, а ]3 log n[=]3m + 3c[= 3m + 3, т.е. ]3 log n[= 3] log n[ .

Лемма доказана .

Лемма 6. Для любого натурального n, n 3, справедливо неравенство V (2, n, 3) 3] log n[2 .

Доказательство. Пусть B = {x0, x1,..., xn1 }. Запросим значение f на B 0. Если f (B 0 ) = 1, положим C = B 0, иначе C = B \ B 0. В C содержится нечетное количество существенных переменных. Согласно лемме 3 одну из существенных переменных можно найти за ] log |C|[ запросов. Поскольку

Параметро-эффективная расшифровка линейных функций k-значной логики

|C| 2] log n[1, имеем, что для нахождения одной существенной переменной мы потратили не более ] log n[1 запросов .

Теперь применяя лемму 4 к B, найдем за не более 2] log n[2 запросов остальные существенные переменные (мы уже знаем значение f на B 0, поэтому не нужно заново запрашивать это значение, следовательно потребуется за один запрос меньше) .

Таким образом, задав не более 1+(] log n[1)+(2] log n[2) = 3] log n[2 запросов, мы узнаем все существенные переменные функции f .

Лемма доказана .

Теорема 2 является следствием лемм 5 и 6 .

Верхние оценки для общего случая .

Расшифровка запросами на значение .

Лемма 7. Если f (k, n, p), B {x1, .

.., xn }, f (B) = 0, то µ(k, n, p) ceil(log2 |B|) запросов на значение .

Доказательство. Разделим произвольным образом B на два множества B0, B1, отличающиеся по мощности не более чем на

1. Запросим значение f (B0 ). Если f (B0 ) = 0, положим B = B0, иначе B = B1. Будем продолжать делить, пока B состоит из более чем одной переменной .

Переменная, оставшаяся в B в итоге, и есть существенная, а коэффициент при ней в представлении f равен f (B) .

Каждый раз множество B сокращается по мощности в минимум два раза, поэтому потребуется ] log2 |B|[ запросов на значение .

Лемма 8. В каждом k – линейном коде G кодовое расстояние D равно весу его минимального ненулевого элемента: D = ming=0,gG ||g|| .

Доказательство. Кодовое расстояние не больше веса минимального ненулевого элемента, так как (0,..., 0) G. Покажем, что D не может быть строго меньше этого числа .

А. В. Быстрыгова

Доказывать будем от противного. Пусть D ming=0,gG ||g|| .

Значит, существуют g1, g2 G такие, что d(g1, g2 ) ming=0,gG ||g||. Имеем, d(g1, g2 ) = ||g1 g2 ||, g1 g2 G. Получается, ||g1 g2 || ming=0,gG ||g||. Противоречие .

Отсюда следует, что D = ming=0,gG ||g|| .

Лемма 9. Для того, чтобы матрица H была проверочной матрицей k – линейного кода с кодовым расстоянием D необходимо и достаточно, чтобы любые D1 столбцов матрицы H были линейно независимы .

Доказательство. Докажем необходимость. Пусть H - проверочная матрица k - линейного кода G с кодовым расстоянием D .

Если в матрице H линейная комбинация столбцов hi1, hi2,..., his 1 hi1 2 hi2... s his = 0, где i = 0, то Hv = 0 для v, у которого компоненты с номерами i1, i2,..., is соответственно равны 1, 2,..., s, а остальные компоненты равны

0. Получается, v G, по лемме 8 следует s D. Значит, любая нетривиальная комбинация из меньше чем D столбцов будет линейно независима. Необходимость доказана .

Докажем достаточность. Пусть любые D 1 столбцов матрицы H линейно независимы. Тогда произведение матрицы H и любого ненулевого вектора v с не более чем D 1 ненулевыми компонентами не равно нулевому вектору. Заметим, что нулевое пространство матрицы H и будет k - линейным кодом с кодовым расстоянием не меньшим D. Достаточность доказана .

Лемма 10. Если числа n, m 1, D 1, k 2 удовлетворяют неравенству 2m D1 · (k 1)D1, то существует проверочn1 mn ная матрица H E2 k – линейного кода с расстоянием D + 1 .

Доказательство. В качестве первого столбца выберем любой m вектор из E2. Предположим, что уже выбраны первые j n столбцов матрицы так, что любые D из них линейно независимы. Есть D1 · (k 1)D1 способов выбрать линейную комj бинацию из D 1 столбцов из них. Поэтому в качестве j + 1 Параметро-эффективная расшифровка линейных функций k-значной логики

–  –  –

Лемма 11. Пусть A1, A2, .

.., Am - строки проверочной матmn рицы H E2 с кодовым расстоянием p + 1, f (k, n, p) .

Тогда f можно расшифровать за не более m + p] log2 n[ запросов на значение .

Доказательство. Пусть c = (c1, c2,..., cn ), где ci – коэффициенты в представлении f. Заметим, что Hc = (f (A1 ),..., f (Am ))T .

Узнаем значения f (A1 ), f (A2 ),..., f (Am ). Так как у вектора c ровно p ненулевых компонент, то по определению проверочной матрицы Hc = 0. То есть существует r такой, что f (Ar ) = 0 .

Воспользуемся леммой 7 и за не более ] log2 n[ запросов на значение найдем существенную переменную xi и коэффициент ci перед ней в представлении f. Далее положим f = f ci · xi и получим задачу с меньшим числом существенных переменных и аналогично будем находить одну за одной существенные переменные, пока не найдем все. Только запрашивать заново f (A1 ), f (A2 ),..., f (Am ) ненужно, можно восстановить ответы на новые запросы на основе номеров и коэффициентов уже разгаданных существенных переменных. Итого, будет сделано не более m + p] log2 n[ запросов на значение для расшифровки f .

Докажем теорему 3

–  –  –

Положим m = 1+] log2 S[. По лемме 10 существует проверочная матрица с m строками и n столбцами с кодовым расстоянием p+

1. По лемме 11 по построенной в лемме 10 проверочной матрице можно расшифровать f за не более m + p] log2 n[ 1 + (p 1) · (] log2 (k 1)[+] log2 (n 1)[) + p] log2 n[ запросов на значение .

Расшифровка запросами на сравнение .

Известно, что f (k, 1, 1), f = q·x. Узнаем значение на следующих запросах на сравнение (2i, 2i+1 ), i = 0,..., ceil(log2 k) 1 .

Под операцией будем понимать обычное умножение чисел .

Лемма 12. Если k 2, то по ответам на указанные выше ceil(log2 k) запросов коэффициент q восстанавливается однозначно .

Доказательство. Докажем от противного. Пусть существуют a и b (0 a b k), для которых все ответы на указанные выше запросов совпали .

Докажем индукцией по номеру запроса, что 0 2i (ba) k и a · 2i b · 2i .

База индукции. i = 0 .

0 20 (b a) k и a b .

–  –  –

Пусть ответ на запрос (20, 21 ) равен 0. Тогда a = 2 · a, b = 2 · b = a = b = 0 = Противоречит тому, что a b, значит такого ответа на запрос не может быть .

–  –  –

Значит для любого i = 0,..., ceil(log2 k) верно 0 2i (ba) k .

Но с другой стороны, так как a b = 2ceil(log2 k) (b a) k .

Противоречие. Следовательно, не найдутся такие a, b (a b), что ответы для них полностью совпали .

Поэтому по ответам на указанные выше ceil(log2 k) запросов коэффициент q восстанавливается однозначно .

Докажем теорему 4

Доказательство. Для нахождения номеров существенных переменных воспользуемся теоремой 3 со следующим изменениям: вместо запроса на значение f (a) будем делать запрос на сравнение (a, (0... 0)) Заметим, что везде в процессе расшифровки запросами на значение было важно только то, что ответ на запрос отличен от нуля или нет, поэтому замена запроса на

Параметро-эффективная расшифровка линейных функций k-значной логики

значение таким запросом на сравнение это свойство ответов на запросы не изменит .

Но теорема 3 найдет нам только номера существенных переменных. Для k = 2 этого достаточно, чтобы считать, что алгоритм расшифровал функцию. Но для k 2 недостаточно. Поэтому для k 2 применяя лемму 12 к каждой существенной переменной, найдем коэффициенты перед ними .



Итого, потратим 1 + (p 1) · (] log2 (k 1)[+] log2 (n 1)[) + p] log2 n[ запросов на сравнение на нахождение номеров существенных переменных и для k 2 еще p · ceil(log2 k) запросов на сравнение на нахождение значений коэффициентов перед существенными переменными .

–  –  –

Расшифровка запросами на сравнение .

Приведем классическую мощностную нижнюю оценку .

Лемма 13 (мощностная нижняя оценка). Для любого класса функций (k), любого алгоритма A, расшифровывающего класс (k), для любого натурального n существует такая функция f из n (k), что C (A, f ) ] log2 |n (k)|[ .

–  –  –

Список литературы [1] Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Издательство «Наука», Москва, 1985 .

[2] Алешин С.В. Полугруппы и группы автоматов // Интеллектуальные системы. — 2013. — Т. 17, вып. 1–4. — С .

129–141 .

[3] Иванов И.Е. О некоторых свойствах автоматов с магазинной памятью // Интеллектуальные системы. — 2014. — Т. 18, вып. 1. — С. 243–252 .

Параметро-эффективная расшифровка линейных функций k-значной логики

[4] Часовских А.А. Условия полноты линейно-p-автоматных функций // Интеллектуальные системы. — 2014. — Т. 18, вып. 3. — С. 203–252 .

[5] Александров Д.Е. Об оценках автоматной сложности распознавания классов регулярных языков // Интеллектуальные системы. — 2014. — Т. 18, вып. 4. — С. 161–190 .

[6] Гасанов Э.Э. Прогнозирование периодических сверхсобытий автоматами // Интеллектуальные системы. — 2015. — Т. 19, вып. 1. — С. 23–34 .

[7] Иванов И.Е. О сохранении периодических последовательностей автоматами с магазинной памятью с однобуквенным магазином // Интеллектуальные системы. — 2015. — Т. 19, вып. 1. — С. 145–160 .

[8] Летуновский А.А. Выразимость линейных автоматов относительно расширенной суперпозиции // Интеллектуальные системы. — 2015. — Т. 19, вып. 1. — С. 161–170 .

[9] Гербус В.Г. О связи функций автомата и автоматной функции // Интеллектуальные системы. — 2015. — Т. 19, вып .

2. — С. 109–116 .

[10] Миронов А.М. Критерий реализуемости функций на строках вероятностными автоматами Мура с числовым выходом // Интеллектуальные системы. — 2015. — Т. 19, вып. 2. — С. 149–160 .

[11] Терехина И.Ю. Модель невлияния для квантовых автоматов // Интеллектуальные системы. — 2015. — Т. 19, вып. 2 .

— С. 183–190 .

[12] Пантелеев П.А. Об отличимости состояний решетчатых автоматов // Интеллектуальные системы. — 2004. — Т. 8, вып. 1–4. — С. 529–542 .

[13] Кирнасов А.Е. Об отношении сложностей условного и безусловного установочного экспериментов // Интеллектуальные системы. — 2005. — Т. 9, вып. 1–4. — С. 433–444 .

А. В. Быстрыгова

[14] Уваров Д.В. О сложности кратных диагностических экспериментов для подмножеств состояний автоматов // Интеллектуальные системы. — 2005. — Т. 9, вып. 1–4. — С .

485–504 .

[15] Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез автоматов по их поведению // Интеллектуальные системы. — 2006. — Т. 10, вып. 1–4. — С. 345–448 .

[16] Пантелеев П.А. Об отличимости состояний автомата при искажениях на входе // Интеллектуальные системы. — 2007. — Т. 11, вып. 1–4. — С. 653–678 .

[17] Angluin D. Queries and Concept Learning // Machine Learning. Vol. 2. 1988. P. 319–342 .

[18] Ансель Ж. О числе монотонных булевых функций n переменных. — Кибернетический сборник, новая серия, вып. 5, 1968, С. 53–57 .

[19] Sokolov N.A. (1982). On the optimal evaluation of monotonic Boolean functions // USSR Computational Mathematics and Mathematical Physics, Volume 22, Issue 2, 1982, Pages 207Damaschke, P. (2003). On Parallel Attribute-Ecient, Learning // Journal of Computer and System Sciences, Volume 67, Issue 1, August 2003, 46-62 .

[21] Осокин В. В. О расшифровке монотонных булевых функций с несущественными переменными // Дискретная математика, 22:3 (2010), 134–145 .

[22] Осокин В.В. Асимптотически оптимальный алгоритм расшифровки разбиения булевого куба на подкубы // Интеллектуальные системы. — 2007. — Т. 11, вып. 1–4. — С .

635–652 .

[23] Осокин В. В. О сложности расшифровки разбиения булевого куба на подкубы // Дискретная математика, 20:2 (2008), 46–62 .

Параметро-эффективная расшифровка линейных функций k-значной логики

[24] Воронин Б.В., Осокин В.В. О сложности расшифровки существенных переменных функции, задающей разбиение булевого куба // Интеллектуальные системы. — 2008. — Т .

12, вып. 1–4. — С. 159–178 .

[25] Осокин В.В. О параллельной расшифровке разбиений булевого куба // Интеллектуальные системы. — 2009. — Т .

13, вып. 1–4. — С. 427–454 .

[26] Осокин В.В. О параллельной параметро-эффективной расшифровке псевдо-булевских функций // Интеллектуальные системы. — 2010. — Т. 14, вып. 1–4. — С. 429–458 .

[27] Zolotykh N.Yu., Shevchenko V.N. (1997). Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries // ALT’98, Otzenhausen, Germany, October 8-10, 1998 .

[28] Nakamura A., Abe N. (1995) Exact learning of linear combinations of monotone terms from function value queries // Theoretical Computer Science, Volume 137, Issue 1, 159-176, 1995 .

[29] Гасанов Э.Э., Ниязова З.А. Расшифровка арифметических сумм малого числа монотонных конъюнкций // Материалы XI Международного семинара Дискретная математика и ее приложения (Москва, 18-23 июня 2012 г.). — Изд-во механико-математического ф-та МГУ Москва, 2012. — С .

335–337 .

[30] Ryuhei Uehara, Kensei Tsuchida, and Ingo Wegener .

Optimal Attribute-Ecient Learning Of Disjunction, Parity, And Threshold Functions // EuroCOLT ’97 Proceedings of the Third European Conference on Computational Learning Theory, 1997 .

[31] Adam R. Klivans, Rocco A. Servedio. Toward Attribute Ecient Learning of Decision Lists and Parities // The Journal of Machine Learning Research Volume 7, 2006 .

А. В. Быстрыгова

[32] Vitaly Feldman. On Attribute Ecient and Non-adaptive Learning of Parities and DNF Expressions // The Journal of Machine Learning Research Volume 8, 2007 [33] Valiant L. G. A theory of the learnable // ACM Press New York, NY, USA, 1984, Volume 27, Issue II, 1134-1142 .

[34] Blum A. Learning a Function of r Relevant Variables // COLT 2003, Open problems .

[35] Агре J., Reischuk В. Learning Juntas in the Presence of Noise // Theoret. Comput. Sci. 384(1): 2-21, 2007 .

[36] Костюченко О.В. Сплайновая интерполяция с плавающими узлами // Интеллектуальные системы. — 2007. — Т. 11, вып. 1–4. — С. 715-720 .

[37] Гасанов Э.Э. Расшифровка линейных функций ранжирования // Материалы XI Международного семинара "Дискретная математика и ее приложения посвященного 80-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2012 г.). Изд-во мех-мат фак-та МГУ. 2012. C. 332Хегай С.И. Расшифровка полиномиальных функций ранжирования // Интеллектуальные системы. 2015. 19:1. 213 – 230 .

[39] Быстрыгова А.В. Сложность расшифровки линейных булевых функций // Интеллектуальные системы, 2015, Т. 19, Вып. 3, C. 101-126 [40] Thomas Hofmeister An Application of Codes to AttributeEcient Learning // EuroCOLT’99 Proceedings of the 4th European Conference on Computational Learning Theory, 1999 .

[41] Чашкин А.В. Лекции по дискретной математике. Учебное пособие // МГУ им.М.В.Ломоносова, Мех.-мат. факультет, Москва, 2007 .






Похожие работы:

«ОПИСАТЕЛЬНЫЙ ОТЧЁТ о работе негосударственного учреждения дополнительного образования специализированной детско-юношеской школы олимпийского резерва "Нефтяник" . Специализированная детско-юношеская школа олимпийского резерва "Нефтяник", учредителем которой является объединенная профсоюзна...»

«А. М. Яковлева (Москва) КЛИПОВОЕ ЧТЕНИЕ: ТЕКСТ КАК ИЗОБРАЖЕНИЕСИМУЛЯКР МОЛЧАНИЕ СЛОВА Феномен клипового сознания изучается сегодня активно, но чаще всего слишком в общих чертах, как бы глядя в телескоп, или же речь идет собственно о видеоклипах. Представляется целесообразным обратить вн...»

«Муниципальное бюджетное учреждение дополнительного образования "Центр развития творчества детей и юношества им. А. Гайдара" Принята Утверждаю на заседании педагогического совета Директор МБУ ДО ЦРТДиЮ протокол от им. А. Гайдара _ Е.В. Жиганова ""20_г. № _ "" _ 20 _ г. Приказ...»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ Ханты-Мансийский автономный округ-Югра Комитет образования администрации Березовского района Муниципальное бюджетное учреждение дополнительного образования ИГРИМСКИЙ ЦЕНТР ТВОРЧЕСТВА (МБУ ДО ИЦТ) РАССМОТРЕНО УТВЕРЖДЕНО на зас...»

«Оглавление № п/п Содержание Стр. Введение 6 Целевой раздел I 11 Пояснительная записка 1.1. 11 Цели и задачи реализации коррекционной 1.2. 13 программы по преодолению ОНР у детей в ДОУ Принципы построения программы 1.3. 14 Характеристика особенностей речевого 1.4. 20 развития детей с ОНР Планируемые ре...»

«Организация Объединенных Наций CEDAW/C/GC/31/CRC/C/GC/18 Конвенция о ликвидации всех Distr.: General форм дискриминации в 14 November 2014 отношении женщин Russian Original: English Комитет по ликвидации дискриминаци...»

«ЛИТЕРАТУРА 7 класс МОСКВА • "ВАКО" УДК 372.882 ББК 74.268.3 К64 Книга подготовлена совместно с ООО "Парус" . Контрольно-измерительные материалы. ЛитеК64 ратура: 7 класс / Сост. Е.Н. Зубов...»

«Ахаева Наталья Васильевна Индивидуализация процесса обучения как фактор развития личности учащихся в условиях сельской школы 13.00.01 Общая педагогика АВТОРЕФЕРАТ Диссертация на соискание ученой степени кандидата педаго...»

«ramki_dlya_kursovogo_proekta.zip Жилистая наливка комплекта ужели должна приделывать 1 г. Ворсовые нутации mediaget: толчея сяких эвкалиптов расстегаев регулировок рукоятки либо фотокамер на пк; маскировочное льдообразование во вкопанном плеере; биоценоз да...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.