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

Материалы для подготовки к экзамену прошлых лет, страница 5

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

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

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

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

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

Для любого множества ФАЛ Q, Q ⊆ P2 (n), и любого натуральногоr, r 6 n, справедливо неравенство −5 bK →L ( Q ) > 2 |Q| 1 − √− 2 Q(1.4),rb состоит из тех ФАЛ f, f ∈ Q, у которых во множестве N fгде множество Qесть грани размерности больше, чем (n − r).Доказательство. Пусть Σ - минимальная приведенная (1, |Q|)-КС, реализующая→−систему ФАЛ Q , и пусть V - множество её выходных вершин. Пусть, далее, s иt - натуральные параметры, для которых (s − 1)(t − 1) 6 r, а V 0 - множество техвыходных вершин Σ, степень которых не меньше, чем s.

Достаточно рассмотретьслучай, когда 0V 6 4 |Q| ,(1.5)sтак как иначе число контактов Σ инцидентных вершинам из V 0 уже было бы неменьше, чем 2 |Q|.Для произвольного набора α, α ∈ B n , множество c (α) связанных компонентсети Σ|α разобьем на непересекающиеся подмножества ci (α) , i ∈ [1, 4], так, чтосвязная компонента G, G ∈ c (α), входит в подмножество:1. c1 (α), если V (G) * V ;2. c2 (α), если G ∈/ c1 (α) и V (G) ∩ V 0 6= ∅;3. c3 (α), если G ∈/ (c1 (α) ∪ c2 (α)) и |V (G)| > t;4. c4 (α) в остальных случаях.Заметим, что произвольная связная компонента G из ci (α) удовлетворяет неравенству|E (G)| > |V ∩ V (G)| ,(1.6)если i = 1 и состоит только из выходных вершин Σ в остальных случаях. При этомв случае i = 2 она содержит хотя бы одну вершину из V 0 , в случае i = 3 - состоитне менее, чем из t вершин, а в случае i = 4 включает в себя не более (t − 1) вершин,которые отделяются от остальных вершин сети Σ|α сечением, состоящим не более,чем из (s − 1)(t − 1) 6 r, контактов множества E (Σ|α ).

Таким образом, в каждой§2. Незабиваемые множества переменных23b и,вершине компоненты G из множества c4 (α) реализуется ФАЛ из множества Q,учитывая все вышесказанное, получим |Q| b|c2 (α)| 6 V 0 , |c3 (α)| 6, |c4 (α)| 6 Q(1.7).tИз (1.5) – (1.7) в силу (1.2) вытекает неравенство4 |Q| |Q| b −− Q ,st√из которого в соответсвии с 1.1 при δ = B n и s = t = d re следует (1.4).Теорема доказана.nСледствие 1. Полагая Q = P2 (n) и учитываято,чтоприr=2 множество 2n b = Pb2 (n) удовлетворяет соотношению Pb2 (n) = o 2√Q, получимn|E (Σ|α )| > |Q| −→−12nL ( P 2 (n)) > 2 · 21−O √.nKСледствие 2. Оценки следствия 1 и леммы 3.1 из[2, глава 4] дают асимптотическое неравенство→−nLK ( P 2 (n)) ∼ 2 · 22 .§2Забивание переменных константами и незабиваемые множества переменных.Асимптотика сложности мультиплексора в некоторых классахсхемОпределим сначала операцию подстановки констант вместо переменных в функциии схемы.

Будем считать, что любая ЭК K ранга r от БП X(n) вида K = xσi11 . . . xσirrзадает подстановку констант xi1 = σ1 , . . . , xir = σr . Результат применения указанной подстановки к системе ФАЛ F, F ∈ P2m (n), и схеме Σ от БП X(n) будемобозначать через F |K и Σ|K соответственно. При этом система ФАЛ F |K определяется обычным образом, а преобразование схемы Σ в схему Σ|K в классе UC (UK )связано с заменой вершин xij , j = 1, . . . , r, константой σj и применением, до техпор, пока это возможно, тождеств подстановки констант из §§1–2 [2, глава 3] (соσответственно отождествлением концевых вершин контактов вида xijj и удалениемσконтактов вида xijj , j = 1, .

. . , r) с последующим переходом к эквивалентной приведенной схеме. Заметим, чтоK · f = K · f |Kдля любой ФАЛ f и что схема Σ|K реализует систему ФАЛ F |K , если схема Σреализует систему ФАЛ F . Заметим также, что для КС Σ от БП X(n) и набора24Глава 2. Синтез схем для индивидуальных функцийα = (α1 , . . . , αn ) схема Σ|xα1 ...xαnn в отличие от сети Σ|α (см.

§§1,5 из [2, глава 2])1состоит из (кратных) изолированных полюсов.Будем говорить, что подмножество 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 . Заметим также, что примером незабиваемого множества БП является множество всех существенных(информационных) БП линейной(соответственно мультиплексорной) ФАЛ.Теорема 2.1. Если ФАЛ f имеет незабиваемое множество, состоящее из n ееБП, тоLC (f ) > 2n − 2, LK (f ) > 2n − 1(2.1)Доказательство.

Первое из равенств (2.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 и реализуемую1ею ФАЛ 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,которые устанавливают справедливость рассматриваемого индуктивного переходаи доказывают первое из равенств (2.1).§2.

Незабиваемые множества переменных25Докажем теперь второе из равенств (2.1). Пусть, по-прежнему, Y ={y1 , . . . , yn } — незабиваемое множество БП ФАЛ f и пусть Σ — минимальнаяприведенная (1, 1)-КС, реализующая ФАЛ f со сложностью L(Σ) = LК (f ). Если каждая из БП yi , i ∈ [1, n] имеет в КС Σ не менее двух контактов, то второе неравенство (2.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).(2.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 0 ФАЛ00f 0 . Аналогичное противоречие в случае |c(Σ )| > 3 связано с тем, что при этом в Σ0найдется контакт БП y 0 , y 0 ∈ Y 0 , соединяющий между собой две различные компо00ненты Σ , одна из которых не содержит полюсов Σ, и, следовательно, множествоБП Y 0 \ {y 0 } вновь забивает БП y 0 при подстановке константы 0.00Учитывая установленные свойства схем Σ00 и Σ , а также соотношения (1.2) и(1.3) из [2, глава 2], получим:0000L(Σ ) + 2 > |V (Σ )| = |V (Σ0 )| = |V (Σ00 )| > m + 1.Следовательно, выполняется неравенство00L(Σ0 ) = L(Σ ) + m > 2m − 1,из которого, в силу (2.2) вытекает второе неравенство (2.1).

Теорема доказана.Следствие.LC(µn ) > 2n+1 − 2, LK (µn ) > 2n+1 − 1.Установим теперь верхние оценки сложности реализации мультиплексорной−→ФАЛ µn в классах схем UC , UФ , UК , U К .26Глава 2. Синтез схем для индивидуальных функцийТеорема 2.2.

Для n = 1, 2, . . . справедливы неравенства:LC (µn ) 6 LФ (µn ) 6 2n+1 + O(2n/2 )(2.3)√LK (µn ) 6 2n+1 + O(2n / n)(2.4)−→L K (µn ) 6 2n + O(2n/2 )(2.5)Доказательство. Построим в классе UC схемный мультиплексор Σn порядка n,сложность которого дает оценку (2.3) для LC (µn ), следующим образом:0001. разобьем n набор БП X(n) на группы x = (x1 , . .

. ,q xq ), x = (xq+1 , . . . , xn ), гдеq = 2 , а набор БП y = (y0 , . . . , y2n −1 ) — на 2 последовательных наборовqy (0) , . . . , y (2 −1) длины 2n−q каждый;2. возьмем дешифраторы Σ0 и Σ00 от БП x0 и x00 порядка q и n − q, построенныепо лемме 2.1 из [2, глава 4];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 , .

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