Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Материалы для подготовки к экзамену (2012-2013 учебный год)

Материалы для подготовки к экзамену (2012-2013 учебный год), страница 13

PDF-файл Материалы для подготовки к экзамену (2012-2013 учебный год), страница 13 Дополнительные главы кибернетики и теории управляющих систем (53099): Ответы (шпаргалки) - 7 семестрМатериалы для подготовки к экзамену (2012-2013 учебный год): Дополнительные главы кибернетики и теории управляющих систем - PDF, страница 13 (53099) 2019-09-18СтудИзба

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

PDF-файл из архива "Материалы для подготовки к экзамену (2012-2013 учебный год)", который расположен в категории "". Всё это находится в предмете "дополнительные главы кибернетики и теории управляющих систем" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

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

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

. . .При n = 2 неравенство (2.4) выполняется в силу (2.2), что составляет базис рассматриваемой индукции. Для обоснования индуктивного перехода возьмем произвольную минимальную линейную СФЭ Σ порядка n, n > 3, от БП X(n) и покажем,что для некоторых i, i ∈ [1, n], и σ, σ ∈ B, выполняется неравенствоL(Σ) > L(Σ|xσi ) + 4.(2.5)Будем считать, что на каждом шаге преобразования СФЭ Σ в СФЭ Σ00i,σ = Σ|xσiудаляется один ФЭ E с константой на входе. При этом вершина, с которой связан ФЭ E, обьявляется константной входной вершиной типа σ новой схемы, еслина выходе E реализуется константа σ, σ ∈ B, и удаляется вместе с E в остальныхслучаях. Заметим, что для любой промежуточной схемы Σ0 указанного преобразования выполняется неравенствоL(Σ00i,σ ) 6 L(Σ0 ) − IC(Σ0 ),(2.6)где IC(Σ0 ) — число дуг Σ0 , исходящих из её константных входов.

Будем предполагать также, что в любой вершине СФЭ Σ00i,σ реализуется неконстантная ФАЛ.64Глава 2.Полустепень исхода, то есть число исходящих дуг вершины v СФЭ Σ будемобозначать через d+ (v), а число исходящих из v дуг, которые ведут в вершины,связанные с ФЭ типа Φ, Φ ⊆ Б0 , — через d+Φ (v). Заметим, что для любой вершины vСФЭ Σ и для любого любого i, i ∈ [1, n], выполняются неравенстваd+¬ (v) 6 1,++d+ (xi ) = d+& (xi ) + d∨ (xi ) + d¬ (xi ) > 2,(2.7)первое из которых вытекает непосредственно из минимальности Σ, а второе — изследствия 1 леммы 2.1. Нетрудно убедиться в том, что неравенство (2.5) выполняется в следующих случаях:1. d+ (xi ) > 4 — при любом σ;++2.

d+& (xi ) > 2 или d& (xi ) = d¬ (xi ) = 1 — при σ = 0;++3. d+∨ (xi ) > 2 или d∨ (xi ) = d¬ (xi ) = 1 — при σ = 1.Действительно, в каждом из этих случаев СФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ00i,σ в результате удаления d+ (xi ) ФЭ, связанных с входом xi ,имеет при d+ (xi ) < 4 не меньше, чем (4 − d+ (xi )), константных входных дуг и,следовательно, в силу (2.6) выполняется (2.5).Таким образом, с учётом (2.7) осталось рассмотреть основной случай — случай,++когда d+& (xi ) = d∨ (xi ) = 1 и d¬ (xi ) = 0 для каждого i, i ∈ [1, n]. В этом случае вСФЭ Σ найдутся два входа, связанные с одним и тем же ФЭ типа & или ∨. Пустьдля определённости, данными входами Σ будут БП x1 и x2 , котороые поступаютна входы одного и того же ФЭ &, связанного с вершиной v.

Пусть при этом втораядуга, исходящая из вершины xi , i = 1, 2, идёт в вершину wi , связанную с ФЭ ∨,на другой вход которого поступает дуга из вершины ui . Заметим, что в силу минимальности Σ для любого i, i = 1, 2, вершина ui отлична от вершины v, так какпри v = ui в вершине wi реализуется ФАЛ xi .Покажем, что в случае w1 6= w2 неравенство (2.5) выполняется. Действительно,рассмотрим в этом случае СФЭ Σ0 , которая пролучается при переходе от СФЭ Σк СФЭ Σ001,0 в результате удаления двух ФЭ, связанных с вершинами w1 и v, а также одного ФЭ, связанного с какой-либо вершиной v 0 , в котороую идет дуга из v.Так как u2 6= v и, следовательно, v 0 6= w2 , то вход x2 схемы Σ0 поступает толькона вход ФЭ ∨, связанного с вершиной w2 .

Из леммы 2.1 вытекает, что при этомв вершине u2 СФЭ Σ0 реализуется ФАЛ 0, то есть при переходе от Σ0 к Σ001,0 ещёодин ФЭ — ФЭ ∨, связанный с вершиной w2 , — будет удалён. Неравенство (2.5) вслучае w1 6= w2 доказано.Пусть, наконец, w1 = w2 и, следовательно, x1 = u2 , x2 = u1 и пусть, для опреде+лённости, либо d+ (v) > 2, либо d+ (v) = d+ (w) = 1 и d+&,∨ (v) > d∨,¬ (w).

РассмотримСФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ001,0 в результатеудаления двух ФЭ, связанных с вершинами v и w, а также всех тех ФЭ, входыкоорых присоединены к v (число таких ФЭ равно d+ (v)). Заметим, что в случае§3. Незабиваемые множества переменных65d+ (v) > 2 неравенство (2.5) вытекает из неравенства L(Σ) − L(Σ0 ) > 4, а в слу0чае d+ (v) = d+&,∨ (v) = 1 — из неравенства L(Σ) = L(Σ ) + 3 и неравенства (2.6),++где IC(Σ) > 1. В оставшемся случае d+ (v) = d+∨ (v) = d (w) = d& (w) = 1 из вер0шины v (w) исходит единственная дуга, ведущая в вершину v (соответственно w0 ),связанную с ФЭ ∨ (соответственно &).

В этом случае СФЭ Σ0 имеет в вершине w2вход x2 степени 1, поступающий на вход ФЭ &, и, следовательно, в силу леммы 2.1удовлетворяет неравенству L(Σ0 ) − L(Σ001,0 ) > 1, из которого, с учётом равенстваL(Σ) − L(Σ0 ) = 3, вытекает (2.5).Теорема доказана.§3Незабиваемые множества переменных. Асимптотика сложности мультиплексора в некоторых классах схемБудем говорить, что подмножество U множества X, состоящего из всех БП ФАЛ f ,забивает БП x, x ∈ X \ U , этой ФАЛ, если существует ЭК K от БП U такая, чтоФАЛ f |K не зависит существенно от x. При этом будем считать, по определению,что пустое множество U = ∅ забивает любую несущественную БП ФАЛ f и незабивает её существенные БП. Непустое подмножество Y множества БП ФАЛ fназывается незабиваемым множеством переменных этой ФАЛ, если для любойБП y, y ∈ Y , множество Y \ {y} не забивает y.

Заметим, что если Y — незабиваемоемножество БП ФАЛ f , то:1. любая БП из Y является существенной БП ФАЛ f ;2. для любой ЭК K от БП Y множество её несущественных БП является незабиваемым множеством БП ФАЛ f |K . Заметим также, что примером незабиваемого множества БП является множество всех существенных (информационных) БП линейной (соответственно мультиплексорной) ФАЛ.Теорема 3.1.

Если ФАЛ f имеет незабиваемое множество, состоящее из n еёБП, тоLC (f ) > 2n − 2,LК (f ) > 2n − 1(3.1)Доказательство. Первое из равенств (3.1) докажем индукцией по n, n = 1, 2, . . . .При n = 1 это неравенство, очевидно, выполняется. Пусть оно верно для любойФАЛ f 0 , которая имеет незабиваемое множество, состоящее из n0 , n0 6 (n − 1), еёБП, и пусть Y = {y1 , . . . , yn } — незабиваемое множество БП ФАЛ f , где n > 2.Возьмём миниимальную приведённую СФЭ Σ в базисе Б0 , которая реализуетФАЛ f со сложностью LC (f ).

В силу существенной зависимости ФАЛ f от БП y1в СФЭ имеется цепь из последовательно соединённых вершин v1 , . . . , vt , где v1 —вход y1 СФЭ Σ, а vt — выход Σ. При этом в вершине v1 реализуется ФАЛ y1 и, таккак f 6= y1 , то, следовательно, t > 2. Для σ1 ∈ B и σ1 = 0 тогда и только тогда,когда вершина v2 связана с ФЭ &, рассмотрим СФЭ Σ0 = Σ|yσ1 и реализуемую166Глава 2.ею ФАЛ f 0 = f |yσ1 , которая имеет незабиваемое множество БП Y 0 = Y \ {y1 } и1поэтому отлична от констант.Заметим, что в вершинах v1 и v2 СФЭ Σ при y1 = σ1 реализуются константы σ1и σ2 соответственно, а так как f 0 6= σ2 , то значит t > 3.

При этом константа σ2из вершины v2 поступает на вход ФЭ вершины v3 и, следовательно, при переходеот СФЭ Σ к СФЭ Σ0 элементы, связанные с вершинами v2 и v3 будут устранены(«забиты»). Таким образом, выполняются неравенстваLC (f ) = L(Σ) > L(Σ0 ) + 2 > LC (f 0 ) + 2,которые устанавливают справедливость рассматриваемого индуктивного переходаи доказывают первое из равенств (3.1).Докажем теперь второе из равенств (3.1). Пусть, по-прежнему, Y ={y1 , . .

. , yn } — незабиваемое множество БП ФАЛ f и пусть Σ — минимальнаяприведённая (1, 1)–КС, реализующая ФАЛ f со сложностью L(Σ) = LК (f ). Если каждая из БП yi , i ∈ [1, n], имеет в КС Σ не менее двух контактов, то второенеравенство (3.1), очевидно, выполняется. Таким образом, достаточно рассмотретьслучай, когда множество Y 0 , состоящее из тех БП yi , i ∈ [1, n], которым в Σ соответствует ровно один контакт, не пусто. Пусть, для определённости, Y 0 = {y1 , . . . , ym },1 6 m 6 n, и пусть каждая из БП yi , i ∈ [1, m], имеет в Σ только один замыкающийконтакт (это предположение не ограничивает, очевидно, общности рассуждений).Рассмотрим КС Σ0 = Σ|ym+1 ·...·yn , которая реализует ФАЛ f 0 = f |ym+1 ·...·yn снезабиваемым множеством БП Y 0 и для которой в силу выбора Y 0 выполняетсянеравенствоL(Σ0 ) 6 L(Σ) − 2(n − m).(3.2)Схема Σ0 по построению является связным графом и для каждого i, i ∈ [1, m],содержит ровно один (замыкающий) контакт БП yi .

Пусть, далее, КС Σ00 являетсяостовной подсхемой КС Σ0 , содержащей все контакты БП Y 0 и только их, а остовная0000подсхема Σ схемы Σ0 служит дополнением Σ00 , то есть Σ = Σ0 \ Σ00 .Покажем, что в КС Σ00 нет циклов, то есть Σ00 представляет собой систему де00ревьев, и что |c(Σ )| 6 2. Действительно, если бы в КС Σ00 контакт БП y 0 , y 0 ∈ Y 0 ,принадлежал циклу, то множество БП Y 0 \ {y 0 } при подстановке константы 1 забивало бы БП y 0 в КС Σ0 , что противоречит незабиваемости множества БП Y 000ФАЛ f 0 . Аналогичное противоречие в случае |c(Σ )| > 3 связано с тем, что приэтом в Σ0 найдётся контакт БП y 0 , y 0 ∈ Y 0 , соединяющий между собой две различ00ные компоненты Σ , одна из которых не содержит полюсов Σ, и, следовательно,множество БП Y 0 \ {y 0 } вновь забивает БП y 0 при подстановке константы 0.00Учитывая установлённые свойства схем Σ00 и Σ , а также соотношения (1.2)и (1.3) из [3, глава 2], получим:0000L(Σ ) + 2 > |V (Σ )| = |V (Σ0 )| = |V (Σ00 )| > m + 1.§3.

Незабиваемые множества переменных67Следовательно, выполняется неравенство00L(Σ0 ) = L(Σ ) + m > 2m − 1,из которого, в силу (3.2) вытекает второе неравенство (3.1).Теорема доказана.Следствие.LC(µn ) > 2n+1 − 2,LК (µn ) > 2n+1 − 1.Установим теперь верхние оценки сложности реализации мультиплексорной−→ФАЛ µn в классах схем UC , UФ , UК , U К .Теорема 3.2. Для n = 1, 2, . . . справедливы неравенства:nLC (µn ) 6 LФ (µn ) 6 2n+1 + O 2 2 ,√ LК (µn ) 6 2n+1 + O 2n / n ,−→nL К (µn ) 6 2n + O 2 2 .(3.3)(3.4)(3.5)Доказательство.

Построим в классе UC схемный мультиплексор Σn порядка n,сложность которого даёт оценку (3.3) для LC (µn ), следующим образом:1. разобьём набор БП X(n) на группы x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ),где q = dn/2e, а набор БП y = (y0 , .

. . , y2n −1 ) — на 2q последовательныхqнаборов y (0) , . . . , y (2 −1) длины 2n−q каждый;2. возьмём дешифраторы Σ0 и Σ00 от БП x0 и x00 порядка q и n − q, построенныепо лемме ? главы ?;b 00 , которая содержит дешифратор Σ00 в качестве подсхе3. построим схему Σмы и для каждого σ 00 , σ 00 ∈ B n−q , на выходе zj , где j = ν(σ 00 ), реализуетФАЛ µn−q (x00 , z (j) ) по её сокращённой ДНФ, используя для этого 2n−q ФЭ &и (2n−q − 1) ФЭ ∨;b 00 в качестве подсхем и реализует4. искомая схема Σn содержит СФЭ Σ0 и Σ0000ФАЛ µn (x , x , y) = µq (x , z0 , . . .

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