В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 10
Описание файла
PDF-файл из архива "В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 10 страницы из PDF
Пусть (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.
