О расшифровке логических функций

Осокин, Виктор Владимирович

О расшифровке логических функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Осокин, Виктор Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «О расшифровке логических функций»

Автореферат диссертации на тему "О расшифровке логических функций"

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

4846879

На правах рукописи УДК 519.71

Осокин Виктор Владимирович О РАСШИФРОВКЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

1 9 МАЙ 2011

МОСКВА - 2011

4846879

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель - доктор физико-математических наук, профессор

Эльяр Эльдарович Гасанов

Официальные оппоненты:

доктор физико-математических наук, профессор Александр Александрович Михалев кандидат физико-математических наук Денис Владимирович Зайцев

Ведущая организация — Московский Энергетический Институт

(Технический университет)

Защита диссертации состоится 10 июня 2011 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 27 апреля 2011 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О.Иванов

Общая характеристика работы

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

- активный учитель: ученик может сам выбирать, какие вопросы задавать учителю. Учитель отвечает на вопросы ученика. В прикладной среде такой подход называется классификацией с активным учителем (обучение у активного учителя);

- пассивный учитель: ученик никак не влияет на учителя, учитель сам генерирует возможные вопросы ученика и сам же отвечает на них. Другими словами, учитель генерирует примеры с ответами, и ученик должен обучиться по ним. В прикладной среде такой подход называется классификацией с пассивным учителем (обучением у пассивного учителя);

- учитель отсутствует. Ученик получает некоторое множество данных, выделяет в нем какие-либо закономерности и в соответствии с этими закономерностями разбивает множество на классы, такие что в одном классе содержатся «похожие» друг на друга элементы. В прикладной среде такой подход называется кластеризацией.

В диссертации исследуется сложность расшифровки дискретных функций из различных классов при активном учителе в модели точной расшифровки при помощи запросов на значение функции (Д.Англуин1, Е.Н.Гильберт 2, В.К.Коробков3). Задачу расшифровки псевдо-булевских функций можно рассматривать как задачу расшифровки автоматов без памяти, т.е. как частную подзадачу более общей задачи расшифровки автоматов4. Модель точной расшифровки — это модель расшифровки, в которой

1D.Angluin Queries and Concept Learning, Machine Learning, Vol. 2, pp. 319-342,1988.

2E.N.GilbertIaitice theoretic properties of frontal switching functions, J. Math. Phys., 33 (1954), S7-97

3В.К.Коробков 0 монотонных функциях алгебры логики, Проблемы кибернетики, 13, 5-28,1965

4В.Б.Кудрявцев, С.В.Алешин, А.С.Подколзин Введение в теорию автоматов, НАУКА, М., 1985

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

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

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

Пример 2. Распознавание речи и другие задачи распознавания, в которых «правильные ответы» учителя стоят очень дорого. Использование подхода с активным учителем позволяет минимизировать число запросов к учителю путем их оптимального выбора.

Пример 3. Задачи поиска, в частности, поиска в интернете. Уже несколько лет ведущие поисковые системы «расшифровывают» собственные функции ранжирования страниц сайтов в попытке сделать их наиболее точными. В данном случае расшифровка с активным учителем -снова единственная возможность: подбираются конкретные запросы (поисковые запросы) и ответы поисковых систем на них и только по

5P.Damaschke On Parallel Attribute-Efficient Learning, Journal of Computer and System Sciences, Volume 67, Issue 1, August 2003, 46-62

этим запросам специально обученные люди оценивают соответствие запросов и ответов (т.е., функцию ранжирования).

В описанных прикладных задачах существенную роль играют следующие два фактора.

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

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

Неполный список исследований, проведенных в точности в рамках модели точной расшифровки при помощи запросов на значение функции, но не рассматривающих ни задачу параметро-эффективной расшифровки, ни задачу параллельной расшифровки, включает в себя следующие: С.Чой и др.6, В.Торвик 7, Е.Борос и др.8, Н.Ю.Золотых, В.Н.Шевченко9, Б.Ковалерчук и др.10, А.Накамура и др.11, К.Макино и др.12, Д.Н.Гайнанов13, Н.А.Соколов14.

Некоторые общие результаты по сложности параметро-эффективной (но не параллельной) расшифровки в модели точной расшифровки

6S.Choi, K.Jung, J.Kirn Almost Tight Upper Bound ¡or Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions, COLT 2008, 123-134

7V.I.Torvik Data Mining and Knowledge Discovery: a Guided Approach based on Monotone Boolean Functions, Ph.D. in Engineering Science, May 24, 2002, Louisiana State University

sE.Boros, P.Hammer, T.Ibaraki, K.Kawakami Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle, SIAM Journal on Computing, Volume 26, Issue 1, 93-109, 1997

9N.Yu.Zolotykh, V.N.Shevchenko Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries, ALT'98, Otzenhausen, Germany, October 8-10, 1998

1DB.Kovalerchtick, E.TYiantapliyllou, A.S.Deshpande, E.Vityaev Interactive learning of monotone Boolean function's, Information Scienccs: an International Journal, Volume 94, Issue 1-4, 87 - 118, 199S

"A.Nakainura, N.Abe Exact learning of linear combinations of monotone terms from function value queries, Theoretical Computer Science, Volume 137, Issue 1,159-176,1995

12K.Makino, T.Ibaraki The maximum latency and identification of positive Boolean functions. SIAM Journal on Computing, Volume 26, Issue 5, 1363 - 1383, 1997

1аД.Н.Гайнанов Об одном, критерии оптимальности алгоритма расшифровки монотонных булевых функций, USSR Computational Mathematics and Mathematical Physics, Volume 24, Issue 4, 1985, Pages: 176-181

"Н.А.Соколов On the optimal evaluation of monotonic Boolean functions, USSR Computational Mathematics and Mathematical Physics, Volume 22, Issue 2, 1982, Pages 207-220

при помощи запросов на значение функции получены Н.Бшаути и др.15. И.Вегенер и др.16 получили точные оценки сложности параметро-эффективной расшифровки некоторых классов булевских функций в этой модели.

Параллельная (но не параметро-эффективная) расшифровка в модели точной расшифровки при помощи запросов на значение функции исследовалась Н.Бшаути17. Наконец, параллельная параметро-эффективная расшифровка в этой модели рассматривалась в работах П.Дамашке18,19.

В большинстве упомянутых работ рассматривается расшифровка булевских функций. В настоящей диссертации исследована задача параллельной параметро-эффективной расшифровки псевдо-булевских функций. Основные свойства псевдо-булевских функций описаны в работе Е.Борос, П.Хаммер20. Некоторые классы псевдо-булевских функций описаны в работе С.Фолдс, П.Хаммер21.

Параметро-эффективная расшифровка (иначе, расшифровка хунт) исследовалась в рамках нескольких моделей стимулирующего обучения и обучения с учителем. Параметро-эффективный алгоритм расшифровки пороговых функций в рамках модели ограниченной ошибки стимулирующего обучения предложил Н.Литтлстоун22. Впоследствии различные аспекты параметро-эффективной расшифровки рассматривали А.Блюм и др.23. Пассивное обучение с учителем, т.е. расшифровка по случайной выборке обычно изучается в рамках так называемой модели вероятно примерно точной расшифровки24. Параметро-эффективная расшифровка по случайной равномерно распределенной выборке в РАС модели является открытой проблемой25. Для ознакомления с недавними результатами по пассивной

15N.Bshouty, L.Hellerstein Attribute efficient learning in query and mistake-bound models, Journal of Computer and System Sciences, 56: 310-319, 1998

16R.Uehara, K.Tsuchida, I.Wegener Optimal attribute-efficient learning of disjunction, parity, and threshold functions, Lecture Notes In Computer Science; Vol. 1208, 1997

"N.Bshouty Exact learning of formulas in parallel, Machine Learning. Volume 26. Issue I, 25-41,1997

l8P.Damaschke Adaptive uersus nonaiiapti™ attribute-efficient learning,Machine Learning 41 (2000), 197215

19P.Damaschke Parallel Attribute-Efficient Learning of Monotone Boolean Functions, Lecture Notes in Computer Science, Algorithm Theory - SWAT 2000, 473-479

20E.Boros, P.Hammer Pseudo-boolean optimization, Discrete Applied Mathematics, Volume 123, Issue 1-3, 155-225, 2002

slS.Foldes, P.Hammer Monotone, Horn and Quadratic Pseudo-Boolean Functions, J. UCS, Volume 6, Number 1, 97-104, 2000

22N.Littlestone Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm, Machine Learning, 2(4): 285-318, 1987

23A.Blum, L.Hellerstein, N.Littlestone Learning in the presence of finitely or infinitely many irrelevant attributes, Journal of Computer and System Sciences, 50: 32-40,1995

24L. Valiant A theory of the learnable, ACM Press New York, NV, USA, Volume 27, Issue II, 1134-1142

25A.Blum Learning a Function of r Relevant Variables, COLT 2003, Open problems

расшифровке хунт см. Д.Арпе и др.26, М.Колоунтзакис и др.27, Е.Моссель и др.28. Параллельную расшифровку рассматривали Д.Бальказар и др.29, Д.Виттер и др.30.

Среди направлений, близких к рассматриваемому направлению расшифровки функций, можно выделить теорию тестового распознавания31'32.

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

Научная новизна. Исследования, проведенные в данной диссертации, направлены на изучение обычной, параметро-эффекгивной и параллельной сложности алгоритмов расшифровки булевских монотонных функций, псевдо-булевских монотонных функций, интервально-постоянных функций, разбивающих функций, полных разбивающих функций, симметрических интервально-постоянных функций, пороговых функций и дизъюнкций переменных. Также исследована связь между сложностью расшифровки функций и сложностью определения их существенных переменных.

Впервые предложены аналоги шенноновской функции для сложности параметро-эффективной и параллельной расшифровки, позволяющие строить оптимальные алгоритмы расшифровки.

В работе получены следующие результаты.

26J.Arpe, B.Reischuk Learning Juntas in the Presence of Noise, Theoret. Comput. Sci. 384(1): 2-21, 2007

27M.KoIountzakis, E.MarkaJds, A.Mehta Learning Symmetric Juntas in Time In the proceedings of "Interface between Harmonic Analysis and Number Theory 2005"

28E.Mossel, R.O'Donnell, R.Servedio Learning juntas, In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

20J.L.Balcazar, J.Diaz, R.Gavalda, O.Watanabe An optimal parallel algorithm for learning DFA, Proceedings of the seventh annual conference on Computational learning theory, 208-217,1994

30J.S.Vitter, J.Lin Learning in Parallel, Inf. Comput. 96(2): 179-202, 1992

31В.Б.Кудрявцев, А.Е.Андреев, Э.Э.Гасанов Теория тестового распознавания, ФИЗМАТЛИТ, М., 2007

32В.Б.Кудрявцев, Э.Э.1Ъсанов, О.А.Долотова, Г.Р.Погосян Теория тестирования логических устройств, ФИЗМАТЛИТ, М., 2006

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

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

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

Основные методы исследования. В работе используются методы дискретного анализа и теории сложности.

Теоретическая и практическая ценность работы. Работа имеет теоретический характер и может быть полезна специалистам по расшифровке функций, специалистам по теории алгоритмического обучения, по теории автоматов и их приложений.

Апробация работы. Результаты настоящей работы докладывались

• на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (2006г.),

• на IX Международном семинаре «Дискретная математика и ее приложения» (2007г.),

• на Международной конференции «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика В.А.Садовничего (2009г.),

• на Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009», «Ломоносов-2010», «Ломоносов-2011» (2009, 2010, 2011гг.). На конференции «Ломоносов-2011» награжден дипломом за лучший доклад на секции «Математика и Механика».

• на Международном семинаре «Дискретная математика» (2010г.)

• на семинаре «Вопросы сложности алгоритмов поиска» под руководством профессора Э. Э. Гасанова, 2005-2010 гг. (неоднократно);

• на научно-исследовательском семинаре кафедры Математической теории интеллектуальных систем «Теория автоматов», 2008-2010 гг. (неоднократно);

• на семинаре «Кибернетика и информатика» под руководством профессора В.В.Кудрявцева, МГУ им.М.В.Ломоносова, 2010-2011 гг. (неоднократно);

Публикации по теме диссертации. Основные результаты диссертацииопубликовайыввосьми^ и материалах конференций [9]-[14], список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения и трех глав. Объем диссертации 117 стр. Список литературы содержит 37 наименований.

Краткое содержание работы

В диссертации мы используем следующие обозначения для классов функций. Пусть Ф — некоторый класс функций. Тогда Ф" С Ф есть подкласс, состоящий из функций от п переменных rci,..., хп\ Ф*'п С Ф" есть подкласс, состоящий из функций от п переменных xi,...,xn, существенно зависящих не более чем от к переменных; Ф=п С Ф" есть подкласс, состоящий из функций от п переменных ..., хп, существенно зависящих от всех п своих переменных.

Пусть / : {0,1}у" —► N — псевдо-булевская функция. Если для любых фиксаций а,р, 7 £ {0,1}V", таких что а > 7 > /? из /(а) = /(/?) следует, что /(а) = /(7), то будем называть / интервалъпо-постоянной. Другими словами, если такая функция присваивает одно и то же значение двум сравнимым наборам, то она присваивает то же значение любому набору из грани, задаваемой этими двумя наборами. Класс всех таких функций будем обозначать через ICF (interval constant functions).

Рассмотрим такую псевдо-булевскую функцию, что если она присваиваг ет одно и то же значение двум произвольным фиксациями, то она присваивает то же значение любой фиксации из грани, задаваемой этими двумя фиксациями. Такие функции будем называть разбивающими функциями и обозначать соответствующий класс как SPL {splitting functions). Очевидно, что класс интервально-постоянных функций содержит класс разбивающих функций, т.е. SPL С ICF. Если разбивающая функция, существенно зависящая от к переменных, принимает 2к значений, то будем называть ее полной разбивающей функцией. Класс полных разбивающих функций будем обозначать через CSPL (complete splitting functions).

Рассмотрим такую псевдо-булевскую функцию, что для любых двух фиксаций а и /3 из того, что а < Д следует, что f(a) < /(/?). Такие функции будем называть псевдо-булевскими монотонными функциями и обозначать соответствующий класс через РМ. Очевидно, что класс ICF содержит класс псевдо-булевских монотонных функций, т.е. РМ С ICF. Класс булевских монотонных функций обозначим через М, М С РМ. Фиксацию а е {0,1}Гп будем называть верхним нулем функции / € М", если /(а) = 0 и /(/?) = 1 для любой фиксации 0 > а. Аналогично а является нижней единицей, если f(a) = 1 и f(0) — 0 для любой фиксации 0 < а.

Симметрическая функция, зависящая от всех своих переменных — это функция, присваивающая одно и то же значение любым перестановкам произвольной фиксации. Функция с несущественными переменными является симметрической, если ее проекция, задаваемая фиксацией, фиксирующей в точности ее существенные переменные, является симметрической

функцией. Класс всех симметрических интервально-постоянных функций будем обозначать через SICF. Класс симметрических интервально-постоянных функций с не более чем с + 1 различными значениями обозначим через SICFc. Подмножество SICF, состоящее из булевских монотонных функций, назовем множеством пороговых функций и обозначим через THR. Рассмотрим булевскую функцию, являющуюся дизъюнкцией некоторых своих переменных. Класс таких функций будем обозначать через OR. Очевидно, OR С THR.

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

Псевдо-булевская функция над {0,1}Гп, V„ = {xi,...,xn} называется 2-разделяемой, если существует такая перестановка (н,... ,in), что для переменных у\ — X{it... ,уп = Xjn выполнено: а) если iji не является существенной, то yj не является существенной при j > г; Ь) если переменная 2/2t-i является существенной и /3 — частичная фиксация, фиксирующая /%2i-i) = 1, то проекция fp не зависит от переменной yj при j > 2i - 1; с) если переменная да является существенной и ¡3 — частичная фиксация, фиксирующая P(y2i-i) = P{y2i) = 0, то проекция /а не зависит от переменной yj при j > 2г. Класс Ф функций будем называть 2-разделяемъш, если для любых п,к & N класс Фк'п содержит 2-разделяемую функцию с к существенными переменными. Далее показано, что классы булевских монотонных функций и разбивающих функций являются 2-разделяемыми.

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

В работе исследуется сложность расшифровки в худшем случае. Будем говорить, что алгоритм расшифровки класса Ф является эффективным

на Ф, если его сложность на Фп не более чем полиномиальна по п. Алгоритм является параметро-эффективным на Ф, если сложность алгоритма на Фк,п как функция от к и п слабо зависит от п.

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

Пусть tp(A, /) — это число запросов на значение функции, требуемое алгоритму А для расшифровки функции /. Будем называть </?(Л, /) сложностью алгоритма А на функции f. Положим

<р(Ф,п) = min maxip(A.f). v ' АеА( Ф)/еФ" 4 '

Заметим, что здесь используется min, а не inf, поскольку число алгоритмов расшифровки функций из Ф" конечно. Будем называть величину тах/еф у?(Л, /) сложностью алгоритма на классе Ф. Функцию у(Ф,п) назовем сложностью расшифровки Ф. Если сложность алгоритма на Ф" по порядку равна сложности расшифровки Ф при п —> оо, будем говорить, что алгоритм А оптимальный на Ф.

Положим, что

</>(Ф, п, k) = min max ip(A, f).

ЛеЛ(Ф) /е

Заметим, что 1р(Ф,п) = <р(Ф,п,п). Функцию (р(Ф,п,к) будем называть сложностью параметро-эффективной расшифровки класса Ф. Если сложность алгоритма А на Фк,п по порядку равна сложности параметро-эффективной расшифровки Ф при п, к —► оо, будем говорить, что алгоритм А является оптимальным параметро-эффективным на Ф.

Пусть ipp(A, /) — это число блоков запросов на значение функции, требуемых алгоритму А для расшифровки функции /. Величину ipp(A, /) будем называть параллельной сложностью алгоритма А на функции /. Величину max/g$y>p(A,/) назовем параллельной сложностью алгоритма А на классе Ф.

Обозначим Ад{Ф,п,к) = {А е Д(Ф) : < ?}.

Положим

<pP{$,n,k,q) = min max <fip{F,f).

Пусть Ф — некоторый класс псевдо-булевских функций. Будем говорить, что алгоритм определяет существенные переменные функций класса Ф, если для любого п € N он находит существенные переменные любой функции из Ф" при условии, что он получает п в виде входного параметра. Обозначим множество алгоритмов определения существенных переменных функций класса Ф через В(Ф). Как и в случае расшифровки функций, любой элемент множества В(Ф) можею понимать и как единичный алгоритм, получающий п на вход, и как последовательность алгоритмов, такую что п-й алгоритм последовательности расшифровывает функции из Ф".

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

■ф(Ф,п)= min таxib(B.f).

Мы снова используем min, а не inf, поскольку число соответствующих алгоритмов для Фп конечно. Будем называть величину max_f6$ ф{В, f) сложностью алгоритма В на Ф. Функцию ф(Ф,п) назовем сложностью определения существенных переменных функций в Ф. Если сложность алгоритма В на Ф" по порядку равна сложности определения существенных переменных функций в Ф при п —> оо, будем говорить, что алгоритм В оптимальный на Ф.

Положим, что

ф[Ф,п,к) — min max ih(B,f).

' ВеВ{ v '

Заметим, что ф(Ф,п) = ф(Ф,п,п). Функцию ф(Ф,п,к) будем называть сложностью параметро-эффективного определения существенных переменных функций класса Ф. Если сложность алгоритма В на Ф*'" по порядку равна сложности параметро-эффективного определения существенных переменных функций из Ф при п, к —> оо, будем говорить, что алгоритм В является оптимальным параметро-эффекгптным на Ф.

Пусть фр(В, /) — это число блоков запросов на значение функции, требуемых алгоритму В для определения существенных переменных функции /. Величину фр(В, /) будем называть параллельной сложностью алгоритма В на функции /. Величину max/e$ Фр(В, f) назовем параллельной сложностью алгоритма В на классе Ф.

Обозначим В9(Ф, п, к) = {В е В(Ф) : Ф{В, Фк'п) < q}.

Положим

фр(Ф,п,к,д) = min max

ВеВ,(Ф,п,к) /еФМ

В главе 1 исследуется сложность определения существенных переменных различных классов псевдо-булевских функций. Для классов монотонных, разбивающих и интервальнопостоянных функций получены порядки сложности определения существенных переменных.

Теорема 1. Имеет место асимптотическое равенство ^¿(Ф,п,к) >; /с log 7i при п,к -* 00 и2к = O(fclogn), где Ф е {PM,M,SPL,ICF}.

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

Теорема 2. Имеет место асимптотическое равенство

^(SPL,n,k) ~ klogn

при n,k—> оо и 2k = o(k log n).

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

Теорема 3. Пусть k — log2 log п + /3(п), —» 0 при п-* оо. Тогда

^(CSPL, п, к) ~ log п.

Теорема 4. При к ~ п, п —» оо выполнено

■¡/»(CSPL ,п,к)~п.

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

Теорема 5. Для к,п £ N и произвольной константы с > 2, такой что 2k < (§ - l)Jfclognf выполнено

•фр(Ф,п,к,с- к log п)~хк при к, 71 —► 00, где Ф е {PM,M,SPL,ICF}.

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

Теорема 6. Пусть Ф С ICF, А 6 -4(Ф) и для некоторой функции £(п) выполнено ip(A, Ф") = 0(£(п)) при п —* оо. Тогда существует такой алгоритм расшифровки А' € Д(Ф), чтоу{А!, Ф*'п) = O^logn+^iLj^i)) при п,к —► оо.

Упомянутые нижние оценки и алгоритм расшифровки позволили получить асимптотические оценки сложности параметро-эффективной расшифровки для многих подклассов интервально-постоянных функций.

Теорема 7. Имеют место следующие асимптотические равенства

• <^(ICF, п, к) х (¿>(РМ, п, к) х ip(SPL,n,k) х klogn + 2k при п,к -* оо,

• га, к) х к log п + ^ при п, к —> оо,

• Vc = const <p(SICFc, п, к) х <р(ТНЕ, п, к) х </j(OR, п, к) ж fclogn при п —> оо и log/с = o(logn).

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

Теорема 8. Пусть Ф С ICF. Существует такой алгоритм А £ -Д(Ф), что <р(А,Фк<п) = 0(klogn + 2k) при п, к —► оо и 1рр(А,Фк'п) - 0(к) при п,к—* оо.

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

Теорема 9. Пусть Ф С ICF. Тогда для любого А € Д(Ф) выполнено klogn = 0(ip(A,Ф*>п)) при п,к —► оо. Если для некоторого А е -4(Ф) выполнено (р(А,Фк'п) = 0{k\ogn), то к = 0(ipp(A, Фк'п)) при коо, где $eICF,PM,SPL,M.

Другими словами, любой оптимальный на Фк>п алгоритм расшифровки из Д(Ф) имеет параллельную сложность на Фк'п, большую или равную к по порядку при п -> оо и 2к = O(fclogn), где Ф е ICF,PM,SPL,M.

Для данных классов получен порядок сложности параллельной расшифровки для оптимальных по порядку в смысле обычной сложности параметро-эффективных алгоритмов расшифровки.

Теорема 10. Для к,п £ N и произвольной константы с > 2, такой что 2k < (| — l)fclogn, выполнено

<рр(Ф,п,к,с-кlogп) ж к при к, п -> оо, где Ф е ICF, РМ, SPL, М.

Последняя теорема есть следствие теорем 8 и 9 и утверждает, что алгоритм из теоремы 8 имеет минимальную по порядку параллельную сложность на Фк,п среди всех оптимальных на Фк,п алгоритмов из -4(Ф) при п оо и 2к = O(k\ogn), где Ф е ICF, РМ,SPL,М.

Благодарности

Я выражаю глубокую благодарность своему научному руководителю профессору Гасанову Эльяру Эльдаровичу за постановку задач и помощь в работе. Выражаю благодарность заведующему кафедрой математической теории интеллектуальных систем академику, профессору Валерию Борисовичу Кудрявцеву и всему коллективу кафедры за творческую атмосферу, способствующую исследовательской работе. Благодарю своих родителей, Владимира Викторовича Осокина и Аллу Васильевну Осокину, за поддержку.

Публикации автора по теме диссертации

1. Осокин В.В.: Асимптотически оптимальный алгоритм расшифровки разбиения булевого куба на подкубы, Интеллектуальные системы, том 11, вып. 1-4, стр. 635-652 (2007).

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

3. Осокин В.В., Воронин Б.В: 0 сложности расшифровки существенных переменных функции, задающей разбиение булевого куба, Интеллектуальные системы, том 12, вып. 1-4, стр. 159-178 (2008). Осокину В.В. принадлежат доказательства лемм 4.1, 4.2, 5.1, утверждений 6.1 и 6.2 и частично доказательство теорем 2.1, 2.2, 6.1.

4. Осокин В.В.: О параллельной расшифровке разбиений булевого куба, Интеллектуальные системы, том 13, вып. 1-4, стр. 427-454 (2009).

5. Осокин В.В.: Сложность расшифровки монотонных функций с малым числом существенных переменных, Дискретная математика, том 22, вып. 3, стр. 134-145 (2010).

6. Осокин В.В.: О параллельной параметро-эффективной расшифровке псевдо-булевских функций, Интеллектуальные системы, том 14, вып. 1-4, стр. 395-424 (2010).

7. Osokin V.V.: On the complexity of decoding Boolean cube splitting into cube faces. Discrete Mathematics and Applications. Volume 18, Issue 3, Pages 155-172, 2008.

8. Osokin V.V.: On learning monotone Boolean functions with irrelevant variables. Discrete Mathematics and Applications. Volume 20, Issue 3, Pages 307-320, 2010.

9. Осокин B.B.: Асимптотика сложности разбиения булевого куба на подкубы. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23-27 октября 2006 г.), том 1, часть 1, с. 191-193.

10. Осокин В.В.: О расшифровке разбиения булевого куба на грани. Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2007 г.), с. 343-346.

И. Осокин В.В.: Расшифровка к-существенных монотонных функций. Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В.А.Садовничего (30 марта - 2 апреля 2009г., Москва). Материалы конференции. С. 367-368.

12. Осокин В.В.: О расшифровке одного класса дискретных функций. Материалы Международного семинара "Дискретная математика" (Москва, 1-5 февраля 2010 г.). 394-396.

13. Осокин В.В.: О расшифровке существенных переменных дискретных функций. Сборник тезисов XVI Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009», секция «Математика и механика» (Москва, 13-18 апреля 2009). С. 51-52.

14. Осокин В.В.: Расшифровка обобщенных псевдо-булевсшх монотонных функций. Сборник тезисов XVII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2010», секция «Вычислительная математика и кибернетика» (Москва, 12-15 апреля 2010). С. 36-37.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж /£30экз. Заказ № Ц.К.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Осокин, Виктор Владимирович

Введение

1. Общая характеристика работы.

2. Содержание работы.

3. Обзор известных результатов

1 Определение существенных переменных

1.1 Алгоритмы ответов на запросы и нижние оценки

1.1.1 Оценка для класса разбивающих функций.

1.1.2 Оценки для класса полных разбивающих функций

1.1.3 2-разделяемые классы функций

1.1.4 Оценка для 2-разделяемых классов функций.

1.1.5 Оценки для 2-разделяемых классов функций в параллельной среде.

1.1.6 2-разделяемость класса булевских монотонных функций

1.1.7 2-разделяемость класса разбивающих функций

1.2 Алгоритмы расшифровки переменных и верхние оценки

1.2.1 Алгоритм расшифровки переменных полных разбивающих функций.

1.2.2 Алгоритм расшифровки переменных полных разбивающих функций с малым числом существенных переменных

1.2.3 Связь расшифровки переменных и расшифровки функций

Введение диссертация по математике, на тему "О расшифровке логических функций"

1. Общая характеристика работы.

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

В настоящей диссертации исследуется сложность расшифровки дискретных функций из различных классов при активном учителе в модели точной расшифровки при помощи запросов на значение функции [1, 2, 3]. Задачу расшифровки псевдо-булевских функций можно рассматривать как задачу расшифровки автоматов без памяти, т.е. как частную подзадачу более общей задачи расшифровки автоматов [4]. Модель точной расшифровки — это модель расшифровки, в которой предполагается, что загаданную учителем функцию ученик должен отгадывать точно, а не приближенно с некоторой вероятностью (как, например, в модели вероятно примерно точной расшифровки). В модели точной расшифровки функция / от п переменных задана при помощи черного ящика и задача ученика (алгоритма расшифровки) состоит в том, чтобы расшифровать /, т.е. полностью восстановить ее таблицу значений. Чтобы расшифровать загаданную функцию, алгоритм расшифровки может делать запросы на значение функции, т.е. подавать произвольные наборы из области определения функции черному ящику. Алгоритм расшифровки подает запросы блоками, учитель одновременно отвечает на все вопросы из одного блока. В стандартной постановке алгоритм расшифровки должен расшифровать загаданную функцию, использовав по возможности наименьшее число запросов на значение функции. В параллельной постановке алгоритм расшифровки должен минимизировать число блоков, требуемых для расшифровки [5].

В описанных прикладных задачах существенную роль играют следующие два фактора.

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

Некоторые общие результаты по сложности параметро-эффективной (но не параллельной) расшифровки в модели точной расшифровки при помощи запросов на значение функции получены в [16]. И.Вегенер и др. [17] получили точные оценки сложности параметро-эффективной расшифровки некоторых классов булевских функций в этой модели.

Параллельная (но не нараметро-эффективная) расшифровка в модели точной расшифровки при помощи запросов на значение функции исследовалась в [18]. Наконец, параллельная параметро-эффективная расшифровка в этой модели рассматривалась в работах П.Дамашке [5, 19, 20].

В большинстве упомянутых работ рассматривается расшифровка булевских функций. В настоящей диссертации исследована задача параллельной параметро-эффективной расшифровки псевдо-булевских функций. Основные свойства псевдо-булевских функций описаны в [21]. Некоторые классы псевдо-булевских функций описаны в [22].

Параметро-эффективная расшифровка (иначе, расшифровка хунт) исследовалась в рамках нескольких моделей стимулирующего обучения и обучения с учителем. Параметро-эффективный алгоритм расшифровки пороговых функций в рамках модели ограниченной ошибки стимулирующего обучения предложен в [23]. Впоследствии различные аспекты параметро-эффективной расшифровки были рассмотрены в [24, 16]. Пассивное обучение с учителем, т.е. расшифровка по случайной выборке обычно изучается в рамках так называемой модели вероятно примерно точной расшифровки [25]. Параметро-эффективная расшифровка по случайной равномерно распределенной выборке в РАС модели является открытой проблемой [26]. Для ознакомления с недавними результатами по пассивной расшифровке хунт см. [27, 28, 29]. Параллельная расшифровка рассматривалась в [30, 18, 31].

Среди направлений, близких к рассматриваемому направлению расшифровки функций, можно выделить теорию тестового распознавания [32, 33].

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

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

В диссертации получены следующие результаты.

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

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

Диссертация имеет теоретический характер и может быть полезна специалистам по расшифровке функций, специалистам по теории алгоритмического обучения, по теории автоматов и их приложений.

Результаты диссертации докладывались

• на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (2006г.),

• на IX Международном семинаре «Дискретная математика и ее приложения» (2007г.),

• па Международной конференции «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика В.А.Садовничего (2009г.),

• на Международном семинаре «Дискретная математика» (2010г.)

• на научно-исследовательском семинаре кафедры Математической' теории интеллектуальных систем «Теория автоматов», 2008-2010 гг. (неоднократно);

• на семинаре «Кибернетика и информатика» под руководством профессора В.Б.Кудрявцева, МГУ им. М.В. Ломоносова, 2010-2011 гг. (неоднократно);

Основные результаты диссертации опубликованы в восьми статьях [38, 39, 40, 41, 42, 43, 44, 45] и материалах конференций [46, 47, 48, 49, 50, 51].

Диссертация состоит из введения и трех глав. Объем диссертации 117 стр. Список литературы содержит 37 наименований.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

3.2 Заключение

Теорема 8 следует из описания алгоритма расшифровки, приведенного в параграфе 3.1.2. Теорема 9 следует из нижних оценок главы 1 и того факта, что для расшифровки функции необходимо хотя бы расшифровать ее существенные переменные. Теорема 10 — основной результат по сложности параллельной расшифровки функций, он вытекает из теорем 8 и 9.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Осокин, Виктор Владимирович, Москва

1. Angluin, D. (1988). Queries and Concept Learning. Machine Learning, Vol. 2, pp. 319-342, 1988.

2. Коробков, В.К. (1965). О монотонных функциях алгебры логики. Проблемы кибернетики, 13, 5-28, 1965.

3. Gilbert, E.N. (1954). Lattice theoretic properties of frontal switching functions. J. Math. Phys., 33 (1954), 57-97.

4. Кудрявцев, В.В., Алешин, C.B., Подколзин, А.С (1985). Введение в теорию автоматов. НАУКА, М., 1985.

5. Damaschke, Р. (2003). On Parallel Attribute-Efficient, Learning. Journal of Computer and System Sciences, Volume 67, Issue 1, August 2003, 46-62.

6. Hansel, G. (1966). Nombre minimal de contacts de fermeture nécessaires pour realiser une fonction booléenne symetrique de n variables. C. R. Acad. Sci. Paris, 258 (1964), 6037-6040.

7. Choi, S., Jung, K., Kirn, J. (2008). Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions. COLT 2008, 123-134.

8. Torvik, V.I. (2002). Data Mining and Knowledge Discovery: a Guided Approach based on Monotone Boolean Functions. Ph.D. in Engineering Science, May 24, 2002, Louisiana State University.

9. Boros, E., Hammer, P.L., Ibaraki, Т., Kawakami, К. (1997). Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle. SIAM Journal on Computing, Volume 26, Issue 1, 93-109, 1997.

10. Zolotykh, N.Yu., Slievchenko, V.N. (1997). Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries. ALT'98, Otzenhausen, Germany, October 8-10, 1998.

11. Kovalerchuck, В., Triantapliyllou, E., Deshpande, A. S., Vityaev, E. (1996). Interactive learning of monotone Boolean functions. Information Sciences: an International Journal, Volume 94, Issue 1-4, 87 118, 1996.

12. 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.

13. Makino, K., Ibaraki T. (1994). The maximum latency and identification of positive Boolean functions. SIAM Journal on Computing, Volume 26, Issue 5, 1363 1383, 1997.

14. Гайнанов Д.Н. (1984). Об одном критерии оптимальности алгоритма расшифровки монотонных булевых функций. USSR Computational Mathematics and Mathematical Physics, Volume 24, Issue 4, 1985, Pages: 176-181.

15. Соколов H.A. (1982). On the optimal evaluation of monotonic Boolean functions. USSR Computational Mathematics and Mathematical Physics, Volume 22, Issue 2, 1982, Pages 207-220.

16. Bshouty, N. Hellerstein, L. (1998). Attribute efficient learning in query and mistake-bound models. Journal of Computer and System Sciences, 56: 310-319, 1998.

17. Uehara, R., Tsuchida, K., Wegener. I. (1997). Optimal attribute-efficient learning of disjunction, parity, and threshold functions. Lecture Notes In Computer Science; Vol. 1208, 1997.

18. Bshouty, N.H. (1997). Exact learning of formulas in parallel. Machine Learning. Volume 26. Issue I, 25-41, 1997.

19. Damaschke, P. (2000). Adaptive versus nonadaptive attribute-efficient learning. Machine Learning 41 (2000), 197-215.

20. Damaschke, P. (2000). Parallel Attribute-Efficient Learning of Monotone Boolean Functions. Lecture Notes in Computer Science, Algorithm Theory SWAT 2000, 473-479.

21. Boros, E., Hammer P.L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, Volume 123, Issue 1-3, 155-225, 2002.

22. Foldes, S. Hammer, P.L. (2000). Monotone, Horn and Quadratic Pseudo-Boolean Functions. J. UCS, Volume 6, Number 1, 97-104, 2000.

23. Littlestone. N. (1987). Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm. Machine Learning, 2(4): 285318, 1987.

24. Blum, A., Hellerstein, L., Littlestone, N. (1995). Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences, 50: 32-40, 1995.

25. Valiant, L. G. (1984). A theory of the learnable. ACM Press New York, NY, USA, Volume 27, Issue II, 1134-1142.

26. Blum A. (2003). Learning a Function of r Relevant Variables. COLT 2003, Open problems.

27. Arpe, J. Reischuk, B. (2007). Learning Juntas in the Presence of Noise. Theoret. Comput. Sci. 384(1): 2-21, 2007.

28. Kolountzakis, M., Markakis, E., Mehta. A. (2005). Learning symmetric k-juntas in time In the proceedings of «Interface between Harmonic Analysis and Number Theory 2005».

29. Mossel, E., O'Donnell, R., Servedio, R. (2003). Learning juntas. In Proceedings of-the 35th Annual ACM Symposium on Theory of Computing, 2003.

30. Balcazar, J.L., Diaz, J., Gavalda, R., Watanabe, O. (1994). An optimal parallel algorithm for learning DFA. Proceedings of the seventh annual conference on Computational learning theory, 208-217, 1994.

31. Vitter, J.S., Lin, J. (1992). Learning in Parallel. Inf. Comput. 96(2): 179202, 1992.

32. Кудрявцев В.В., Андреев А.Е., Гасанов Э.Э. (2007). Теория тестового распознавания. ФИЗМАТЛИТ, М., 2007.

33. Кудрявцев В.Б., Гасанов Э.Э., Долотова О.А., Погосян Г.Р. (2005). Теория тестирования логических устройств. ФИЗМАТЛИТ, М., 2006.

34. Bshouty, N.H., Eiron, N. (2002). Learning Monotone DNF from a Teacher that Almost does not Answer Membership Queries. Journal of Machine Learning Research, 3 (Jul): pp. 49-57., 2002.

35. Plotkin, M. (I960). Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6:445-450, I960.

36. Kargupta, H., Park, B. (2001). Gene expression and fast construction of distributed evolutionary representation. Evolutionary Computation, 9(1):1—32, 2001.

37. Heckendorn, R.B., Wright. A.H. (2003). Efficient linkage discovery by limited probing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), pages 1003-1014, 2003.

38. Публикации автора по теме диссертации

39. Осокин, В.В. (2007). Асимптотически оптимальный алгоритм расшифровки разбиения булевого куба на подкубы. Интеллектуальные системы, том 11, вып. 1-4, стр. 635-652 (2007).

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

41. Осокин, В.В. (2009). О параллельной расшифровке разбиений булевого куба. Интеллектуальные системы, том 13, вып. 1-4, стр. 427-454 (2009).

42. Осокин, В.В. (2010). Сложность расшифровки монотонных функций с малым числом существенных переменных. Дискретная математика, том 22, вып. 3, стр. 134-145 (2010).

43. Осокин, В.В. (2010). О параллельной параметро-эффективной расшифровке псев до-булевских функций. Интеллектуальные системы, том 14, вып. 1-4, стр. 395-424 (2010).

44. Osokin, V.V. (2008). On the complexity of decoding Boolean cube splitting into cube faces. Discrete Mathematics and Applications. Volume 18, Issue 3, Pages 155-172, 2008.

45. Osokin, V.V. (2010). On learning monotone Boolean functions with irrelevant variables. Discrete Mathematics and Applications. Volume 20, Issue 3, Pages 307-320, 2010.

46. Осокин, В.В. (2006). Асимптотика сложности разбиения булевого куба на подкубы. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23-27 октября 2006 г.), том 1, часть 1, с. 191-193.

47. Осокин, В.В. (2007). О расшифровке разбиения булевого куба на грани. Материалы IX Международного семинара «Дискретная математика и