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

• Романов Дмитрий Сергеевич
• доктор наук
• 2019

Оглавление диссертации доктор наук Романов Дмитрий Сергеевич

Введение

В1. Обзор результатов, примыкающих к теме диссертации

В2. Базовые определения и обозначения

В3. Структура и основные результаты диссертации

Глава 1. Некоторые оценки длин тестов при неисправностях на входах схем

§ 1. Проверяющие тесты для счетчика четности относительно некоторых типов константных неисправностей на входах схем

§ 2. Тесты относительно локальных слипаний входов схем

§ 3. Тесты относительно перестановок входов схем

Глава 2. Некоторые оценки длин тестов при неисправностях в схемах из функциональных элементов

§ 4. Единичные проверяющие тесты при константных неисправностях на выходах функциональных элементов произвольного полного базиса

§ 5. Единичные проверяющие тесты при константных неисправностях на входах и выходах функциональных элементов

§ 6. Полные проверяющие тесты при константных неисправностях на выходах функциональных элементов некоторого базиса

§ 7. Полные проверяющие тесты при инверсных неисправностях на выходах функциональных элементов некоторого базиса

§ 8. Единичные диагностические тесты при константных неисправностях на выходах функциональных элементов

§ 9. Единичные диагностические тесты при инверсных неисправностях на

выходах функциональных элементов

Глава 3. Некоторые оценки длин проверяющих тестов при неисправностях контактов в схемах переключательного типа

§ 10. Проверяющие тесты при неисправностях контактов в контактных схемах

§ 11. Проверяющие тесты при неисправностях контактов в обобщенных итеративных контактных схемах

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Об оценках длин минимальных тестов для логических схем»

Введение

В1. Обзор результатов, примыкающих к теме диссертации

Булевы функции и схемы. Двоичная система счисления была в современном виде представлена в работе Г. В. Лейбница [382]. Под булевой функцией (функцией алгебры логики) понимают функцию, отображающую при некотором натуральном п множество п-мерных двоичных векторов (п-разрядных двоичных наборов) в множество двоичных цифр. Булевы функции вошли в математический обиход в результате переосмысления У. С. Джевонсом [369, 370, 372], Ч.С. Пирсом [395, 396], Э. Шредером [420] и Г.М. Шеффером [424] работ 1847 и 1854 гг. Дж. Буля по символическому анализу логики [324, 325] и работы 1847 г. О. де Моргана [345] (с интерпретацией исходной алгебры классов Буля, а также с начальной историей развития алгебры логики можно ознакомиться в работах [334, 335]). Вводимая естественным образом операция суперпозиции над булевыми функциями приводит к понятиям замкнутого класса булевых функций (т. е. класса, содержащего те и только те булевы функции, которые можно выразить суперпозициями над множеством функций из этого класса) и полной системы булевых функций (т. е. такого множества функций, с помощью которого можно выразить любую булеву функцию). В 1920 году Э. Л. Пост сформулировал критерий полноты произвольной системы булевых функций и полностью построил решетку включений замкнутых классов булевых функций [402, 403].

Именно развитие идей алгебры логики приводит к появлению представлений о дискретных вычислительных устройствах как моделях физических вычислительных и коммуникационных систем. П. С. Эренфест в 1910 г. своем реферате [304] на русский перевод книги Л. Кутура [338] увязал разработанность алгебры логики с возможностью решения синтезных задач для сетей

автоматических телефонных линий, указав на простую связь способов соединения проводников с логическими функциями [428, с. 125-128]. Это замечание Эренфеста можно считать моментом зарождения теории синтеза дискретных управляющих систем без памяти. Отметим, что аналогичное замечание, но в частной переписке, возникло за 24 года до публикации Эренфеста, — в письме [397] 1886 г. Ч. С. Пирса первому американскому изобретателю логической машины А. Маркванду. Построенная Марквандом в 1882 г. логическая машина [386] сохранилась до настоящего времени. На постройку машины Маркванд был воодушевлен сконструированной в 1869 г. логической машиной Джевонса [371], также сохранившейся; логическая машина Маркванда, как и логическая машина Джевонса, была механической, однако впоследствии — после получения упомянутого письма Пирса — Маркванд изобразил и электрическую схему, выполняющую функции логической машины, что считается первым в мире примером синтеза дискретной управляющей системы [337, с. 110-114], [333, с. 917].

Первой и исторически естественной моделью дискретных управляющих систем без памяти оказываются контактные схемы — неориентированные мультигра-фы, в которых некоторые вершины объявляются входными полюсами, некоторые — выходными полюсами, а каждому ребру приписан либо символ переменной, либо символ переменной с отрицанием (помеченное указанным образом ребро именуется контактом, число контактов называется сложностью контактной схемы). На каждом наборе значений переменных проводят те и только контакты, для которых приписанное контакту выражение обратилось в единицу. Для каждой неупорядоченной пары "входной полюс, выходной полюс" на рассматриваемом наборе следующим образом определяется значение функции проводимости между этими полюсами: единица тогда и только тогда, когда полюса соединены цепью из проводящих на данном наборе контактов. Перебирая все наборы, можно установить, какую систему булевых функций реализует контактная схема. С середины

1930-х годов в Японии (А. Накашима [390]), США (К. Э. Шеннон [422]), СССР (В. И. Шестаков [301, 302]) и Германии (Х. Пиш [399]) начинаются обширные теоретические исследования контактных схем; с подробностями первых примерно 20 лет развития теории контактных схем можно ознакомиться в книге [428]. Наряду с контактными схемами появляются и другие математические модели дискретных управляющих систем без памяти — схемы из функциональных элементов (изобретение основных электромеханических логических вентилей обычно связывают с построением в Германии в 1938 г. программируемого компьютера Z1 К. Цузе; разработанный им же в 1941 г. компьютер Z3 считается первым в мире реально работающим компьютером [337, с. 204-207]; транзисторные вентили появились с изобретением в 1947 году У. Шокли, Дж. Бардином и У. Браттейном биполярного транзистора [316, с. 2-17]), двоичные решающие диаграммы или БОБ (автор модели — К. Ли, 1959 г. [381]), КМОП-схемы (изобретатель — Ф. Вонлас, 1963 г. [316, с. 12-56]) и др. (см., например, [120, с. 73-145]).

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

В классической работе [423] К. Э. Шеннон вводит одну из важнейших сложностных характеристик множества булевых функций в целом, впоследствии названную функцией Шеннона Ь^(п) (относительно сложностного функционала Ф), — это минимальное значение сложностного функционала Ф схемной реализации самой труднореализуемой (относительно функционала Ф) булевой функции п переменных. Под сложностным функционалом Ф здесь может пониматься связанный со схемой функционал из достаточно широкого класса, — например, собственно сложность схемы (число ее контактов/элементов или сумма весов ее элементов), задержка, глубина, длина теста [120, с. 65-67, 73-145, 186-187].

Отметим: сложностной функционал «длина теста» не обладает свойством монотонности относительно удаления элементов схемы [120, с. 186], что, впрочем, не влияет на определение функции Шеннона.

В определении функции Шеннона в явном виде проявляется дуализм понятия «управляющая система», состоящий в том, что каждая управляющая система представляет собой упорядоченную пару объектов, первый из которых является схемой, построенной по четким правилам, а второй — функционированием, строго определяемым схемой (см. работы С. В. Яблонского [305] и А. А. Ляпунова и С. В. Яблонского [134]). Крайне важным является при этом наличие большого (возможно, бесконечного) числа различных эквивалентных схем, т. е. схем с одним и тем же функционированием. Для всех классов управляющих систем, исследуемых в данной диссертации, под функционированием схемы будет пониматься булева функция или система булевых функций, реализуемая схемой. В дальнейшем будем говорить, что схема моделирует булеву функцию, если при подаче констант вместо некоторых входных переменных этой схемы реализуется данная булева функция.

В упоминавшейся уже работе [423] К. Э. Шеннон устанавливает порядок в (2-) роста функции Шеннона сложности контактных схем (КС) и обнаруживает эффект, впоследствии названный эффектом Шеннона: минимальная сложность схем для почти всех булевых функциий п переменных с ростом п ведет себя примерно (точнее, асимптотически, что выяснится из результатов О. Б. Лупанова) как функция Шеннона. Кроме того, Шеннон для доказательства нижней оценки функции Шеннона изобретает так называемый мощностной метод, ставший затем одним из основных методов получения нижних оценок функции Шеннона сложности схем. Аналогичные вычисления для оценивания роста функции Шеннона сложности схем из функциональных элементов в стандартном базисе были проделаны Д. Э. Маллером (Э. Е. МиПег) в работе [389]. Существенным продвижением

стало нахождение О. Б. Лупановым асимптотик функций Шеннона сложности а)

суп

для контактных схем [125]: 27, б) для схем из функциональных элементов (СФЭ) с

оп

положительными весами в произвольном конечном полном базисе В [126]: рв • 2п (где рв — минимум по всем неодновходовым элементам из базиса отношения веса элемента к уменьшенному на 1 количеству входов этого же элемента), в) для формул в произвольном полном конечном базисе В с положительными весами элементов [127, 128]: рв • щ^п' г) а также установление возможности одновременной оптимизации (на уровне асимптотик функций Шеннона) СФЭ по сложности и задержке [130]. Благодаря разработанному О. Б. Лупановым принципу локального кодирования [129] стало возможно устанавливать асимптотики функций Шеннона сложности основных типов управляющих систем не только по классу всех булевых функций, но и по специальным классам булевых функций. Отметим, что Л. А. Шоломов установил [303] асимптотику функции Шеннона рв • 1о]ТпТ | сложности реализации недоопределенных булевых функций с помощью СФЭ в произвольном полном конечном базисе В при весьма слабых ограничениях на мощность области определения Тп булевой функции (впоследствии этот результат усиливался А. Е. Андреевым [29] и А. В. Чашкиным [280, 281]). Важнейший шаг в изучении функций Шеннона сложности схем был сделан С. А. Ложкиным и его учениками, уточнившими асимптотические оценки функций Шеннона сложности схем до так называемых асимптотических оценок высокой степени точности, — с указанием асимптотики второго члена в асимптотическом разложении функции Шеннона сложности схем [117, 118, 119, 121, 384, 122, 123, 124]. Представляет отдельный интерес серия работ О. М. Касим-Заде по оцениванию поведения функций Шеннона сложности и глубины схем над бесконечными базисами [86, 87, 88, 89, 90, 91, 374, 92, 93], в результате которой выяснилось, что для бесконечных базисов функция Шеннона сложности схем из функциональных элементов либо ограничена сверху константой, либо лежит в пределах между

в(1с^п) и в(п), либо лежит в пределах между в(п) и в(2п/2). Все указанные работы предполагали либо разработку новых, более эффективных по сравнению с известными ранее, методов синтеза схем, либо получение новых нижних оценок сложности булевых функций.

Самокорректирование и надежность схем. Производство и эксплуатация вычислительных устройств сопряжены с возникновением в этих устройствах различных дефектов или поломок — неисправностей. В связи с этим в математической кибернетике выделились три направления теоретических исследований: синтез надежных схем из ненадежных элементов, синтез самокорректирующихся схем и контроль работы схем (читателю можно порекомендовать обзоры [308, 112]).

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

Ю. Г. Потапов и С. В. Яблонский [204] показали (1960 г.), что функция Шеннона сложности КС, самокорректирующихся относительно одного замыкания контакта, асимптотически равна 2^. Затем аналогичный результат для коррекции одного размыкания получил в 1964 г. Х. А. Мадатян [135]. Полученные в дальнейшем результаты Э. И. Нечипорука [146, 147, 148], Д. Улига [277], Н. П. Редькина [205, 206] и А. Е. Андреева [28] были связаны с ослаблением ограничений на число возможных поломок контактов при сохранении самокорректирующимися КС асимптотики или порядка роста функции Шеннона сложности обычных

схем. В работе [277] (1978 г.) доказано, что при числе размыканий и замыканий

0( " )

вида 2 ('°82п', верхняя оценка функции Шеннона сложности схем ухудшается асимптотически не более чем в два раза для самокорректирующихся схем. Один из результатов, полученных в работе [28] (1985 г.), можно сформулировать так: при количестве замен контактов на произвольные двухполюсные КС, имеющем

вид 2°(^ 1°8™2п^ асимптотика функции Шеннона сложности схем сохраняется для самокорректирующихся схем (в этой же работе найдены асимптотики функций Шеннона сложности самокорректирующихся КС, последовательно-параллельных КС, контактно-вентильных схем и формул в стандартном базисе, реализующих частичные булевы функции и функции из инвариантных классов).

При рассмотрении самокорректирующихся СФЭ становится очевидной необходимость деления базиса на непустые абсолютно надежную и ненадежную части. Г. И. Кириенко доказал, что в случае, когда надежная часть базиса функционально полна, имеют место такие факты: 1) если число поломок элементов в схеме не превосходит константы, то поведение функции Шеннона сложности самокорректирующихся СФЭ асимптотически совпадает с поведением функции Шеннона сложности СФЭ [97] (1964 г.); 2) если двоичный логарифм числа ( поломок элементов в схеме растет медленнее числа п входных переменных (^2 ( = о(п)), то поведение функции Шеннона сложности самокорректирующихся СФЭ асимптотически совпадает с поведением функции Шеннона сложности СФЭ, и при этом доля надежных элементов в схеме мала [98] (1970 г.). Д. Улиг в 1974 г. [276] продемонстрировал, что если ( = о(), то поведение функции Шеннона сложности самокорректирующихся СФЭ асимптотически совпадает с поведением функции Шеннона сложности СФЭ и при этом число надежных элементов в схеме зависит только от (, более того, если надежная часть базиса полна, то число надежных элементов не превосходит С(, где С — некоторая константа.

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

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

• построение надежных схем и оценки функции Шеннона их сложности,

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

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

Первыми работами по надежности схем была статья Дж. фон Неймана [392] и последовавшая за ней публикация Э. Ф. Мура и К. Э. Шеннона [387] (обе относятся к 1956 г.). В работе [387] предлагается метод построения сколь угодно надежных контактных схем из ненадежных контактов. Работа [392] — о надежности специальных сетей из нейронов. Если переложить высказанные в ней идеи на синтез надежных СФЭ (см., например, [215, с. 33-46]), то основной результат можно переформулировать так: для любого е, 0 < е < 1/6 и для любого 6, 6 > 0, 5(1 — у/-1—2§), в любом конечном полном базисе для любой булевой функции / возможно построение реализующей / СФЭ, ненадежность которой не превышает 6 (при условии, что элементы независимо подвергаются инверсным неисправностям на выходах с вероятностями не выше е). Эти же идеи фон Нейма-

на привели С. В. Яблонского [310, с. 138-139] к следующей интерпретации: для любого 6 > 0 и для любой булевой функции ](х\,..., хп) в базисе, состоящем из ненадежных элементов отрицания и двуместных конъюнкции и дизъюнкции и абсолютно надежного элемента медианы, при независимых инверсных неисправностях на выходах ненадежных элементов с вероятностями, меньшими 0,5, возможно построение схемы, которая реализует функцию / с вероятностью, большей 1 — 6. В 1982 г. С. В. Яблонский [306] усилил этот результат, доказав существование указанных выше схем, сложность которых асимптотически не превосходит функции Шеннона сложности СФЭ (2ПП • (1 + о(1)) для данного базиса). Отметим, что здесь речь шла не просто о построении надежных схем (для которых задается ограничение сверху на вероятность появления ошибки на выходе схемы при всяком входном наборе), а о построении схем, с высокой вероятностью реализующих требуемую функцию.

С момента выхода в свет пионерской работы Дж. фон Неймана [392] инверсные неисправности на выходах элементов стали классическим видом неисправностей для задач надежности схем. Дж. фон Нейман в этой же статье обнаружил для реализации штриха Шеффера достаточность логарифмической (по сложности) надежностной избыточности схем в модели с увеличением числа выходов схемы при заданном пороге количества неверных значений на выходах. В 1977 г. Р. Л. Добрушин и С. И. Ортюков [67] показали, что при е < 0,07 в базисе из трехвходовых элементов и в базисе {х | у} для надежной реализации произвольной булевой функции сложности С достаточно О (С 1п С) элементов, что дало логарифмическую (по сложности) верхнюю оценку надежностной избыточности схем. В статье Р. Л. Добрушина и С. И. Ортюкова [66] (1977 г.), продолженной вызванными ею работами Н. Пиппенджера, Дж. Д. Стамулиса и Дж. Н. Цицикли-са [401] (1991 г.), А. Гал [357] (1991 г.), Р. Райшука и Б. Шмельца [413] (1991 г.) и П. Гача и А. Гал [355] (1994 г.) доказывается существование классов функций,

которые не могут быть реализованы надежными схемами с менее чем логарифмической по сложности избыточностью. Отметим здесь же статью 1997 г. Д. Клейтмана, Т. Лейтона и Ю. Ма [376], в которой, фактически, изучаются оценки надежностной избыточности СФЭ в стандартном базисе, находящихся под действием источника неисправностей, способного замыкать какой-то из входов функционального элемента на его выход.

В работах А. А. Мучника и С. Г. Гиндикина [57] (1965 г.) и В. В. Тарасова [272, 273, 274] (1975, 1976, 2006 гг.) сформулированы условия полноты и возможности построения сколь угодно надежных схем в ненадежных базисах.

В 1977 г. С. И. Ортюков [169] доказал возможность сохранения для надежных СФЭ в произвольном конечном полном ненадежном базисе асимптотики функции Шеннона сложности обычных СФЭ, однако при значительных ограничениях на характер убывания к нулю величины е в зависимости от роста п; в статье этого же автора 1981г. [170] эти ограничения были существенно ослаблены. Н. Пиппенджер [400] в 1985 г. установил для произвольного конечного полного ненадежного базиса сохранение порядка роста функцией Шеннона сложности надежных СФЭ по сравнению с функцией Шеннона сложности обычных СФЭ в том же базисе. Д. Улиг [431] продемонстрировал сохранение для надежных СФЭ в произвольном конечном полном ненадежном базисе асимптотики функции Шеннона сложности обычных СФЭ при произвольном убывании к нулю величины е в зависимости от роста п (а при постоянном е асимптотику функции Шеннона сложности обычных СФЭ оказалось достаточным домножить на (1 + с), где с — произвольная положительная константа).

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

Обширное исследование асимптотически минимальных по ненадежности схем в различных базисах проводится М. А. Алехиной и ее учениками с 1993 г. по настоящее время: [9, 312, 18, 19, 20, 21, 42, 43, 44, 45, 46, 47] — относительно инверсных неисправностей на выходах элементов, [10, 25, 287, 288, 289, 290, 291]

— относительно инверсных неисправностей на входах элементов, [4, 8, 11, 14, 22]

— относительно однотипных константных неисправностей на выходах элементов, [5, 6, 7, 8, 11, 12, 13, 23] — относительно однотипных константных неисправностей на входах элементов, [313, 15, 17] — относительно неисправностей как на входах, так и на выходах элементов, [16, 24] — относительно слипаний входов элементов. При этом в ряде случаев сложность получаемых надежных схем имела тот же порядок роста, что и функция Шеннона сложности обычных схем [7, 8, 9, 11, 312, 42, 287, 291].

Тесты для схем. Одним из подходов к распознаванию наличия неисправностей в вычислительных устройствах является тестовый подход, методология которого основана на генерации на входах вычислительного устройства некоторых входных воздействий и на анализе информации, появляющейся на выходах устройства. Основоположниками математической теории тестового контроля работы схем являются С. В. Яблонский и И. А. Чегис, опубликовавшие в 1955 году статью [311] и затем в 1958 году — ставшую классической работу [283] (см. также работы С. В. Яблонского [307, 308]).

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

вид схемы меняться не может. Тестовое исследование схемы заключается в подаче на входы схемы входных наборов и анализе выдаваемых при этом выходных значений. Множество входных наборов схемы называется проверяющим тестом тогда и только тогда, когда по этому множеству с точностью до функциональной эквивалентности можно распознать факт наличия неисправности. Множество входных наборов схемы называется диагностическим тестом тогда и только тогда, когда по этому множеству с точностью до функциональной эквивалентности можно распознать тип неисправности. Число наборов в тесте называется длиной теста. Тест минимальной длины называется минимальным. Если источник неисправностей может вызвать не более чем одну поломку в схеме, то тест относительно этого источника называется единичным; если же число поломок может быть любым, то тест относительно этого источника называется полным. В данной работе используется понятие тривиальной неисправности — такой неисправности, при возникновении которой для любого набора входных значений и для любого входа элемента (выхода элемента, входа схемы) у исходной и неисправной схем значения на указанном входе элемента (выходе элемента, входе схемы соответственно) совпадают. (Контакт в КС при этом можно считать элементом схемы, его состояния на входных наборах «разомкнут», «замкнут» — значениями на выходах элемента, а значения приписанной контакту переменной

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

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

на тестопригодные схемы), и что в упоминаемых далее работах К. А. Попкова рассматриваются неизбыточные (и даже тестопригодные) схемы именно в таком смысле; для результатов из остальных работ используемая в диссертации корректировка понятий неизбыточности и тестопригодности несущественна. Под длиной минимального теста для системы булевых функций будем подразумевать минимум — по всем тестопригодным схемам, реализующим эту систему булевых функций, — длины минимального теста для схемы, или же ноль, если таких тестопригодных схем нет. Под функцией Шеннона (натурального аргумента п) длины теста будем подразумевать максимум — по всем неконстантным булевым функциям, существенно зависящим от п переменных, — длины минимального теста для булевой функции. Требование тестопригодности (как и неизбыточности) схем, учитываемых в определении длины теста для системы булевых функций, возникает естественным образом, — дабы избежать вырожденности ряда задач тестирования, связанной с самокорректированием схем (см. [215, стр. 110-111]). Константы же исключены из рассмотрения в определении функции Шеннона, т. к. в ряде классов управляющих систем для них нет неизбыточных (во вводимом в этой работе смысле) схем или схем без дополнительных переменных.

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

мальная длина тестовой последовательности в дереве решений — глубина дерева решений (см., например, [143, 144]).

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

Список литературы диссертационного исследования доктор наук Романов Дмитрий Сергеевич, 2019 год

Литература

1. Алексеев В. Б. Лекции по дискретной математике : учебное пособие. — М.: ИНФРА-М, 2018. — 90 с.

2. Алексеев В. Б. О расшифровке некоторых классов монотонных многозначных функций // Журн. вычисл. математики и матем. физики. — 1976. — Т. 16, №1. —С. 189-198.

3. Алексеев В. Б., Вороненко А. А., Селезнева С.Н. О сложности реализации функций к-значной логики поляризованными полиномами // Труды V Международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 26-29 мая 2003 г.). — М.: МАКС Пресс, 2003. — С. 8-9.

4. Алехина М. А. О надежности схем из ненадежных функциональных элементов при однотипных константных неисправностях на выходах элементов // Дискрет. матем. 1993. — Т. 5, вып. 2. — С. 59-74.

5. Алехина М. А. О надежности схем в базисах {х | у}, {х ^ у} при однотипных константных неисправностях на входах элементов // Дискретный анализ и исследование операций. Серия 1. — 2001. — Т. 8, №2. — С. 3-14.

6. Алехина М. А. Нижние оценки ненадежности схем в некоторых базисах при однотипных константных неисправностях на входах элементов // Дискретный анализ и исследование операций. Серия 1. — 2002. — Т. 9, № 3. — С. 3-28.

7. Алехина М. А. Синтез и сложность надежных схем в базисе {&, V, —} при однотипных константных неисправностях на входах элементов // Дискретная математика. — 2003. — Т. 15, вып. 1. — С. 98-109.

8. Алехина М. А. О сложности надежных схем из ненадежных элементов при однотипных константных неисправностях // Дискретный анализ и исследование операций. Серия 1. — 2004. — Т. 11, №2. — С. 3-17.

9. Алехина М. А. О надежности и сложности схем в базисе {х | у} при инверсных неисправностях элементов // Дискретн. анализ и исслед. опер. Сер. 1. — 2005.—Т. 12, №2.— С. 3-11.

10. Алехина М. А. О надежности и сложности схем в базисе {х | у} при инверсных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. — 2005. — №6(21). — С. 36-41.

11. Алехина М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов. — Пенза: ИИЦ ПГУ, 2006. — 156 с.

12. Алехина М. А. О надежности схем в базисе {х V у V г,ж&у&г,ж} при однотипных константных неисправностях на входах элементов // Дискретная математика. — 2006. — Т. 18, вып. 1. — С. 116-125.

13. Алехина М. А. О надежности схем в базисе при однотипных константных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2007. — № 1. — С. 18-27.

14. Алехина М. А. О надежности схем в произвольном полном конечном базисе при однотипных константных неисправностях на выходах элементов // Дискретная математика. — 2012. — Т. 24, вып. 3. — С. 17-24.

15. Алехина М. А. Синтез надежных схем при константных неисправностях на входах и выходах элементов // Известия высших учебных заведений. Физико-математические науки. — 2015. — №2. — С. 3-15.

16. Алехина М. А. Синтез надежных схем при линейных слипаниях переменных в базисе "антиконъюнкция" // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2016. — № 1. — С. 63-70.

17. Алехина М. А. Об асимптотически оптимальных по надежности схемах при неисправностях элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2016. — №4. — С. 6067.

18. Алехина М. А., Барсукова О. Ю. О ненадежности схем из функциональных элементов, подверженных двум типам неисправностей // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2013. — №3. — С. 33-50.

19. Алехина М. А., Васин А. В. О надежности схем в базисах, содержащих функции не более чем трех переменных // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. — 2009. — Т. 151, книга2. — С. 25-35.

20. Алехина М. А., Васин А. В. Достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадежностью // Изв. вузов. Матем. — 2010. — № 5. — С. 79-82.

21. Алехина М. А., Васин А. В. О базисах с коэффициентом ненадежности 2 // Матем. заметки. — 2014. — Т. 95, №2. — С. 170-201.

22. Алехина М. А., Клянчина Д. М. Об асимптотически оптимальных по надежности схемах в некоторых специальных базисах. // Известия высших

учебных заведений. Поволжский регион. Физико-математические науки. — 2010. —№4(16). — С. 3-13.

23. Алехина М. А., Курышева В. В. О надежности схем в базисе "антиконъюнкция" при константных неисправностях на входах элементов // Известия вузов. Математика. — 2016. — № 7. — С. 3-9.

24. Алехина М. А., Логвина О. А. Ненадежность схем при слипаниях входов элементов // Прикладная дискретная математика. Приложение. — 2016. № 9. — С. 98-100.

25. Алехина М. А., Чугунова В. В. Об асимптотически наилучших по надежности схемах в базисе {&, V, —} при инверсных неисправностях на входах элементов // Дискретн. анализ и исслед. опер. Сер. 1. — 2006. — Т. 13, №4. — С. 3-17.

26. Андреев А. Е. О качественных и метрических свойствах тестовых алгоритмов : Дисс. ... канд. физ.-мат. наук. : 01.01.09 / Андреев Александр Егорович. — М.: МГУ, 1981. — 145 с.

27. Андреев А. Е. Об асимптотическом поведении числа тупиковых тестов и минимальной длины теста для почти всех таблиц // Проблемы кибернетики. — Вып. 41. — М: Наука, 1984. — С. 117-141.

28. Андреев А. Е. Универсальный принцип самокорректирования // Математический сборник. — 1985. — Т. 127(169), №2(6). — С. 147-172.

29. Андреев А. Е. О сложности реализации частичных булевых функций схемами из функциональных элементов // Дискретная математика. — 1989. — Т. 1, вып. 4. — С. 36-45.

30. Антюфеев Г. В., Романов Д. С. Об оценках функции Шеннона длины диагностического теста при локальных константных неисправностях на входах схем // Вопросы радиоэлектроники. Серия ЭВТ. — 2016. — №7. — С. 49-51.

31. Башов М. А., Селезнева С. Н. О длине функций к-значной логики в классе полиномиальных нормальных форм по модулю к // Дискретная математика. — 2014. — Т. 26, вып. 3. — С. 3-9.

32. Беджанова С. Р. О минимальных тестах для схем, реализующих дизъюнкцию // Дискретн. анализ и исслед. опер. — 2008. — Т. 15, №2. — С. 3-11.

33. Беджанова С. Р. Легкотестируемые схемы для линейных функций // Вестн. Моск. ун-та. Серия 1. Матем. Механ. — 2011. — Т. 66, №4. — С. 57-59.

34. Бендер Э. А. Асимптотические методы в теории перечислений // Перечислительные задачи комбинаторного анализа. — М.: Мир, 1979. — С. 266-311.

35. Бородина Ю. В. Синтез легкотестируемых схем в базисе {&, V, —} для систем функций из некоторых классов // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 2007. — Т. 62, №4. — С. 68-72.

36. Бородина Ю. В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. — 2008. — № 1. — С. 40-44.

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

38. Бородина Ю. В. Нижняя оценка длины полного проверяющего теста в базисе {ж|у} // Проблемы теоретической кибернетики. Материалы XVII международной конференции (Казань, 16-20 июня 2014 г.). — Казань: Отечество, 2014. — С. 38-39.

39. Бородина Ю. В. Нижняя оценка длины полного теста в базисе {х|у} // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. — 2015. — Т. 70, №4. — С. 49-51.

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

41. Бубнов С. Е., Вороненко А. А., Чистиков Д. В. Некоторые оценки длин тестов для бесповторных функций в базисе {&, V} // Прикладная математика и информатика. — Вып. 33. — М.: МАКС Пресс, 2009. — С. 90-100.

42. Васин А. В. Об асимптотически оптимальных схемах в базисе {х&у, ^у, х} при инверсных неисправностях на выходах элементов // Изв. вузов. Поволжский регион. Физико-математические науки. — 2008. — №4. — С. 3-17.

43. Васин А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов : Дисс. ... канд. физ.-мат. наук.: 01.01.09 / Васин Алексей Валерьевич. — Пенза, 2010. — 100 с.

44. Васин А. В. О надежности схем в базисах, содержащих функции специального вида // Интеграл. — 2013. — № 1-2. — С. 48-50.

45. Васин А. В. О полных базисах с коэфициентом 5 // Прикладная дискретная математика. Приложение. — 2014. — №7. — С. 113-115.

46. Васин А. В. О широком классе базисов с коэффициентом ненадежности 1 // Дискретный анализ и исследование операций. — 2015. — Т. 22, № 1(121). — С. 5-18.

47. Васин А. В. О базисах с коэффициентом ненадежности 1, содержащих функции, существенно зависящие не более чем от пяти переменных // Известия высших учебных заведений. Математика. — 2015. — № 9. — С. 3-11.

48. Вартанян С.М. Единичные диагностические тесты для последовательных блочных схем : Дисс. ... канд. физ.-мат. наук.: 01.01.09 / Вартанян Сейран Мясникович. — М.: МГУ имени М. В. Ломоносова, 1987. — 114 с.

49. Вороненко А. А. О проверяющих тестах для бесповторных функций // Матем. вопр. киберн. — Вып. 11. — М.: Физматлит, 2002. — С. 163-176.

50. Вороненко А. А. Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикл. матем. и информатика. — 2003. — № 15. — С. 85-97.

51. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0; 1; &; V; -} // Дискр. матем. — 2005. — Т. 17, вып. 2. — С. 139-143.

52. Вороненко А. А. О тестировании бесповторных функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. — 2006. — №2. — С. 45-48.

53. Вороненко А. А. Методы представления дискретных функций в задачах подсчета, тестирования и распознавания свойств : Дисс. ... д. ф.-м. н. : 01.01.09 / Вороненко Андрей Анатольевич. — М.: МГУ, 2007. — 154 с.

54. Вороненко А. А., Чистиков Д. В. Индивидуальное тестирование бесповторных функций // Ученые записки Казанского государственного университета. Сер. Физико-математические науки. — 2009. — Т. 151, кн. 2. — С. 36-44.

55. Вороненко А. А., Чистиков Д. В. Расшифровка бесповторных функций оракулом — счетчиком четности // Прикладная математика и информатика. — Вып. 34. — М.: МАКС Пресс, 2010. — С. 93-106.

56. Гайнанов Д. Н. Об одном критерии оптимальности алгоритма расшифровки монотонных булевых функций // Журн. вычисл. матем. и матем. физ. — 1984. — Т. 24, № 8. — С. 1250-1257.

57. Гиндикин С. Г., Мучник А. А. Решение проблемы полноты для систем функций алгебры логики с ненадежной реализацией // Проблемы кибернетики. — Вып. 15. — М.: Физматгиз, 1965. — С. 65-85.

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

59. Горяинов М. В., Сапоженко А. А. О расшифровке монотонных функций на частично упорядоченных множествах // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 3. — С. 79-80.

60. Горяшко А. П. О синтезе схем с минимальной трудоемкостью тестирования // Автомат. и телемех. — 1981. — № 1. — С. 145-153.

61. Горяшко А. П. О синтезе комбинационных схем, легко тестируемых относительно неисправностей типа «коротких замыканий» // Техническая кибернетика. — 1983. — №5. — С. 70-77.

62. Горяшко А. П. Синтез диагностируемых схем вычислительных устройств. — М.: Наука, 1987. — 288 с.

63. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. : Пер. с англ. — М.: Мир, 1998. — 703 с.

64. Дистель Р. Теория графов. — Новосибирск: Изд-во ин-та математики им. С. Л. Соболева СО РАН, 2002. — 336 с.

65. Дмитриев А. Н., Журавлев Ю. И., Кренделев Ф. П. О математических принципах классификации предметов и явлений // Дискрет. анализ. — Вып. 7. — Новосибирск: ИМ СО АН СССР, 1966. — С. 3-15.

66. Добрушин Р. Л., Ортюков С. И. О нижней оценке для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Проблемы передачи информации. — 1977. — Т. 13, вып. 1. — С. 82-89.

67. Добрушин Р. Л., Ортюков С. И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Проблемы передачи информации. — 1977. — Т. 13, вып. 3. — С. 56-76

68. Долотова О. А. О сложности проверяющих тестов для классов Поста // Труды семинара по дискретной математике и ее приложениям. — М.: Изд-во МГУ, 1989. — С. 233-244.

69. Дюкова Е. В. Об одном алгоритме построения тупиковых тестов // Сборник работ по математической кибернетике. — Вып. 1. — М.: ВЦ АН СССР, 1976. — С. 167-185.

70. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов для бинарных таблиц // Проблемы кибернетики. — Вып. 34. — М.: Наука, 1978. — С. 169-186.

71. Дюкова Е. В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания : Дисс. ... канд. физ.-мат. наук. : 01.01.09 / Дюкова Елена Всеволодовна. — М.: МГУ, 1979. — 127 с.

72. Дюкова Е. В. Асимптотически оптимальные методы дискретного анализа информации в задачах распознавания : диссертация ... доктора физико-математических наук : 05.13.17 / Дюкова Елена Всеволодовна. — М., 1996. — 232 с.

73. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990. — 384 с.

74. Жегалкин И. И. О технике вычислений предложений в символической логике // Математический сборник. — 1927. — Т. 34, № 1. — С. 9-28.

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

76. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. — Вып. 33. — М.: Наука, 1978. — С. 5-68.

77. Золотых Н. Ю. Оценки мощности минимального разрешающего множества пороговой функции многозначной логики // Матем. вопросы кибернетики. — Вып. 17. — М.: Физматлит, 2008. — С. 159-168.

78. Золотых Н. Ю. Расшифровка пороговых и близких к ним функций : Дисс. ... д. ф.-м. н.: 01.01.09 / Золотых Николай Юрьевич. — М.: МГУ, 2013. — 208 с.

79. Золотых Н. Ю., Чирков А. Ю. О верхней оценке мощности минимального разрешающего множества пороговой функции // Дискретный анализ и исследование операций. — 2012. — Т. 19, №5. — С. 35-46.

80. Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций к-значной логики // Дискретный анализ и иссл. операций. — 1995. — Т. 2, №3. — С.18-23.

81. Золотых Н. Ю., Шевченко В.Н. О нижней оценке сложности расшифровки пороговых функций к-значной логики // Журн. вычисл. матем. и матем. физики. — 1999. — Т. 39, №2. — С. 346-352.

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

83. Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука. Физматлит, 1999. — 296 с.

84. Ильин В. А., Садовничий В. А., Сендов Бл. Х. Математический анализ. Начальный курс. — М.: Издательство МГУ, 1985. — 662 с.

85. Ильин В. А., Садовничий В. А., Сендов Бл.Х. Математический анализ. Продолжение курса. — М.: Издательство МГУ, 1987. — 358с.

86. Касим-Заде О. М. О сложности схем в одном бесконечном базисе // Вестник Московского университета. Серия 1. Математика. Механика. — 1994. — №6. — С. 40-44.

87. Касим-Заде О. М. О сложности реализации булевых функций схемами в одном бесконечном базисе // Дискретный анализ и исследование операций. — 1995.— Т. 2, №1. —С. 7-20.

88. Касим-Заде О. М. Общая верхняя оценка сложности схем в произвольном бесконечном полном базисе // Вестник Московского университета. Серия 1. Математика. Механика. — 1997. — №4. — С. 59-61.

89. Касим-Заде О. М. Об одном методе получения оценок сложности схем над бесконечными базисами. // Математические вопросы кибернетики. — Вып. 11. — М.: Физматлит, 2002. — С. 247-254.

90. Касим-Заде О.М. Об одном методе получения оценок сложности схем над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Серия 1. — 2004. — Т. 11, №2. — С.41-65.

91. Касим-Заде О. М. О глубине булевых функций над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Серия 1. — 2007.—Т. 14, №1. —С.45-69.

92. Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным бесконечным базисом // Вестник Московского университета. Серия 1. Математика. Механика. — 2012. — №6. — С. 55-57.

93. Касим-Заде О. М. О порядках роста функций Шеннона сложности схем над бесконечными базисами // Вестник Московского университета. Серия 1. Математика. Механика. — 2013. — № 3. — С. 55-57.

94. Катериночкина Н. Н. Поиск максимального верхнего нуля монотонной функции алгебры логики // Докл. АН СССР. — 1975. — Т. 224, № 3. — С. 557-560.

95. Катериночкина Н. Н. Поиск максимального нуля для некоторых классов монотонных функций из классификации Поста // Журн. выч. матем. и матем. физики. — 1988. — Т. 28, №9. — С. 1397-1406.

96. Кибкало А. А. О -алгоритмах распознавания, использующих короткие тексты : Диссертация ... кандидата физико-математических наук : 01.01.09. / Кибкало Александр Алексеевич. — М.: МГУ, 1988. — 153 с.

97. Кириенко Г. И. О самокорректирующихся схемах из функциональных элементов // Проблемы кибернетики. — Вып. 12. — М.: Наука, 1964. — С. 29-37.

98. Кириенко Г. И. Синтез самокорректирующихся схем из функциональных элементов для растущего числа ошибок в схемах // Дискретный анализ. — Вып 16. — Новосибирск.: ИМ СО АН СССР, 1970. — С. 38-43.

99. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика. — 2005. — Т. 17, вып. 3. — С. 80-88.

100. Коршунов А. Д. О длине минимальных тестов для прямоугольных таблиц. I // Кибернетика. — 1970. — №6. — С. 17-26.

101. Коршунов А. Д. О длине минимальных тестов для прямоугольных таблиц. II // Кибернетика. — 1971. — № 1. — С. 1-11.

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

103. Коляда С. С. О единичных проверяющих тестах для константных неисправностей на выходах функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. — 2011. — №6. — С. 47-49.

104. Коляда С. С. Единичные проверяющие тесты для схем из функциональных элементов в базисах из элементов, имеющих не более двух входов // Дискретный анализ и исследование операций. — 2013. — Т. 20, №2. — С. 58-74.

105. Коляда С. С. Единичные проверяющие тесты для схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. — 2013. — №4. — С. 32-34.

106. Коробков В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Доклады АН СССР. 1963. Т. 150, №4. С. 744-747.

107. Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. — Вып. 13. — М.: Наука, 1965. — С. 5-29.

108. Коробков В. К. Некоторые обобщения задачи «расшифровки» монотонных функций алгебры логики // Дискретный анализ. — Вып. 5. — Новосибирск: ИМ СО АН СССР, 1965. — С. 19-25.

109. Коробков В. К., Резник Т. Л. О некоторых алгоритмах вычисления монотонных функций алгебры логики // Доклады АН СССР. — 1962. — Т. 147, № 5. — С. 1022-1025.

110. Коршунов А. Д. Монотонные булевы функции // Успехи матем. наук. — 2003. — Т. 58, №5.— С. 5-108.

111. Кренделев Ф. П., Дмитриев А. Н., Журавлев Ю. И. Сравнение геологического строения зарубежных месторождений докембрийских конгломератов с помощью дискретной математики // Доклады АН СССР. — 1967. — Т. 173, №5.— С. 1149-1152.

112. Кудрявцев В. Б., Андреев А. Е. Тестовое распознавание // Фундаментальная и прикладная математика. — 2009. — Т. 15, вып. 4. — С. 67-99.

113. Кудрявцев В. Б., Андреев А. Е., Гасанов Э. Э. Теория тестового распознавания. — М.: ФИЗМАТЛИТ, 2007. — 320 с.

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

115. Кузнецов И. А., Романов Д. С. Об оценках длин полных локальных проверяющих тестов относительно слипаний переменных // Материалы XVII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). — Новосибирск: Издательство Института математики СО РАН, 2008. — С. 84-90.

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

117. Ложкин С. А. О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 1996. — №1. — С. 62-69.

118. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. — Вып. 6. — М.: Наука, 1996. — С. 189-214.

119. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем : Диссертация ... доктора физико-математических наук : 01.01.09 / Ложкин Сергей Андреевич. — М.: МГУ им. М.В. Ломоносова, 1998. — 99 с.

120. Ложкин С. А. Лекции по основам кибернетики : Учебное пособие. — М.: Изд. отдел ф-та ВМиК МГУ, 2004. — 256 с.

121. Ложкин С. А., Кондратов А. В. Асимптотические оценки высокой степени точности для сложности реализации систем функций итеративными контактными схемами // Прикладная математика и информатика. — Вып. 21. — М.: МАКС Пресс, 2005. — С. 102-110.

122. Ложкин С. А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучшие оценки высокой степени точности // Вестник Московского университета. Серия 1. Математика. Механика. — 2007. — № 3. — С.19-25.

123. Ложкин С. А., Коноводов В. А. О сложности формул алгебры логики в некоторых полных базисах, состоящих из элементов с прямыми и итеративными входами // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — № 1. — С. 55-68.

124. Ложкин С. А., Коноводов В. А. Оценки высокой степени точности для сложности булевых формул в некоторых базисах из элементов с прямыми и итеративными входами // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — №2. — С. 16-30.

125. Лупанов О. Б. О синтезе контактных схем // Докл. АН СССР. — 1958. — Т. 119, №1. —С. 23-26.

126. Лупанов О. Б. Об одном методе синтеза схем // Изв. ВУЗ. Радиофизика. — 1958. — Т. 1,№1. —С. 120-140.

127. Лупанов О. Б. Об асимптотических оценках сложности формул, реализующих функции алгебры логики // Докл. АН СССР. — 1959. — Т. 128, № 3. — С. 464-467.

128. Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. — Вып. 3. — М.: Физматгиз, 1960. — С. 61-80.

129. Лупанов О. Б. О принципе локального кодирования и реализации функций из некоторых классов схемами из функциональных элементов // Докл. АН СССР. — 1961. — Т. 140, №2. — С. 322-325.

130. Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. — Вып. 23. — М.: Наука, 1970. — С. 43-81.

131. Любич И. Г., Романов Д. С. Новые оценки функции Шеннона длины единичного диагностического теста в некоторых базисах // Проблемы теоретической кибернетики. Материалы XVIII Международной конференции (Пенза, 19-23 июня 2017 г.). — М: МАКС Пресс, 2017. — С. 150-152.

132. Любич И. Г., Романов Д. С. Новые оценки функции Шеннона длины единичного диагностического теста в одном базисе // Дискретные модели в

теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды. — Москва: МАКС Пресс, 2018. — С. 185-187.

133. Любич И. Г., Романов Д. С. О единичных диагностических тестах относительно инверсных неисправностей элементов в схемах над некоторыми базисами // Прикладная математика и информатика. — Вып. 58. — М.: МАКС Пресс, 2018. — С. 47-61. (Перевод: Lyubich I. G., Romanov D. S. Single fault diagnostic tests for inversion faults of circuit elements over some bases // Computational Mathematics and Modeling. — 2019. — Vol. 30, Iss. 1. — Pp. 36-47).

134. Ляпунов А. А., Яблонский С. В. Теоретические проблемы кибернетики // Проблемы кибернетики. — Вып. 9. — М.: Наука, 1963. — С. 5-22.

135. Мадатян Х. А. О синтезе схем, корректирующих размыкание контактов // Доклады АН СССР. — 1964. — Т. 159, №2. — С. 290-293.

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

137. Мадатян Х. А. Построение единичных тестов для контактных схем // Сборник работ по математической кибернетике. — М.: ВЦ АН СССР, 1981. — С. 77-86.

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

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

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

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

142. Морозов Е. В., Романов Д. С. Проверяющие тесты для булевых функций при линейных локальных неисправностях входов схем // Дискретный анализ и исследование операций. — 2015. — Т. 22, № 1. — C. 51-63. (Перевод: Morozov E. V., Romanov D. S. Detecting tests for Boolean functions in presence of local linear faults of the inputs of circuits // Journal of Applied and Industrial Mathematics. — 2015. — Vol. 9, No. 2. — Pp. 263-270.)

143. Мошков М. Ю. Условные тесты // Проблемы кибернетики. — Вып. 40. — М.: Наука, 1983.— С. 131-170.

144. Мошков М. Ю. Деревья решений. Теория и приложения. — Нижний Новгород: Издательство Нижегородского университета, 1994. — 176 с.

145. Мучник А. А., Гиндикин С. Г. О полноте системы ненадежных элементов, реализующих функции алгебры логики // Доклады АН СССР. — 1962. — Т. 144, №5.— С. 1007-1010.

146. Нечипорук Э. И. О корректировании обрывов в вентильных и контактных схемах // Кибернетика. 1968, №5. С. 40-48.

147. Нечипорук Э.И. О топологических принципах самокорректирования // Доклады АН СССР. — 1968. — Т 179, №4. — С. 786-789.

148. Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. — Вып. 21. — М.: Наука, 1969. — С. 5-102.

149. Носков В. Н. О тупиковых и минимальных тестах для одного класса таблиц // Дискрет. анализ. — Вып. 12. — Новосибирск: ИМ СО АН СССР, 1968. — С. 27-49.

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

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

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

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

154. Носков В. Н, Метод синтеза контролепригодных схем из функциональных элементов // Методы дискретного анализа в изучении булевых функций и графов. — Вып. 48. — Новосибирск: Ин-т математики СО АН СССР, 1989. — С. 52-69.

155. Носков В. Н. Самокорректирующиеся комбинационные схемы, допускающие простой контроль // Методы дискретного анализа в оптимизации управляющих систем. — Вып. 48. — Новосибирск: Ин-т математики СО АН СССР, 1989. — С. 42-59.

156. Носков В. Н. Метод синтеза удобных для контроля комбинационных схем // Дискретная математика. — 1993. — Т. 5, вып. 4. — С. 3-23.

157. Носков В. Н. Преобразование схем из функциональных элементов к виду, удобному для контроля // Тр. ин-та мат. СО РАН. — 1994. — Т. 27. — С. 142165.

158. Носков В.Н. О диагностике частей схем из функциональных элементов // Сиб. журн. исслед. опер. — 1994. — Т. 1, № 3. — С, 60-96.

159. Носков В.Н. О преобразованиях комбинационных схем, повышающих надежность их частей // Дискрет. анализ и исслед. операций. — 1996. — Т. 3, №2. — С. 33-61.

160. Носков В.Н. О восстановлении правильной работы неисправных частей комбинационных схем // Дискрет. анализ и исслед. операций. Сер. 1. — 1997. — Т. 4, №4.— С. 47-74.

161. Носков В.Н. Диагностика частей схем в автоматных базисах // Дискрет. анализ и исслед. операций. Сер. 1. — 1999. — Т. 6, № 1. — С. 44-64.

162. Носков В. Н. О преобразованиях, повышающих надежность частей схем в автоматных базисах // Дискрет. анализ и исслед. операций. Сер. 1. — 1999. — Т. 6, №3. — С. 10-41.

163. Носков В. Н. О диагностических и установочных задачах для схем из ненадежных автоматов // Дискрет. анализ и исслед. операций. Сер. 1. — 2000. — Т. 7, № 3. — С. 45-71.

164. Носков В.Н. Об условных тестах для контроля сетей автоматов // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 3. — С. 46-72.

165. Носков В.Н. Эффективная диагностика неисправностей в сетях автоматов // Дискрет. анализ и исслед. операций. Сер. 1. — 2002. — Т. 9, № 3. — С. 48-74.

166. Носков В.Н. О построении контролируемых схем с небольшим числом дополнительных полюсов // Дискретн. анализ и исслед. опер. Сер. 1. — 2003. — Т. 10, №4. — С. 79-102.

167. Носков В.Н., Слепян В. А. О числе тупиковых тестов для некоторого класса таблиц // Кибернетика. — 1972. — № 1. — С. 60-65.

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

169. Ортюков С. И. К вопросу о синтезе асимптотически безызбыточных самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ. — 1977. — Т. 13, вып. 4. — С. 3-8.

170. Ортюков С. И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок // Пробл. передачи информ. — 1981. — Т. 17, вып. 4. — С. 84-97.

171. Осокин В. В. О расшифровке монотонных булевых функций с несущественными переменными // Дискрет. матем. — 2010. — Т. 22, вып. 3. — С. 134-145.

172. Осокин В. В. О параллельной параметро-эффективной расшифровке псевдобулевых функций // Интеллектуальные системы. — 2010. — Т. 14, № 1-4. — С. 429-458.

173. Осокин В. В. О расшифровке логических функций : Дисс. ... к. ф.-м. н. : 01.01.09 / Осокин Виктор Владимирович. — М.: МГУ, 2011. — 117 с.

174. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. — 1995. — Т. 34, № 3. — С. 323-326.

175. Погосян Г. Р. О проверяющих тестах для логических схем. — М.: ВЦ АН СССР, 1982. — 57 с.

176. Попков К. А. Диагностика состояний контактов // Дискрет. матем. — 2013. — Т. 25, вып. 4. — С. 30-40.

177. Попков К. А. Проверяющие и диагностические тесты для функциональных элементов // Дискрет. матем. — 2014. — Т. 26, вып. 2. — С. 83-99.

178. Попков К. А. Оценки длин проверяющих и диагностических тестов для функциональных элементов // Дискретн. анализ и исслед. опер. — 2014. — Т. 21, №6. — С. 73-89.

179. Попков К. А. О единичных тестах для функциональных элементов // Дискрет. матем. — 2015. — Т. 27, №2. — С. 73-93.

180. Попков К. А. Оценки длин тестов для функциональных элементов при большом числе допустимых неисправностей // Дискретн. анализ и исслед. опер. — 2015. — Т. 22, №5. — С. 52-70.

181. Попков К. А. О точном значении длины минимального единичного диагностического теста для одного класса схем. — Препринт № 74 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2015. — 20 с.

182. Попков К. А. О тестах замыкания для контактных схем. — Препринт № 14 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2016. — 20 с.

183. Попков К. А. О тестах замыкания для контактных схем // Дискретная математика. — 2016. — Т. 28, вып. 1. — С. 87-100.

184. Попков К. А. О единичных диагностических тестах для схем из функциональных элементов в базисе Жегалкина. — Препринт № 50 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2016. — 16 с.

185. Попков К. А. Нижние оценки длин полных диагностических тестов для схем и входов схем. — Препринт № 60 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2016. — 12 с.

186. Попков К. А. Нижние оценки длин полных диагностических тестов для схем и входов схем // Прикладная дискретная математика. — 2016. — №4(34). — С.65-73.

187. Попков К. А. Нижние оценки длин единичных тестов для схем из функциональных элементов. — Препринт № 139 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2016. — 20 с.

188. Попков К. А. Нижние оценки длин единичных тестов для схем из функциональных элементов // Дискретная математика. — 2017. — Т. 29, вып. 2. — С. 53-69.

189. Попков К. А. Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание». — Препринт № 030 ИПМ им. М. В. Келдыша РАН. — М.: ИПМ им. М. В. Келдыша РАН, 2017. — 31 с.

190. Попков К. А. Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание» // Прикладная дискретная математика. — 2017. — № 38. — С. 66-88.

191. Попков К. А. О точном значении длины минимального единичного диагностического теста для одного класса схем // Дискретн. анализ и исслед. опер. — 2017. — Т. 24, № 3. — С. 80-103.

192. Попков К. А. Полные диагностические тесты длины два для схем при инверсных неисправностях функциональных элементов. — Препринты ИПМ им. М. В. Келдыша. 2017. № 103. — М.: ИПМ им. М. В. Келдыша РАН, 2017. — 10 с.

193. Попков К. А. Полные проверяющие тесты длины два для схем при произвольных константных неисправностях элементов. — Препринты ИПМ им. М. В. Келдыша. 2017. № 104. — М.: ИПМ им. М. В. Келдыша РАН, 2017. — 16 с.

194. Попков К. А. О проверяющих тестах размыкания для контактных схем // Дискретная математика. — 2017. — Т. 29, вып. 4. — С. 66-86.

195. Попков К. А. Полные проверяющие тесты длины два для схем при произвольных константных неисправностях элементов // Дискретн. анализ и исслед. опер. — 2018. — Т. 25, №2. — С. 62-81.

196. Попков К. А. Полные диагностические тесты длины 2 для схем при инверсных неисправностях функциональных элементов // Комплексный анализ, математическая физика и приложения. Сборник статей. — Тр. МИАН. № 301. — М.: МАИК «Наука/Интерпериодика», 2018. — С. 219-224.

197. Попков К. А. Короткие единичные тесты для схем при произвольных константных неисправностях на выходах элементов. — Препринты ИПМ им. М.В. Келдыша. 2018. №033. — М.: ИПМ им. М.В. Келдыша РАН, 2018. — 16 с.

198. Попков К. А. Короткие единичные тесты для схем при произвольных константных неисправностях на выходах элементов // Дискретная математика. — 2018. — Т. 30, вып. 3. — С. 99-116.

199. Попков К. А. Синтез легкотестируемых схем при однотипных константных неисправностях на входах и выходах элементов. — Препринты ИПМ им. М.В. Келдыша. 2018. №087. — М.: ИПМ им. М.В. Келдыша РАН, 2018. — 18 с.

200. Попков К. А. Синтез легкотестируемых схем при произвольных константных неисправностях на входах и выходах элементов. — Препринты ИПМ им. М. В. Келдыша. 2018. № 149. — М.: ИПМ им. М. В. Келдыша РАН, 2018. — 32 с.

201. Попков К. А. Минимальные полные проверяющие тесты для схем из функциональных элементов в стандартном базисе. — Препринты ИПМ им. М. В. Келдыша. 2018. № 171. — М.: ИПМ им. М. В. Келдыша РАН, 2018. — 7 с.

202. Попков К. А. Короткие полные проверяющие тесты для схем из двухвходо-вых функциональных элементов. — Препринты ИПМ им. М. В. Келдыша, 2018. № 197. — М.: ИПМ им. М. В. Келдыша РАН, 2018. — 24 с.

203. Попков К. А. О диагностических тестах размыкания для контактных схем. — Препринты ИПМ им. М.В. Келдыша, 2018. №271. — М.: ИПМ им. М.В. Келдыша РАН, 2018. — 24 с.

204. Потапов Ю. Г., Яблонский С. В. О синтезе самокорректирующихся контактных схем // Доклады АН СССР. — 1960. — Т. 134, № 3. — С. 544-547.

205. Редькин Н. П. О самокорректировании контактных схем // Проблемы кибернетики. — Вып. 33. — М.: Наука, 1978. — С. 119-138.

206. Редькин Н. П. О самокорректировании контактных схем // Проблемы кибернетики. — Вып. 36. — М.: Наука, 1979. — С. 195-208.

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

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

209. Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Вестник Моск. ун-та. Серия 1. Матем. Механика. — 1986. — №1. — С. 72-74.

210. Редькин Н. П. О проверяющих тестах для схем при однотипных константных неисправностях на входах элементов // Изв. вузов. Математика. — 1988. — №7. — С. 57-64.

211. Редькин Н. П. О схемах, допускающих короткие тесты // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. — 1988. — № 2. — С. 17-21.

212. Редькин Н. П. О схемах, допускающих короткие единичные диагностические тесты // Дискрет. матем. — 1989. — Т. 1, вып. 3. — С. 71-76.

213. Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. — Вып. 2. — М.: Наука, 1989. — С. 198-222.

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

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

216. Редькин Н. П. О единичных проверяющих тестах схем при инверсных неисправностях элементов // XII Международная конференция по проблемам теоретической кибернетики (Нижний Новгород, 1999). Тезисы докладов. — М.: Изд-во механико-математического факультета МГУ, 1999. — С. 196.

217. Редькин Н. П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов // Математические вопросы кибернетики. — Вып. 12. — М.: Физматлит, 2003. — С. 217-230.

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

219. Редькин Н. П. К вопросу о длине диагностических тестов для схем // Матем. заметки. — 2017. — Т. 102, №4. — С. 624-627.

220. Редькин Н. П. О полных диагностических тестах для контактных схем // Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды. — М.: МАКС Пресс, 2018. — С. 231-233.

221. Романов Д. С. Построение тестов и оценка их параметров для некоторых классов контактных схем : Дисс. ... канд. физ.-мат. наук. : 01.01.09 / Романов Дмитрий Сергеевич. — М.: МГУ имени М. В. Ломоносова, 2000. — 114 с.

222. Романов Д. С. О проверяющих тестах для входов счетчиков четности // Материалы XII Международной школы-семинара «Синтез и сложность управляющих систем» (Пенза, 15-21 октября 2001 г.). — М.: Изд-во центра прикладных исследований при мех.-мат. ф-те МГУ, 2001. — Часть II. — С. 188-192.

223. Романов Д. С. О тестах относительно перестановок переменных булевых функций // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г.). — Часть II. — М.: Изд-во центра прикладных исследований при мех.-мат. ф-те МГУ, 2002. — С. 155.

224. Романов Д. С. О единичных диагностических тестах относительно транспозиций переменных булевых функций // Математические методы и приложения. Труды десятых математических чтений МГСУ (26-30 января 2002 года). — М.: Изд-во МГСУ, 2003 г. — С. 114-118.

225. Романов Д. С. О длинах единичных тестов относительно транспозиций переменных булевых функций // Материалы VIII Международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г.). — М.: Изд-во мех.-мат. ф-та МГУ, 2004 г. — С. 96-97.

226. Романов Д. С. О тестах относительно перестановок переменных булевых функций // Труды VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 7-11 декабря 2004 г.). — М.: МАКС Пресс, 2004 г.— С. 69-72.

227. Романов Д. С. Об оценках функций Шеннона длины единичных тестов относительно транспозиций переменных // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. — 2007. — № 2. — С. 23-29. (Перевод: Romanov D. S. On estimates of Shannon functions of the length of unit tests for transpositions of variables // Moscow University Computational Mathematics and Cybernetics. — 2007. — Vol. 31, No. 2. — Pp. 60-65.)

228. Романов Д. С. О полных диагностических тестах относительно локальных слипаний переменных // Научная конференция «Тихоновские чтения» (по-

свящается памяти Андрея Николаевича Тихонова, 25-29 октября 2010 г.). — М.: Изд-во ООО «МАКС Пресс», 2010. — С. 10-11.

229. Романов Д. С. О диагностических тестах относительно локальных слипаний переменных в булевых функциях // Прикладная математика и информатика. — Вып. 36. — М.: МАКС Пресс, 2010. — С. 91-98. (Перевод: Romanov D. S. Diagnostic tests for local coalescences of variables in Boolean functions // Computational Mathematics and Modeling. — 2012. — Vol. 23, Iss. 1. — Pp. 7279.)

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

C. 396-399.

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

232. Романов Д. С. Метод синтеза легкотестируемых схем в одном базисе, допускающих единичные проверяющие тесты константной длины // Вестн. Моск. ун-та. Матем. Механ. — 2012. — №2. — С. 24-29. (Перевод: Romanov

D. S. A method for synthesis of easily-testable circuits in some basis admitting single fault detection tests of constant length // Moscow University Mathematics Bulletin. — 2012. — Vol. 67, No. 2. — Pp. 69-73.)

233. Романов Д. С. Об оценках функции Шеннона длины единичного проверяющего теста относительно произвольных константных неисправностей на выходах элементов // Материалы XI Международного семинара «Дискретная

математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.). — М.: Изд-во мех.-мат. ф-та МГУ, 2012. — С. 160-163.

234. Романов Д. С. Об оценках функции Шеннона длины полного проверяющего теста относительно инверсных неисправностей на выходах элементов в одном базисе // Синтаксис и семантика логических систем: Материалы 4-й Российской школы-семинара, посвященной 80-летию основания Бурятского государственного университета (Улан-Удэ, 14-19 августа 2012 г.). — Иркутск: Изд-во ФГБОУ ВПО «Восточно-Сибирская государственная академия образования», 2012. — С. 105-109.

235. Романов Д. С. О тестах относительно перестановок переменных в булевых функциях // Прикладная математика и информатика. — Вып. 41. — М.: МАКС Пресс, 2012. — С. 113-121. (Перевод: Romanov D. S. Tests with respect to permutations of variables in Boolean functions // Computational Mathematics and Modeling. — 2013. — Vol. 24, Iss. 4. — Pp. 558-565.)

236. Романов Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно произвольных константных неисправностей на выходах элементов // Дискретная математика. — 2013. — Т. 25, вып. 2. — С. 104-120. (Перевод: Romanov D. S. On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates // Discrete Mathematics and Applications. — 2013. — Vol. 23, Iss. 3-4. — Pp. 343-362.)

237. Романов Д. С. О проверяющих тестах для константных неисправностей на входах схемы счетчика четности // Прикладная математика и информатика. — Вып. 46. — М.: МАКС Пресс, 2014. — С. 128-136. (Перевод: Romanov D. S.

Fault detection tests for stuck-at faults on parity counter inputs // Computational Mathematics and Modeling. — 2015. — Vol. 26, Iss. 3. — Pp. 429-435.)

238. Романов Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины // Дискретная математика. — 2014. — Т. 26, вып. 2. — С. 100-130. (Перевод: Romanov D. S. Method of synthesis of easily testable circuits admitting single fault detection tests of constant length // Discrete Mathematics and Applications. — 2014. — Vol.24, Iss. 4. — Pp. 227-251.)

239. Романов Д. С. О синтезе контактных схем, допускающих короткие проверяющие тесты // Ученые записки Казанского университета. Серия Физико-математические науки. — 2014. — Т. 156, кн. 3. — С. 110-115. (Перевод: Romanov D. S. On the design of switching circuits admitting small detection test sets // Lobachevskii Journal of Mathematics. — 2015. — Vol. 36, No. 4. — Pp. 461-465.)

240. Романов Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно инверсных неисправностей на выходах элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. — 2015. — №1. — С. 30-37. (Перевод: Romanov D. S. Synthesis of circuits admitting complete checking tests of constant length under inverse faults at outputs of elements // Moscow University Computational Mathematics and Cybernetics. — 2015. — Vol. 39, No. 1. — Pp. 26-34.)

241. Романов Д. С. Метод синтеза неизбыточных схем в базисе Жегалкина, допускающих единичные диагностические тесты длины один // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — № 4. — С. 38-54.

242. Романов Д. С. О некоторых оценках функций Шеннона длины проверяющих и диагностических тестов // Ломоносовские чтения: Научная конференция, Москва, факультет ВМК МГУ имени М. В. Ломоносова, 18-27 апреля 2016 г. : Тезисы докладов. — М.: Издательский отдел факультета ВМиК МГУ, 2016. — С. 85.

243. Романов Д. С. Метод синтеза неизбыточных схем в стандартном базисе, допускающих единичные диагностические тесты длины два // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2016. — № 3. — С. 56-72.

244. Романов Д. С. О тестах для схем при неисправностях на выходах элементов // Проблемы теоретической кибернетики. Материалы XVIII Международной конференции (Пенза, 19-23 июня 2017 г.). — М: МАКС Пресс, 2017. — С. 213-216.

245. Романов Д. С. Оценки функций Шеннона длин тестов для логических схем // Проблемы теоретической кибернетики. Материалы XVIII Международной конференции (Пенза, 19-23 июня 2017 г.). — М: МАКС Пресс, 2017. — С. 216-220.

246. Романов Д. С., Антюфеев Г. В. О тестах относительно примитивных сдвигов переменных в булевых функциях // Вопросы радиоэлектроники. Сер. ЭВТ. — 2013. — Вып. 2. — С. 64-68.

247. Романов Д. С., Казачек А. Е. Об оценках функций Шеннона длин локальных тестов относительно слипаний // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем». — М.: Изд-во мех.-мат. ф-та МГУ, 2006. — С. 91-97.

248. Романов Д. С., Романова Е. Ю. О единичных проверяющих тестах для схем переключательного типа // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — № 1. — С. 5-23.

249. Романов Д. С., Романова Е. Ю. Единичные проверяющие тесты для схем переключательного типа // Дискретные модели в теории управляющих систем: IX международная конференция (Москва и Подмосковье, 20-22 мая 2015 г.) : Труды. — М.: МАКС Пресс, 2015. — С. 205-207.

250. Романов Д. С., Романова Е. Ю. О единичных проверяющих тестах константной длины для обобщенных итеративных контактных схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2015. — № 3. — С. 42а-50. (Перевод: Romanov D. S., Romanova E. Yu. Single fault detection tests for generalized iterative switching circuits // Moscow University Computational Mathematics and Cybernetics. — 2015. — Vol.39, No. 3. — Pp. 144-152.)

251. Романов Д. С., Романова Е. Ю. Метод синтеза неизбыточных схем, допускающих короткие единичные диагностические тесты при константных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2016. — №2. — С. 87-102.

252. Романов Д. С., Романова Е. Ю. Об оценках функций Шеннона длины теста относительно константных неисправностей // Материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, МГУ, 20-25 июня 2016 г.). — М.: Издательство механико-математического факультета МГУ, 2016. — С. 159-161.

253. Романов Д. С., Романова Е. Ю. Короткие тесты для схем в базисе Жегалкина // Интеллектуальные системы. Теория и приложения. — 2016. — № 3. — С. 7378.

254. Романов Д. С., Романова Е. Ю. Метод синтеза неизбыточных схем, допускающих единичные проверяющие тесты константной длины // Дискретная математика. — 2017. — Т. 29, №4. — С. 87-105. (Перевод: Romanov D.S., Romanova E. Yu. A method of synthesis of irredundant circuits admitting single fault detection tests of constant length // Discrete Mathematics and Applications. — 2019. — Vol. 29, Iss. 1. — Pp. 35-48.)

255. Романов Д. С., Романова Е. Ю. Короткий диагностический тест для одного класса схем // XXI век: итоги прошлого и проблемы настоящего плюс. Серия: Технические науки. Информатика, вычислительная техника и управление. — 2017. —№04(38). — С. 91-93.

256. Рыбко А. И. О контактных схемах, корректирующих замыкания и допускающих контроль // Математические вопросы кибернетики. — Вып. 1. — М.: Наука, 1988. — С. 168-190.

257. Сапоженко А. А. О поиске максимального верхнего нуля монотонных функций на ранжированных множествах // Журн. выч. матем. и матем. физики. — 1991. — Т. 31, № 12. — C. 1871-1884.

258. Сачков В.Н. Введение в комбинаторные методы дискретной математики. — М: Наука, 1982. — 384 с.

259. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика. — 2002. — Т. 14, вып. 2. — С. 48-53.

260. Селезнева С.Н. О сложности обобщенно-поляризованных полиномов к-значных функций // Дискретная математика. — 2009. — Т. 21, вып. 4. — С. 20-29.

261. Селезнева С. Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. — 2015. — Т. 27, вып. 1. — С. 111-122.

262. Селезнева С. Н. Полиномиальные представления дискретных функций. Дисс. ... д. ф.-м. н. : 01.01.09 / Селезнева Светлана Николаевна. — М.: МГУ, 2015. — 257 с.

263. Селезнева С. Н., Дайняк А. Б. О сложности обобщенных полиномов к-значных функций // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008. — № 3. — С. 34-39.

264. Сержантов А. В. Оптимальный алгоритм расшифровки некоторых классов монотонных функций // Журн. вычисл. математики и матем. физики. — 1983. — Т. 23, № 1. — С. 206-212.

265. Слепян В. А. Вероятностные характеристики распределения тупиковых тестов // Дискрет. анализ. — Вып. 12. — Новосибирск: ИМ СО АН СССР, 1968. — С. 50-74.

266. Слепян В. А. Параметры распределения тупиковых тестов и информационные веса столбцов в бинарных таблицах // Дискрет. анализ. — Вып. 14. — Новосибирск: ИМ СО АН СССР, 1969. — С. 28-43.

267. Соколов Н. А. Поиск максимального верхнего нуля для одного класса монотонных дискретных функций // Докл. АН СССР. — 1980. — Т. 251, № 5. — С. 1077-1080.

268. Соколов Н. А. О поиске максимального верхнего нуля для одного класса монотонных функций конечнозначной логики // Журн. выч. матем. и матем. физики. — 1981. — Т21, №6. — С. 1552-1565.

269. Соколов Н. А. Оптимальная расшифровка монотонных булевых функций // Журн. вычисл. математики и матем. физики. — 1987. — Т. 27, № 12. — С. 18781887.

270. Соловьев Н. А. Тесты (теория, построение, применение). — Новосибирск: Наука (Сибирское отделение), 1978. — 192 с.

271. Супрун В. П. Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика. — 1993. — Т. 5, вып. 2. — С. 111-115.

272. Тарасов В. В. К проблеме полноты для систем функций алгебры логики с ненадежной реализацией // Матем. сборник. — 1975. — Т. 98, №.3. — С. 378-394.

273. Тарасов В. В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. — 1976. — Т. 20, вып. 3. — С. 391-400.

274. Тарасов В. В. К проблеме реализуемости функций алгебры логики схемами в базисе из ненадежных функциональных элементов // Пробл. передачи информ. — 2006. — Т. 42, вып. 2. — С. 94-100.

275. Тоноян Р. Н. О единичных тестах для контактных схем, реализующих линейные функции // Изв. АН Арм. ССР. — 1971. — Т. VI, № 1. — С. 61-66.

276. Улиг Д. О синтезе самокорректирующихся схем из функциональных элементов с малым числом надежных злементов // Матем. заметки. — 1974. — Т. 15, вып. 6. — С. 937-944.

277. Улиг Д. Самокорректирующиеся контактные схемы, исправляющие большое число ошибок // Доклады АН СССР. — 1978. — Т. 241, № 6. — С. 1273-1276.

278. Харари Ф. Теория графов. — М.: Мир, 1973. — 300с.

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

280. Чашкин А. В. О сложности сужений булевых функций // Дискретная математика. — 1996. — Т. 8, вып. 2. — С 133-150.

281. Чашкин А. В. Об одном разложении булевых функций // Дискретная математика. — 2000. — Т. 12, вып. 3. — С. 114-123.

282. Чашкин А. В. Лекции по дискретной математике. — М.: Изд-во мех.-мат. ф-та МГУ имени М. В. Ломоносова, 2007. — 261 с.

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

284. Чистиков Д. В. Бесповторные функции с труднотестируемыми подфункциями // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. — 2010. — №4. — С. 38-41.

285. Чистиков Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. — 2011. — Т. 23, № 1. — С. 46-50.

286. Чистиков Д. В. Тестирование бесповторных функций в элементарном базисе // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. — 2011. — №4. — С. 37-40.

287. Чугунова В. В. Синтез асимптотически оптимальных по надежности схем при инверсных неисправностях на входах элементов : Дисс. ... канд. физико-математических наук : 01.01.09 / Чугунова Варвара Валерьевна. — Пенза,

2007. — 110 с.

288. Чугунова В. В. О надежности схем в некоторых приводимых полных базисах // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2007. — №2. — С. 26-39.

289. Чугунова В. В. О реализации булевых функций асимптотически оптимальными по надежности схемами // Дискретный анализ и исследование операций. —

2008. — Т. 15, № 6. — С. 64-90.

290. Чугунова В. В. Асимптотические оценки ненадежности схем при инверсных неисправностях на входах // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2008. — №2. — С. 75-85.

291. Чугунова В. В. Об асимптотически оптимальных по надежности схемах в базисе {х & х2 & Ж3,Ж1_ V х2 V ж^^} при инверсных неисправностях на входах элементов // Математические заметки. — 2011. — Т. 89, вып. 3. — С. 440-458.

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

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

матике: Межвуз. тематич. сб. науч. тр. — Горький: Издательство Горьковского государственного университета, 1988. — С. 86-97.

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

295. Шевченко В. И. О сложности диагностики неисправностей типов «0», «1», «&» и «У».схем из функциональных элементов // Комбинаторно-алгебраические и вероятностные методы и их применение: Межвуз. тематич. сб. науч. тр. — Горький: Издательство Горьковского государственного университета, 1990. — С. 123-150.

296. Шевченко В. И. 0 глубине условных тестов для контроля неисправностей типа «отрицание» в схемах из функциональных элементов // Сибирский журнал исследования операций. — 1994. — Т. 1. — С. 63-74.

297. Шевченко В. И. О глубине условных тестов для диагностики неисправностей в схемах из функциональных элементов // Вестник ВВО АТН РФ. — № 1. — Нижний Новгород, 1995. — С. 11З-118.

298. Шевченко В. И. Исследование сложности условных тестов для диагностики неисправностей схем из функциональных элементов : Дисс. ... канд. физ.-мат. наук. : 01.01.09 / Шевченко Владимир Иванович. — Нижний Новгород: Научно-исследовательский институт прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского, 1995. — 149 с.

299. Шевченко В.Н. О расшифровке пороговых функции многозначной логики // Комбинаторно-алгебраические методы в прикл. матем. — Горький: Горьковский гос. ун-т, 1987. — С. 155-163.

300. Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций k-значной логики // Доклады РАН. — 1998. — Т. 362, №5. — C. 606-608.

301. Шестаков В. И. Некоторые математические методы конструирования и упрощения двухполюсных электрических схем класса А : Дисс. ... канд. физ.-мат. наук. / Шестаков Виктор Иванович — М.: НИИ физики МГУ, 1938. — Часть I. С. 1-34; Часть II. С. 1-79.

302. Шестаков В. И. Алгебра двухполюсных схем, построенных исключительно из двухполюсников (алгебра А-схем) // Журнал технической физики. — 1941. — Т. 11, вып. 6. — С. 532-549.

303. Шоломов Л. А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики. — Вып. 21. — М.: Наука, 1969. — С. 215-226.

304. Эренфест П. Реферат на книгу: Л. Кутюра. Алгебра логики. Переводъ съ французскаго съ прибавлешями проф. И. Слешинскаго // Журналъ Русскаго физико-химическаго общества. Физическш отд. — 1910. — Т. 42, отд. 2. — С. 382-387.

305. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. — Вып. 2. — М.: Государственное издательство физико-математической литературы, 1959. — С. 7-38.

306. Яблонский С. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach center publications. — 1982. — №7. — С. 11-19.

307. Яблонский С. В. Надежность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и ее приложениям (Москва, 31 января - 2 февраля 1984 г.). — М.: Издательство МГУ, 1986. — С.7-12.

308. Яблонский С. В. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. — Вып. 1. — М.: Наука, 1988. — С. 5-25.

309. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.

310. Яблонский С. В. Элементы математической кибернетики. — М.: Высшая школа, 2007. — 188 с.

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

312. Alekhina M. A. Synthesis and complexity of asymptotically optimal circuits with unreliable gates // Fundamenta Informaticae. — 2010. — Vol. 104, No. 3. — Pp. 219-225.

313. Alekhina M. A., Barsukova O. Yu. The reliability of circuits in the basis anticonjuction with constant faults of gates // Computer Science and Information Technology. — 2014. — Vol. 2(1). — Pp. 51-54.

314. Angluin D. Queries and concept learning // Mach. Learning. — 1988. — No. 2. — Pp. 319-342.

315. Angluin D., Hellerstein L., Karpinski M. Learning read-once formulas with queries // J. Assoc. Comput. Mach. — 1993. — Vol.40, Iss. 1. — Pp. 185-210.

316. Bassett R. K. To the digital age : research labs, start-up companies, and the rise of MOS technology. — Baltimore, London: The Johns Hopkins University Press, 2002. — xii+423 p.

317. Bellare M., Coppersmith D., Hastad J., Kiwi M., Sudan M. Linearity testing in characteristic two // IEEE Trans. on Information Theory. — 1996. — Vol. 42, Iss.6. — Pp. 1781-1795.

318. Bellare M., Goldwasser Sh., Lund C., Russell A. Efficient probabilistically checkable proofs and applications to approximations // Proc. of the 25th Symposium on Theory of Computing. — 1993. — Pp. 294-304.

319. Bellare M., Sudan M. Improved non-approximability results // Proc. of the 26th Symposium on Theory of Computing. — 1994. — Pp. 184-193.

320. Bioch J. C., Ibaraki T. Complexity of identification and dualization of positive Boolean functions // Inform. and Comput. — 1995. — Vol. 123, Iss. 1. — Pp. 50-63.

321. Blais E. Testing properties of Boolean functions : Report (PhD thesis) CMU-CS-12-101 / Blais Eric. — Pittsburgh: School of Computer Science, Carnegie Mellon University, 2012. — 149 p.

322. Blum A., Hellerstein L., Littlestone N. Learning in the presence of finitely or infinitely many irrelevant attributes // Journal of Computer and System Sciences. — 1995. — Vol. 50, Iss. 1. — Pp. 32-40.

323. Blum M., Luby M., Rubinfeld R. Self-testing/correcting with applications to numerical problems // J. Comput. Syst. Sci. — 1993. — Vol.47, Iss.3. — Pp. 549-595.

324. Boole G. The mathematical analysis of logic, being an essay towards a calculus of deductive reasoning. — Cambridge: Macmillan, Barclay, & Macmillan, 1847. — 87 p.

325. Boole G. An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities. — London: Macmillan, 1854. — 328 p.

326. Boros E., Hammer P. L., Ibaraki T., Kawakami K. Polynomial-time recognition of 2-monotonic positive Boolean functions given by an oracle // SIAM J. Comput. — 1997. — Vol. 26, Iss. 1. — Pp. 93-109.

327. Bose P., Bandyopadhyay S., Majumder D.D. Synthesis of testable PLAs using adaptive heuristics for efficiency // Proceedings of 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD '90).— 1990.— Pp. 116-120.

328. Breuer M. A. Generation of fault tests for linear logic networks // IEEE Trans. Comput. — 1972. — Vol. C-21, Iss. 1. — Pp. 79-83.

329. Bshouty N. H. Exact learning of formulas in parallel // Machine Learning. — 1997. — Vol. 26, Iss. 1. — Pp. 25-41.

330. Bshouty N. H. Exact learning from an honest teacher that answers membership queries // Theoretical Computer Science. — 2018. — Vol. 733. — Pp. 4-43.

331. Bshouty N. H., Hancock T., Hellerstein L. Learning arithmetic read-once formulas // Proc. 24th ACM Symposium on Theory of Computing. — New York: ACM, 1992. — Pp. 370-381.

332. Bshouty N., Hellerstein L. Attribute efficient learning in query and mistake-bound models // Journal of Computer and System Sciences. — 1998. — Vol. 56, Iss. 3. — Pp. 310-319.

333. Burks A. W. Review: Charles S. Peirce, The new elements of mathematics // Bulletin of the American Mathematical Society. — 1978. — Vol.84, No. 5. — Pp. 913-918.

334. Burris S.N. George Boole // The online Stanford Encyclopedia of Philosophy. — [Электронный ресурс], URL: http://plato.stanford.edu/entries/boole/ (дата обращения 01.10.2018).

335. Burris S. N., Sankappanavar H. P. The Horn theory of Boole's partial algebras // Bull. Symb. Logic. — 2013. — Vol. 19, No. 1. — Pp. 97-105.

336. Chakradhar S. T., Agrawal V. D., Bushnell M. L. Polynomial time solvable fault detection problems // Digest of Papers of 20th International Symposium on Fault-Tolerant Computing. — Newcastle Upon Tyne, UK, 1990. — Pp. 56-63.

337. Computing before computers / edited by W. Aspray. — Ames: Iowa State University Press, 1990. — ix+266 p.

338. Couturat L. L'algebre de la logique. — Paris: Gauthier-Villars, 1905. — 100p. (Перевод: Кутюра Л. Алгебра логики / Переводъ съ прибавлешями проф. И. Слешинскаго. — Одесса: Mathesis, 1909. — iv+l07+xii+6 с.)

339. Damarla T. R. Fault detection in Reed-Muller canonical (RMC) networks // Proceedings of the Conference on Energy and Information Technologies in the Southeast (Southeastcon '89). — IEEE, 1989. — Vol. 1. — Pp. 192-196.

340. Damarla T. R., Karpovsky M. Fault detection in combinational networks by Reed-Muller transforms // IEEE Transactions on Computers. — 1989. — Vol. 3, Iss. 6. — Pp. 788-797.

341. Damaschke P. Adaptive versus nonadaptive attribute-efficient learning // Mach. Learn. — 2000. — Vol. 41, Iss. 2. — Pp. 197-215.

342. Damaschke P., Parallel attribute-efficient learning of monotone Boolean functions // Algorithm Theory — SWAT 2000. SWAT 2000. — Lecture Notes in Computer Science, vol. 1851. — Berlin, Heidelberg: Springer, 2000. — Pp. 504-512.

343. Damaschke P. On parallel attribute-efficient learning // J. Comput. Syst. Sci. — 2003. — Vol. 67, Iss. 1. — Pp. 46-62.

344. DasGupta S., Hartmann C. R. P., Rudolph L. D. Dual-mode logic for function-independent fault testing // IEEE Trans. Comput. — 1980. — Vol. C-29, No. 11. — Pp. 1025-1029.

345. De Morgan A. Formal logic: or, the calculus of inference, necessary and probable. — London: Taylor and Walton, 1847. — xvi+336 p.

346. Dubrova E. V., Muzio J. C. Testability of generalized multiple-valued Reed-Muller circuits // Proceedings of 26th International Symposium on Multiple-Valued Logic. — IEEE, 1996. — Pp. 56-61.

347. Dubrova E. V., Muzio J. C. Generalized Reed-Muller canonical form for a multiple-valued algebra // Multiple-Valued Logic. — 1996. — Vol.1. — Pp. 104-109.

348. Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions // IEEE Trans. Elect. Comput. — 1967. — Vol. EC-16, Iss. 5. — Pp. 671674.

349. Fujiwara H. On closedness and test complexity of logic circuits. IEEE Trans. Comput. — 1981. — Vol. 030, Iss. 8. — Pp. 556-562.

350. Fujiwara H. A new PLA design for universal testability // IEEE Transactions on Computers. — 1984. — Vol. C-33, Iss. 8. — Pp. 745-750.

351. Fujiwara H. Computational complexity of controllability/observability problems for combinational circuits // Proceedings of the 18th International Symposium on Fault Tolerant Computing. — IEEE, 1988. — Pp. 64-69.

352. Fujiwara H. Logic testing and design for testability. — Cambridge, Massachusetts, London: MIT Press, 1990. — 284 p.

353. Fujiwara H., Kinoshita K. A Design of programmable logic arrays with universal tests // IEEE Transactions on Computers. — 1981. — Vol. C-30, Iss. 11. — Pp. 823828.

354. Fujiwara H., Toida S. The complexity of fault detection problems for combinational logic circuits // IEEE Transactions on Computers. — 1982. — Vol. C-31, No. 6. — Pp. 555-560.

355. Gacs P., Gal A. Lower bounds for the complexity of reliable Boolean circuits with noisy gates // IEEE Transactions on Information Theory. — 1994. — Vol.40. — Pp. 579-583.

356. Gainanov D. N. On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions // Comput. Math. Math. Phys. — 1984. — Vol. 24. — Pp. 176-181.

357. Gal A. Lower bounds for the complexity of reliable Boolean circuits with noisy gates // Proc. 32nd Ann. Symp. Foundations Comput. Sci. — 1991. — Pp. 594-601.

358. Geetha V., Devarajan N., Neelakantan P. N. Analysis of different types of faults in a class of Boolean circuits // International Journal of Engineering and Innovative Technology (IJEIT). — 2012. — Vol. 2, Iss. 4. — Pp. 145-149.

359. Geetha V., Devarajan N., Neelakantan P. N. Single network structure for stuck-at and bridging fault analysis and diagnosis for Exclusive-OR sum of products in Reed-Muller canonical circuits // Elixir Elec. Eng. — 2013. — Vol.57. — Pp. 14080-14085.

360. Geetha V., Devarajan N., Neelakantan P.N. Network structure for testability improvement in exclusive-OR sum of products ReedyMuller canonical circuits // Int. J. Eng. Res. Gen. Sci. - 2015. - Vol. 3, Iss. 3. Pp. 368-378.

361. Genkin A. V., Dubner P.N. Aggregation algorithm for finding the informative features // Automat. Remote Control. - 1988. - Vol. 49. - Pp. 81-86.

362. Hansel G. Sur le nombre des fonctions booleennes monotones des n variables // Comptes Rendus de l'Academie des Sciences Paris. Serie A-B. - 1966. -V. 262. - P. 1088-1090. (Русский перевод: Ансель Ж. О числе монотонных булевых функций n переменных // Киберн. сб. Новая серия. - Вып. 5. - М.: Мир., 1968. -C. 53-57).

363. Hayes J. P. On realizations of Boolean functions requiring a minimal or near-minimal number of tests // IEEE Transactions on Computers. - 1971. - Vol. C-20, Iss. 12. - Pp. 1506-1513.

364. Hayes J. P. On modifying logic networks to improve their diagnoaability // IEEE Transactions on Computers. - 1974. - Vol. C-23, Iss. 1. - Pp. 56-62.

365. Hirayama T., Koda G., Nishitani Y., Shimizu K. Easily testable realization based on OR-AND-EXOR expansion with single-rail inputs // IEICE Trans. Inf. & Syst. - 1999. - Vol. E-82D, No. 9. - Pp. 1278-1286.

366. Ibarra O. H., Sahni S. K. Polynomially complete fault detection problems // IEEE Transactions on Computers. - 1975. - Vol. C-24, Iss. 3. - Pp. 242-249.

367. Inose H., Sakauchi M. Synthesis of automatic fault diagnosable logical circuits by function conversion method // Proc. First USA-Japan Computer Conf. - 1972. -Pp. 426-430.

368. Jameil A. K. A new single stuck fault detection algorithm for digital circiuts // Int. J. Eng. Res. Gen. Sci. - 2015. - Vol. 3, Iss. 1. Pp. 1050-1056.

369. Jevons W. S. Pure logic, or the logic of quality apart from quantity: with remarks on Boole's system and on the relation of logic and mathematics. — London: Edward Stanford, 1864. — 87 p.

370. Jevons W. S. Pure logic and other minor works. — London: Macmillan & Co., 1890. — xxiii+300 p.

371. Jevons W. S. On the mechanical performance of logical inference // Philosophical Transactions of the Royal Society. — 1870. — Vol. 160. — Pp. 497-518.

372. Jevons W. S. The Principles of Scientific Method. — 2 vols. — London, New York: Mcmillan & Co., 1879.

373. Kalay U., Hall D. V., Perkowski M. A. A minimal universal test set for self-test of EXOR-Sum-of-Products circuits // IEEE Transactions on Computers. — 2000. — Vol. 49, No. 3. — Pp. 267-276.

374. Kasim-Zade O.M. Depth of boolean functions over an arbitrary infinite basis // Journal of Applied and Industrial Mathematics. — 2008. — Vol.2, No.2. — Pp. 196-210.

375. Kaufman T., Litsyn S., Xie N. Breaking the ^-soundness bound of the linearity test over GF(2) // SIAM Journal on Computing. — 2010. — Vol. 39. — Pp. 1988-2003.

376. Kleitman D., Leighton T., Ma Y. On the design of reliable boolean circuits that contain partially unreliable gates // Journal of Computer and System Sciences. — 1997. — Vol. 55, Iss. 3. — Pp. 385-401.

377. Klivans A., Servedio R. Learning DNF in time 2O(nV3) // Journal of Computer and System Sciences. — 2004. — Vol. 68, Iss. 2. — Pp. 303-318.

378. Kodandapani K. L. A note on easily testable realizations for logic functions // IEEE Transactions on Computers. — 1974. — Vol. C-23, No. 3. — Pp. 332-333.

379. Kovalerchuck B., Triantaphyllou E., Deshpande A. S., Vityaev E. Interactive learning of monotone Boolean functions // Information Sciences: an International Journal. - 1996. - Vol. 94, Iss. 1-4. - Pp. 87-118.

380. Krishnamurthy B., Akers S.B. On the complexity of estimating the size of a test set // IEEE Transactions on Computers. — 1984. — Vol. C-33, No. 8. — Pp. 750-753.

381. Lee C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal. — 1959. — Vol. 38. — Pp. 985-999.

382. Leibnitz G.-G. Explication de l'arithmetique binaire, qui se sert des seuls caracteres 0 et 1 avec des remarques sur son utilite et sur ce qu'elle donne le sens des anciennes figures chinoises de Fohy // Memoires de mathematique et de physique de l'Academie royale des sciences. — Paris: Academie royale des sciences, 1703. — Pp. 85-89.

383. Littlestone N. Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm // Machine Learning. — 1987. — Vol. 2, Iss. 4. — Pp. 285-318.

384. Lozhkin S.A., Shiganov A.E. High accuracy asymptotic bounds on the bdd size and weight of the hardest functions // Fundamenta Informaticae. — 2010. — Vol. 104, No. 3. — Pp. 239-253.

385. Makino K., Ibaraki T. The maximum latency and identification of positive Boolean functions // ISAAC '94 Algorithms and Computation. — Lecture Notes in Comput. Sci. 834. — Berlin: Springer-Verlag, 1994. — Pp. 324-332.

386. Marquand A. A machine for producing syllogistic variation // Studies in logic by members of the Johns Hopkins University. — Boston: Little, Brown, and Company, 1883. — Pp. 12-15.

387. Moore E. F., Shannon C.E. Reliable circuits using less reliable relays // Journal of the Franklin Institute. — 1956. — Vol. 262, Iss. 3. — Pp. 191-208; — Vol. 262, Iss. 4. — Pp. 281-297. (Перевод: Шеннон К. Э. Надежные схемы из ненадежных реле // Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 1963. — С. 114-153).

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

389. Muller D. E. Complexity in electronic switching circuits // IRE Transactions on Electronic Computers. — 1956. — Vol. EC-5, Iss. 1. — Pp. 15-19.