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

Н6 ОД

На правах рукописи

ШЕВЧЕНКО Владимир Иванович

ИССЛЕДОВАНИЕ СЛОЖНОСТИ УСЛОВНЫХ ТЕСТОВ ДЛЯ ДИАГНОСТИКИ НЕИСПРАВНОСТЕЙ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

05.13.17—Теоретические основы информатики

Автореферат

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

Нижний Новгород, 1995

Работа выполнена в Научно-исследовательском институте прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

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

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

главный научный сотрудник Нижегородского научно-исследовательского приборостроительного института доктор технических наук

К. Г. Кирьянов;

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

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

Защита состоится « ^ » л. 1995 г. в /часов

на заседании диссертационного совета КР 063.43.01 научно-исследовательского института прикладной математики и кибернетики при Нижегородском госуниверситете им. Н. И. Лобачевского по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

С диссертацией можно ознакомиться в научной библиотеке НИИ прикладной математики и кибернетики.

п / <—;

Автореферат разослан « ^ ' » /Ю_1995 р.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Ю. Л. Кетков.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Начало математической теории контроля было положено работами С.В.Яблонского и И. А. Чегис". В частности, в этих работах на примере контактных схем и схем из функциональных элементов даются описания основных задач теории контроля и способов их решения.

Проблемы контроля и диагностики являются одними иэ основных в математической кибернетике и теоретической информатике. Рассматриваемые в диссертации СФЭ представляют собой математическую модель дискретных устройств, в которых время преобразования входных сигналов в выходные существенно мало по сравнению с длительностью сигналов (устройства комбинационного типа или устройства без памяти). Такие устройства широко используются в »ычислительной технике. Для СФЭ в настоящей работе определяется большое семейство типов неисправностей. В частности это семейство включает в себя такие хорошо известные типы неисправностей, как константные неисправности, неисправности типа "отрицание", 'V- и "v''-замыкания и всевозможные их комбинации.

Цель работы. Для всевозможных базисов СФЭ (конечных непустых множеств булевых функций, существенно зависящих от всех своих переменных) и типов неисправностей исследование

"Яблонский C.B. , Чегис И. А. О тестах для электрических схем // УМН. - 1955. - 10, вып. 4(56). - С. 182 - 184.

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

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

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

Все основные результата являются оригинальными.

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

Апробация работы. Результаты, представленные в диссертации, докладывались на Всесоюзных конференциях по проблемам теоретической кибернетики (Иркутск, 1985, Горький, 1988, Волгоград, 1990), на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва,1989,1991,1993), на семинаре Научного Совета АН УССР по проблеме "Кибернетика" (Донецк, 1-990), на Международных конференциях "Интеллектуальные системы" (Москва, 1992,1993), на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем (Н.Новгород, 1992, 1994, Минск, 1993), на

Международной конференции по грубым множествам и компьютерным вычислениям ССША, Сан-Хосе, 1994), на Международной научной конференции "Математические модели в теории управлявших систем" СМосква, 1995), на семинарах в Нижегородском и Московском университетах.

Публикации. Результаты по теме диссертации опубликованы в работах С1 - 111.

Структура и объем работы. Диссертация изложена на 149 страницах машиннописного текста. Состоит из введения, четырех глав и списка литературы, содержащего 44 наименования.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ Введение состоит из трех параграфов. В первом параграфе дается краткий обзор известных постановок задач и результатов •теории контроля, относящихся к СФЭ. Во втором параграфе даются точные определения основных понятий, используемых в диссертации: СФЭ, неисправностей в, СФЭ, задачи диагностики неисправностей в СФЭ, условного теста.

Схемой из функциональных элементов (CtG) будем называть конечный ориентированный граф без контуров, в котором дуги и вершины помечены следующим образом. Множество вершин разбито на три непустых подмножества. Первое подмножество образуют вершины, которым не инцидентны входящие дуги и каждой приписана переменная, причем разным вершинам приписаны разные переменные. Эти вершины называются входами СФЭ. Вершинам второго подмножества приписаны булевы функции. При этом каждой вершине, которой не инцидентна входящая дуга, приписана константа 0 или 1, а каждой вершине, которой инцидентно т > 1 входящих дуг, приписана булева функция, зависящая от т переменных. Эти вершины можно интерпретировать как

функциональные элементы. Все дуги, входящие в вершины второго подмножества, занумерованы. При этой, еали некоторой вершине инцидентно т входящих дуг, то эти дуги занумерованы числами от 1 до т. Третье подмножество состоит из одной вершины, которой инцидентна ровно одна входящая дуга, исходящая из некоторой вершины второго подмножества, не инцидентна ни одна исходящая дуга и которая помечена символом "*". Эта вершина называется выходом СФЭ.

Будем говорить, что в схеме вершина V предшествует вершине у^, если существует ориентированный путь из у в у^. Если вершины У4 и Уа соединены дугой (у(,уа), то иногда будем говорить, что У( непосредственно предшествует Уа.

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

1) вершине схемы, которой приписана переменная Сконстанта), сопоставим функцию, равную переменной

С константе), приписанной этой вершине;

2) пусть уо - вершина схемы, которой приписана булева Функция 4*-У1- •••. Ут). ау, ..., ут - вершины, непосредственно предшествующие уо. Пусть дуге Су^, уо) приписан номер 1, 1 » 1, .... г, а вершинам у , ..., ут уже

сопоставлены функции д1.....дт соответственно. Тогда вершине

уо сопоставим функцию ^С^, ..., дт).

Схема реализует функцию, сопоставленную вершине, которая непосредственно предшествует выходу схемы.

Число всех вершин в охеме каждая из которых не является выходом г, будем называть сложностью схемы Б и обозначать через КБ).

Если все функции, которые приписаны вершинам 8, принадлежат некоторому конечному множеству булевых функций В,

. // -

то будем говорить, что S есть схема в базисе В.

Неисправности в схемах определяются путем введения в схему нового функционального элемента. Пусть уСх^Э - некоторая

булева функция, xt= Сх(.....xt>. Определим операцию введения

у> - элемента в схему S:

1) Пусть t > 0. Произвольным образом возьмем в S последовательность вершин v » v , ..., vt, причем некоторые вершины могут не один раз входить в v. Далее, возьмем в S некоторое множество дут Е « Си , ..., ив>, исходящих из вершин последовательности v и обладающих следующим,свойством: любая вершина, в которую входит хотя бы одна дуга из Е, не содержится в v и не предшествует ни одной вершине из v. Пусть

Uj- вершина из S, в которую входит дуга в «Е, J»i..... s,

Удалим из S множество дуг Е, добавим вершину е и проведем дуги (v ,е), .... Cvt,e) и Ce,«t3, ..., Се,«в). При этом вершине е припишем булеву функцию у, дуге Cv^e) припишем номер i, i »

1.....t, а дуге Ce.Uj) - номер дуги uJt J = 1.....s.

Полученную таким образом охему обозначим Г. О схеме Г будем говорить, что она получена из S путем введения у - элемента.

2) Пусть t = 0. В этом случае у есть константа 0 или 1. Возьмем в S произвольным образом множество дуг Е = Си , .... ив>. Пусть coj - вершина из S, в которую входит дута uJf J =1, .... s. Удалим из S множество дуг Е, добавим вершину е и проведем дуги Ce,wf), ..., Се,ив). При этом вершине е припишем константу у, а дуге (e,Uj) - номер дуги uJ( J = 1,

..., s. Полученную схему обозначим U. О схеме U будем говорить, что она получена из схемы S путем введения у -элемента.

Пусть Р - некоторое конечное множество булевых функций. Определим множество схем Hp(S) следующим образом:

- J'-

1) Б € Hj.CS);

2) Пусть и € Hj.CS) и уСх^) б Р. Тогда схема, которая может быть получена из I) путем введения у - элемента, также принадлежит НрС8). Никаких других схем Hj.CS) не содержит.

В дальнейшем множество Р будем называть базисом источника неисправностей, который схему Б "переводит" в одну из схем множества Hj.CS). Множество различных булевых функций, реализуемых схемами из Hj.CS), обозначим через Fj.CS).

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

■ ■(

Пусть Б - схема, Р - базис источника неисправностей. Задача диагностики Б относительно Р (задача диагностики Р-неисправностей схемы 5), которую обозначим через <3,Р>, состоит в том, чтобы по любой схеме II е Hj.CS) определить функцию, реализуемую схемой и. Для решения этой задачи используются условные тесты.

Пусть схема 5 имеет п входов. Условным тестом для задачи <Б,Р> будем называть конечное ориентированное корревое дерево, обладающее следующими свойствами:

а) каждой вершине, не являющейся концевой, приписан набор из (О, 1>п;

б) каждой концевой вершине приписана некоторая булева функция из Fj.CS);

в) из каждой вершины, не являющейся концевой, исходят ровно две дуги, которым приписаны числа 0 и 1;

г) для любой функции дСхп) е Fj.CS) найдется путь от корня до концевой вершины у = V , и(Р ..., уг, иг, такой, что

ьершине V приписана функция д и, если для ч = 1, ..., г

- ^ -

вершине vq приписан набор а^ с (О, 1)", a дуге - число

6 е <0, 1>, то аСа ) = 6 . ч ч ч

В качестве меры сложности условного теста рассматривается его глубина, то есть максимальная длина пути от корня до концевой вершины. Глубину условного теота Y будем обозначать через hCY).

Минимальной глубиной условного теста для задачи <S, Р> будем называть величину hpCS) = min htY), где минимум бёрется по всем условным тестам Y для <S, Р>.

Пусть F - некоторое множество булевых функций. Тогда через С F3 будем обозначать замыкание F относительно операций суперпозиции, а также введения и изъятия несущественных переменных. Если F = (F), то F называется замкнутым классом. "

. В третьем параграфе введения определяется цель исследования.

Возьмем произвольным образом дару базисов В и Р для CÎQ и источника неисправностей соответственно и на множестве <2,3, ...} определим функцию Шеннона:

Ьд рСО = max ihpCS): S б ЛСВ), LCS) < 1 >, где ЯСВ) - множество всех схем в базисе В.

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

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

hB.pa)-_

"Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М. : Наука, 1966.

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

Глава 1 состоит иэ двух параграфов. В первой параграфе даются определения понятий и обозначений иэ теории функций алгебры логики, которые используются в работе. Приводится таблица 1, в которую сведены результаты исследования верхних и нижних оценок функции Шеннона hg pCt) для всевозможных пар базисов ВиР.

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

В главах 2-4 для всевозможных пар базисов ВиР соответственно для СФЭ и источника неисправностей исследуются верхние и нижние оценки для функции hg р(1). При описании содержания каждой иэ этих глав полностью результаты приводить не будем, а укажем только минимальные нижние и максимальные верхние оценки для функции hg рШ, когда она: а) ограничена сверху константой; б) растет линейно и в) растет быстрее любого наперед заданного полинома.

Глава 2 состоит иэ двух, параграфов. В первом параграфе исследуется поведение функции hB p(t) в случае, когда базис источника неисправностей Р содержит немонотонную функцию и нелинейную функцию. В этом случае для любого базиса В для СФЭ

при I г 2 справедливы неравенства

21"М 5 Ьд рСУ <г1-\ Во втором параграфе исследуется поведение функции ^ рШ в случае, когда базис источника неисправностей Р содержит только монотонные функции и при этом в Р содержится: а) функция, отличная от конъюнкции и константы; 6У функция, отличная от дизъюнкции и константы. В этом случае:

1) если базис В содержит только монотонные булевы функции, то при 1^5 справедливы неравенства

мС1-1,0) * ьврш 5 «/С1,0), где „С1.Г) ♦ г € <-1.0,♦!>.

а при I = 2, 3, 4 выполняются неравенства О < Ьв рШ £ 4;

2) если базис В содержит немонотонную булеву функцию, то справедливы неравенства

2ич < ьв рШ < 2й'. Глава 3 состоит из двух параграфов. В первом параграфе исследуется поведение функции Ьв рСО в случае, когда баэио источника неисправностей Р содержит только линейные булевы функции, из которых по крайней мере одна зависит от двух или более переменных. В этом случае при I £ 2:

1)- если базис В содержит только линейные булевы функции, то справедливы неравенства

I - 2 2Ьв рси <1; 1) если базис В содержит нелинейную булеву функцию, то справедливы неравенства

2liz.J-._2 $ ^ ^ 21-,

Во втором параграфе исследуется поведение функции Ьв рШ в случае, когда базис источника неисправностей Р содержит или только конъюнкции вида х4л ...л хт, г Н, и, возможно.

константы или только дизъюнкции вида х^ ... V хт, т М «, возможно, константы, причем в Р содержится хотя бы одна функция, аавиоящая не менее, чем от двух переменных. Предположим, что Р содержит только конъюнкции и, возможно, константы.

1) Пусть базис Р содержит константу 1. В этом случае при 1 ?. 2;

а) если все функции, входящие в базис В, являются конъюнкциями или константами, то справедливы неравенства

1-15 £ I;

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

г^'к Ьв рСО 1 уи.О);

в) если базис В содержит немонотонную булеву функцию, то справедливы неравенства

$ \рш < г1-'.

2) Пусть базис Р не содержит константу 1. В атом случае при 1 £ 2:

а) если В = <0>, то ^ рСО = 0;

б) если все функции, входящие в В, являются конъюнкциями или константами и В * <0>, то справедливы неравенства

X - 2 < Ьв рШ < I;

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

г1с1-.>✓».!< ь^СО < 1X1,0);

Г) если базис В содержит немонотонную булеву функцию, то справедливы неравенства

< ьв рсо £ г1-*.

Результаты, когда Р содержит только дизъюнкции и, возможно, константы формулируются двойственным образом.

Глава 4 состоит из двух параграфов. В этой главе исследуется поведение функции Ьд рСО в случае, когда базис для источника неисправностей Р содержит только функции, зависящие не более, чем от одной переменной.

В'первом параграфе поведение функции р(1) исследуется в случае, когда Р £ СОД}.

Пусть Р = <0,1). В этом случае при I £ 2:

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

1 5 Ьд рСУ < 2;

2) если В содержит только линейные булевы функции вида

..хр® с, с е {0,1>, 1" 2 1, а, возможно, константы или только конъюнкции вида X л ... л X , Г г 1, и, возможно,

I Г

константы, или только дизъюнкции вида , г I: 1 и,

I Г

возможно, константы и содержит хотя бы одну функцию, зависящую не менее, чем от двух переменных, то справедливо равенство ^ рСи = I - Г^-П/тТ + 1;

3) если В содержит только монотонные булевы функции и при этом в В содержится:

а) функция, отличная от конъюнкции и константы;

б) функция, отличная от дизъюнкции и константы, то справедливы неравенства

21<1*.ьв рси 5 1>а-Га-1Э/т1.0);

4) если базис В содержит немонотонную функцию и нелинейную функцию, то справедливы неравенства

ь си з 2»-Г«1-.»/т1

О, Р

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

Приведенные оценки для функции hg pCt) при Р = <0,1> несколько улучшают оценки, полученные М. Ю. Мошковым".

Пусть для базиса источника неисправностей справедливо равенство Р » (1>. В этом случае при t £ 2:

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

и, возможно, константы, то справедливы неравенства О < h^CU < 2;

2) если В содержит только линейные булевы функции вида

xtffl ...о хг® с, с « <0,1), г Ь 1 и, возможно, константы или только конъюнкции вида . ..л xr, г i 1 и, возможно, константы и содержит хотя бы одну функцию, зависящую не менее, чем от двух переменных, то справедливы неравенства

t - pCt-13/Tl й ЬврШ S t - ÍU-IVtI + 1;

3) если В содержит только монотонные булевы функции и при этом в В содержится:

tú функция, отличная от конъюнкции и константы; б) функция, отличная от дизъюнкции и константы; то справедливы неравенства

h^pCO. s vCt-rtt-D/Tl.O);

4) если базис В содержит немонотонную функцию и нелинейную функцию, то справедливы неравенства

где г - наибольшее число переменный у функций из В.

Если для базиса источника неисправностей справедливо равенство Р = 40), то результаты формулируются двойственным

"Мошков М. Ю. Условные тесты для диагностики константных неисправностей CtQ // Материалы 8 Всесоюзной конференции по проблемам теоретической кибернетики. Горький, 1988. Ч. 2. С. 50.

- /Л -

образом.

Во втором параграфе поведение функции ^ рШ исследуется в случае, когда <х> 2 Р 5 <0,1,х>.

Пусть Р = <х>. В этом случае при 1^2:

1) если В содержит только линейные булевы функции, та

=

2>'если В оодержит нелинейную булеву функцию, то справедливы неравенства:

2^- 1 5 ьв рси * г^Г«!-.»^!,

где г - наибольшее число переменных у функций из В.

Пусть Р е «х,1>, {х,0>, (х,0,1)>. В этом случае при 1 5: 2:

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

1 5 Ир рШ < 2;

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

Ьв рСО « 1 - ГС1-1)/т1 + 1;

3) если В содержит нелинейную булеву фун'кцию, то справедливы неравенства: л

г1! 5 Кв рСи <; 21-Г'1-«>'Т11 где т - наибольшее число переменных у функций из В. Кроме того в главе 4 показано, что:

1) если Р = <х), то для любого базиса В ц I £ 2 справедливо равенство

Ьв рС1) - 0;

2) для произвольных базисов В и Р и базиса Р*= Р и (х> при I > 2 справедливо равенство Ьв р,СО = Ьв (О.

Заключительные замечания:

13 Используя структуру замкнутых классов булевых функций, можно убедиться в том, что рассмотрены всевозможные пары ВиР базисов для СФЭ и источников неисправностей.

2) Для произвольной пары базиоов ВиР функция Шеннона Ьд с ростом I или растет быстрее любого наперед заданного полинома, или по порядку растет как I, или ограничена сверху костантой 2.

3) Если пара базисов ВиР удовлетворяет хотя бы одному из следующих условий:

а) Р содержит только тождественную функцию;

б) В и Р содержит только дизъюнкции и, возможно, конотанты;

в) В и Р содержит только конъюнкции и, возможно, константы;

г) В и Р содержит только линейные функции, то при I £ 2 справедливы неравенства

О 5 \pCt3 5 I.

Если базисы ВиР не удовлетворяют ни одному из перечисленных выше условий а) - г), то при I > 2 справедливы неравенства

* 21и«>/г1 < Ьв рСи < 21-.

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

-

СПИСОК РАБОТ. ОПУБЛИКОВАННЫХ Ш ТЕМЕ ДИССЕРТАЦИИ

1. Шевченко В.И. О синтезе самокорректирующихся схем с малой трудоемкостью тестирования // Комбинаторно -алгебраические методы в прикладной математике: Межвуз. тематич. сб. науч. тр. / Под ред. Ал. А. Маркова; Горьк. гоо. ун-т. Горький, 1985. С. 133 - 143.

Z." Шевченко В. И. Синтез схем р минимальной трудоемкостью тестирования // Материалы 7 Всесоюзной конференции по проблемам теоретической кибернетики. Иркутск, 1Я85. Ч. 1. С. 202.

3. Шевченко В. И. О сложности диагностики одного типа неисправностей схем из функциональных элементов с помощью условных тестов // Комбинаторно - алгебраические и вероятностные методы в прикладной математике: Межвуз. тематич. сб. науч. тр. / Под ред. A.A. Маркова; Горьк. гос. ун-т, Горький, 1988. С. 86 - 97.

4. Шевченко В. И. О сложности диагностики неисправностей типа схем из функциональных элементов с помоиью условных тестов // Материалы 8 Всесоюзной конференции по проблемам теоретической кибернетики. Горький, 1988. Ч. 2. С. 161 - 162.

5. Шевченхо В. И. О сложности диагностики неисправностей типа схем из функциональных элементов // Комбинаторно -алгебраические методы дискретного анализа: Межвуз. тематич. сб. науч. тр. у Под ред. A.A. Маркова; Горьк. гос. ун-т, Горький, 1989. С. 129 - 140.

6. Шевченко В. И. О оложности условных тестов для контроля и диагностики СФЭ // Матералы 9 Всесоюзной конференции по проблемам теоретической кибернетики. Волгоград, 1990. Ч. 1СЗ). С. 49.

-

7. Шевченко В. И. О сложности диагностики неисправностей типов "О", "1", "&" и "у".схем из функциональных элементов // Комбинаторно - алгебраические и вероятностные методы и их применение: Межьуэ. тематич. об. науч. тр. у Под

ред. А. А. Маркова; Горьк. гоо. ун-т. Горький, 1990. -С. 123 - 150.

8. Шевченко В. И. 0 глубине условных тестов для контроля неисправностей типа "отрицание" в схемах из функциональных элементов // Сибирский журнал исследования операций. Новосибирск, ИМ СЮ РАН, 1994. Т.1. С. 63 - 74.

9. Шевченко В. И. 0 глубине условных тестов для диагностики неисправностей в схемах из функциональных элементов Вестник ВВО АТН РФ. Н. Новгород, 199S. N1. С. ИЗ - 118.

10. Shevtchenko V. On the depth of decision trees for diagnosing faults in circuits // RSSC'94 The Third International Workshop on Rough Sets and Soft Computing. Conference Proceedings. - San Jose State University, San Jose, USA.- 1994. P. - 601.

11. Sheytchenko V. On the depth of decision trees for diagnosing faults in circuits ✓✓ Soft Computing CSelected papers from the Third International Workshop on Rough Sets and Soft Computing, San Jose, USA, 1994), San Diego, The Society for Computing Simulation. 1993. P. 200 - 203.