В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиВ. Б. Алексеев, А. А. Вороненко, С. А. Ложкин,Д. С. Романов, А. А. Сапоженко, С. Н. СелезневаЗАДАЧИ ПО КУРСУ“ОСНОВЫ КИБЕРНЕТИКИ”Москва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.