Сложность тестирования бесповторных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

0050009»о

Чистиков Дмитрий Викторович Сложность тестирования бесповторных функций

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

АВТОРЕФЕРАТ 1 7 НОЯ 2011

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

Москва — 2011

005000996

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

Научный руководитель:

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

Ведущая организация:

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

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

доктор физико-математических наук Кочергин Вадим Васильевич

Институт системного анализа РАН

Защита состоится 9 декабря 2011 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. (495)939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/ в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

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

Ученый секретарь

диссертационного совета __^ Трифонов Н. П.

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

Актуальность темы. Задача тестирования управляющих систем была впервые подробно описана И. А. Чегис и C.B. Яблонским в 1950-х годах1 и считается в настоящее время одной из основных задач математической кибернетики. Предложенная ими постановка, фактически дающая определение теста для матрицы, обобщает различные задачи логического контроля управляющих систем, в первую очередь — задачу проверки корректности функционирования и задачу диагностики неисправностей. Тестовый характер имеют многие задачи дискретной математики: в частности, широко известная задача о «расшифровке» неизвестной функции, решенная В. К. Коробковым и Ж. Анселем для класса монотонных булевых функций2'3, является задачей условного диагностического тестирования.

В терминах тестов описываются многие из задач теории вычислительного обучения (computational learning theory) — возникшего за рубежом в 1980-х годах раздела машинного обучения (machine learning). Целью алгоритмов обучения с запросами (query learning — по сути изучения, или даже распознавания) является точная идентификация неизвестного объекта из известного множества4,5 — такие постановки приводят к задаче диагностического тестирования. В качестве же меры сложности обучения как передачи знаний (teaching — научения) в этой теории используется функционал0, совпадающий с функцией Шеннона длины проверяющего теста (наибольшей сложностью проверяющего теста среди объектов заданного размера).

В диссертации задачи тестирования изучаются для бесповторных булевых функций — классических объектов дискретной математики. Практическое

1чегис И. А., Яблонский C.B. Логические способы контроля электрических схем // Тр. МИАН СССР. 1958. Т. 51. С. 270-36(1.

2Коробков В. К. Оценка числа монотонных булевых функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Докл. АН СССР. 1963. Т. 150, №4. С. 744-747.

3Hansel G. Sur le nombre des fonctions booléennes monotones de ri variables // C. R. Acad. Sei. Paris. 13G6. Vol. 202. P. 1088-1090. (апсель Ж. О числе моногонных булевых функций п переменных // Кибернетический сборник, изд-во Мир. Новая серия. Вып. 5. 1968. С. 53-57.)

4Angluin D. Queries and concept learning // Machine Learning. 1987. Vol. 2. P. 319-342.

5Angluin D. Computational learning theory: survey and selected bibliography // Proc. of 24th Annual ACM STOC. New York: ACM Press, 19Ü2. P. .451-360.

6Goldman S.A., Kearns M.J. On the complexity of teaching // Journal of Computer and System ' Sciences. 1995. Vol. 50, №1. P. 20-31.

значение разложимости функции в бесповторную суперпозицию (функциональной разделимости) было указано К. Шенноном в 1949 году7. Фундаментальная теорема о полной системе тождеств для бесповторных формул была доказана А. В. Кузнецовым8. Свойство бесповторности играет ключевую роль в задаче сравнения булевых базисов, которая была поставлена О. Б. Лупано-вым в начале 1960-х годов и впервые описана в работе Б. А. Субботовской9. Д. Ю. Черухин доказал10, что сложность формульной реализации произвольных функций при переходе от одного базиса к другому увеличивается не более чем в фиксированное число раз тогда и только тогда, когда все функции первого базиса бесповторно выразимы во втором. Для классов функций, бесповторных в различных базисах, известен ряд характеризаций11'12,13, алгоритмов распознавания и нахождения бесповторных представлений14'15.

Задачи, связанные с диагностическим тестированием бесповторных функций, изучались за рубежом с 1980-х годов, начиная с фундаментальной работы JI. Валианта16. Классические алгоритмы точной идентификации бесповторных функций с помощью запросов различных типов были разработаны Д. Англуин, Л. Хеллерштайн и М. Карпински17; обобщение на случай произвольного конечного базиса принадлежит Н. Бшаути, Т. Ханкоку и Л. Хел-

7Shannon С. The synthesis of two-terminal switching circuits // Bell System Technical Journal. 1949. Vol. 28, №1, P. 59-98. (Шеннон К. Синтез двухполюсных переключательных схем. В кн.: Работы по теории информации и кибернетике. М.: Изд-во иностранной литературы. 19(33. С. 59-105.)

^Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр. МИАН СССР. 1958. Т. 51. С. 186-225.

9Субботовская В. А. О сравнении базисов при реализации функций алгебры логики формулами // Докл. АН СССР. 1963. Т. 149, №4. С. 784-787.

10Черухин Д. Ю, Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики. Вып. 8. М.: Физматлит, 1999. С. 77-122.

11Избранные вопросы теории булевых функций. Под ред. С. Ф. Винокурова и Н. А. Перязсва. М.: Физматлит, 2001. 192 с.

12Karchmer М., Linial N., Newman I., Saks M., Widgerson A. Combinatorial characterization of read-once formulae // Discrete Mathematics. 199.4. Vol. 114, №1-3. P. 275-282.

i3Bopohehko А. А., Федорова B.C., Чистиков Д. В. Повторность булевых функций в элементарном базисе // Известия высших учебных заеедений. Математика. 2011. №11. С. 72-77.

14Golumbic М.С., Mintz A., Rotics U. Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with par tial &-trees // Discrete Applied Mathematics. 2000. Vol. 154, № 10. P. 14G5-1477.

l5B0P0HEHK0 А. А. Распознавание бесповторности в произвольном базисе // Прикладная математика и информатика. Вып. 23. М.: МАКС Пресс, 2(1(1«. С. (¡7-84.

16Vauant L.G. A theory of the learnable // Communications of the ACM. 1984. Vol. 27. P. 1134-1142.

17Angluin D., Hellerstein L., Karpinski M. Learning read-once formulas with queries // Journal о/ the ACM. 1993. Vol. 40. P. 185-210.

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

Невырожденная задача проверяющего тестирования для бесповторных функций была поставлена А. А. Вороненко в 2002 году20. Для построения проверяющих тестов был предложен метод квадратов существенности, позволивший установить порядок роста соответствующей функции Шеннона. Точное значение было впоследствии установлено Л. В. Рябцом21. Известно обобщение метода квадратов существенности на случай больших базисов — метод гиперкубов существенности15, устанавливающий порядок функции Шеннона для базисов всех функций четырех и менее переменных, а также родственный метод, дающий линейные верхние и нижние оценки функции Шеннона для элементарного базиса из конъюнкции, дизъюнкции и отрицания22.

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

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

Научная новизна. Результаты диссертации являются новыми.

18Bshouty N. Н., Hancock Т. R., Hellerstein L. Learning Boolean read-once formulas over generalized bases // Journal oj Computer and System Sciences. 1995. Vol. 50, №3. P. 521-542.

19Goldman S. A., Kearns M. J., Schafire R. E. Exact identification of read-once formulas using fixed points of amplification functions // SIAM Journal on Computing. 1993. Vol. 22, №4. P. 705-735.

20Bopohehko А. А. О проверяющих гестах для бесповторных функций // Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163-176.

21Рябец Л. В. Сложностьпроверяющих тестов для бесповторных булевых функций. Серия: Дискретная математика и информатика. Вып. 18. Иркутск: Изд-во Ирк. гос. пед. ун-та, 2007. 30 с.

22Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1,&, v, -■} // Дискретная математиш. 2005. Т. 17, №2. О. 139-143.

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 13 работ, в том числе б работ [2; 4; 6; 7; 9; 12] в рецензируемых изданиях, включенных в перечень ВАК. Пять работ [1; 2; 4; 6; 11] опубликовано в соавторстве. В работах [1; 11] решение задачи принадлежит автору диссертации, а постановка задачи — научному руководителю. В работе [2] автору диссертации принадлежат результаты по проверяющим тестам для бесповторных функций в базисе всех функций двух переменных, в работе |4] — нижние оценки для индивидуальных функций и универсальная нижняя оценка для функций, представи-мых бесповторными КНФ и ДНФ. В работе [6] автору диссертации принадлежит экспоненциальная нижняя оценка сложности диагностических тестов для функций, бесповторных в неэлсментарных базисах.

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

— XVII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (г. Новосибирск, 27 октября — 1 ноября 2008 г.);

— XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (г. Пенза, 28 сентября — 3 октября 2009 г.);

— 3-я Российская школа-семинар «Синтаксис и семантика логических систем» (г. Иркутск, 10-14 августа 2010 г.);

— 22-й Международный семинар по комбинаторным алгоритмам IWOCA 2011 (22nd International Workshop on Combinatorial Algorithms, г. Виктория, Британская Колумбия, Канада, 20-22 июня 2011 г.);

— 1-й Российско-финский симпозиум по дискретной математике RuFiDiM (г. Санкт-Петербург, 21-24 сентября 2011 г.);

— 13-й Международный симпозиум по символьным и численным алгоритмам для научных расчетов SYNASC 2011 (13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, г. Тимишо-apa, Румыния, 2G-29 сентября 2011 г.).

Кроме того, результаты обсуждались на научных семинарах кафедры математической кибернетики факультета ВМК МГУ.

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы, содержащего 71 наименование. Диссертация содержит 5 таблиц, общий объем текста составляет 135 страниц.

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

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

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

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

Формула 3" над базисом 05 называется бесповторной, если каждая переменная встречается в У не более одного раза. Булева функция / называется бесповторной в базисе 05, если она выразима хотя бы одной бесповторной формулой над 03.

Пусть базис 05 фиксирован, функция ¡{хи..., хп) бесповторна в 05 и существенно зависит от всех своих переменных. Множество входных наборов М С {О, I}*1 называется проверяющим тестом для функции /, если значения / на наборах из М отличают / от всех остальных бесповторных в 05 функций, зависящих от переменных хъ..., хп. Число наборов в проверяющем тесте называют его длиной. Минимальная длина проверяющего теста для бесповторной функции / в 03 обозначается символом 7щ(/). Определение 7®(/) задает функционал сложности для бесповторных функций.

Неориентированный граф <3 = (X, Е) без петель и кратных ребер называется кографом, если его можно преобразовать в пустой граф операциями взятия дополнения связной компоненты. Корневое дерево называется кодере-вом, если каждая его нелистовая (внутренняя) вершина имеет не менее чем двух сыновей и множество всех таких вершин правильно раскрашено в два цвета 0,1 (соседние вершины красятся в разные цвета). Множество когра-фов на вершинах X и множество кодеревьев с листьями X связаны взаимно однозначным соответствием.

В § 1.2 задача проверяющего тестирования бесповторных функций изучается для базиса В2 всех функций двух переменных. Основным результатом является теорема 1.1; в ее формулировке символом £>/ обозначено ко-дерево, связанное с каноническим представлением функции /, а символом //(•) - целочисленная характеристика кодерева, равная минимальной длине

«графового» теста для соответствующего кографа (явная формула для вычисления этой характеристики была найдена А. А. Вороненко [2]).

Теорема 1.1. [2] Для любой бесповтпорпой в базисе функции / справедливо неравенство

TB2(f)^Au(Df).

Теорема 1.1 уточняет метод квадратов существенности для получения индивидуальных верхних оценок минимальной длины проверяющего теста. Немодифицированный метод20 дает универсальную оценку 4 Q); известно другое уточнение21, приводящее к неулучшаемой в общем случае оценке (£) + + п+ 1.

Дерево с единственной внутренней вершиной и п листьями будем называть п-листовой звездой.

Теорема 1.3. [3] Характеристика произвольного кодерева D с п ^ 2 листьями удовлетворяет двойному неравенству 2п —3 ^ v{D) ^ нижняя граница в котором достигается на двоичных деревьях и, в случае п = 3, трехлистовой звезде (и только на них), а верхняя — на деревьях с одной и двумя внутренними вершинами (и только на них), причем значения v{D) для всевозможных Den листьями заполняют весь указанный отрезок.

Функция Шеннона длины проверяющего теста для бесповторных функций в базисе 33 определяется по стандартному правилу

Тв(п) = max ЗД), /(zi.-A.)

где максимум берется по всем бесповторным в функциям переменных Х\, . . - , хп.

В § 1.3 задача проверяющего тестирования изучается для элементарного базиса Во = {&, V,-i). Ранее было известно22, что значение функции Шеннона длины проверяющего теста для функций, бесповторных в этом базисе, заключено между п+1 и 7/2-п (то же верно и для базиса {&, V}). Существует не доказанная и не опровергнутая гипотеза о том, что Тв0(/) = п + 1 для всех бесповторных в Во функций /, имеющих в точности п существенных переменных.

Теорема 1.4. [12] Справедливо равенство

Т{иу]{п) = п+1.

Теорема 1.5. [12] Справедливо неравенство

Тд,(п)<2п+1.

Параграф 1.4 посвящен изучению задачи проверяющего тестирования для базиса {&, V}. Везде в данном параграфе для удобства записи используется обозначение Т(/) вместо Символами То(/) и ТЦ/) обозначается минимальное количество нулевых и соответственно единичных наборов в проверяющем тесте для /. Основная теорема 1.6 сводит задачу определения точного значения Т(/) минимальной длины теста к нескольким экземплярам специальной задачи комбинаторной оптимизации. Входом этой задачи является произвольное мультимножество ^ разбиений натуральных чисел, а оптимальное решение обозначается символом 2{Р).

Теорема 1.6. [13] Пусть функция / задана соотношением

/ - (Лд V ... V ДГ1) & (/2Д V ... V ДГ2) & ... к (/ц V ... V Д-,),

где I > 2, все > 1, функции бесповторны в {&, V}, не выражаются бесповторными дизъюнкциями и не имеют общих существенных переменных, причем если г* = 1, то /¡д — переменная. Тогда

I

7о(/) = ^ТоШ и Т1(/) = ад, ¿=1

где Р1 мультимножество разбиений д) Н-----ЬТ^Д,..) для г = 1,..., I,

а /г = /¿,1 V ... V ДГ,..

Отметим, что результат теоремы 1.6 непосредственно переносится на двойственный случай (меняются местами символы & и V, а также булевы константы 0 и 1).

Теорема 1.6 дает индуктивный способ получения оценок и точных значений величины Т(/) из оценок и соответственно точных значений величины Z{F). Кроме того, показывается, что значение Z{F) можно, в свою очередь, определять по значению Т(/) для специально подобранной /, так что задачи вычисления этих двух величин оказываются в данном смысле эквивалентны.

Следствие 1.6.1. [13] Для всех неконстантных функций /, бесповторных в базисе {&, V}, справедливо равенство

Т(/) = Г0(/) + Т1(/).

Если все компоненты каждого разбиения из Р равны 1, то значение Z{F) обозначается также символом 2(г\,. ,.,Г1), где п,...,г; — соответствующие количества компонент в этих разбиениях (с учетом кратности).

Следствие 1.6.2. [13] Для функции /, выразимой бесповторной КНФ

(х1Л V ... V х1<Г]) & (х2,1 V ... V х2,г2) & ... & (Х1Л V ... V х1п)

с I ^ 2 и Г{ ^ 1 для г = 1,..., I, минимальная длина проверяющего теста определяется равенством

т(л = 1 + г(г1,...,г1).

Теорема 1.7. [13] Если Р состоит из разбиений т.{ = ¿¿д Ч-----1- , где

г = 1то

^ тах < тахть тах(гг- + гк - 1), log2 [ - I + 1 ] + 1 >.

I ' ¥к 1 )

С. Е. Бубнов доказал неравенство Т(/) ^ 2^/п, справедливое для всех бесповторных в {&, V} функций, существенно зависящих от п переменных [4]. Оценки теоремы 1.7 позволяют улучшить этот результат для функций, выразимых бесповторными монотонными КНФ и ДНФ.

Теорема 1.8. [4] Для всех функций /, выразимых бесповторнъши монотонными КНФ и ДНФ и зависящих существенно от п переменных, справедливо неравенство

Т{/)>

Отметим, что для специальной подпоследовательности КНФ п переменных А. А. Вороненко доказал [4] верхнюю оценку Т(/) ^ Зл/п - 1, близкую к нижней границе теоремы 1.8 (теорема 1.7 обращает эту верхнюю оценку в точное равенство).

Теорема 1.9. [13] Если п. ^ г2 > ... ^ ц, то

{Г1ое2(;+1)1 1 5> " 4(тах{г1,1} - 1), - 1) У+ 1.

г^ЗА: 1=1 ]

Используя следствие 1.6.2, теорему 1.9, а также известные свойства почти всех разбиений п-элементного множества, удается определить асимптотику величины Т(/) для почти всех функций, выразимых бесповторными монотонными КНФ (результат для ДНФ формулируется двойственным образом).

Теорема 1.10. [13] Для почти всех функций /, выразимых бесповторными монотонными КНФ и зависящих существенно от п переменных, справедливо соотношение

1пгг

В главе 2 задача проверяющего тестирования изучается для случая произвольного базиса. В §2.1 формулируются необходимые для дальнейшего изложения определения и факты. Базис всех функций I переменных при I ^ 2 обозначается символом

Множество из 2' входных наборов, отличающихся только в компонентах с номерами ¿1,..., г';, называется 1-мерным гиперкубом существенности переменных Хц,.. .,Хц функции /, если остаточная подфункция / на этом множестве существенно зависит от всех своих I переменных15.

Произвольное множество входных наборов, содержащее для каждой 1-кя переменных функции /, для которой это возможно, некоторый /-мерный гиперкуб их существенности, называется множеством 1-мерных гиперкубов существенности функции /. Предположение о том, что множества ¿-мерных гиперкубов существенности являются проверяющими тестами для любых бесповторных функций в базисах Б/ при произвольном I, было названо гипотезой гиперкубов существенности. Справедливость гипотезы гиперкубов существенности означает, в частности, полиномиальность относительно п функции Шеннона длины проверяющего теста для бесповторных функций в произвольном конечном базисе. Для I ^ 4 справедливость этой гипотезы была ранее доказана А. А. Вороненко15.

Параграф 2.2 посвящен доказательству гипотезы гиперкубов существенности для базиса В5.

Теорема 2.1. [1] Любое множество пятимерных гиперкубов существенности произвольной бесповторной в функции f, существенно зависящей от всех своих переменных, образует проверяющий тест:

Следствие 2.1.1. Тв,(п) = в(п5).

Базис 25 называется наследственным, если с каждой функцией /г он содержит все ее остаточные подфункции, получаемые подстановками констант на места переменных.

В §2.3 устанавливается, что в широком классе базисов, вообще говоря, неверно правило подфункции — импликация «если /' — подфункция /, то

Теорема 2.2. [7] Если конечный наследственный базис 23 содержит двухместную дизъюнкцию и последовательность Т<%{х\ V ... V хп)/п не является ограниченной, то в 03 не выполняется правило подфункции.

Входной набор а функции / называется изолированным23, если для всех соседних с ним наборов /? справедливо неравенство /(а) ф /(/3).

Следствие 2.2.1. [7] Правило подфункции не выполняется в любом конечном наследст.венном базисе, содержащем дизъюнкцию и какую-либо не бесповторную в {&, V, ->} функцию, имеющую изолированный набор.

Условия следствия 2.2.1 справедливы, в частности, для базисов В[ всех функций I переменных при любом фиксированном I ^ 2. Для базиса из конъюнкции и дизъюнкции, напротив, не выполнены даже условия теоремы 2.2, однако в нем правило подфункции удается опровергнуть с помощью результатов § 1.4.

В § 2.4 предлагается специальная постановка задачи проверяющего тестирования, в которой базис бесповторных функций выбирается с учетом тестируемой функции /. Вводится функционал Т*(/), равный минимуму длины проверяющего теста / по всем наследственным базисам, содержащим /. Это

23Вороненко А. А. Тестирование дизъюнкции как бесповторной функции в произвольном бесповторном базисе // Вестник Московского университета. Сер. 15. Вычислительная математика и кабеще-тика. 2008. №4. С. 01-52.

ЗД'КЗД)».

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

Утверждение 2.4. Справедливо соотношение max Г,(/) = 0(22n/3/V^), где максимум берется по множеству всех булевых функций переменных

Х\, . . . j хп.

Теорема 2.4. [10] При любом п ^ 3 для функции

XOR„(aji, • • ■, хп) = {хх V ... V хп) k (zi V ... хп). справедливо равенство

7ЦХ OR„) = 5.

Теорема 2.5. [10] Если п ^ 5 и функция f существенно зависит от п переменных, то

Tt(f) ^ 5.

Теорема 2.6. [10] Если п ^ 5 и для функции /, существенно зависящей от п переменных, справедливо равенство

ад = 5,

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

Глава 3 посвящена задаче диагностического тестирования для бесповторных функций. В § 3.1 формулируется определение условного диагностического теста и описывается общая постановка задачи.

В качестве множества возможных состояний управляющей системы (допустимых объектов) рассматривается множество Rn (соответственно R'!п) всех функций, бесиовторных в фиксированном базисе © и зависящих произвольным (соответственно существенным) образом от переменных xt,..., хп. В качестве элементарных вопросов, используемых для диагностики (точной идентификации неизвестной функции из рассматриваемого множества), рассматриваются стандартные запросы значения функции в точке, а также обобщающие их запросы к подкубам булева куба {0,1}™ — области определения

неизвестной функции. Запрос, связанный с подкубом Г 6 {0,1, —}п, возвращает значение некоторого функционала от значений неизвестной функции на наборах подкуба Г. В случае нулевой размерности подкуба возвращается значение функции в запрошенной точке.

Рассмотрим ориентированное (от корня) корневое дерево, каждой внутренней (нелистовой) вершине которого приписаны допустимый запрос, выходящим из нее дугам — все возможные ответы на этот запрос, а листьям — функции из Яп (Я^) и символы *. Назовем такое дерево условным диагностическим тестом, если для каждого листа этого дерева ориентированный маршрут из корня в этот лист несет последовательность пометок (запрос — ответ), согласованную с пометкой этого листа / и только с ней (соответственно не согласованную ни с одной функцией / в случае пометки *). Слооюпостъ условного диагностического теста определяется как максимальное число дуг на пути от корня к листу (число вопросов, которые задает изображаемый деревом алгоритм в худшем случае). Минимальная сложность условного диагностического тсста для множества Ип (11'п) при условии, что доступны запросы типа F, обозначается символом Ь%(п)

В §3.2 изучаются запросы тождественности, возвращающие 1 для тех подкубов, на которых неизвестная функция постоянна, и 0 для всех остальных иодкубов (обозначение: =).

Теорема 3.1. [9] Если I < оо — максимальная арность функций базиса 03, то

Ь%{п) < 2пТъ{п) +0(п1+2).

Следствие 3.1.1. [9] Если для конечного базиса 58 функция Шеннона Т<з(п) длины проверяющего теста растет не быстрее некоторого полинома от п, то задача условного диагностического тестирования на множестве всех бесповторных функций в базисе 03 с запросами тождественности решается алгоритмом полиномиальной сложности (величина Щ(п) также ограничена некоторым полиномом от п).

Параграф 3.3 посвящен запросам числа единиц по модулю 2: такой запрос возвращает 1, если число единиц неизвестной функции на запрошенном подкубе нечетно, и 0 иначе (обозначение: ф). Для элементарного базиса В0 = {&, V, -1} А. А. Вороненко доказал [6] неравенство (п) ^ п2 — п -I-1.

Теорема 3.3. [6] Если базис 05 является наследственным, допускает бесповторное выражение всех функций базиса Во и содержит хотя бы одну функцию, не являющуюся бесповторпой в В0, то

1'§(п) = 2П<В>.

Следствие 3.3.1. [6] Пусть 03 — наследственный базис, допускающий бесповторное выражение всех функций базиса В0. Тогда задача условного диагностического тестирования па множестве всех бесповторных функций в базисе 25, существенно зависящих от переменных х\,...,хп, с запросами числа единиц по модулю 2 решается алгоритмом полиномиальной сложтсти в том и только том случае, когда все функции 03 бесповторны вВ0.

В § 3.4 рассматриваются запросы двух младших бит числа единиц. Обращенные к подкубу Г б {0,1, -}™ запросы этих двух типов возвращают два младших бита в! и во числа единиц в;.. .«^о неизвестной функции на запрошенном подкубе (общее обозначение для совокупности запросов к младших бит: (2к)). Каждому биту соответствует отдельный тип запроса; запросы младшего бита йд — это запросы суммы по модулю 2.

Теорема 3.4. [8] Справедливо неравенство

Теорема 3.4 показывает, что в случае элементарного базиса возможность запрашивать значения 5х (в дополнение к во) позволяет сократить сложность условного диагностического теста примерно на четверть.

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

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

1. ВОРОНЕНКО А. А., Чистиков Д. В. О тестировании бесповторных булевых функций в базисе В5 // Материалы XVII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). Новосибирск: Изд-во ИМ СО РАН, 2008. С. 24-30.

2. вороненко А. А., Чистиков Д. в. Индивидуальное тестирование бесповторных функций // Ученые записки Казанского государственного университета. Сер. Физико-математические науки. 2009. Т. 151, кн. 2. С. 36-44.

3. ЧИСТИКОВ Д. В. Об одной характеристике деревьев, связанной с индивидуальным тестированием бесповторных функций // Материалы XVIII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Пенза, 28 сентября - 3 октября 2009 г.). М.: Изд-во механико-математического ф-та МГУ, 2009. С. 94-99.

4. Бубнов С.Е., Вороненко А. А., Чистиков Д. В. Некоторые оценки длин тестов для бесповторных функций в базисе {&,V} // Прикладная математика и информатика. Вып. 33. М.: МАКС Пресс, 2009. С. 90-100. (Bubnov S. е., Voronenko a. a., Chistikov D.V. Some test length bounds for nonrepeating functions in the {&, V} basis // Computational Mathematics and Modeling. 2010. Vol. 21, №2. P. 196-205.)

5. чистиков Д. В. Тестирование бесповторных функций в различных базисах // Сборник тезисов лучших дипломных 'работ 2010 года. М.: Изд. отдел ф-та ВМК МГУ им. М. В. Ломоносова. 2010. С. 102-104.

6. ВОРОНЕНКО А. А., Чистиков Д. В. Расшифровка бесповторных функций оракулом — счетчиком четности .// Прикладная математика и информатика. Вып. 34. М.: МАКС Пресс, 2010. С. 93-106. (Voronenko A. A., Chistikov D.V. Learning read-once functions using subcube parity queries // Computational Mathematics and Modeling. 2011. Vol. 22, №1. P. 81-91.)

7. ЧИСТИКОВ Д. В. Бесповторные функции с труднотестируемыми подфункциями // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2010. №4. С. 38-41.

8. ЧИСТИКОВ Д. В. Расшифровка бесповторных функций по двум младшим битам числа единиц подфункций // Синтаксис и семантика логических систем: материалы 3-й Российской школы-семинара. Иркутск: Изд-во Восточно-Сибирской государственной академии образования, 2010. С. 114-118.

9. ЧИСТИКОВ Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, №1. С. 4G-50.

10. ЧИСТИКОВ Д. В. Бесповторные функции наименьшей тестовой сложности // Сборник статей молодых ученых факультета ВМК МГУ. Вып. 8. М.: Изд. отдел ф-та ВМК МГУ им. М. В. Ломоносова; МАКС Пресс, 2011. С. 135-144.

11. вороненко А. А., Чистиков Д. в. Расшифровка бесповторных функций запросами тождественности // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 105-108.

12. ЧИСТИКОВ Д. В. Тестирование бесповторных функций в элементарном базисе // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2011. №4. С. 37-40.

13. CHISTIKOV D.V. Testing monotone read-once functions // Proc. of IWOCA 2011. Lecture Notes in Computer Science. Vol. 7056. Berlin; Heidelberg: Springer-Verlag, 2011. P. 121-134.

Напечатано с готового оригинал-макета

Подписано в печать 31.10.2011 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 454.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г.

119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 939-3890,939-3891. Тел./факс 939-3891.

Введение

Глава 1. Проверяющие тесты для функций, бесповторных в классических базисах.

§1.1. Основные определения и обозначения.

§1.2. Тестирование в бинарном базисе.

§1.3. Тестирование в элементарном базисе

§ 1.4. Тестирование в базисе из конъюнкции и дизъюнкции.

Глава 2. Проверяющие тесты для функций, бесповторных в произвольных базисах

§2.1. Основные определения и обозначения.

§2.2. Тестирование в базисе всех функций пяти переменных

§2.3. Опровержение гипотезы подфункции.

§ 2.4. Функции наименьшей тестовой сложности

Глава 3. Диагностические тесты для бесповторных функций

§3.1. Основные определения и обозначения.

§ 3.2. Тестирование с запросами тождественности

§3.3. Тестирование с запросами числа единиц по модулю два

§3.4. Тестирование с запросами двух младших бит числа единиц

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

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

Бесповторные булевы функции являются одним из классических объектов дискретной математики. Практическое значение разложимости в бесповторную суперпозицию было указано К. Шенноном в 1949 году [69]. Фундаментальная теорема о полной системе тождеств для бесповторных формул была доказана А. В. Кузнецовым в работе [26]. Критерии бесповторности в элементарном базисе доказывались Б. А. Субботовской [36], В. А. Гурвичем [20; 19] и рядом зарубежных авторов [66]. Новому критерию тестового характера для функций, не являющихся бесповторными, посвящена статья [12]. Критерии бесповторности в базисе всех функций двух переменных, а также ряд других результатов можно найти, например, в монографии [18]; оценки числа бесповторных функций — в работах [68; 21].

Свойство бесповторности оказывается ключевым в задаче сравнения формульной сложности в разных базисах: справедливость гипотезы О. Б. ЛуПанова о критерии эквивалентности базисов (его собственные результаты опубликованы в работе [36]) была доказана Д. Ю. Черухиным в работе [41]. Результаты, имеющие важное самостоятельное значение, на этом пути получили Б. А. Субботовская [35; 36] и В. А. Стеценко [34]. Различным подходам к распознаванию бесповторности и нахождению бесповторных представлений посвящены статьи [63; 10]. Свойства булевых функций, родственные формульной бесповторности, изучались в работах [38; 28; 65]; свойству бесповторности для многозначных функций посвящена статья [40].

Задача тестирования управляющих систем, обобщающая задачи проверки и диагностики, была впервые подробно описана И. А. Чегис и С. В. Яблонским в работе [39]. Большое количество связанных с тестами задач и результатов можно найти в монографиях [33; 30; 37] и в обзорной статье [51]. Из ранних зарубежных работ, связанных с проверяющими тестами для булевых функций, можно отметить статью [71]. Функционал, совпадающий с функцией Шеннона длины проверяющего теста, предлагался как мера сложности обучения (teaching) в работе [60].

Невырожденная задача проверяющего тестирования для бесповторных функций была поставлена А. А. Вороненко в 2002 году. Все переменные тестируемой функции в этой постановке должны быть существенными. В первой посвященной этой задаче работе [7] установлено, что функция Шеннона длины проверяющего теста для функций, бесповториых в базисе всех функций двух переменных, имеет квадратичный порядок роста относительно числа п переменных тестируемой функции. Для получения верхней оценки был предложен метод квадратов существенности — метод восстановления бесповторной в этом базисе функции по ее (£) подфункциям, каждая из которых существенно зависит ровно от двух переменных. Уточнение этого метода Л. В. Рябцом [31] привело к понижению верхней оценки 4(") до известной нижней (2) + п + 1 и, таким образом, к определению точного значения функции Шеннона.

Для той же постановки задачи в случае других базисов известны следующие результаты. Для элементарного (стандартного) базиса из конъюнкции, дизъюнкции и отрицания было установлено, что функция Шеннона длины проверяющего теста имеет линейный порядок роста [4]. Для базиса всех функций / переменных, где / ^ 3, известна нижняя оценка функции Шеннона вида £1(п1), а для случаев I — 3,4 — совпадающая по порядку роста верхняя оценка [8; 10]. Для получения верхней оценки метод квадратов существенности был его автором обобщен, и была сформулирована гипотеза о корректности обобщенного метода (гиперкубов существенности) для произвольного 1^3.

В главе 1 настоящей диссертации изучается задача проверяющего тестирования для функций, бссповторных в классических базисах: в базисе всех функций двух переменных, в базисе из конъюнкции, дизъюнкции и отрицания, в базисе из конъюнкции и дизъюнкции. При решении задач, связанных с бесповторными функциями, чаще всего рассматривают именно эти базисы (см., например, [20; 55; 18]).

Параграф 1.1 посвящен основным определениям и обозначениям, связанным с задачей проверяющего тестирования бесповториых функций. Формулируется общая постановка для произвольного базиса 23, определяется функционал Т®(/) минимальной длины проверяющего теста. Кроме того, вводится в рассмотрение известный класс графов — так называемых кографов, — тесно связанный с бесповторными функциями в классических базисах. Формулируется несколько эквивалентных определений и приводятся некоторые свойства графов этого класса. Описывается используемое в дальнейшем взаимно однозначное соответствие между кографами и корневыми деревьями из специального класса.

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

Ранее А. А. Вороненко построил примеры последовательностей бесповторных в этом базисе функций с произвольной скоростью роста минимальной длины теста от линейной до квадратичной [9]. В работе [13] он же поставил и решил задачу тестирования кографов, предложив использовать ее как инструмент для получения оценок минимальной длины проверяющего теста для бесповторных функций. В § 1.2 излагаются опубликованные в той же работе результаты автора диссертации. Описывается уточнение метода квадратов существенности, отличное от разработанного Л. В. Рябцом и ориентированное на получение индивидуальных оценок. Основным результатом является теорема 1.1, устанавливающая верхнюю оценку, равную 4^(1)/), где Df — дерево, связанное с каноническим бесповторным представлением функции /, а !/(•) — целочисленная характеристика дерева, дающее точное значение минимальной длины теста для сопоставляемого этому дереву кографа.

Далее в § 1.2 изучается характеристика ъ>(-). Утверждение 1.1 преобразует известную явную формулу для и(-) к виду, более удобному для применения. В утверждении 1.2 приводится точное значение этой характеристики для д-ичных деревьев. Теорема 1.3 определяет наибольшее и наименьшее возможные значения характеристики для деревьев с любым заданным числом п листьев (соответствующих переменным тестируемой бесповторной функции) и устанавливает необходимые и достаточные условия достижения этих значений. Кроме того, эта же теорема указывает способ построения деревьев с произвольным числом листьев и любым заданным значением характеристики между максимумом и минимумом.

В § 1.3 задача проверяющего тестирования изучается для элементарного базиса из конъюнкции, дизъюнкции и отрицания. Ранее было известно [4], что значение функции Шеннона длины проверяющего теста для функций, бесповторных в этом базисе, заключено между n + 1 и 7/2 • п (то же верно и для базиса из конъюнкции и дизъюнкции). Теорема 1.4 устанавливает точное значение п 4- 1 функции Шеннона для базиса из конъюнкции и дизъюнкции, а теорема 1.5 улучшает верхнюю оценку для элементарного базиса до значения 2п -f 1.

Параграф 1.4 посвящен изучению задачи проверяющего тестирования для базиса из конъюнкции и дизъюнкции. Основная теорема 1.6 сводит задачу определения точного значения минимальной длины теста T{&)V}(/) к нескольким экземплярам специальной задачи комбинаторной оптимизации, связанной с разбиениями множеств. Далее в параграфе показывается, что оптит мальное решение в этой задаче можно, в свою очередь, определять по значению минимальной длины теста для специально подобранной бесповторной функции, так что эти задачи оказываются в данном смысле эквивалентны.

В том же параграфе доказываются нижние и верхние оценки оптимального решения построенной задачи оптимизации (теоремы 1.7 и 1.9). В некоторых случаях этих оценок оказывается достаточно для нахождения точных значений минимальной длины теста. Для функций, представимых в виде бесповторных монотонных ДНФ и КНФ (дизъюнктивных и конъюнктивных нормальных форм), устанавливается универсальная нижняя оценка 2у/2д/п — 1 (теорема 1.8), улучшающая (для частного случая) оценку С. Е. Бубнова 2-y/ñ. Доказывается также оценка n/lnn, дающая асимптотическое значение длины проверяющего теста для почти всех функций, представимых бесповторными монотонными ДНФ и КНФ (теорема 1.10). В общем случае оценки значений 7{&>V} (/) получаются из оценок для вспомогательной задачи оптимизации с помощью простой индуктивной процедуры.

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

В § 2.2 доказывается корректность метода гиперкубов существенности для базиса из всех функций пяти переменных. Теорема 2.1 устанавливает, что для любой существенно зависящей от всех своих переменных и бесповторной в этом базисе функции / любое множество пятимерных гиперкубов существенности является проверяющим тестом для /. Следствие 2.1.1 выводит из этого, что функция Шеннона длины проверяющего теста растет как 0(п5).

В § 2.3 устанавливается, что для широкого класса базисов неверно естественное предположение о том, что минимальная длина проверяющего теста всех остаточных подфункций произвольной бесповторной функции / (получаемых подстановкой констант на места переменных) не превосходит минимальной длины проверяющего теста /. Теорема 2.2 приводит достаточные условия (на базис 05) наличия двух бесповторных функций / и /' таких, что /' — подфункция /, но Тоз(/') > Т<в(/). Следствие 2.2.1 показывает, что эти условия выполняются для любого конечного наследственного (содержащего с каждой функцией все ее подфункции) базиса 25, содержащего дизъюнкцию и какую-либо не бесповторную в элементарном базисе {&, V, ->} функцию, имеющую изолированный набор (входной набор, значение функции на котором отличается от ее значений на всех соседних наборах). Условия следствия 2.2.1 выполняются, в частности, для базиса всех функций I переменных при любом фиксированном 1^2.

В § 2.4 предлагается специальная постановка задачи проверяющего тестирования, в которой базис бесповторных функций выбирается с учетом тестируемой функции /. Вводится функционал Т*(/), равный минимуму длины проверяющего теста / по всем наследственным базисам, содержащим /. Это равносильно выбору множества всех подфункций функции /, включая /, в качестве базиса. Устанавливается, что максимум функционала Т*(/) по всем булевым функциям, существенно зависящим от п переменных, растет как экспонента (утверждение 2.4), а минимум при всех п ^ 5 равен 5 (теоремы 2.4 и 2.5). Устанавливается, что все функции п ^ 5 переменных, на' которых достигается минимум Т*(/) = 5, принимают одно из значений 0,1 на двух противоположных наборах и другое значение на всех остальных наборах (теорема 2.6).

Глава 3 диссертации посвящена задаче диагностического тестирования для бесповторных функций.

Условные диагностические тесты для произвольного множества объектов можно рассматривать как алгоритмы расшифровки неизвестного объекта из этого множества (цель расшифровки — точное определение неизвестной функции; каждый задаваемый вопрос может зависеть от ответов на предыдущие). Для дискретных функций стандартным способом получения информации является запрос значения в точке (на входном наборе). Широко известна связанная с такими запросами задача расшифровки монотонных функций, решенная В. К. Коробковым и Ж. Анселем [25; 64].

Родственные постановки задачи изучались за рубежом в рамках одного из разделов машинного обучения — теории вычислительного обучения (computational learning theory), основателем которой считается JL Валиант, автор фундаментальной работы [70]. К тестовым постановкам наиболее близки задачи и понятия теории обучения с помощью запросов (query learning; см., например, классические работы Д. Англуин [54; 53]). Известна связь задач этой области с криптографией, обсуждавшаяся, в частности, в работе Д. Англуин и М. Харитонова [56] и в обзорной работе Р. Ривеста [67].

Задача расшифровки с различными типами запросов для бесповторных булевых функций рассматривалась еще JI. Валиантом в работе [70]; предложенный им алгоритм был впоследствии значительно усовершенствован Д. Ан-глуин, J1. Хеллерштайн и М. Карпински. В работе [55] ими описан алгоритм, выполняющий расшифровку неизвестной бесповторной в элементарном базисе функции за 0(п3) запросов значения в точке (в терминах теории вычислительного обучения — membership queries, то есть запросов принадлежности) и 0(п) так называемых запросов эквивалентности (запросы именно этих двух типов доступны в классической модели обучения); для базиса из конъюнкции и дизъюнкции при этом достаточно 0(п2) запросов значения функции в точке (без запросов эквивалентности). Обобщение алгоритма на случай произвольного конечного базиса получено в работе Н. Бшаути, Т. Ханкока и JI. Хеллерштайн [57]: предлагаемый алгоритм использует 0(п1+2) запросов значения в точке и п запросов эквивалентности (здесь I — максимальная арность функций 25). Вероятностному подходу к задаче идентификации неизвестной бесповторной функции посвящена статья [61].

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

В качестве элементарных вопросов, используемых для диагностики (расшифровки), рассматриваются стандартные запросы значения функции в точке, а также обобщающие их запросы к подкубам булева куба {0,1}п — области определения неизвестной функции. Запрос, связанный с подкубом Г G £ {0,1, —}п, возвращает значение некоторого функционала от значений неизвестной функции на наборах подкуба Г. В случае нулевой размерности под-куба возвращается значение функции в запрошенной точке. В общем случае запросы к подкубам позволяют получать информацию о наличии или отсутствии определенных свойств у подфункций неизвестной функции (в теории обучения с помощью запросов при описании моделей такого типа используется аббревиатура UAV —• unspecified attribute values, то есть неопределенные значения атрибутов [62]). Сложность условного диагностического теста определяется как число запросов в худшем случае.

В § 3.2 изучаются запросы тождественности, возвращающие 1 для тех под-кубов, на которых неизвестная функция постоянна, и 0 для всех остальных подкубов. Использование запросов такого типа означает возможность получать ответы на вопросы вида: «Можно ли точно определить значение /, если известны значения только некоторых входных переменных «¿и • • •, ctik?» Теорема 3.1 дает верхнюю оценку сложности диагностики для бесповторных функций в произвольном конечном базисе 93 через функцию Шеннона длины проверяющего теста; следствие 3.1.1 утверждает, что достаточным условием полиномиальной разрешимости является ограниченность этой функции Шеннона полиномом произвольной фиксированной степени от п. Теорема 3.2 показывает невозможность распространения этого результата на общий случай бесконечных базисов. Полученную экспоненциальную нижнюю оценку нельзя получить из мощностных соображений (утверждение 3.1), причем для всех конечных подбазисов диагностика осуществима тестом полиномиальной сложности.

Параграф 3.3 посвящен запросам числа единиц по модулю 2: каждый такой запрос возвращает 1, если число единиц неизвестной функции на запрошенном подкубе нечетно, и 0 иначе. Для запросов этого типа известно, что если априорной информации о существенности переменных нет, то уже в случае элементарного базиса из конъюнкции, дизъюнкции и отрицания имеется экспоненциальная нижняя оценка сложности [5]. Если же множество существенных переменных подается на вход, то для диагностики можно использовать построенный А. А. Вороненко в работе [16] алгоритм расшифровки (условный диагностический тест) сложности п2 — п + 1. В §3.3 излагается полученное автором диссертации в той же работе доказательство экспоненциальной нижней оценки сложности для любого нетривиального расширения элементарного базиса (теорема 3.3).

В § 3.4 рассматриваются обращенные к подкубам запросы, возвращающие два младших бита числа единиц неизвестной функции на запрошенном подкубе. Каждому биту соответствует отдельный тип запроса; запросы младшего бита — это запросы суммы по модулю 2. Теорема 3.4 показывает, что использование запросов второго младшего бита позволяет модифицировать алгоритм Вороненко из [16] и сократить используемое алгоритмом число запросов примерно на четверть.

Излагаемые в диссертации результаты автора опубликованы в рецензируемых работах [3; 13; 16; 44; 45; 49], а также в работах [14; 15; 43; 46-48; 58]. Результаты докладывались на следующих конференциях и семинарах:

XVII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (г. Новосибирск, 27 ок. тября — 1 ноября 2008 г.);

XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (г. Пенза, 28 сентября — 3 октября 2009 г.);

3-я Российская школа-семинар «Синтаксис и семантика логических сии стем» (г. Иркутск, 10-14 августа 2010 г.);

22-й Международный семинар по комбинаторным алгоритмам IWOCA 2011 (22nd International Workshop on Combinatorial Algorithms, г. Виктория, Британская Колумбия, Канада, 20-22 июня 2011 г.);

1-й Российско-финский симпозиум по дискретной математике RuFiDiM (г. Санкт-Петербург, 21-24 сентября 2011 г.);

13-й Международный симпозиум по символьным и численным алгоритмам для научных расчетов SYNASC 2011 (13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, г. Тимишо-apa, Румыния, 26-29 сентября 2011 г.).

Исследования выполнялись при финансовой поддержке гранта Российского фонда фундаментальных исследований 09-01-00817, гранта Президента РФ МД-757.2011.9, а также при поддержке федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 20092013 годы.

Заключение

Изложенные в диссертации результаты связаны с оценками сложности в задачах тестирования бесповторных функций. Результаты главы 1 в значительной степени уточняют и улучшают известные ранее оценки в задаче проверяющего тестирования. В частности, для базиса всех функций двух переменных показана возможность модификации известных тестовых конструкций для получения индивидуальных оценок (другой пример такого подхода дает линейная верхняя оценка, полученная в § 2.3). Основная теорема о тестировании в базисе {&, V} позволяет получать оценки и точные значения длин тестов чисто комбинаторными методами. Возможно сочетание этих оценок со специальными свойствами вспомогательных построений параграфа по тестированию в базисе Во — {&, V, -1} для понижения верхних оценок в Во. Не исключено, что этот путь приведет к доказательству гипотезы о точном равенстве Тв0(/) = п + 1 для всех бесповторных в этом базисе функций /, существенно зависящих от п переменных.

Глава 2 связана с задачей проверяющего тестирования для произвольного базиса. Доказательство гипотезы гиперкубов существенности для больших базисов В/, по-видимому, связано со значительными трудностями, однако основная идея рассуждений для базиса всех функций пяти переменных может быть применима и случае произвольного I. Из теоремы, опровергающей гипотезу подфункции, следует, что нижние оценки величины Тдз(/) для индивидуальных функций в общем случае нельзя получать из соответствующих оценок для подфункций. Проблема получения нижних оценок связана также с результатами параграфа о функциях наименьшей сложности. Из доказанных теорем вытекают, в частности, нижние константные оценки величины Т$в(/) для всех функций п 5 переменных, неулучшаемые в общем случае. В части дальнейшего развития этих результатов можно ожидать, что множество функций, близких к наиболее легкотестируемым, окажется существенно богаче найденного экстремального множества А^пип Т* (/).

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

1. алексеев В. Б. Лекции по дискретной математике. М.: Изд. отдел ф-та ВМК МГУ им. М. В. Ломоносова. 2004. 76 с.2. баранов В. И., Стечкин б. С. Экстремальные комбинаторные задачи и их приложения. 3-е изд., исправ. М.: ФИЗМАТЛИТ,~2006. 240 с.

2. Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163-176.

3. ВОРОНЕНКО А. А. О тестировании бесповторных функций // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2006. №2. С. 45-48.

4. ВОРОНЕНКО A.A. Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикладная математика и информатика. Вып. 15. М.: МАКС Пресс, 2003. С. 85-97.

5. ВОРОНЕНКО А. А. Распознавание бесповторности в произвольном базисе // Прикладная математика и информатика. Вып. 23. М.: МАКС Пресс, 2006. С. 67-84.

6. ВОРОНЕНКО А. А. Тестирование дизъюнкции как бесповторной функции в произвольном бесповторном базисе // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2008. №4. С. 51-52.

7. Вороненко А. А., Федорова В. С., Чистиков Д. В. Повторность булевых функций в элементарном базисе // Известия высших учебных заведений. Математика. 2011. №11. С. 72-77.

8. ВОРОНЕНКО А. А., Чистиков Д. В. Индивидуальное тестирование бесповторных функций // Ученые записки Казанского государственного университета. Сер. Физико-математические науки. 2009. Т. 151, кн. 2. С. 36-44.

9. Избранные вопросы теории булевых функций. Под ред. С. Ф. Винокурова и Н. А. Перязева. М.: Физматлит, 2001. 192 с.

10. ГУРВИЧ В. А. Критерии бесповторности функций алгебры логики // Докл. АН СССР. 1991. Т. 318, №3. С. 532-537.

11. ГУРВИЧ В. А. О бесповторных булевых функциях // Успехи математических наук. 1977. Т. 32, №1. С. 183-184.

12. ЗУБКОВ О. В. Асимптотика числа бесповторных булевых функций в элементарном базисе // Мат. заметки. 2007. Т. 82, №6. С. 822-828.

13. Коробков В. К. Оценка числа монотонных булевых функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Докл. АН СССР. 1963. Т. 150, №4. С. 744-747.

14. Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр. МИАН СССР. 1958. Т. 51. С. 186-225.

15. ЛОЖКИН С. А. Лекции по основам кибернетики. М.: Изд. отдел ф-та BMK МГУ им. М. В. Ломоносова, 2004. 256 с.28. мадатян X. А. О полных проверяющих тестах для квазибесповторных контактных схем // Дискретная математика. 1996. Т. 8, №3. С. 111-118.

16. ЧЕГИС И. А., ЯБЛОНСКИЙ С. В. Логические способы контроля электрических схем // Тр. МИАН СССР. 1958. Т. 51. С. 270-360.

17. ЧЕРЕМУШКИН А. В. Бесповторная декомпозиция сильно зависимых функций // Дискретная математика. 2004. Т. 16, №3. С. 3-42.

18. ЧЕРУХИН Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики. Вып. 8. М.: Физматлит, 1999. С. 77-122.

19. ЧЕРУХИН Д. Ю. О сложности реализации формулами произведений булевых функций // Дискретный анализ и исследование операций. Сер. 1. 2002. Т. 9, №1. С. 84-94.

20. ЧИСТИКОВ Д. В. Бесповторные функции наименьшей тестовой сложности // Сборник статей молодых ученых факультета ВМК МГУ. Вып. 8. М.: Изд. отдел ф-та ВМК МГУ им. М. В. Ломоносова; МАКС Пресс, 2011. С. 135-144.

21. ЧИСТИКОВ Д. В. Бесповторные функции с труднотестируемыми подфункциями // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2010. №4. С. 38-41.

22. ЧИСТИКОВ Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, №1. С. 46-50.

23. ЧИСТИКОВ Д. В. Тестирование бесповторных функций в элементарном базисе // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2011. №4. С. 37-40.

24. ЯБЛОНСКИЙ С. В. Введение в дискретную математику. 2-е изд., перераб. и доп. М.: Наука, 1986. 384 с.

25. ANGLUIN D. Queries and concept learning // Machine Learning. 1987. Vol. 2. P. 319-342.

26. Angluin D., Hellerstein L., Karpinski M. Learning read-once formulas with queries // Journal of the ACM. 1993. Vol. 40. P. 185-210.

27. Corneil D.G., Lerchs H., Stewart Burlingham L. Complement • reducible graphs // Discrete Applied Mathematics. 1981. Vol. 3, №3. P. 163174.

28. Goldman S.A., Kearns M. j. On the complexity of teaching // Journal of Computer and System Sciences. 1995. Vol. 50, №1. P. 20-31.

29. Goldman S.A., Kearns M. j., Schapire R. E. Exact identification of read-once formulas using fixed points of amplification functions // SIAM Journal on Computing. 1993. Vol. 22, №4. P. 705-735.

30. Goldman S.A., Kwek S.S., Scott S. D. Learning from examples with unspecified attribute values // Information and Computation. 2003. Vol. 180, №2. P. 82-100.

31. Golumbic m.c., mlntz A., Rotics U. Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial &-trees // Discrete Applied Mathematics. 2006. Vol. 154, № 10. P. 1465-1477.

32. Savicky P., Woods A. R. The number of Boolean functions computed by formulas of a given size // Random Structures and Algorithms: Proc. of the Eighth International Conference. 1998. Vol. 13, №3-4. P. 349-382.

33. VALIANT L. G. A theory of the learnable // Communications of the ACM. 1984. Vol. 27. P. 1134-1142.

34. Weiss C. D. Bounds on the length of terminal stuck-fault tests // IEEE Trans. Comput. 1972. Vol. c-21, №3. p. 305-309.