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

• Автор: Чистиков, Дмитрий Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 135 с.

Оглавление
Введение
Глава 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; 37J и в обзорной статье [51]. Из ранних зарубежных работ, связанных с проверяющими тестами для булевых функций, можно отметить статью [71]. Функционал, совпадающий с функцией Шеннона длины проверяющего теста, предлагался как мера сложности обучения (teaching) в работе [60].
Невырожденная задача проверяющего тестирования для бесповторных функций была поставлена A.A. Вороненко в 2002 году. Все переменные тестируемой функции в этой постановке должны быть существенными. В первой посвященной этой задаче работе [7] установлено, что функция Шеннона длины проверяющего теста для функций, бесповторных в базисе всех функций двух переменных, имеет квадратичный порядок роста относительно числа п переменных тестируемой функции. Для получения верхней оценки был предложен метод квадратов существенности — метод восстановления беспо-вторной в этом базисе функции по ее (”) подфункциям, каждая из которых существенно зависит ровно от двух переменных. Уточнение этого мето-

=>/(7і,о) = 0, 7і,о = («ід О ... О І О «2 2 О ... О І 1 І ... І 1),
(из монотонности /) где «2 2 получается ИЗ «2,2 заменой какой-либо единицы нулем.
Значения / на трех наборах 7ід, 7од и 7цо доказывают наличие у нее подфункции — КОНЪЮНКЦИИ некоторых двух переменных /ід И /2Д. Согласно сказанному выше, таким образом доказана связность порожденного подграфа для /і и /2. Случай, когда хотя бы одна из этих функций имеет лишь одну существенную переменную, разбирается аналогичным образом. Лемма доказана.
Теорема 1.4. [49] Справедливо равенство
Т{&у}{п) =п+ 1.
Верхняя оценка теоремы 1.4 следует из лемм 1.6 и 1.7, а нижняя дается длиной теста для дизъюнкции п переменных (см., например, [4]).
Теорема 1.5. [49] Справедливо неравенство
Тв0{п) 2п + 1.
Доказательство. Покажем, что всякая бесповторная в базисе Во функция /(жі