В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011), страница 10
Описание файла
PDF-файл из архива "В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 10 страницы из PDF
. . , x2 , y2 , x1 , y1 . Указание. Для построениятеста используется таблица неисправностей из задачи 6.18.3.6.22. (S. M. Reddy [21]). Указание. Рассмотрите разложение булевойфункции в полином Жегалкина.6.23. (В. Н. Носков [15]). Указание. Верхняя оценка очевидна.
Длядоказательства нижней рассмотрите функцию x1 x2 . . . xn ∨ x̄1 x̄2 . . . x̄n .6.24. (И. А. Чегис, С. В. Яблонский [20]). Указание. Используйтеасимптотически наилучший метод синтеза схем.6.25. Указание. Доказательства проводятся от противного.К параграфу 7.7.1. 1) Следует из (6.1)–(6.3). 2) Достаточно использовать (6.5). 3)Достаточно выразить ξ(Σ) через вероятности ξ(Ei , β).77.2. 1) ξ(M) = η(M) = 41 . 2) ξ(M) = η(M) = 16. 3) ξ(M) =5η(M) = 9 .7.3. 1) p = 13 . 2) p = 14 .7.4. 1) Да.
2) Да.7.5. Указания. 1) Реализуйте сколь угодно надежно функцию x|y. 2)Реализуйте сколь угодно надежно функции x ⊕ y и 1.7.6. 1) Доказательство проводится от противного. 2) Используйте КС,построенную по совершенной ДНФ функции x1 ⊕ x2 , а также результатзадачи 7.6.1.7.9.
Указание. Используйте описанное в предисловии эквивалентноепреобразование связных многополюсных подсхем, состоящих из контактов одного вида.7.10. 1) Указание. Аналогично 7.9. 2) Воспользуйтесь тем, что схемареализует функцию x1 (x̄4 ∨ x3 ) ∨ x2 , а также результатом задачи 7.6.1.7.11. Схемы представлены на рис. 36 и 37 соответственно.7.12. (В. М. Рабинович [16]). Указание.
К схеме на рис. 21 надо добавить 4 контакта x1 , x̄1 , xn , x̄n так, чтобы первые два были бы инцидентны полюсу b (но не полюсу a), вторые два — полюсу a (но не полюсуb) схемы, и при этом каждый из новых контактов должен быть смеженс имеющимся в схеме противоположным контактом той же переменной.7.13.
Указание. Используйте результат задачи 7.12.•x1ax2x2x3•x3x1b ax1x2x3x2x2x3••x3x2x3x1•x1•ab•x̄3x2 •x3 x̄1 x̄3••x̄2x̄2 •x̄1•x3x2bx1•Рис. 36.Рис. 37.Рис. 38.7.14. Схема представлена на рис. 38. Указание. Нижняя оценкасложности следует из задачи 7.6.1.7.15. Указание. Используйте параллельное (последовательное) соединение схем, на которых достигаются Lk1 (f ), . .
. , Lks (f ).7.16. (Е. В. Валентинов [13]). Указание. а) Верхняя оценка. Используйте при n = 3 схемы на рис. 21 и из решения задачи 7.12, далее воспользуйтесь результатом задачи 7.15. б) Верхняя оценка. Используйте схемуна рис. 17 (при n = 3 и r = 2) и схему на рис. 36, далее воспользуйтесьрезультатом задачи 7.15. Нижние оценки следуют из задачи 7.6.1.7.17. (А. И. Рыбко [17]). Указание. Пусть (a1 , b1 ), (a2 , b2 ), . . ., (as , bs )— указанные в условии задачи s пар вершин. Достройте к схеме Σ дваизоморфных контактных дерева так, что листьями первого дерева являются вершины a1 , a2 , . .
. , as , листьями второго — вершины b1 , b2 , . . . , bs ,все внутренние вершины деревьев являются новыми, и для любого i,i ∈ {1, 2, . . . , s}, проводимость между корнем первого дерева и ai равнапроводимости между корнем второго дерева и bi .Список литературы[1] А. Ахо, Д. Хопкрофт, Д. Ульман, Построение и анализ вычислительных алгоритмов, М.: Мир, 1979, 536 с.[2] Г. П. Гаврилов, А. А. Сапоженко, Задачи и упражнения по курсудискретной математики М.: Наука, 1992, 408 с.[3] М.
Гэри, Д. Джонсон, Вычислительные машины и труднорешаемыезадачи, М.: Мир, 1982, 416 с.[4] Кибернетический сборник (Новая серия), №12, М.: Мир, 1975, с. 5-10.[5] О. Б. Лупанов, Асимптотические оценки сложности управляющихсистем, М.: Изд-во МГУ, 1984, 137 с.[6] Н. П. Редькин, Надежность и диагностика схем, М.: Изд-во МГУ,1992, 192 с.[7] А.
А. Сапоженко, Некоторые вопросы сложности алгоритмов, М.:МАКС Пресс, 2001, 46 с.[8] С. В. Яблонский, О невозможности элиминации перебора всех функций из P2 при решении некоторых задач теории схем // ДАН СССР,124, 1, 1959, с. 44-47.[9] С. В. Яблонский, Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, М.: Наука,Вып. 2, 1959, с. 75-121.[10] С. В. Яблонский, Введение в дискретную математику, М.: Наука,1986, 384 с.[11] С. В. Яблонский, Элементы математической кибернетики, М.: Высшая школа, 2007, 188 с.[12] С. А. Ложкин, Лекции по основам кибернетики, М.: Издательскийотдел факультета ВМиК МГУ им.
М.В. Ломоносова, 2004, 256 с.Дополнительная литература[13] Е. В. Валентинов, О сложности булевых функций, от трех переменных в классе контактных схем, корректирующих обрывы // Труды II Международной конференции “Дискретные модели в теорииуправляющих систем” (Красновидово, 13-18 июня 1997 г.), М.: Диалог МГУ, 1997, с. 10.[14] Х. А. Мадатян, Полный тест для бесповторных контактных схем //Проблемы кибернетики, вып.
23, М.: Наука, 1970, с. 103-118.[15] В. Н. Носков, О длинах минимальных единичных диагностическихтестов, контролирующих работу входов логических схем // Дискретный анализ, вып. 32, Новосибирск: Изд-во ИМ СО АН СССР, 1978,с. 40-52.[16] В. М. Рабинович, О самокорректирующихся контактных схемах длясчетчика четности // Проблемы кибернетики, вып.
17, М.: Наука,1966, с. 227-231.[17] А. И. Рыбко, О схемах, допускающих корректирующий контроль //Проблемы кибернетики, Вып. 39, М.: Наука, 1983. — С. 87–99.[18] Р. Н. Тоноян, О единичных тестах для контактных схем, реализующих линейные функции // Изв. АН Арм. ССР. — Т. VI. — N 1. —1971. — С. 61–66.[19] Р. Н. Тоноян, Некоторые тесты для контактных схем, реализующихэлементарные симметрические функции // Прикладная математика,межвузовский сборник. — 1983, вып. 2. — Ереван: Изд-во ЕГУ.
—С. 129–140.[20] И. А. Чегис, С. В. Яблонский, Логические способы контроля работыэлектрических схем // Труды МИАН СССР, т. 51, М., 1958, с. 270360.[21] S. M. Reddy, Easily testable realization for logic functions // IEEETrans. Comput., 1972, №1, p. 124-141.СодержаниеВведение . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Часть 1. Инвариантные классы и сложность алгоритмов . . . . . . . . . . . . . . 4§ 1. Инвариантные классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 4§ 2. Сложность алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Часть 2. Эквивалентные преобразования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19§ 3. Эквивалентные преобразования формул . . . . . . . . . . . . . . . . . . .
. . . . . . .19§ 4. Эквивалентные преобразования контактных схем . . . . . . . . . . . . . . . . 23Часть 3. Надежность и контроль управляющих систем . . . . . . . . . . . . . . 32§ 5. Задача контроля управляющих систем. Тесты для таблиц . . . . . . . 32§ 6. Тесты для контактных схем и схем из функциональных элементов37§ 7. Оценка надежности схем. Самокорректирующиеся схемы .
. . . . . . . 46Ответы и решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 69.