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

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

Файл №1156402 Материалы для подготовки к экзамену (2012-2013 учебный год) (Материалы для подготовки к экзамену (2012-2013 учебный год)) 9 страницаМатериалы для подготовки к экзамену (2012-2013 учебный год) (1156402) страница 92019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Тогда функцией Шеннона для класса ФАЛ или операторов Q при их реализации в классе схем U относительно функционала сложности L называетсяфункция натурального аргументаL(Q(n)) = max L(f ),f ∈Q(n)где L(f ) — минимальная L–сложность схем из U, реализующих (систему) ФАЛ f .Для класса ФАЛ или операторов Q0 и класса ФАЛ Q00 введём такие функцииJ Q0 (n) =log |Q0 (n)|log log |Q0 (n)|и σQ (n) =log |Q00 (n)|,2nгде n = 1, 2, . . .

. При этом из определения следует, что 0 6 σQ (n) 6 1 для всех n,n = 1, 2, . . . .Класс ФАЛ (операторов) Q называется:1) невырожденным, если n + mQ (n) = o J Q(n) ;§8. Специальные классы функций432) строго невырожденным классом ФАЛ, если log n = o log |Q(n)| ;3) ненулевым классом ФАЛ, если limn→∞ σQ (n) > 0.На основе стандартного мощностного метода получения нижних оценок можноустановить справедливость следующего утверждения.Лемма 8.1. Если Q — невырожденный класс ФАЛ (операторов), то 1LИКС Q(n) & · J Q(n) ,2а если Q — строго невырожденный класс ФАЛ, тоLК Q(n) & J Q(n) .LCБ Q(n) & ρБ · J Q(n) ,Следствие. Для всякого ненулевого класса ФАЛ Q выполнены асимптотическиенеравенства2nLC,Б Q(n) & ρБ · σQ (n)n 1log |Q(n)|LИКС Q(n) & · σQ (n),2n2nLК Q(n) & σQ (n) .nКласс ФАЛ (операторов) Q называется стандартным относительно функционала сложности L класса схем UCБ , если выполнено асимптотическое неравенствоLCБ Q(n) .

ρБ · J Q(n) + O n + m(n) .Аналогично вводится определения стандартного класса операторов относительнодругих классов схем и функционалов их сложности, если соответствующая функция Шеннона имеет порядок роста 2n /n. Отметим, что при этом для невырожденного стандартного класса ФАЛ Q имеет место асимптотическое равенствоLCБ Q(n) ∼ ρБ · J Q(n) .Для n = 1, 2, . . .

и r = r(n) > 1 рассмотрим множество ФАЛ P2 (n, t), котороевключает в себя все ФАЛ из P2 (n), обращающиеся в 0 на наборах с номерамиt, t+1, . . . , 2n −1, и мощность которого равна, очевидно, 2t . Для любой функции r =r(n) > 1 рассмотрим класс ФАЛ Q, определённый равенствами Q(n) = P2 (n, r(n)),n = 1, 2, . . . .Лемма 8.2. Для любой функции r = r(n) > 1 соответствующий класс Q(n) =P2 (n, r(n)) является стандартным относительно функционала сложности Lсхем класса UCБ , то естьrLC+ O(n).Б Q(n) . ρБlog r44Глава 1.Доказательство. Будем считать, для удобства, что при лексикографической ν–нумерации наборов куба B n от БП X(n), n = 1, 2, .

. . , БП xi «старше» БП xj ,если i > j. Полученные при этом предположении оценки сложности будут справедливы, очевидно, и для «обычного» порядка «старшинства» БП.Рассмотрим сначала случай, когда r > 2n−1 . Выберем из множества P2 (n, r)произвольую ФАЛ f и построим для неё СФЭ Σf с помощью асимптотически наилучшего метода синтеза (см.

§5). Напомним, что при этом ФАЛ f (см. доказательство теоремы 5.1) разлагается по БП x00 = (xq+1 , . . . , xn ) следующим образом:_f (x0 , x00 ) =Kσ00 (x00 )fσ00 (x0 ),σ 00 ∈B n−qгде x0 = (x1 , . . . , xq ), и что для реализации каждой ФАЛ fσ00 (x0 ) в СФЭ Σf используется одна формула Ft . Из принадлежности ФАЛ f классу P2 (n, r) следует, чтопри ν(σ 00 ) > dr/2q e функция fσ00 (x0 ) тождественно равна нулю, и, таким образом,из схемы Σf можно удалить подсхемы, реализующие все указанные подфункции.e f в силу (5.9) будет выполняться нераДля сложности полученной при этом СФЭ Σвенствоl me f 6 Lj r t + O 2n−m + p · 2s + p · 2 2s +m ,L Σ2qиз которого при значениях параметров (5.10) следует, чтоe f .

ρБ r .(8.1)L Σlog rПусть теперь r 6 2n−1 . В этом случае найдём число k такое, чтоk < n,2k−1 < r 6 2kи, следовательно,f (x1 , . . . , xn ) = xk+1 · . . . · xn · f 0 (x1 , . . . , xk ).(8.2)Заметим, что функция f 0 принадлежит классу P2 (k, r), где r > 2k−1 , и для неё поe f 0 , удовлетворяющую (8.1). Искомаяпредыдущему случаю можно построить СФЭ Σe f строится на основе (8.2) так, чтоСФЭ Σef 6 L Σe f 0 + O(n) . ρБ r + O(n).L Σlog rЛемма доказана.Следствие. Если n = o logr r , то Q(n) = P2 (n, r(n)) — стандартный невырожденный класс ФАЛ, для которого выполнено асимптотическое равенствоr.LCБ Q(n) ∼ ρБlog r§8.

Специальные классы функций45Замечание. Аналогично доказывается стандартность класса Q(n) = P2 (n, r(n)) относительно функционала «обычной» сложности и классов схем UИКС , UК .Рассмотрим теперь следующие операции над ФАЛ:1) добавление и изъятие фиктивных БП (переход к равной ФАЛ);2) переименование БП без отождествления (переход к конгруэнтной ФАЛ);3) подстановка констант 0, 1 вместо БП (переход к подфункции).Если функция g получена из функции f применением операций 1–3, то говорят,что g является квазиподфункцией ФАЛ f , а f — квазинадфункцией ФАЛ g.

Длямножества функций F через F q и Fy будем обозначать множества всех квазинадфункций и квазиподфункций для функций из F соответственно.Множество ФАЛ Q, Q ⊆ P2 , называется инвариантным классом ФАЛ, если онозамкнуто относительно трёх указанных операций. Множества {0}, {1}, {0, 1} называются тривиальными инвариантными классами. Если инвариантный класс Q неявляется тривиальным, то Q ⊇ {0, 1}, поскольку Q содержит неконстантую функцию, из которой при помощи операции 3 можно получить обе константы. Отметим, что если класс Q замкнут по суперпозиции и {0, 1} ⊆ Q, то класс Q являетсяинвариантным.

Примерами инвариантных классов могут, следовательно, служитьb всех монотонных и всех линейных ФАЛ соответственно. При этомклассы M и Lкласс самодвойственных функций, а также классы T0 и T1 — классы сохраненияконстант 0 и 1 соответственно, — не являются инвариантными (они не замкнутыотносительно операции 3). Класс всех симметрических ФАЛ также не являетсяинвариантным, так как он не замкнут относительно операции 1.

При этом инвариантным является класс Sb — класс квазисимметрических ФАЛ, то есть функций,симметрических по всем своим существенным переменным.Лемма 8.3. Пусть Q — инвариантный класс ФАЛ. Тогда существует пределσQ = lim σQ (n) = limn→∞n→∞log |Q(n)|,2nгде число σQ удовлетворяет неравенствам 0 6 σQ 6 1.Доказательство. Из определения последовтельности σQ (n) следует, что для каждого n выполнено неравенство 0 6 σQ (n) 6 1, то есть эта последовательностьσQ (n) ограничена.

Покажем, что она монотонно не возрастает, откуда будет следовать её сходимость. В силу инвариантности класса Q, всякую функцию f измножества Q(n + 1) можно представить в видеf (x1 , . . . , xn+1 ) = xn+1 f0 (x1 , . . . , xn ) ∨ xn+1 f1 (x1 , . . . , xn ),46Глава 1.где fσ (x1 , . . . , xn ) = f (x1 , . . . , xn , σ), σ ∈ B, и обе ФАЛ f0 , f1 принадлежат множеству Q(n). Отсюда сразу вытекает неравенство|Q(n + 1)| 6 |Q(n)|2 ,из которого, в свою очередь, следуeт, чтоσQ (n + 1) =log |Q(n + 1)|log |Q(n)|6= σQ (n).2n+12nСходимость последовательности σQ (n), n = 1, 2, . . . , доказана, а принадлежностьеё предела σQ действительному отрезку [0, 1] следует из того, что ему принадлежатвсе члены данной последовательности.Лемма доказана.Замечание.

Предел σQ будем называть мощностной характеристикой класса Q.Инвариантный класс Q с характеристикой σQ = 0 называется нулевым. Покажем, что существует только один инвариантный класс Q с характеристикойσQ = 1 — это класс P2 . Действительно, если инвариантный класс Q не совпадает с P2 , то для некоторого m будет выполнено неравенство |Q(m)| < |P2 (m)|,которое равносильно неравенству σQ (m) < 1. Из последнего неравенства в силумонотонного невозрастания последовательности σQ (n), n = 1, 2, . . .

, и её сходимости к пределу σQ следует, что σQ 6 σQ (m) < 1.b и S.b Известно [],Найдём значение характеристик инвариантных классов M , Lчто2nlog |M (n)| ∼ Cndn/2e ∼ √,2πnоткуда следует, что σM = 0. Для класса линейных функций, очевидно, при люbбом n выполняется равенство |L(n)|= 2n+1 и, значит, σL = 0. Всякую функцию изbмножества S(n)можно получить так: сначала выбираем k её существенных БП, азатем не более чем 2k+1 способами определяем значение этой функции на каждомслое куба B k (в пределах одного слоя значение функции одно и то же).

Отсюдаследует, чтоnXb|S(n)|6Cnk · 2k+1 = 2 · 3n ,k=0b Sb являются нулевыми.и поэтому σSb = 0. Таким образом, все три класса M , L,Примером ненулевого инвариантного класса, отличного от P2 , является класс Q,состоящий из всех ФАЛ вида f (xi1 , . . . , xir )(xi1 ⊕ · · · ⊕ xir ⊕ σ), где 1 6 i1 < · · · < irи σ ∈ B. Действительно, класс Q замкнут относительно операций 1–3. При этомлюбая ФАЛ из Q(n) однозначно определяется множеством X её существенныхБП, X ⊆ X(n), и своими значениями на множестве тех наборов единичного куба§8.

Специальные классы функций47от БП X, которые имеют либо чётное, если σ = 1, либо нечётное, если σ = 0, числоединиц. Таким образом,2·22n−16 |Q(n)| 6nXr−12 · Cnr · 226 22n−1 +n+1r=0и, следовательно, σQ = 21 .Выше было установлено, что существует единственный инвариантный класс схарактеристикой 1. Можно доказать, что при при любом σ, 0 6 σ < 1 существуетконтинуум инвариантных классов с характеристикой σ. Докажем это в частномслучае σ = 0.Лемма 8.4.

Существует континуум различных инвариантных классов с характеристикой 0.Доказательство. Отметим, что число различных инвариантных классов не можетбыть больше континуума, поскольку множество P2 счётно.{0,m}Рассмотрим симметрические функции sm , определяемые при m > 1 следующим образом:s{0,m}(x1 , . . . , xm ) = x1 · . . . · xm ∨ x1 · . .

Характеристики

Список файлов ответов (шпаргалок)

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