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

Предисловие

Глава 1. Введение.

1.1.0 теории деревьев решений

1.2. О содержании диссертационной работы

Глава 2. Условные тесты

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

2.2. Нижние оценки сложности условных тестов.

2.3. Верхние оценки сложности условных тестов

2.4. Алгоритм построения условных тестов

2.5. О сложности решения проблем оптимизации условных тестов

2.6. Сложность вычисления булевых функций из замкнутых классов.

Глава 3. Деревья решений. Локальный подход

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

3.2. Использование теории тестов при анализе деревьев решений.

3.3. Локальные функции Шеннона.

3.4. Проблемы локальной оптимизации деревьев решений.

3.5. Мощностные характеристики тестовых таблиц.

3.6. Алгоритм построения тестовых таблиц.

3.7. Алгоритм построения деревьев решений.

Глава 4. Деревья решений. Глобальный подход

4.1. Глобальные функции Шеннона.

4.2. Проблемы глобальной оптимизации деревьев решений.

4.3. Допустимые меры сложности

4.4. Выбор проверок

Глава 5. Деревья решений над системами квазилинейных проверок

5.1. Оценки сложности и алгоритмы построения деревьев решений над системами квазилинейных проверок

5.2. Предварительные леммы. ЛОЗ

5.3. Основные леммы

5.4. Доказательства теорем.

5.5. Глобальные функции Шеннона для некоторых тестовых троек

Глава 6. Классы задач над системами квазилинейных проверок

6.1. Условие принадлежности задачи множеству задач над системой квазилинейных проверок.

6.2. Задачи дискретной оптимизации

6.3. Задачи распознавания и сортировки

Глава Т. Ациклические программы в базисе {х +у,х — у, 1; 5(ж)}

7.1. Основные определения и результаты.

7.2. Доказательство теоремы 7.1.

Глава 8. Распознавание слов регулярных языков, заданных автоматными источниками.

8.1. Оценки глубины деревьев решений, распознающих слова регулярного языка.

8.2. Доказательство теоремы 8.1.

Глава 9. Диагностика константных неисправностей схем из функциональных элементов

9.1. Основные понятия

9.2. Сложность алгоритмов диагностики.

9.3. Сложность построения алгоритмов диагностики.

9.4. Диагностика неисправностей бесповторных схем

9.5. Подход к синтезу схем и диагностике их неисправностей

Дополнение. Замкнутые классы булевых функций.

1. Некоторые определения и обозначения

2. Описание всех замкнутых классов булевых функций

1.1. О теории деревьев решений

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

1.1.1. Основные понятия

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

Пусть А - непустое множество и Е - некоторое множество функций, определенных на А и принимающих значения из множества Е). = {0,1, ., к — 1}. Функции из Е называются проверками, а пара V = (А, Е) - системой проверок. Система проверок 11 называется конечной, если множество проверок Е конечно, и бесконечной - в противном случае.

Задача над V - это набор вида 2 = О, . , /т), где Д,. . , /т ё Е, V : Е™ и) и и> = {0, 1,2,.}. Задача & состоит в определении по произвольному элементу а € А значения »(а) = КЛ(«),. ., ЛгО))

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

Мера сложности для системы проверок С/ - функция ф : Е —» иЛ{0), сопоставляющая каждой проверке / £ Е ее сложность ■ф(/), которую можно интерпретировать как время выполнения этой проверки. Мера сложности Ч> продолжается на множество деревьев решений над II следующим образом. Сложность пути в дереве решений -сумма сложностей проверок, приписанных вершинам этого пути. Сложность дерева решений - максимальная сложность пути от корня до концевой вершины дерева. Если 1 2 3 1 U з

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

Менее формально суть сказанного состоит в следующем. Пусть fi, - ■ ■ ,fm - проверки из F. Эти проверки разбивают множество А на классы так, что для элементов из одного и того же класса набор значений проверок /i, ■ ■ ■, /т остается неизменным, а для элементов из различных классов наборы значений проверок различаются. Классы перенумерованы, причем, различные классы могут иметь одинаковые номера. Рассматривается задача, заключающаяся в том, чтобы по элементу а множества А определить номер класса, в котором он содержится. В таком виде могут быть представлены разнообразные задачи распознавания образов, диагностики неисправностей, дискретной оптимизации. Пусть выбрана проверка / € F, определено значение /(а), и оно оказалось равным 6. Тогда из множества А удаляются все элементы, для которых значение проверки / не равно 6. Процесс заканчивается, когда все оставшиеся классы (классы, еще содержащие хотя бы один элемент) имеют один и тот же номер. Процесс определения номера класса представляется в виде дерева решений. Каждой проверке сопоставлено натуральное число - ее сложность (вес). Мерой сложности дерева решений служит его взвешенная глубина.

Пример 1.1.1. Пусть имеются три перевернутые чашки и шарик под одной из них (см. рис. 1.1.1). Требуется определить номер чашки, под которой находится шарик.

Для решения этй задачи будем использовать три проверки /i. /2, /з. Определим проверку /2-, г € {1,2, 3} . Поднимаем г-ю чашку. Если шарик был под ней, то значение fi равно 1. В противном случае значение. /. равно 0. Эти проверки определены на множестве {а-,, а2, щ}, где a¿ - расположение шарика под г-й чашкой, i = 1,2,3, и принимают значения из множества E-¿.

Рассматриваемая задача может быть представлена в следующем виде: z = (ц/1,/2,/3), где 1/(1,0,0) = 1, 1/(0,1,0) = 2, 1/(0,0,1) = 3 и u(6u62,6s) = 0 для любого набора {S1,82,S3) {(1, 0,0), (0,1,0), (0,0,1)}. Это задача над системой проверок U = (A, F), где А = {%, а3) и F = {/ь /2, /3 j.

Дерево решений над С/, изображенное на рис. 1.1.2, решает рассматриваемую задачу. Глубина этого дерева решений равна 2.

Имеются многочисленные разновидности определений приведенных понятий. Отметим некоторые из них. В ряде исследований, например, в [117] определение системы проверок U = (А, F) включает вероятностное распределение, заданное на некотором классе подмножеств множества А. Во многих работах [116, 133] рассматриваются не только точные, но и приближенные постановки задачи Z. Кроме детерминированных деревьев решений, изучаемых в этой работе, рассматриваются различные виды

Рис. 1.1.2. недетерминированных [35, 38, 39, 91, 92, 94, 95, 106, 107]. Исследуются разные представления деревьев решений, например, бинарные программы, применяемые при вычислении булевых функций [46, 137]. Помимо мер сложности, используемых в диссертации и характеризующих время работы в худшем случае, рассматриваются также меры сложности, характеризующие время работы в среднем [73, 81, 109, 110, 111, 112, 117], и пространственные меры сложности, например, число вершин в дереве или его представлении [46, 125].

1.1.2. Конечные системы проверок

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

Имеется несколько направлений, в которых рассматриваются конечные системы проверок. Это теория тестов [9, 11, 23, 25, 29, 51, 52, 56, 64, 67], теория информационных систем и грубых (rough) множеств [115, 116, 132, 133], теория вопросников [47, 48, 117, 118], теория таблиц решений [81, 119], теория машинного обучения [80, 123, 124, 125], теория поиска [53, 68].

В работах, относящихся к этим направлениям, изучаются не только деревья решений над системой проверок U = (A,F), решающие задачу Z над J7, но и близкие к ним объекты: конечные подмножества множества проверок F. достаточные для решения задачи а также решающие правила для задачи Z - истинные в U выражения вида

Л(*) = 6г) Л . А (Д(®) = 6Р)] (z(x) = 6).

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

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

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

1.1.3. Бесконечные системы проверок

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

Будем использовать обозначения R, Q и Z для множеств действительных, рациональных и целых чисел. Пусть D С R", В С R и Sn(B) = {sCC^iA'37* + ¿»n+i) : h £ В, 1 < i < n + 1}, где .s(a;) = 1 4- sign x, то есть s(c) =

0, если с < О,

1, если с = О,

2, если с > О для любого с £ R. Систему проверок (D,Sn(B)) назовем системой линейных проверок. Деревья решений над (D>Sn(B)) называются линейными деревьями решений.

В работах [75 , 76 , 88, 89] для некоторых задач z — (у, fi,., fm) над (Rn, ¿»„(R)) были получены близкие к п log2 т нижние оценки минимальной глубины деревьев решений над (Rn, iSri(R)), решающих эти задачи. Позднее методы доказательства нижних оценок были обобщены на случай алгебраических деревьев решений, использующих проверки вида s(p(xi,., хп)), где р - полином с вещественными коэффициентами [70, 134].

В работе [74] при п > 2 была получена верхняя оценка (3 • 2п~~2 + п — 2)(log.¿ т -f 1) минимальной глубины дерева решений над (R'1, Sn.(R)), решающего задачу z = (?л /ъ . fm) над (R^. Sn(H)). В работе [23] содержится верхняя оценка (2(тг + 2)3log2(m + 2 n + 2))/log2( п 2) минимальной глубины для деревьев решений и задач над (Qrt. Sn(Z)). Полное доказательство более слабой верхней оценки 4(n+2)3 ln(m-f 2п + 2) приведено в работе [24]. Аналогичная верхняя оценка получена в работе [85] для деревьев решений над (Rn, <S'„(R)) и задач над (R", <S„.(Z)). В работах [32, 34] рассматриваются деревья решений над системами квазилинейных проверок, которые являются обобщением линейных и алгебраических деревьев решений. Для них получены верхние оценки сложности, аналогичные приведенным в работе [23] для линейных деревьев решений. Тем самым, в частности, положительно решен поставленный в работе [86] вопрос о существовании невысоких верхних оценок минимальной глубины деревьев решений над (R"'. i9r,(R)), решающих задачи над (Rn, iSn(R)).

Особо следует отметить исследования в области вычислительной геометрии, в которых в качестве моделей вычислений часто рассматриваются линейные и алгебраические деревья решений [122]. Значительное внимание при этом уделяется задачам на плоскости и в трехмерном пространстве. В некоторых исследованиях помимо времени работы изучаются необходимая для работы память и время построения деревьев решений.

Насколько известно автору, до появления работ [33, 90] вопросы сложности деревьев решений над произвольными бесконечными системами проверок не рассматривались. В указанных работах на основе методов теории тестов развиты два подхода к исследованию деревьев решений над произвольной системой проверок U = (A,F): локальный, когда для задачи z над U рассматриваются деревья решений, использующие только те проверки, которые входят в описание задачи z, и глобальный, когда допускается использование любых проверок из F.

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

1Л.4. Приложения

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

Непроцедурные языки программирования - языки, в которых порядок выполнения операций не определяется пишущим программу. Соображения об использовании таблиц решений и деревьев решений для создания непроцедурных языков подробно рассматриваются в [81]. При этом программой служит таблица решений, которая далее машинно преобразуется в дерево решений.

Результаты исследований деревьев решений могут применяться при анализе алгоритмов других типов. Например, в работах [2, 3, 4, 72] высокие нижние оценки глубины линейных деревьев решений специального вида использованы при доказательстве неполиномиальных нижних оценок сложности для ряда известных методов решения NP-полных задач.

Пусть В - произвольный базис, состоящий из операций предикатного и функционального типов, определенных на некотором множестве D. Имеется тесная связь между ациклическими программами в базисе Ben входными переменными хг,., хп и деревьями решений над системой проверок (Dn, 'Р(В)). Множество 'Р(В) состоит из проверок вида P(gi,., ут). где Р - предикатная операция базиса В и f/i,. дт - функции, полученные с помощью суперпозиции из функциональных операций базиса В и зависящие от переменных Xi,., хп. Например, упомянутые ранее верхние оценки сложности линейных деревьев решений использованы в [27] для анализа соотношения глубины детерминированных и недетерминированных ациклических программ в базисе {х + у,х — у, 1; sign х) и в [86] при моделировании параллельных ациклических программ в сходном базисе с помощью деревьев решений.

Развитые в [35, 38, 95] методы сравнительного анализа сложности описания задач и сложности их решения с помощью детерминированных и недетерминированных деревьев решений использованы в [41, 104] при изучении временной сложности деревьев-программ в произвольном базисе.

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

В области дискретной оптимизации имеются различные математические модели для классов задач. Например, часто рассматривается класс задач минимизации линейной формы на конечном подмножестве множества К". Исследования линейных деревьев решений позволили в качестве следствий получить нелинейные нижние [75, 88] и полиномиальные верхние [23, 85] оценки глубины линейных деревьев решений для ряда 1ЧР-полных задач с фиксированной размерностью, неполиномиальные нижние оценки сложности для некоторых известных методов решения 1\Р-полных задач [4]. Ряд работ посвящен вопросу о компактном представлении линейных деревьев решений, решающих задачи дискретной оптимизации и имеющих небольшую глубину [15, 17, 18, 19, 20, 24, 26]. При этом изучаются тесно связанные с представлением деревьев решений задания областей оптимизации с помощью операций типа объединения множеств и сдвига множества, исходя из одноэлементных множеств.

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

Распространенной моделью класса задач распознавания образов является семейство задач распознавания слов фиксированной длины некоторого бесконечного языка. Для таких задач каждая проверка состоит в определении значения некоторой буквы слова. При этом слово длины п в ¿¡-буквенном алфавите соответствует ¿¡-цветному изображению на экране, состоящем из п ячеек, а определение значения г-н буквы слова соответствует определению цвета г-й ячейки экрана [52, 64].

Контроль и диагностика неисправностей - старейшая область приложений, берущая начало с работ [56, 67, 69, 77, 87, 126]. Для описания класса задач здесь достаточно указать класс схем и вид неисправностей. В этом направлении имеется большое число работ, в которых изучаются как устройства с памятью [5, 6, 87], так и устройства без памяти [7, 10, 13, 28, 31, 49, 58, 59, 60]. Обзор результатов и обширная библиография содержатся в работе [65].

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

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

1. Алексеев В.Е. Об энтропии двумерных фрагментно замкнутых языков // Комбинаторно-алгебраические методы и их применение. Межвуз. сб. научн. трудов / Под ред. Ал.А.Маркова. - Горький: Изд-во Горьковского ун-та, 1987.- С. 5-13.

2. Бондаренко В.А. Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов // Автоматика и телемеханика. 1983. - N 9. - С. 45-50.

3. Бондаренко В.А. О проблеме труднорешаемости и анализ эвристик в дискретной оптимизации // Автоматика и телемеханика. 1992. - N 12. - С. 20-24.

4. Бондаренко В.А. Оценки сложности задач комбинаторной оптимизации в одном классе алгоритмов // Доклады РАН. 1993. - Т. 328. N 1. - С. 22-24.

5. Василевский М.П. О распознавании неисправности автоматов // Кибернетика.- 1973. N 4. - С, 98-108.

6. Василевский М.П, О расшифровке автоматов // Кибернетика. 1974. - N 2. - С. 19-23.

7. Гольдман P.C., Чипулис В.П. Диагностика бесповторных комбинационных схем // В сб. Дискретный анализ. Вып. 14 / Под ред. Ю.И.Журавлева. Новосибирск: Изд-во Наука, 1969. - С. 3-15.

8. Журавлев Ю.И. Об одном классе не всюду определенных функций алгебры логики // В сб. Дискретный анализ. Вып. 2 / Под. ред. Ю.И.Журавлева. Новосибирск: Изд-во ИМ СО АН СССР, 1964. - С. 23-27.

9. Каравай М.Ф. Диагноз древовидных схем произвольного базиса // Автоматика и телемеханика. 1973. - N 1. - С. 173-181.

10. Iviosbkov M.Ju. On the depth of decision trees over infinite information systems // Proceedings of the Congress "Information Processing and Management of Uncertainty in Knowledge-Based Systems". Granada, Spain, 1996. - P. 885-886.

11. Moshkov M.Ju. On global Shannon functions of two-valued information systems // Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 142-143.'

12. Moshkov M.Ju. Diagnosis of constant faults of circuits // Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 325-327.

13. Moshkov M.Ju. Some bounds on minimal decision tree depth // Fundamenta Infor-maticae. 1996. - V. 27. N 2, 3. - P. 197-203.

14. Moshkov M.Ju. Unimprovable upper bounds on complexity of decision trees over information systems // Foundations of computing and decision sciences. 1996. - V. 21. N 4. - P. 219-231.

15. Moshkov M.Ju. On complexity of decision trees over infinite information systems // Proceedings of the Third Joint Conference on Information Sciences. Duke University, USA, 1997. - P. 353-354.

16. Moshkov M.Ju. Unimprovable upper bounds on time complexity of decision trees // Fundamenta Informaticae. 1997. - V. 31. N 2. - P. 157-184.

17. Moshkov M.Ju. Rough analysis of tree-programs // Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1997. - P. 231-235.

18. Moshkov M.Ju. Complexity of deterministic and nondeterministic decision trees for regular language word recognition // Proceedings of the 3rd International Conference Developments in Language Theory. Thessaloniki, Greece, 1997. - P. 343-349.

19. Moshkov M.Ju, Three ways for construction and complexity estimation of decision trees // Programme of 16th European Conference on Operational Research. Brussels, Belgium, 1998. - P. 66-67.

20. Moshkov M. Ju., Chikalov I. V. On the average depth of decision trees over information systems // Proceedings of the Fourth European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1996.

21. Moshkov M.Ju., Chikalov I.V. Upper bound on average depth of decision trees over information systems // Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 139-141.

22. Moshkov M.Ju., Chikalov I.V. Bounds on average weighted depth of decision trees // Fundamenta Informaticae. 1997. - V. 31. N 2. - P. 145-156.

23. Moshkov M.Ju., Chikalov I.V. Bounds on average depth of decision trees // Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing.- Aachen, Germany, 1997. P. 226-230.

24. Moshkov M.Ju., Moshkova A.M. Optimal bases for some closed classes of Boolean functions // Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1997. - P. 1643-1647.

25. Pawlak Z. Information systems theoretical foundations. - Warsaw: PWN, 1981 (in Polish).

26. Pawlak Z. Rough sets theoretical aspects of reasoning about data. - Dordrecht: Kluwer Academic Publishers, 1991.

27. Picard C.F. Theorie des questionnaires. Paris: Gauthier-Villars, 1965.

28. Picard C.F. Graphes et questionnaires. V. 1, V. 2. Paris: Gauthier-Villars, 1972.

29. Pollack S.L. Decision tables: theory and practice. J. Wiley k, Sons Inc., 1971.

30. Post E. Introduction to a general theory of elementary propositions // Amer. J. Math.- 1921. V. 43. - P. 163-185.

31. Post E. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. V. 5. Princeton-London: Princeton Univ. Press, 1941.

32. Preparata F.P., Shamos M.I. Computational geometry: an introduction. SpringerVerlag, 1985.

33. Quinlan J.R. Discovering rules by induction from large collections of examples // In Experts Systems in the Microelectronic Age / Edited by D. Michie. Edinburg University Press, 1979.

34. Quinlan J.R. Induction of decision trees // Machine Learning. 1986. - V. 1. N 1. -P. 81-106.

35. Quinlan J.R. Generating production rules from decision trees // Proceedings of the 10th Int. Joint Conf. on AI. 1987. - P. 304-307.

36. Roth J.P. Diagnosis of automata failuresa: a calculus and method // Journal Research and Development. 1966. - P. 278-291.

37. Sauer N.' On the density of families of sets // J. of Combinatorial Theory (A). 1972.- V. 13. P. 145-147.

38. Shelah S. A combinatorial problem; stability and order for models and theories in infinitary languages // Pacific J. of Mathematics. 1972. - V. 41. - P. 241-261.

39. Shevtchenko V.I. On the depth of decision trees for diagnosing faults in circuits // Proceedings of the Third International Workshop on Rough Sets and Soft Computing.- San Jose, USA, 1994. P. 594-601.

40. Shevtchenko V.I. On the depth of decision trees for control faults in circuits // Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 328-330.

41. Slowinski R. (Ed.) Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory. Dordrecht: Kluwer Academic Publishers, 1992.

42. Steele J.M., Yao A.C, Lower bounds for algebraic decision trees // J. of Algorithms.- 1982. V. 3. - P. 1-8.

43. Vapnik V.N., Chervonenkis A.Ya. On the uniform convergence of relative frequencies of events to their probabilities // Theory of Probability and its Applications. 1971.- V. 16. N 2. P. 264-280.

44. Wegener I. The complexity of Boolean functions. John Wiley & Sons and B.G. Teubner, Stuttgart, 1987.