Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики

В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 7

PDF-файл В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 7 Основы кибернетики (53053): Книга - 7 семестрВ.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики: Основы кибернетики - P2019-09-18СтудИзба

Описание файла

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

Просмотр PDF-файла онлайн

Текст 7 страницы из PDF

24 б), имеющийXX SPPXXXSS S PP длину не более 4.A∨ A∨ A∨ AAA∗6.22. Показать существование такогоA−A−A−базиса из ФЭ, в котором для любой булеAAASSвой функции n переменных существует схе SS∨∨∨AAAA∨ ма, допускающая единичный проверяющийAAAAконстантные неисправности на выходах ФЭA−A−A−A−AAAHAтест длины, не превосходящей n + 1. HH CHC6.23.∗ Доказать, что длина полного проA∨ A∨ AAверяющего теста для входов n-входовой схеSS A∨ мы не превосходит 2n.

Показать неулучшаA?zемость предыдущей оценки для некоторойРис. 25.функции.6.24.∗ Показать, что, начиная с некоторого n, любая булева функция n переменных обладает схемой, допускающей нетривиальный единичный тест, диагностирующий константныенеисправности на выходах ФЭ.6.25. Покажите, что минимальный проверяющий единичные константные неисправности на выходах ФЭ тест для произвольного дешифратора (для произвольного универсального многополюсника) состоит извсех наборов.§ 7. Оценка надежности схем.

Самокорректирующиеся схемы.Для определения уровня надежности схемы часто применяется вероятностный подход (см., например, [6, 12]). Пусть M = (Σ, И) — ненадежная схема Σ от переменных x1 , . . . , xn , переходящая под действиемисточника неисправностей И в состояния Σ = Σ(1) , Σ(2) , . . . , Σ(t) , в которых реализуются функции F = F (1) , F (2) , . . .

, F (t) соответственно, определенные на множестве наборов N = {β1 , . . . , βp }. Пусть далее вероят(i)ность того, что схема Σ находитсяPt в состоянии Σ ,известна и равна πi ,где i = 1, . . . , t, 0 ≤ πi ≤ 1 и i=1 πi = 1. Введем следующие величины,характеризующие ненадежность схемы Σ в модели M:Xξ(M) =πj ,(6.1)F (j) 6= F2≤j≤tXξ(M, β) =Fπj ,(6.2)(j)(β) 6= F (β)2≤j≤tгде β ∈ N , а затем положимη(M) = max ξ(M, β),(6.3)qM (x1 , . . . , xn ) = ξ(M, (x1 , .

. . , xn )).(6.4)β∈NЗаметим, что величина ξ(M) (ξ(M, β)) задает вероятность того, чтосхема Σ реализует функцию, не равную F (соответственно не равную Fна наборе β), и поэтомуη(M) ≤ ξ(M) ≤ pη(M),(6.5)откуда следует, в частности, что η(M) = 0 тогда и только тогда, когда ξ(M) = 0. Схема Σ считается абсолютно надежной в модели M,если η(M) = 0 (или ξ(M) = 0). Это означает, что все состояния схемы Σ, имеющие положительную вероятность, эквивалентны Σ. ФункцияqM (x1 , . . .

, xn ) называется функцией вероятности неправильного срабатывания схемы Σ. В дальнейшем, при записи введенных величин вместопары M = (Σ, И) будем писать просто Σ, если из контекста ясно, какойисточник неисправностей имеется в виду.Рассмотрим вероятностный подход на примере ненадежных СФЭ надбазисом Б = {Ei }bi=1 , где ФЭ Ei реализует булеву функцию ϕi (u1 , . . . , uki ).Пусть для каждого i, i = 1, .

. . , b, известно распределение режимов раkботы ФЭ Ei , то есть для каждого j, j = 1, . . . , 22 i , известна и равна πi,jвероятность того, что ФЭ Ei реализует j-ю булеву функцию от булевыхпеременных u1 , . . . , uki (если считать, что все булевы функции от переменных u1 , . . . , uki упорядочены в соответствии с номерами их столбцовзначений). При нахождении ненадежности схемы Σ над базисом Б будемсчитать, что все ее ФЭ переходят в свои состояния независимо друг отдруга и что любое состояние СФЭ Σ определяется состояниями ФЭ Σ(см. § 5). В соответствии с этим на основе введенных выше соотношений(6.1)-(6.4) можно найти значения ненадежности ξ(Σ) и η(Σ) для СФЭΣ, а также распределение режимов ее работы и функцию qΣ (x1 , .

. . , xn ).Считается, что функция f (x1 , . . . , xn ) допускает сколь угодно надежную реализацию в базисе Б, если для любого ε, ε > 0, существует СФЭΣ над Б, которая реализует f и для которой ξ(Σ) < ε. Повышение надежности при реализации ФАЛ f (x1 , . . . , xn ) возможно, если в базисе Бимеется абсолютно надежный ФЭ Ei , реализующий функцию голосования m(x1 , x2 , x3 ) = x1 x2 ∨x1 x3 ∨x2 x3 (см. [12]). Действительно, если СФЭΣ реализует f и η(Σ) = ε, то для ненадежности СФЭ Σ(1) , показаннойна рис. 26 а), которая тоже реализует f , имеет место равенствоη(Σ(1) ) = H(ε) = 3ε2 − 2ε3(график функции τ = H(ε) показан на рис. 26 б)).xXq 1qXq q xq nXXXXXXXXX XXX XXΣΣτ1ΣQQ12QQQQ@ E@ i@0?а)12ε1б)Рис. 26.1Заметим, что H(0) = 0, H 2 = 12 , что первые две производныефункции H(ε) на отрезке 0; 21 неотрицательны, причем H 0 (0) = H 00 21 = 0 иH 0 12 > 0, H 00 (0) > 0, и что η(Σ(1) ) < ε, если ε < 21 .

Поэтому, рекурсивно применяя указанную процедуру повышения надежности к СФЭ Σ(k) ,результатом которой является СФЭ Σ(k+1) , k = 1, 2, ..., построим последовательность СФЭ Σ(1) , Σ(2) , ..., Σ(k) , ..., реализующих f , для которойη(Σ(k) ) = H(η(Σ(k−1) )) → 0.k→∞kЗаметим также, что СФЭ Σ(k) содержит 3 подсхем вида Σ и 1 + 3 +k· · · + 3k−1 = 3 2−1 ФЭ Ei .Аналогичные построения и оценки применимы и для повышения ξненадежности СФЭ.7.1. 1) Доказать, что ξ(M) = η(M) тогда и только тогда, когда дляM существует проверяющий тест длины 1.2) Доказать, что функция f допускает сколь угодно надежную реализацию в базисе Б тогда и только тогда, когда для любого ε, ε > 0,существует СФЭ Σ над Б, которая реализует f и для которой η(Σ) < ε.3) Доказать, что для вычисления ненадежности η(Σ) в соответствиис (6.3) для СФЭ Σ над базисом Б достаточно знать ненадежности видаξ(Ei , β) для всех ФЭ Ei базиса Б и всех наборов β из B ki , i = 1, .

. . , b.7.2. Ниже указана СФЭ Σ и распределения режимов работы ее ненадежных ФЭ. Найти распределение режимов работы СФЭ Σ, а затем вычислить ξ(Σ), η(Σ) и функцию qΣ .1) Σ — СФЭ на рис. 22 а), где конъюнктор работает абсолютно надежно, а распределения режимов работыдизъюнктора u1∨ u2 и инвертораu1 ∨ u2 u1 ⊕ u2ū1 u1ū1 имеют, соответственно, види.321133442) Σ — СФЭ на рис.

23 а), где дизъюнктор работает абсолютно надежно,а распределениережимов работы конъюнктора u1 &u2 имеет видu1 &u2 ū1.31443) Σ — СФЭ на рис. 24 а), где конъюнктор работает абсолютно надежно,а распределениережимов работы дизъюнктора u1 ∨ u2 имеет видu1 ∨ u2 u1 &u2.21337.3. 1) Пусть в СФЭ Σ на рис. 22 а) дизъюнктор работает абсолютнонадежно, а распределения режимовработы конъюнктораu1 &u 2 и инверu1 &u2 0ū1 0тора ū1 имеют, соответственно, види. Известно,311−p p44что вероятность такого функционирования схемы, при котором на обоихвыходах схемы реализуются тождественные нули, равна 16 . Найти p.2) Пусть распределения режимов работы конъюнктора u1 &u2 и дизъu1 &u2 1юнктора u1 ∨ u2 в СФЭ Σ на рис.

23 а) имеют види1−p pu1 ∨ u2 x, соответственно. Известно, что вероятность такого функ1233ционирования схемы, при котором на выходе Σ реализуется тождественная единица, равна 83 . Найти p.7.4. Пусть базис Б состоит из ФЭ, реализующего функцию голосования, который работает абсолютно надежно, и конъюнктораu1 &u2 , расu1 &u2 1.пределение режимов работы которого имеет вид12331) Достаточно ли 40 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.1?2) Достаточно ли 400 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.002?7.5.∗ Ниже приведены распределения режимов работы ФЭ Ei , i =1, ..., b, ненадежного базиса Б.

Покажите, что в данном базисе возможнасколь угодно надежнаяреализация произвольной функции.u1 ⊕ u2 u1 ∨ u21) b = 1, E1 :;1−ppu1 ∨ u2 1u1 ⊕ u2 1u1 &u22) b = 3, E1 :, E2 :, E3 :.1−p p1−p p1Другой (так называемый логико-комбинаторный [12]) подход к определению уровня надежности схемы связан с понятием самокорректируемости. Схема Σ называется самокорректирующейся относительноисточника неисправностей И, если в модели (Σ, И) все состояния эквивалентны. Естественно считать, что чем больше неисправностей корректирует схема Σ, тем выше уровень ее надежности.

Задача синтезасамокорректирующихся схем является важным частным случаем общейзадачи синтеза.Рассмотрим задачу синтеза контактных схем, которые являются самокорректирующимися относительно источника неисправностей Иr,s (см. §5). Простейший способ решения этой задачи связан с последовательными (или) параллельным дублированием двухполюсной КС.

Легко видеть,что если при этом взять l экземпляров самокорректирующейся относительно Иr,s КС Σ и соединить их последовательно (параллельно), то получим эквивалентную Σ КС Σ0 , которая является самокорректирующейся относительно ИR,S , где R = r, S = (s + 1) · l − 1 (соответственноR = (r + 1) · l − 1, S = s). Аналогичный результат дает указанное выше дублирование, если его применять к каждому контакту схемы (этотспособом можно строить многополюсные самокорректирующиеся КС).Другой способ перехода от (многополюсной) КС Σ к эквивалентной ейКС Σ0 , которая является самокорректирующейся относительно Иσ,1−σ ,где σ ∈ {0, 1}, заключается в следующем.

Разобьем КС Σ на непересекающиеся связные (многополюсные) подсхемы Σ1 , . . . , Σl , каждая изкоторых состоит из контактов одного типа, а затем заменим КС Σi ,i = 1, . . . , l, на КС Σ0i , состоящую из контактов того же типа, которая(i)(i)представляет собой цикл, проходящий через все вершины v1 , . . . , vai КСΣi , если σ = 1 (см. рис. 27 а)) и звезду с центром в новой вершине, соеди(i)(i)ненной со всеми вершинами v1 , . . . , vai КС Σi , если σ = 0 (см. рис. 27 б)).(i)xδv2(i)v2xδ(i)v1(i)v3xδ(i)v1xδ•xδ ....(i)xδxδ..(i)v3(i)vaivaiа)б)Рис.

277.6. 1) Доказать, что если функция xσi , где 1 ≤ i ≤ n и σ ∈ {0, 1}может быть получена из функции f (x1 , ..., xn ) в результате некоторойподстановки констант вместо БП x1 , ..., xi−1 , xi+1 , ..., xn , то в любой КС,реализующий f и корректирующей r обрывов (r замыканий), содержитсяне менее (r + 1) контактов xσi .2) Построить для функции x1 ⊕x2 минимальную КС, корректирующуюа) одно размыкание,б) одно замыкание.7.7.

По контактной схеме Σ построить эквивалентную схему, корректирующую замыкание m контактов и содержащую не более l контактов.1) m = 1, l = 6Σ:2) m = 1, l = 7Σ:3) m = 1, l = 10Σ:4) m = 1, l = 4Σ:5) m = 1, l = 10Σ:6) m = 1, l = 6Σ:7) m = 1, l = 9Σ:8) m = 1, l = 4Σ:7.8. По контактной схеме Σ построить эквивалентную схему, корректирующую размыкание (обрыв) m контактов и содержащую не более lконтактов.1) m = 1, l = 10Σ:2) m = 1, l = 4Σ:3) m = 1, l = 9Σ:4) m = 1, l = 8Σ:5) m = 1, l = 4Σ:6) m = 1, l = 9Σ:7) m = 1, l = 10Σ:8) m = 1, l = 4Σ:7.9.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5075
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее