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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

005010612

Беджанова Светлана Руслановна

ТЕСТЫ СХЕМ ДЛЯ НЕКОТОРЫХ КЛАССОВ БУЛЕВЫХ ФУНКЦИЙ

Специальность 01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 0ЕВ 20і2

Москва 2011

005010612

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

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

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

доктор физико-математических наук, профессор Николай Петрович Редькин

доктор физико-математических наук, профессор Лев Абрамович Шоломов кандидат физико-математических наук, профессор Владимир Алексеевич Стеценко

Казанский (Приволжский) федеральный университет '

Защита диссертации состоится /у- февраля 2012 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при МГУ по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-.. математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14-й этаж).

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

Ученый секретарь диссертационого совета Д 501.001.84 при МГУ, доктор физико-математических наук, профессор

А.О. Иванов

Актуальность темы

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

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

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

f(x), х = (2:1,..., хп). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо "правильной" функции f(x) может выдавать какие-то отличные от f(x) функции неисправностей gi(x), ..., gk(i). Характер воздействия источника неисправностей на схему предполагается известным, а потому набор возможных функций неисправностей gi,...,gk заранее известен. В ходе эксперимента на входы схемы можно последовательно .• подавать наборы cri,...,cr| значений переменных и наблюдать значения 7Ti, ...,7Г/ на выходе схемы. Если в результате эксперимента можно ответить на вопрос, реализует ли схема заданную функцию / или же она реализует одну из функций неисправностей, то множество Т = {cri,..., сг/} является проверяющим тестом; если результат эксперимента позволяет ответить на вопрос, какую именно функцию из множества {/, çh,..., g*;} реализует схема, то Т является диагностическим тестом. Различают полные тесты, когда допускается любое подмножество неисправных элементов в схеме,

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

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

и единичные тесты, когда в неисправное состояние может перейти лишь один элемент. Число наборов в тесте Т определяет его длину.

При таком способе контроля исправности и диагностики

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

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

Первоначально существенное внимание уделялось контактным схемам; в качестве неисправностей рассматривались обычно

обрывы и замыкания контактов. Уже в работе2 представлен

ряд результатов, касающихся построения легкотестируемых контактных схем как для произвольных булевых функций, так и для некоторых конкретных булевых функций и операторов. Здесь, а в дальнейшем в работах В.В. Глаголева3, С.М. Вартаняна4,' Д.С. Романова5 и других авторов исследовались возможности построения легкотестируемых схем, имеющих блочную структуру. Схемы с блочной структурой можно строить для булевых функций, допускающих простую декомпозицию (скажем, для линейных и для симметрических булевых функций), а также для достаточно простых булевых операторов (например, сравнения булевых наборов, арифметического сложения двоичных чисел). Типичные полученные при этом верхние оценки длины проверяющих и единичных диагностических тестов носят константный и логарифмический по п характер (п — число переменных у реализуемых функций и операторов).

Заслуживающим внимания классом контактных схем, допускающих короткие тесты, оказался класс бесповторных контактных схем, в которых присутствует ровно по одному контакту каждой переменной. Тесты для таких схем изучали И.В. Коган6,

3Глаголев В.В. Построение тестов для блочных схем // ДАН СССР, — 1962.

- Т. 144. - №6. - С. 1237 - 1240.

4Вартанян С.М. Единичные диагностические тесты для последовательных блочных схем. — Дисс. на соиск. уч. ст. к.ф.-м.н. — М., 1987. — 114с.

5Романов Д.С. Построение тестов и оценка их параметров для некоторых классов контактных схем. — Дисс. на соиск. уч. ст. к.ф.-м.н. — М., 2000. — 114с.

6Коган И.В. О тестах для бесповторных контактных схем // Проблемы кибернетики. — Вып. 12. — М.: Наука, 1964. — С. 39—44.

В.В. Ваксов7, Х.А. Мадатян8. Они установили, что если булева функция от п переменных допускает бесповторную реализацию, то для нее можно строить контактные схемы, допускающие полные проверяющие тесты и единичные диагностические тесты линейной по п длины. Вместе с тем Х.А. Мадатян8 установил, что любая контактная схема для линейной булевой функции от тг переменных допускает лишь тривиальный полный диагностический тест,' содержащий все 2" входных наборов значений переменных, а Н.П. Редькин9 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, длина которого не превосходит Ц 2П. В случаях, когда в качестве неисправностей допускаются только обрывы (или только замыкания) контактов Н.П. Редькин10 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, экспоненциальной, но существенно меньшей чем 2" длины.

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

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

Понятия проверяющего и диагностического тестов для схем<

7Ваксов В.В. О тестах для бесповоротных контактных схем // Автоматика и телемеханика. — 1965. — Т. 26, №3. — С. 521-524.

8Мадатян Х.А. Полный Тест для бесповоротных контактных схем // Проблемы кибернетики. — Вып. 23. — М.: Наука, 1970. — С. 103-118.

9Редькин Н.П. О полных проверяющих тестах для контактных схем // Методы дискретного анализа в исследовании экстремальных структур. — Вып. 39. — Новосибирск: Изд-во ИМ СО АН СССР, 1983. — С. 80-87.

10Редышн Н.П. О проверяющих тестах замыкания и размыкания // Методы дискретного анализа в оптимизации управляющих систем. — Вып. 40. — Новосибирск: Изд-во ИМ СО АН СССР, 1983. — С. 87-99.

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

В работе S.М. Reddy11 было показано, что в случае произвольных константных неисправностей на выходах элементов любую булеву функцию f(xi,...,xn) можно реализовать схемой в базисе Жегалкина, допускающей единичный проверяющий тест длины п + 3. В работах Н.П. Редькина12’13,14 установлено: а) в случае' произвольных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой (в любом конечном функционально полном базисе), допускающей полный проверяющий тест, длина которого по порядку не превосходит 2"/2; б) в случае однотипных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой в классическом базисе {хку, xVу, х}, допускающей единичный диагностический тест, длина которого не превосходит 2n+l, в) в случае однотипных константных неисправностей на выходах элементов для любой булевой функции f(x 1,...,Ж„) можно построить неизбыточную схему15 в бесконечном базисе {x\&,x<2.,xihxihx3,...; æi V X2,£i V Х2 V Хз, допускающую,-единичный диагностический тест, длина которого по порядку не превосходит log п.

Наиболее близкие к окончательным, а в ряде случаев и окончательные результаты установлены для однотипных неисправностей на выходах элементов. Для базиса Жегалкина

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

uReddy S.M. Easily testable realization for logic functions//IEEE Trans. Comput.

- 1972. - V.21. - N 1. - P. 124-141.

12Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов. (1992) , 198-222.

13Редькин Н.П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник •• Московского университета. Серия 1, Математика. Механика. — 1992. — N 5. — С. 43-46.

14Редькин Н.П. О синтезе легкотестируемых схем в одном бесконечном базисе // Вестник Московского университета. Серия 1, Математика. Механика. — 2007, №3. С. 29-33.

15Редькин Н.П. Надежность и диагностика схем. М. : Изд-во МГУ. 1992.

16Коваценко С.В. Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей // Вестник московского университета. Серия 15. Вычислительная математика и кибернетика. — 2000. — № 2. — С. 45-47.

неизбыточной схемой, допускающей единичный проверяющий тест длины 1. Н.П. Редькин17 для произвольного функционально полного конечного базиса и инверсных неисправностей на выходах элементов показал, что любую булеву функцию можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест длины 3. Ю.В Бородина18 для однотипных константных неисправностей на выходах элементов и классического базиса установила, что любую булеву функцию можно реализовать схемой, допускающей полный проверяющий тест длины 2, и для некоторых функций этот результат неулучшаем. Для однотипных константных: неисправностей типа 1 на выходах элементов и базиса Жегалкина она же установила19, что любую булеву функцию можно реализовать схемой, допускающей тест длины 1; аналогичный результат, но в случае неисправностей противоположного типа установлен в работе20 Ю.В. Бородиной и П.А. Бородина.

Что касается направления, связанного с исследованием тестирования схем для индивидуальных булевых функций, то оно вплоть до настоящего времени является малоизученным. Приведем некоторые результаты, касающиеся тестирования схем для отдельных индивидуальных булевых функций. В работах В.Н. Носкова21’22 получены линейные по п нижние оценки длины полных проверяющих тестов для схем, реализующих функцию выбора от п переменных, и единичных диагностических тестов для схем,' реализующих функцию xik...kxn Vzi&:.в случае константных

17Редькин Н.П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов. Математические вопросы кибернетики (2003), 217230.

18Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008.

- № 1. - С. 40-44.

19Бородипа Ю.В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов // Вестник Москва ун-та. Серия 1. Математика. Механика. — 2008, №5. — С. 49-52.

20Бородина Ю.В., Бородин П.А. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа "0"на выходах элементов // Дискретная математика. — 2010. — Т. 22, вып. 3. — С. 127-133. '

21Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ. Новосибирск: ИМ СО АН СССР, — 1975. — Т. 26.

- С. 23-51.

22Носков В.Н. О длинах единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — сборник трудов Института математики СО АН СССР.

- 1978. - вып. 32. - С. 40-51.

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

B.Г. Хахулин24 рассматривал схемы из функциональных элементов для линейной булевой функции 1п = XI ® ... ® хп при наличии произвольных константных неисправностей на входах элементов; им •' установлено, что полный проверяющий тест для таких схем имеет длину не менее п + 1 и что существует схема, реализующая 1п и допускающая полный проверяющий тест длины п + 2.

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

Цель работы •

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

Научная новизна работы

23Редькин Н.П. О зависимости длины проверяющих тестов от вида,-неисправностей // Методы дискретного анализа в теории кодов и схем. — Сборник трудов Института математики СО АН СССР. — 1987. — Вып. 46. —

C. 65-71.

24Хахулин В.Г. О проверяющих тестах для счетчика четности // Дискретная математика. — 1995. — Т.7, вып. 4. — С. 51-59.

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

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

2. Найдена наименьшая возможная длина полного

диагностического теста для схем в базисах {V} и {V,-}, реализующих дизъюнкцию 11 V ... V хп и обобщенную дизъюнкцию XI V ... V хь V 2^+1 V ... V я„, 1 ^ к ^ п, соответственно, в случае инверсных неисправностей на входах элементов схем. •

3. Получена верхняя оценка длины минимального единичного диагностического теста для схем, реализующих линейные функции в классическом базисе {&, V,'}, в случае инверсных неисправностей на выходах элементов.

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

Методы исследования .

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

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации докладывались на семинаре "Диагностика управляющих систем'1 под руководством профессора1'

Н.П. Редькина (МГУ, 2007-2011гг.), на семинаре "Математические вопросы кибернетики" под руководством профессора О.М.

Касим-Заде (МГУ, 2011г.), на XV Международной конференции "Проблемы теоретической кибернетики"(Казань, 2008г.), на VIII Международной конференции "Дискретные модели в теории-• управляющих систем" (Москва, 2009г.), на Международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов—2010" и "Ломоносов—2011"(МГУ, 2010-2011гг.), на научной конференции "Ломоносовские чтения" (МГУ, 2008-2010гг.), на X Международном семинаре "Дискретная математика и ее приложения" (Москва, 2010), на XVI Международной конференции "Проблемы теоретической кибернетики"(Нижний Новгород, 2011г.).

Публикации

Результаты диссертации опубликованы в 8 работах автора, список которых приведен в конце автореферата [1—8].

Структура и объем работы

Диссертация состоит из введения, трех глав и списка литературы из 43 наименований. Общий объем диссертации 96 страниц, в работе содержится 5 таблиц и 45 рисунков.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Теорема 2. Минимальный единичный диагностический тест функции Ж1 V ... V хп содержит п наборов.

Теорема 4. Минимальный полный диагностический тест функции XI V ... V хп содержит 2” - 1 наборов.

Будем рассматривать функции х*1 V... Ух*п, где ..., <тп £ {0,1}. Естественным образом выделяется случай, когда о\ = ... = ап = 1. Целый класс элементарных дизъюнкций'

мы получаем, когда допускается произвольное значение параметров <71,..,а„. Будем называть дизъюнкцию а^1 V ... V хапп обобщенной, если хотя бы один из параметров аи...,оп равен 0, то есть в формуле х\1 V ... V х°п присутствует в качестве слагаемого хотя бы одна переменная с отрицанием. В работе доказано, что каждое' утверждение, касающееся дизъюнкции, справедливо также и для обобщенной дизъюнкции.

В главе 2 допускаются инверсные неисправности на входах элементов.

Пусть Т — полный диагностический тест схемы 5, реализующей функцию <1п(х) = Х\ V ... V хп; через В(Т) обозначим длину теста Т, т.е. число наборов в Т. Пусть -0(5) = тт£(Т), где минимум берется по всем полным диагностическим тестам для схемы 5, а £>(</„) = тпгпй(З), где минимум берется по всем схемам в базисе {V}, реализующим с1„(х). В этих условиях доказана справедливость следующей теоремы .

Теорема 9. Для любого натурального п ^ 2 выполняется равенство

£(<*„) = 2" - 1.

Доказательство этого равенства разбивается на доказательство двух неравенств 0(с1п) < 2" - 1 и 0(йп) > 2” - 1. Справедливость второго неравенства следует из теоремы 4. При доказательстве первого неравенства используется схема Бп (п ^ 2), представляющая собой цепочку из гг - 1 дизъюнкторов ...,Еп^, в которой выход дизъюнктора Е(, г = 1, ...,п — 2, соединен с левым входом дизъюнктора 25,-+1. На входы дизъюнктора Е\ подаются переменные х\ и г2; на правый вход дизъюнктора ] = 2, ...,п - 1, подается переменная х;+1. На выходе дизъюнктора -Еп_1, являющегося , выходом схемы 5П, реализуется дизъюнкция

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

Лемма 1. Функции неисправности схемы Бп, 2, не константы.

Лемма 2. Пусть д',д" — функции неисправности схемы Бп, п ^ 2, значения которых совпадают ровно на одном наборе длины п. Тогда выполняется одна из следующих пар равенств: либо д' = ф1 V хп и д" = ч/’г V хп, либо д' = ^1 V хп и д" = гр2 V хп, где чри'фъ — функции, зависящие от переменных Ях,..., хп~1-

Лемма 3. Пусть д' и д" — функции неисправности схемы Бп, значения которых различны ровно на одном наборе длины п. Тогда выполняется одна из пар равенств: либо д' = ф\У х„ и д" — ф2 V хп, либо д' = фг V х„ и д" — ф2 Ухп, где ф\,ф2 — функции, зависящие от переменных ®1, ..., Хп-1-

Аналогичная теорема справедлива для схем, реализующих' обобщенную дизъюнкцию в базисе {V,-}.

В главе 3 рассматриваются инверсные неисправности на выходах элементов схемы.

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

В первом параграфе главы 3 рассматриваются схемы из функциональных элементов в базисе {&, V,“}, реализующие функцию 1п{х)= ■ '(ВХп (тг ^ 2). Для единичных диагностических

тестов доказана следующая теорема

Теорема 11. Для любого натурального п ^ 2 выполняется неравенство

Щп) <]1о§(п- 1)[ +2.

Доказательство этой оценки проводится конструктивно, также замечено, что эта оценка справедлива и для функции 1п{х).

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

Теорема 12. Функция /(х)=хх\/- --Ухп может быть реализована неизбыточной схемой, допускающей единичный диагностический тест из двух наборов.

Теорема 15. При любом натуральном п > 3 функция /(х)=Хх V ••• V хп может быть реализована схемой, допускающей полный проверяющий тест длины п + 1.

Доказательство этих оценок проводится конструктивно с

указанием явного вида схем.

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

Справедливость утверждений, аналогичных теоремам 12 и 15. установлена и для обобщенных дизъюнкций х\ V... УхкV...Ухп при п^Зи1^А:^п.

В §6 главы 3 доказано, что справедливы утверждения, аналогичные теоремам НО, 12-16, но только применительно к схемам, реализующим конъюнкции и обобщенные конъюнкции соответственно.

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ ‘

1. О минимальных тестах для схем, реализующих дизъюнкцию // Дискретный анализ и исследование операций (2008), т.15 №2, 3-11.

2. Схемы для дизъюнкции, допускающие короткие единичные диагностические тесты // Дискретная математика. — 2010. — Т. 22, вып. 4. — С. 43-54.

3. Диагностика инверсных неисправностей на входах элементов схемы для дизъюнкции // Вестник Московского университета. Серия 15, Вычислительная математика и кибернетика. — 2011. — №3. С. 4446.

4. О минимальных тестах для схем, реализующих дизъюнкцию //

Тезисы XV Международной конференции "Проблемы теоретической кибернетики" (Казань, 2008) — 2008г. — С. 9. '

5. О единичных минимальных тестах для схем, реализующих дизъюнкцию п переменных // Труды VIII Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2009) —Изд-во Макспресс, 2009г. — С. 29-33.

6. Легкотестируемые схемы для дизъюнкции // Материалы X Международного семинара "Дискретная математика и ее приложения" (Москва, 2010) — Изд-во механико-математического факультета МГУ, 2010г. — С. 88-90.

7. Легкотестируемые схемы для дизъюнкции //Сборник тезисов XVII Международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов — 2010” (Москва, 2010) — Изд-во Макспресс, 2010г. — С. 28-29.

8. Об инверсных неисправностях на входах элементов для схем, реализующих дизъюнкцию // Материалы XVI Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 2011) — Изд-во Нижегородского университета, 2011г. —

С. 54-55.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡00 экз- Заказ № 48