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

• Чистиков, Дмитрий Викторович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Чистиков, Дмитрий Викторович

Введение

Глава 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 установлена невозможность такой разрешимости для любых нетривиальных расширений элементарного базиса. Наконец, результаты заключительного параграфа главы указывают возможный подход к использованию информации о двоичных разрядах числа единиц подфункций в задаче расшифровки.

Список литературы диссертационного исследования кандидат физико-математических наук Чистиков, Дмитрий Викторович, 2011 год

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.