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

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

Морозов Евгений Валерьевич

Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем

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

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

005567640

Москва — 2015

2 2 АПР 2015

005567640

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный университет имени М. В. Ломоносова».

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

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

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

Романов Дмитрий Сергеевич,

кандидат физико-математических наук, доцент кафедры математической кибернетики факультета вычислительной математики и кибернетики Федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный университет имени М. В. Ломоносова»

Алехина Марина Анатольевна,

доктор физико-математических наук, профессор, заведующий кафедрой дискретной математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Пензенский государственный университет»

Бородина Юлия Владиславовна,

кандидат физико-математических наук, научный сотрудник Федерального государственного бюджетного учреждения науки Институт прикладной математики им. М. В. Келдыша Российской академии наук

Федеральное государственное автономное образовательное учреждение высшего образования «Нижегородский государственный университет им. Н. И. Лобачевского»

Защита состоится 29 мая 2015 г. в 11 час. 00 мин. на заседании диссертационного совета 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, г. Москва, ГСП-1, Ленинские горы, д. 1, стр. 52, 2-й учебный корпус, аудитория 685.

С диссертацией можно ознакомиться в Научной библиотеке Московского государственного университета имени М. В. Ломоносова по адресу: 119192, г. Москва, Ломоносовский проспект, д. 27 — а также на официальном сайте факультета ВМК МГУ http://cmc.msu.ru в разделе «Диссертации».

Автореферат разослан «0$ 2015 года.

Ученый секретарь

диссертационного совета 501.001.44,

доктор физико-математических наук, доцент „, . ^ О. В. Шестаков

Общая характеристика работы

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

Математически предложенный способ контроля формализуется следующим образом. Пусть f(xi,...,х„) — булева функция, а £/ — схема, ее реализующая. Пусть на схему воздействует источник неисправностей В, в результате чего Е/ может перейти в неисправное состояние и реализовать одну из попарно неравных булевых функций fx{xh ..., хп), f2{x 1,... xn). Функции /1(11, ...,£„),.... fm(xь ...,x„) называются функциями неисправности. Множество наборов Т = {äi,..., äp} называется проверяющим шестом для схемы Е/ относительно источника неисправностей В, если для любой функции неисправности ¡г(х\,..., хп), не равной исходной, в множестве Т найдется набор, на котором функции /(хь...,хп) и fi(xi.....хп) принимают разные значения. Если же в Т для любых двух неравных функций из множества {/(XI, ...,£„). fiOl,..., хп),..., /т(хь ...,хп)} существует набор, на котором значения функций различаются, то такое множество называется диагностическим тестом для схемы Еf относительно рассматриваемого источника неисправностей. Число наборов в тесте Т называется его длиной, обозначается 1(Т). Данная величина характеризует сложность тестирования. Тест минимальной длины называется минимальным.

Сложность тестирования управляющих систем оценивается с помощью функции Шеннона. Определим L(E/,B) = шЫ(Т), где минимум берется по всем проверяющим (диагностическим) тестам для схемы Е/. Сложность тестирования булевой функции обозначим через L(f,B) = minL(E/, В), где минимум берется по всем схемам данного типа, реализующим булеву функцию /. В определенных задачах минимум может браться по всем неизбыточным схемам,

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

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

реализующим булеву функцию. Наконец, величина Ь{п, В) = тах Ь(/, В) на-

/еР2(п)

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

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

В настоящей работе изучаются неисправности входов схем. Пусть а;,-,,...,Х1к — переменные, соответствующие неисправным, входам схемы, реализующей булеву функцию }{х\,..., хп). Тогда вместо значений каждой из переменных на входы схемы поступают значения некоторых функций Ф\(х1, ...,хп), ...,фк{х\, ...,хп). Допустимые функции ф] выбираются в зависимости от рассматриваемого источника неисправностей В. Ясно, что для данных неисправностей тест не зависит от вида схемы, реализующей рассматриваемую функцию, поэтому в случае тестирования относительно неисправностей входов схем будем говорить о тестах для булевых функций. Тогда функцию Шеннона длины проверяющего (диагностического) теста определим как максимум по всем булевым функциям длины минимального проверяющего (диагностического) теста для функции /(хь ■■■,хп) относительно рассматриваемого источника неисправностей В. Далее перечислены основные результаты, полученные разными исследователями по данной теме.

В. Н. Носковым установлено3, что при t > 7 функция Шеннона длины проверяющего теста относительно подстановки констант равна 2га — 2£ — 1, если п = 2* + Ь + 1, и 2га - 2£ - 2, если 2* + Ь + 1 < п < 2м + Ь 4- 1, а для почти

всех функций длина проверяющего теста относительно подстановки констант

п 2 п

асимптотически не менее — и асимптотически не более —. В. Н. Носковым

4 ^

доказано , что функция Шеннона длины диагностического теста относительно

20-оп

подстановки констант асимптотически не меньше, чем —-=, и не больше, чем

2у/п

20,773п(1+о(-^_)) также в н. Носков рассматривал произвольные неисправности-входов схем, при которых неисправны не более, чем к входов5. Им показано, что

3НосковВ.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ. - Вып. 27. - Новосибирск: ИМ СО АН СССР, 1975. - С. 23-51.

4НосковВ.Н. Диагностические тесты для входов логических устройств // Дискретный анализ. — Вып. 27. — Новосибирск: ИМ СО АН СССР, 1974. - С. 72-83.

5НосковВ.Н. Об универсальных тестах для диагностики одного класса неисправностей комбинационных схем // Методы дискретного анализа в исследовании экстремальных структур. — 1979. — Вып. 33. — С. 41-52.

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

Г. Р. Погосян показал7, что функция Шеннона длины проверяющего теста относительно дизъюнктивных слипаний (а, следовательно, и конъюнктивных) в точности равна п — 1, функция Шеннона длины проверяющего теста относительно инверсных неисправностей входов схем лежит в пределах от п — 1 до п.

О. А. Долотова получила ряд оценок длин проверяющих тестов относительно подстановки констант для булевых функций из классов Поста8.

Н. И. Глазунов и А. П. Горяшко установили9, что функция Шеннона длины проверяющего теста относительно единичных транспозиций переменных

ограничена снизу числом -п log п. Д. С. Романов показал, что длина теста отно-4

сительно группы биекций на множестве переменных и их отрицании ограничена сверху логарифмом мощности множества данной группы10. Отсюда и из результата Н. И. Глазунова и А. П. Горяшко следует, что функция Шеннона длины проверяющего теста относительно всевозможных биекций на множестве переменных имеет порядок га log п.

При га ->■ оо, к -» оо, п — к -» со Д. С. Романовым и И. А. Кузнецовым установлено11, что функция Шеннона длины проверяющего теста относительно локальных ¿-кратных слипаний переменных асимптотически равна 2к~1(п — к). Д. С. Романовым доказано12, что при тех же условиях функция Шеннона длины диагностического теста относительно локальных fc-кратных слипаний переменных асимптотически равна 2к(п — к).

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

'Нурмеев Н. Н. Об универсальных диагностических тестах для одного класса неисправностей комбинационных схем // Вероятностные методы и кибернетика. — 1982. — Вып. 18. — С. 73-76.

'Погосян Г. Р. О проверяющих тестах для входов логических устройств. — М.:Издательство ВЦ АН СССР, 1982. - 57 с.

'Кудрявцев В. Б., ГасановЭ.Э., Долотова О. А., Погосян Г. Р. Теория тестирования логических устройств. — М.: Физматлит. 2006.

'Об оценках длин обнаруживающих тестов для классов неконстантных неисправностей входов комбинационных схем // Изв. АН СССР. Серия „Техническая кибернетика". - 1986. — № 3. - С. 197-200.

'"Romanov D. S. Tests with respect to permutations of variables in Boolean functions H Computational Mathematics and Modeling. - 2013. - V. 24, № 4. - P. 558-565.

"КузнецовИ.А., Романов Д. С. О полных проверяющих тестах относительно локальных слипаний переменных в булевых функциях // Ученые записки Казанского университета. Серия Физико-математические науки. — 2009. - т. 151, № 2. - С. 92-97.

,:RomanovD.S. Diagnostic tests for local coalescences of variables in Boolean functions // Computational Mathematics and Modeling. - 2012. - V. 23. № 1. - P. 72-79.

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

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

Основные результаты работы:

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

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

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

Научная новизна.

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

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

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

Апробация работы. Результаты работы докладывались на следующих конференциях.

• XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 2011),

• XI Международный семинар «Дискретная математика и ее приложения» (Москва, 2012),

13ИкрамовА. А. О сложности тестирования логических устройств на некоторые типы неисправностей // Ин- ' теллектуальные системы. — 2013. Т. 17, вып. 1-4. — С. 311-313.

4

• Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов — 2013» (МГУ, 2013),

• IX Молодежная научная школа по дискретной математике и ее приложениям (Москва, 2013),

• Научная конференция «Тихоновские чтения» (Москва, 2013),

• Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов — 2014» (МГУ, 2014),

• XVII Международная конференция «Проблемы теоретической кибернетики» (Казань, 2014),

• Научная конференция «Тихоновские чтения» (Москва, 2014).

Также результаты обсуждались на научных сеюшарах кафедры математической кибернетики ВМК МГУ.

Личный вклад. Все результаты получены автором самостоятельно.

Публикации. Результаты диссертации изложены в 15 печатных изданиях [1-15], из которых [1-6,15] — в журналах из перечня рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук. В работах [1,6] Морозову Е. В. принадлежат все результаты, а Романову Д. С. — постановка задачи.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Общий объем диссертации составляет 83 страницы. Принята сквозная нумерация теорем, лемм и определений. Список литературы содержит 53 наименования.

Содержание работы

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

Также изучается вытеснение переменных функции /(хх, ...,г„). Переменные х\,..., хп разбиваются на два непересекающихся подмножества вытесняемых и вытесняющих переменных. Вытеснение переменных заключается в том, что вместо каждой вытесняемой переменной подставляется произвольная функция, зависящая только от вытесняющих переменных. Подставляемые функции называются функциями вытеснения. Вытеснение переменных обобщает неисправность, связанную с подстановкой констант. В обоих случаях часть переменных становится фиктивными, а часть остаются неизменными. Но в случае константных неисправностей вместо вновь образовавшейся фиктивной переменной всегда подставляется одно и то же значение, в случае вытеснения подставляется произвольное значение в зависимости от значений вытесняющих переменных. Приняты следующие обозначения источников неисправностей:

• <2(Ф) — Ф-слипания;

• <2й(Ф) — /¡-кратные Ф-слипания;

• М<2(Ф) — множественные Ф-слипания;

• МЬ<Эк(Ф) — множественные локальные ^-кратные Ф-слипания;

• I — вытеснение переменных.

Первая глава посвящена линейным слипаниям переменных.

Рассматриваются множества функций слипания Фщ,, состоящее из всех линейных функций, и Ф©, состоящее из линейных функций, существенно зависящих от всех своих переменных.

Первые две теоремы оценивают функции Шеннона длин тестов относительно множественных линейных слипаний, когда функцией слипания может быть любая допустимая линейная функция.

Теорема 1. При п —> ос верно следующее двойное неравенство:

< Ьвж^МЯ (Фщ,)) <у + 0(пу/п).

Теорема 2. Для функции Шеннона длины диагностического теста относительно множественных линейных слипаний верно следующее равенство: ¿«Пчв(п,М(Э(Ф1ш)) = 2".

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

Теорема 3. Пусть Ф —множество функций, такое, что Ук Вд(уи...,ук) е Ф. Тогда для функции Шеннона £йа5п("><Э(Ф)) пРи некоторой вещественной положительной константе С\ справедлива нижняя оценка:

Ьеь&Мт > Сг^.

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

Теорема 4. Для функции Шеннона ¿чКа^гс, <?($)) справедлива верхняя оценка

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

В первой теореме раздела вместо традиционной функции Шеннона оценивается величина Мй^ел^МиЭк^ы)), которая определяется аналогично функции Шеннона ¿алсйО, МЬ<Эк(Фцп)), но максимум берется только по булевым функциям, существенно зависящим от всех своих переменных. Из данного результата и следующей теоремы следует, что трудоемкость проверяющего тестирования относительно множественных локальных ¿-кратных линейных слипаний значительно ниже для булевых функций, существенно зависящих от всех своих переменных, чем для некоторых булевых функций, имеющих фиктивные переменные. Кроме того, результат зависит от четности к, чего не наблюдается в случае традиционной функции Шеннона.

Теорема 5. При п оо, к -> оо, к = о(п) для нечетных к верно: Мй^еМКЗ^ФшО) ~ п, для четных к верно:

Теорема 6. При п -)• оо, к оо, к = о{п) верно: МЬС^и^ы)) ~ 2п.

Последняя теорема данной главы дает оценку функции Шеннона длины диагностического теста относительно локальных ¿-кратных линейных слипаний.

Теорема 7. При п -> оо, к оо, к = о(п) верно: 1ы)) ~ кп.

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

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

Первые две теоремы оценивают функции Шеннона длин тестов для случаев, когда функциями слипания могут быть любые монотонные симметрические функции.

Теорема 8. При п —> ос имеет место неравенство:

п?

2п < Аь*есе(п,М<Э(Фпи)) < — + 0{п1о«п).

Теорема 9. Имеет место равенство: Ь&фЦп, МС)(Фт5)) = 2".

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

Теорема 10. Для функции Шеннона Ь^^п, <5(Ф,/)) при некоторой вещественной положительной константе С% справедлива нижняя оценка:

у/п

Третья глава посвящена тестированию функций относительно вытеснения переменных.

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

Теорема 11. Имеет место двойное неравенство

2п - 1о^2 П - 21о§2П + 0(1) < ¿сидес^П, I) <2п - п + 0(1).

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

8

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

Теорема 12. Для почти всех булевых функций Ам^Д-Сь..., х„), I) = п + 1.

Заключительная теорема устанавливает асимптотику функции Шеннона длины диагностического теста относительно вытеснения переменных. Данная асимптотика существенно превосходит верхнюю оценку функции Шеннона длины диагностического теста относительно подстановки констант, полученную В. Н. Носковым.

Теорема 13. Имеет место асимптотическое равенство: Ь^^п. I) ~ 2".

В заключении приведены основные результаты работы.

Благодарности.

Автор благодарит доцента Дмитрия Сергеевича Романова за руководство данной работой, профессора Сергея Андреевича Ложкина за постоянное внимание к работе, а также сотрудников кафедры математической кибернетики за поддержку и ценные советы. Автор выражает благодарность своей жене, Карине Александровне, и своим родителям, Галине Анатольевне и Валерию Евгеньевичу, за непрекращающуюся поддержку при подготовке данной работы.

СПИСОК ПУБЛИКАЦИЙ АВТОРА

1. МорозовЕ. В., Романов Д. С. О тестах относительно локальных линейных слипаний переменных в булевых функциях // Вестник Нижегородского университета им. Н. И. Лобачевского. — 2012. — № 5(2). — С. 153-158.

2. МорозовЕ. В. О тестах относительно множественных линейных слипаний переменных в булевых функциях // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2014. — № 1. — С. 2225.

3. МорозовЕ.В. О тестах относительно множественных монотонных симметрических слипаний переменных в булевых функциях // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2014.

- № 4. - С. 27-37.

4. МорозовЕ. В. О полных тестах относительно вытесняющих неисправностей входов схем // Вестник Московского университета. Серия 1. Математика. Механика. — 2015. - № 1. - С. 55-59.

5. Морозов Е. В. О тестах для почти всех булевых функций относительно некоторых неисправностей входов схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2015. — № 1. — С. 57-64.

6. МорозовЕ. В., Романов Д. С. Проверяющие тесты для булевых функций при линейных локальных неисправностях входов схем // Дискретный анализ и исследование операций. — 2015. — Т. 22, № 1. — С. 49-61.

7. Морозов Е. В. О единичных диагностических тестах относительно слипаний переменных в булевых функциях // Прикладная математика и информатика: Труды факультета ВМК МГУ имени М. В. Ломоносова. — 2013. — № 44. — С. 103-113.

8. МорозовЕ. В., Романов Д. С. О тестах относительно локальных линейных слипаний входов схем // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 года). — Нижний Новгород: Издательство Нижегородского университета, 2011.

- С. 330-334.

9. МорозовЕ. В., Романов Д. С. О проверяющих тестах относительно множественных линейных слипаний переменных // Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного

80-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 1823 июня 2012 г.). — М.: Издательство механико-математического факультета МГУ, 2012.-С. 144-147.

10. МорозовЕ. В. О диагностических тестах относительно слипаний переменных в булевых функциях // Материалы IX молодежной научной школы по дискретной математике и ее приложениям. — М.: Издательство ИПМ РАН, 2013.-С. 85-88.

11. МорозовЕ.В. О тестах относительно вытесняющих неисправностей входов схем // Тихоновские чтения: Научная конференция, Москва, МГУ имени М. В. Ломоносова, 28 октября - 1 ноября 2013 г.: Тезисы докладов. — М.: МАКС Пресс, 2013. - С. 77.

12. МорозовЕ.В. Тесты для булевых функций относительно линейных и монотонных симметрических слипаний переменных // Тихоновские чтения: Научная конференция, 2014 г.: Тезисы докладов. — М.: МАКС Пресс, 2014. — С. 45-46.

13. МорозовЕ.В. Тестирование схем, реализующих булевы функции, относительно вытесняющих неисправностей входов // Сборник тезисов XXI Международной научной конференции студентов, аспирантов и молодых учёных Ломоносов-2014, секция "Вычислительная математика и кибернетика". — М.: Издательский отдел факультета ВМК МГУ, 2014. — С. 40-41.

14. МорозовЕ.В. О тестах для булевых функций относительно монотонных симметрических слипаний переменных // Проблемы теоретической кибернетики. Материалы XVII международной конференции (Казань, 16-20 июня 2014 г.). - Казань: Отечество, 2014. - С. 213-215.

15. MorozovE.V. Single-fault diagnostic tests for coalescences of variables in Boolean functions // Computational Mathematics and Modeling. — 2014. — V. 25, №4.-P. 583-591.

Напечатано с готового оригинал-макета

Подписано в печать 27.03.2015 г. Формат 60x90 1/16. Усллечл. 1,0. Тираж 100 экз. Заказ 050.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел7Факс 8(495)939-3891.