В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011) (1132784)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиВ. Б. Алексеев, А. А. Вороненко, С. А. Ложкин,Д. С. Романов, А. А. Сапоженко, С. Н. СелезневаЗАДАЧИ ПО КУРСУ“ОСНОВЫ КИБЕРНЕТИКИ”Москва2011УДК 510.5, 519.71ББК 22.12:22.18A47Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д.
С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу “Основы кибернетики". — Издательский отделфакультета ВМиК МГУ (лицензия ЛР No 040777 от 23.07.96), 2011. — 61c.Рецензенты:проф. Марченков С. С., д. ф.-м. н.с. н. с. Кузнецов Ю. В., к. ф.-м. н.Печатается по решению Редакционно-издательского совета факультетавычислительной математики и кибернетики МГУ им. М. В. ЛомоносоваЗадачник содержит материал для семинарских занятий по курсу “Основы кибернетики". В него включены задачи по инвариантным классам,понятию сводимости и NP-полноте, эквивалентным преобразованиям, тестам, надежности и самокоррекции.ISBN 978-5-89407-466-5Издательский отдел факультетавычислительной математи-ки икибернетикиМ.В.Ломоносова2011МГУим.ВведениеВ настоящем пособии собраны упражнения по курсу “Основы кибернетики”. Задачи сгруппированы по темам, среди которых следующие: инвариантные классы, сложность алгоритмов, эквивалентные преобразования управляющих систем, тесты, надежность и самокоррекция.
Каждойтеме отведен параграф, в начале которого даются необходимые определения и теоретические сведения. Пособие предназначено для студентовтретьего-четвертого курсов. Предполагается, что читателю знакомы основные понятия дискретной математики.Параграф 1 посвящен инвариантным классам.В параграфе 2 собраны задачи, касающиеся понятий сводимости и NPполноты. Часть задач посвящена оценкам сложности конкретных алгоритмов.В параграфах 3 –4 предлагаются задачи по эквивалентным преобразованиям формул и схем.Параграфы 5 – 6 посвящены алгоритмам построения тестов и оценкамдлины тестов для таблиц и схем.Параграф 7 посвящен проблеме надежности.
В нем также собраны задачи по построению и оценкам сложности самокорректирующихся схем.Часть 1. Инвариантные классы и сложность алгоритмов§ 1. Инвариантные классыПонятие инвариантного класса было введено С.В.Яблонским [8].Множество функций Q ⊆ P2 называется инвариантным классом, еслинаряду с каждой функцией f ∈ Q оно содержит все функции, получающиеся из f применением следующих трех операций:1) добавление и изъятие фиктивных переменных;2) переименование переменных (без отождествления);3) подстановка констант на места некоторых переменных.Обозначим через Q(n) множество всех функций f из Q, зависящих(не обязательно существенно)от переменных x1 , x2 , . .
. , xn .p2nЧисло σ = log2 lim|Q(n)| называется характеристикой инвариn→∞антного класса Q. Иногда характеристика будет указываться в качествеиндекса при Q или Q(n). Справедлива следующаяТеорема 1.1 (С. В. Яблонский [9]). Для любого σ ∈ [0, 1) существуетконтинуум попарно различных инвариантных классов Q с характеристикой σ.Обозначим через L(f ) минимальную сложность схемы из функциональных элементов, реализующей функцию f , и пусть L(n) =max L(f ), LQ (n) = max L(f ).
В дальнейшем используются следуf ∈P2 (n)f ∈Q(n)ющие утверждения.Теорема 1.2 (О. Б. Лупанов [5]).2nL(n) = (1 + δn ),n(1)где δn → 0 при n → ∞.Теорема 1.3. Если Q — инвариантный класс с характеристикой σ,σ > 0,то2nLQ (n) ≤ σ (1 + ∆n ),(2)nгде ∆n → 0 при n → ∞.Функция fn (x1 , . . . , xn ) называется сложной, если L(fn ) = L(n). Бесконечная последовательность булевых функций (f1 (x1 ), f2 (x1 , x2 ), . . . ,fn (x1 , .
. . , xn ), . . .) называется сложной, если для любого N существуетn ≥ N такое, что функция fn (x1 , . . . , xn ) является сложной.Алгоритм, строящий бесконечную последовательность булевыхфункций (fi (x1 , . . . , xi ))∞i=1 из P2 называется правильным, если он строитвсе функции минимального по включению инвариантного класса, содержащего эту последовательность.Теорема 1.4 (С. В. Яблонский [8]). Любой правильный алгоритм,строящий сложную последовательность функций (fi (x1 , .
. . , xi ))∞i=1 изP2 , строит все множество P2 .Функция g называется порождающим элементом инвариантногокласса Q тогда и только тогда, когда она не лежит в Q и либо g —константа, либо всякая функция, получающаяся из g подстановкой констант, лежит в Q.Множество всех попарно неконгруэнтных порождающих элементовинвариантного класса Q называется неприводимой системой порождающих элементов инвариантного класса Q и обозначается через U (Q).Пучком функции g называется множество Πg тех и только тех функций, из которых функция g может быть получена последовательнымприменением таких операций, как переименование переменных без отождествления, добавление и изъятие фиктивных переменных, подстановкаконстант.1.1.
Пусть A и B — инвариантные классы. Верно ли, что всегда инвариантным классом является:1) A ∩ B;2) A ∪ B;3) A \ B;4) P2 \ A.1.2. 1) Всякий ли замкнутый класс является инвариантным?2) Всякий ли инвариантный класс является замкнутым?1.3. Пусть A — замкнутый класс, содержащий константы 0 и 1. Верноли, что A — всегда инвариантный класс?1.4. Выяснить, какие из следующих классов являются инвариантнымиклассами:1) класс L линейных функций;2) класс M монотонных функций;3) класс T0 функций, сохраняющих константу 0;4) класс T0 ∩ T1 , где Tσ , σ ∈ {0, 1}, — класс функций, сохраняющихконстанту σ;5) класс S самодвойственных функций;6) класс симметрических функций, то есть функций, не изменяющихсяпри любой перестановке их переменных;7) класс симметрических функций и функций, получаемых из симметрических добавлением фиктивных переменных;8) класс функций, принимающих единичные значения только на наборах с четным числом единиц;9) класс функций, степень полинома Жегалкина которых не большенекоторого заданного числа;10) класс функций, число слагаемых полинома Жегалкина которыхне больше половины всех возможных.1.5.
Построить минимальный (по включению) инвариантный класс Q,содержащий в себе класс:1) S - самодвойственных функций;2) T0 - функций, сохраняющих константу 0;3) T1 - функций, сохраняющих константу 1;4) T0 ∩ T1 - функций, сохраняющих константы 0 и 1.1.6. Доказать, что pдля каждого непустого инвариантногоp класса Q2n2n|Q(n)| не возрастает и 1 ≤ lim|Q(n)| ≤ 2.последовательностьn→∞1.7. Доказать, что если инвариантный класс Qσ не совпадает с P2 ,то σ < 1.1.8. Вычислить характеристики следующих инвариантных классов:1) класс L линейных функций;2∗ ) класс M монотонных функций;3) класс функций, представимых в видеf (x1 , .
. . , xn ) = l(x1 , . . . , xn )&g(x1 , . . . , xn ),(3)где l — линейная функция, а g — произвольная функция из P2 , у которой каждая существенная переменная является существенной переменной функции l.1.9. 1) Пусть P2∗ (n) — множество функций из P2 (n), существенно заnn−1висящих от n переменных. Показать, что |P2∗ (n)| ≥ 22 − n22 ;2) Пусть Q, Q ⊆ P2 , — инвариантный класс. Доказать неравенствоn−mпри n ≥ m.|Q(n)| ≤ |Q(m)|21.10. Пусть s(f ) — число попарно различных подфункций функцииf , а s(n) = maxf ∈P2 (n) s(f ). Доказать, что1) s(n) ≤ 3n ;2∗ ) для всякого ε > 0 существует N такое, что s(n) ≤ 3n (1 − ε) длявсех n > N .1.11. Доказать теорему 1.4 из введения к параграфу.1.12. 1.
Найдите неприводимую систему порождающих элементов инвариантного класса Q, если1) Q — это класс M всех монотонных функций,2) Q — это класс L всех линейных функций,3) Q — это класс всех функций, существенно зависящих от не болеечем k переменных,4) Q — это класс, состоящий только из констант и всех тождественныхфункций.2. Приведите пример такого инвариантного класса Q, что его неприводимая система порождающих элементов бесконечна.3. Докажите,S что для любого инвариантного класса Q справедливоравенствоΠg = P2 \ Q.g∈U (Q)4. Докажите, что в P2 имеется ровно континуум попарно различныхинвариантных классов.§ 2. Сложность алгоритмовТермин “машина Тьюринга"(сокращенно МТ) употребляется здесьдля одноленточных детерминированных машин (см., например, [10]).Некоторое (непринципиальное) отличие состоит в том, что, как правило, рассматриваются МТ с односторонней лентой, бесконечной вправо.Алфавит символов ленты МТ обозначим через A, а множество состояний — через Q.
Алфавиты A и Q конечны. Символом q1 обозначаетсяначальное состояние, символом a1 — пустой символ, присутствующий поопределению в алфавите A. Считается, что в начальный момент слово w = b1 b2 . . . bn , обрабатываемое МТ, записано в первых n ячейкахленты, а все остальные ячейки ленты содержат символ a1 .
Детерминированность МТ означает, что для каждой пары вида (a, q), где a —символ входного алфавита, а q — символ состояния, в программе МТприсутствует не более одной команды вида: aq → a0 q 0 d, начинающейся сaq.Пусть в процессе работы МТ на некотором такте t оказалось, что наленте записано слово w = b1 b2 .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
