В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786)
Текст из файла
Часть 1. Иивариаитные классы и сложность алгоритмов 1. Инварпвнтные классы Понятие инвариантного класса было введено С,В.Яблонским [3[. Множество функций гд С Рг называется инвариантным классач, если наряду с каждой функцией? б 9 оно содержит все функции, получаюпшеся из Т применением следующих трех операций: 1) добавление и изъятие фиктивных переменных; 2) переименование переменных (без отождествления); 3) подстановка констант на места некоторых переменных.
Обозначен через ®(и) множество всех функций ?' из (г, зависящих (не обязательно существенно) от переменных хь хг,..., х„. Число о = 1онг 1пп '~/ЩпЯ называется харахтперистикой инвари«-«х антного класса 1г. Иногда характеристика будет указываться в качестве индекса при 1г' илн 1г(и). Справедлива следующая Теорема 1.1 (С. В. Яблонский [9[). Для любого а й [О, 1) срщестпвдет континь?гм попарно различных инвариантных к иегов Сг' с характеристикой о.
Обозначим через Ь(?) минимальную сложность схемы из функциональных элементов, реализующей функцию ?, и пусть В(и) щах Ц?), ЕО(и) = щах Б(у). В дальнейшем используются следу/еРн«) ?ео1«) ющие утверждения. Теорема 1,2 (О. Б. Лупанов [5[). 2« Ци) = — (1+ Б«), (1) где б„-~ О ири и -+ оо. Теорема 1.3. Если Π— инвариантный класс с характеристикой а, а > О то Ьй(и) < и — (1+Ь ), 2" (2) и гдето„-+ О при и -+ со. Функция ?„(хь..., х„) называется сложной, если ЦД ) = Ци). Бесконечная последовательность булевых функций (г1(х1). Ь(хм ха) "° 1«(хь .,х„),...) называется сложной, если для любого У существует и >?э' такое, что функция Яхь..., х„) является сложной.
Алгоритм, строящий бесконечную последовательность булевых функций (Л(х1~ ° ~ хв)), 1 из Рг называется правильным, если он строит все функции минимального по включению инвариантного класса, содержащего эту последовательность. Теорема 1.4 (С. В. Яблонский [3[). Любой правильный алгоритм, строящий сложную последовательность фрнхчий (Яхь. х')), 1 иэ Рю строит все множество Рг. Функция д называется порождающим элементом инвариантного класса О тогда и только тогда,, когда она не лежит в 1г и либо д— константа, либо всякая функция, получающаяся из д подстановкой констант, лежит в О..
Множество всех попарно неконгруэнтных порождающих элементов инвариантного класса О называется неириводимой системой порождающих элементов инвариантного класса (~ и обозначается через У(1«1). Пучком функции д называется множество Пг тех и только тех функций, из которых функция д может быть получена последовательным применением таких операций, как переименование переменных без отождествления, добавление н изъятие фиктивных переменных, подстановка констант. 1.1. Пусть А и  — ннвариантные классы.
Верно ли, что всегда инварнантным классом является: 1) АОВ; 2) АОВ; 3) А~В; 4) Рг ~ А. 1.2. 1) Всякий лн замкнутый класс является инвариантным? 2) Всякий ли инвариантный класс является замкнутым? 1.3. Пусть А — замкнутый класс, содержащий константы О и 1. Верно ли, что А — всегда инвариантный класс? 1,4. Выяснить, какие из следующих классов являются инвариантными классами: 1) класс Ь линейных функций; 2) класс М монотонных функций; 3) класс Тв функций, сохраняющих константу О; 4) класс Те П Ть где Т„а б (О, 1), — класс функций, сохраняющих константу а; 5) класс о самодвойствеииых фуикций; 6) класс симметрических функций, то есть функций, ие измеяяющи при любой перестановке их переменных; 7) класс симметрических фуикпий и функций, получаемых из симметрических добавлением фиктивных переменных; 8) класс функций.
принимающих единичные значения только иа иаборах с четным числом единиц; 9) класс фуикпкй, степень полииома Жегалкииа которых ие больше некоторого залаияого числа; 10) класс фувкций, число слагаемых полияома Жегалкииа которых ие больше половины всех возможных. 1.5. Построить минимальный (по включению) инвариантный класс Я„ содержащий в себе класс: 1) о - самс двойсгвеииых функций; 2) Тэ - функций, сохраняющих константу 0; 3) Т~ - функций, сохраняющих константу 1; 4) Те Г Т~ - функций, сохраняющих константы 0 и 1. 1.6. Доказать, что для каждого иепустого инвариантного класса Я последовательиость '~/ф(п)( не возрастает и 1 < 1пп 'ь/Щл)( < 2, 1.7.
Доказать, что если инвариантный класс Я, ке совпадает с Рг, то о < 1. 1.8. Вычислить характеристики следующих иивариаятпых классов: 1) класс Ь линейных функций; 2") класс М монотонных функций; 3) класс функций, представимых в виде Дхь..., я„) = 1(хь..., х„) Згд(ям..., я„), (3) где 1 — линейная функция, а д — произвольная функция из Рь у которой каждая существенная переменная является существенной переменкой Функции 1. 1.9.
1) Пусть Рэ'(и) — множество функций из Рэ(п), существенно завясящих от и псремеяных. Показать, что (Рэ'(п) ~ > 2э" — п2э" 2) Пусть Я, 1Л С Рм — инвариантный класс. Доказать неравенство !Фп)( < ~Фгп)(г' при п > гп. 1 10 Пусть э(У) — число попарно различных подфуикций функции '~ э(п) шах1егр(э) э(~) Доказать что 1) э(п) < 3"; 2') для всякого е > 0 существует Ф такое, что э(п) < 3"(1 — и) для всех п > Д1. 1.11. Доказать теорему 1.4 из введения к параграфу. 1.12. 1. Найдите иеприводимую систему порождающих элемеитов ии- вариантного класса 11, если 1) Я вЂ” это класс Лй всех монотонных функций, 2) 1~ — это класс Ь всех линейных функций, 3) 1;1 — это класс всех функций, с5ществеяио зависящих от пе более чем Й перемепиых, 4) 1~ — это класс, состоящий только из констант и всех тождественных функций.
2. Приведите пример такого инвариантного класса Я, что его иепри- водимая система порождающих элементов бесконечна. 3. Докажите, что для любого иивариаитиого класса 11 справедливо равенство () Пэ = Р, ~Я. 4. Докажите, что в Рэ имеется ровно коптипуул» попарно различных иивариаятиых классов. 3 2. Сложность алгоритмов Термин "машина Тьюриша" (сокращенно МТ) употребляется здесь для однолеиточиых детерминированных машин (см., например, [10)).
Некоторое (иеприпципиальное) отличие состоит в том, что, как правило, рассматриваются МТ с односторонней лентой, бесконечной вправо. Алфавит символов ленты МТ обозначим через А, а мио. кссгво состояиий — через 1„1. Алфавиты А и Я конечны. Символом д~ обозначается начальное состояние, символом а~ — пустой символ, присутствующий по опредслскию в алфавите А. Считается, что в иачальиый момент слово ш = 6~ 6э ...
6„, обрабатываемое МТ, записано в первых и ячейках ленты, а все остальные ячейки ленты содержат символ аь Детерминированность МТ означает, что для каждой пары вида (а, д), где а— символ входного алфавита, а д — символ состояиия, в программе МТ присутствует ие более одной команды вида: ад -+ а'4'И, начинающейся с ой, Пусть в процессе работы МТ иа некотором такте 1 оказалось, что иа леитезаписаиословош = 6,6э ... 6 . Этоозиачает,чтовпервыхтячсй- ках ленты содержатся символы 6«,...,6м, а ячейки, начиная с (гп+1) й содержат символ а«. Пусть далее на такте т МТ находится в состояш«и а головка обозревает ячейку с номером к.
Ко«4игурацией (мгновенным опио«ниач), соответствующей этому такту 1, называется елово С, вида 6,6«... 6„; а«6»... 6 . Конфигурация, соответствующая первому такту, называется на~альной. а последнему (если МТ останавливается), — заклю «ительной. Вычисление ч МТ М на входе и«называется последовательность конфигурац««й С«, Сг, ...,С„..., возникающая при работе над словом и, Полразул«евается, что конфигурация С«»«однозначно определяется конфигураш:ей С«и командой МТ М, начинающейся с пары (6», д,), гле 6» — символ, обозреваемый МТ н мол«ент $, а о« вЂ” состояннс 6!Т в момент й Время рабе«пы или число шагов 1м(и«) МТ М на входе ю определяется как число конфигураций в вычислении МТ М на входе ш.
Если вычисление бесконечно, полагаем 8м(и«) = оо. Пусть среди состояний МТ имеются выделенные заключительные состояния — принимающее и отвергающее. Тогда вычисление называется принимающим (о«пеергаюи»им), если оно заканчивается в принимающем (отвергающем) состоянии. Недетерминпрованные машины Тьюринга. Отличие недетерминированной МТ (сокращенно, НМТ) от детерминированной состоит в том, что в программе НМТ для пары (а, д), где а — символ из алфавита МТ, а о — символ состояния, в ее программе люжет присутствовать несколько комапл, начинающихся с ао. Без потери общности можно ограничиться случаем, когда паре ао может соответствовать не более двух команд с началом ад. Пусть в программе НМТ имеется пара команд ао -+ а'о'Т, и ао -«а"д"В.
Тогда, находясь в состоянии о и обозревая символ а на ле«гге, НМТ может выбрать любую из двух возможностей: записать в обогреваемую ячейку символ а', перейти в состояние о' и сдвинуть головку влево, либо записать в обогреваемую ячейку символ а", перейти в состояние о" и сдвинуть головку вправо. При этом счнтзется, что НМТ как бы создает две копии самой себя и прослеживает последовательность вычислений обоих способов действия.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
