В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 9
Текст из файла (страница 9)
Для построения теста используются абл»»пы неисправностей из задачи 6.18.1. Пр»» этом существенны следу° ф кты. Дюбаа неиспРавность блока с номеРом и вида Е» схемы Е„ обнаружявается по анашзу функции неисправности на его второл» вы ходе (т. е. на выходе схемы г„). Если неисправность в блоке с номером», 1 <» < и, не обнаруживается на его втором выходе (т. е. на выходе схемы г»), то па наборах теста функция неисправности, реализуемая на выходе схемы г»», отличима от всех функций неисправности, возникающих на этом выходе прн всевозможных неисправностях в блоке с номером» вЂ” 1, Все неисправности в»-м блоке (1 < г' < и), не отличимые по анализу функш»и неисправности на его втором выходе (т.
е. на выходе схемы г;), отличаются на наборах теста по анализу функции неисправности нь выходе схемы з, ». Нижняя оценка длины теста следует из задачи 6.18.1 лля блока, вычисляющего два старших разряда суммы. 2) Наборы теста порождаются словам~» длины 2п следующего вида: [ОО[» '1ЦОЦ" ', [1Ц' '00[ОЦ" ' (г = 1;и), порядок переменных— х:у .. хг,рг.х»,у», Указание, Для построения теста используется таблица неисправносгей из задачи 6.18.2, Нижняя оценка следует из конструктивных соображений. 3) Наборы теста порождаются словами длины 2п следующего вида: [ОЦ", 10[ОЦ" ', 00[10[" ', 01[10[" ', порядок переменных теста используется таблица неисправностей из задачи 6.18.3, 6.22.
(8. М. Не»Ыу [2Ц), Указание. Рассмотрите разложение булевой функции в полинам Жегелкина. 6 23. (В, Н. Носков [16[). Указание. Верхняя оценка очевидна Для доказательства нижней рассмотрите функцию х»хг... х„ч х»хг " " йх 6.24. (И. А. Чегис, С. В. Яблонский [20[) у асимптотически наилучший метод си»»таза 626 У ие Доказательства прова от пр „в х» хз а хз Ь хг х» хз х» хз хг х» Ьа хз хг Рис. Зб Рис. 37. Рис. 38 714. Схема представлена нь рис, 38, указа»»ие. Нижняя оценка К параграфу 7. ') дедусе и' ( ') (6 3) 2) Дост точно использовать (6 б) 3) Достаточно выРазить б(Е) через вероятности г(Е,.
3) т.г. 1) б(М) = П(,Ч) =,, 2) г(,»4) 0(М) = -',. т.з. ц р = -,'. г) р = ,, 7.4. 1) Да, 2) Да. 7.6, Указания. 1) Реализуйте сколь угодно надежно функцию х[у. 2) Реализуйте сколь угодно надежно функции х 6» у и 1, 7.6. 1) Доказательство проводится от противного. 2) Используйте КС, построенную по совершенной ДНФ функции х» е» хг, а также результат задачи 7.6.1. 7,0. Указание. Используйте описанное в предисловии эквивалентное преобрезование связных многополюсных подсхем, состояп»их из контактов одного вида, 7.10.
1) Указание. Аналогично 7.9. 2) Воспользуйтесь тем, что схема реализует функцию х»(хиЧ хз) Ч хг, а также результатом задачи 7.6.1. 7.11. Схемы представлены на рис. Зб и 37 соответственно. 7.12. (В. М, Рабинович [16[). Указание. К схеме на рис. 21 надо добавить 4 контакта х», х», х„, х„так, чтобы первые два были бы инцидеитны полюсу Ь (но не полюсу а), вторые два — полюсу а (но не полюсу Ь) схемы, и при этом каждый нз новых контактов должен быть смежен с имеющимся в схел»е противоположным контактом той же переменной. 7.13. Указание. Используйте результат задачи 7.12.
ложности следует нз ачи ~ 61 . ИспользУйте паРаллельное (посчедоват гь, сзннсние схем, на которых достигаются Е '(/),, .(/) . В. В ~нов (13)). Указание а) Верхнян оценка. И вЂ” 3 емы парис, 21и изрешсннязедачи 712 „ зуйте прп и = схемы н и зазачи 7.15. 6) Верхняя оценка. Исп зуйтесь результатом задач = 3 н г = 2) и схемУ на Рис. 36, далее воспо парис. 17 (прп и = ачи 7.15.
Нижние оценки следуют из задачи 7.6 резуиьтатом задачи 7. 7.17, (А. И, Рыбке (17)). Указание. Пусть (ам 5,), (п 5 ) — указанные в тел в уюо ни задачи э пар вершин. Дострой ге изоморфных контакт рф .' онтактных дерева так, что листьями пер ются вершгны а1 аз а,е .. о, л»стаями второго вершины 5 все внутренние вер вершины деревьев являются новыми, и дчя (1,2.,.., ), проводимость между корнем первого дерева и проводки водкмости между корнем второго дерева и бь Список литератур| ~ Щ А, Ахо, Д. Хопкрофз; Д. Ульман, Построение и акали иых алгоритмов, Мп Мир, 1979, 536 с.
12! Г. П. Гаврилов, А. А. Свпоженко, Задачи и упрел дискРетной математики М.: НаУка, 1992, 408 с Щ М. Гэри, Д. Джонсон, Вычислительньш маш и руд задачи, Мп Мир, 1982, 416 с. ' ', (4) КибеРнетический сбоРник (Новая серия), №12, М.: Мир, 1975,, 5.10 "Щ.О. В. Лупаков, Асимптотические оценки сложно систем М ' Изд во МГУ 1984 137 с ., 161 Н. П. Редькин, Надежность и диагностика схем, Мп Изд во МГУ 1992, 192 с. (7) А. А. Сапоженко, Некоторые вопросы сл МАКС Пресс, 2001, 46 с.
18) С. В. Яблонский, О невозможности злиминации перебора всех функций из Рз при решении некоторых задач теории схем // ДАН СССР, 124, 1, 1959, с. 44-47. 19) С, В. Яблонский, Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, Мп Наука, Вып.
2, 1959, с. 75-121. [10) С. В. Яблонский, Введение в дискретную математику, Мп Наука, 1986, 384 с. (11) С. В. Яблонский, Элементы математической кибернетики, Мп Выс- шая школа, 2007, 188 с. 112) С А. Ложкин, Лекции по основам кибернетики, Мп Издательский отдел факультета ВМиК МГу им. М.В. Ломоносова, 2004, 256 с. Дополнительная литература 3[ Е, В. Валентинов, О сложности булевых ф1н ий ,13, .
а. орректиРУющ~х,брывы // дь! . П МсждУнаролной конфеРенции "Дискр~ „, Зправляюппгх систем [Красновидово, 13-18 июня 1997 лог МГУ, 1997, с. 10. [14] Х. А. Малатян, Полный тест для бесповторных к Проблемы кибернетики, вып. 23, Мл Наука, 1970, с. 103 118 [16[ В Н. Носков, О длинах мпнимальных единичных диагностическ тестов, контролирующих работу входов логических схем // диск ный анализ, вып. 32, Новосибирск: Изд-во ИМ СО АН СССР, Г978 с.
40-52. [16[ В, М. Рабинович, О самокорректирующихся контактных схемах для счетчика четности // Проблемы кибернетики, вып. 17, Мл Наука 1966. с. 227-231. [17[ А. П. Рыбко, О схемах, допускающих корректирующий кщ р // Проблемы кибернетики, Вып. 39, Мл Наука, 1983. — С. 87-99 [18[ Р. Н. Тоноян, О единичных тестах для контактных схем, реализующих линейные функции // Изв. АН Арм. ССР.
— Т. У1. — Х 1,— 1971. — С. 61-66. [19[ Р. Н. Тоноян, Некоторые тесты для контактных схем, реализующих элементарные симметрические функции // Прикладная математика, межвузовский сборник. — 1983, вьш. 2. — Ереван: Изд-во ЕГУ.— С. 129-140.
[20] И. А. Чегис, С. В. Яблонский, Логические способы контроля работы электрических схем // Труды МИАН СССР, т. 51, М,, 1958, с. 270- 360. [21[ В. М. Кеооу, Еав!!у Феэ1аЫе геа!!вас!оп 1ог !об!с Енисее!опэ // 1ЕЕЕ Тгапэ. СошрпФ,, 1972, №1, р. 124-141. Содержание Введение 3 Часть 1. Инвариантные классы и сложность алгоритмов .... „,, 4 с а1. ИнваРиантиые классы 3 2. Сложность алгоритмов . 7 Часть 2. Эквивалентные преобразования ...........,...,... Гй э 3, Эквивалентные преобразования формул .......
„...,,. Г9 а 4. Эквивалентные преобразования контактных схем ....,...,,, „. 23 Часть 3. Надежность и контроль управляющих систем ........,. „. 32 Э 6. Задача контроля управляющих систем. Тесты для таблиц ... „32 8 6. Тесты для контактных схем и схем из функциональных элементов 37 3 7, Оценка надежности схем. Самокорректирующиеся схемы ...,....46 Ответы и решения """ "".... 60 Литература . ...,.........69 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
