Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 24
Текст из файла (страница 24)
Значит, рассматриваемая функция детерминированная. Пример 2. Является ли функция у детерминированной, если у = з(х ) к Рз'„,, где х = х(1)х(2)... х(1) ..., у ' = у(1) у(2)... ...у(1)... и ~(х(1 — 1)., если Е четное число, у(1) = з (х(1) у(1+ 1), если 1 нечетное число? Решение. Если ориентироваться на форму задания функции, то естественно предположить, что она не является детерминированной, так как, например, «выход» в момент времени 1 = 1 зависит от «выхода» в момент 1 = 2. Однако указанная зависимость может оказаться «фиктивной», возникшей только вследствие «плохого» (неудачного) описания функции.
Поэтому необходимо проанализировать «природу» рассматриваемой функции. Пусть 1 = 2в+ 1, где в > О. Имеем у(2в + 1) = х(2в + 1) у(2в + 2) = х(2в + 1) . х(2в + 1) = = О. Следовательно, при всяком нечетном 1 выход у(1) равен О, т.е. 106 Гт 1К Ограниченно-детерминированные. функции является однозначной функцией первых 1 символов входного сло- ва х"'. Очевидно также, что аналогичная однозначность имеет место и для четных значений й Таким образом, рассматриваемая функция детерминированная.
Пример 3. Выяснить, является ли д. функцией отображение у = 1(хы) Е Р '„,, где х'' = х(Цх(2)... х(1)..., у ' = у(Ц у(2)... ...,у(1) ... и О, если существует такое в <1, у(1) = что Зх(в) < х(в + Ц + х(в + 2), 1 в ином случае. Решение. При х(в) = 0 неравенство Зх(в) < х(в+ Ц + х(в+ 2) выполняется независимо от значений х(в+ Ц и х(в -ь 2), а при х(в) = = 1 оно не выполняется ни при каких значениях х(в+ Ц и т(в+ 2).
Следовательно, О, если х(в) = 0 при некотором в < 1ч у(1) = 1 в ином случае, т. е. отображение 1" является д. функцией. Пример 4. Пусть уч' = те(х~) Е Рг'„где хы = х(Цх(2)... ... х(1)..., у = у(Ц у(2)... у(1)... и у(1) есть (1+ 2)-я цифра после запятой в двоичном разложении числа х(1)1'6. Выяснить, явля- ется ли д. функцией отображение 1'(хн). Решение. Из описания функции видно, что выход у(1) в мо- мент времени 1 определяется однозначно значением входа х(е); надо просто найти (1 + 2)-ю цифру после запятой в двоичном разложе- нии числа х(1)/6.
Значит, рассматриваемая функция является де- терминированной. Запишем выход у(1) в «явной форме». Нетрудно 1 1 1 1 1 установить, что — = — + — + — + ... + + ... Следовательно, б 8 32 128 2 4' двоичное разложение числа 11'6 имеет вид 0,0010101... = 0,0 (ОЦ,. а |юзтому 1., если х(1) = 1 и 1 = 2в + 1, где в > 1, у(1) = 0 в иных случаях. Пример 5. Показать., что оба приводимых ниже отображения у~ = 1(ххи) (из Р ',) не являвотся д. функциями (здесь, как обычно, х" = х(Ц х(2)... х(1)...
и у ' = у(Ц у(2)... у(1)... ): а) у(1) = х(,, ), 1 > 1; О, если в слове х(Ц х(2)... х(1' — 21+ 2) имеется б) у(1) массив из 1 нУлей и емУ но пРедшествУет массив из 1 единиц 0 в ином случае. Решение, а) Можно последовательно вычислять у(Ц, у(2) и т.д. до тех пор, пока не придем к соотношению вида у(1о) = х(1е -Ь в) у д Огпобрпженив последовптпевьноси~ей 107 д ля некоторого 1э ) 1 и некоторого в > 1.
Однако такая процедура «последовательного нахождения выходов» у(г) может оказаться практически неосуществимой (например., если минимальное 1э, удовлетворяющее соотношению у(1э) = х(1э + в), где в > 1, равно 2000). Поэтому надо действовать иначе, а именно выяснить, при каком (хотя бы одном) 1 выполняется неравенство (гз + 2гэ + 1)/(гэ + 3) ) > 1+ 1.
Получаем, что это неравенство справедливо при всяком натуральном 1 > 4 (в частности, если 1 = 4, то у(4) = х(5)). Следовательно, при 1 > 4 «выход» у(1) зависит от некоторого «входа» х(1+ в), где в > 1 (здесь в является функцией от 1). Тем самым недетерминированность заданного отображения доказана. б) Прикинем, как меняется длина слова х(1) х(2)... х(1з — 21+ 2) в зависимости от значения 1, чтобы можно было высказать конкретное соображение о том, при каком входном слове х ' «выход» у(1э) в некоторый момент времени гэ зависит от входов вида х(1э + в), где в > 1.
Ясно, что длина упомянутого выше слова равна (1 — 1) + 1. Следовательно, она превосходит значение 1 на заведомо подходящую для наших целей величину уже при 1 = 3: массив из трех нулей может начинаться с 3-го символа входного слова. Имеем следующее: если х" = 01000х(6)..., то у" = 010..., а если х = 01011 х(6)..., то у = 011...
Таким образом, 3-й символ выходного слова, соответствующий входному слову 010 х(4) х(5)..., зависит не только от первых трех букв этого слова, но также и от символов х(4) и х(5). Значит, рассматриваемое отображение не является детерминированным. (Заметим, что у(1) = х(1) и у(2) является однозначной функцией символов х(1) и х(2).) Пример 6. Через 8 обозначим здесь подмножество всех таких слов х' из множества (О, Ц, в которых на четных местах стоят единицы, т.е.
х(2в) = 1 при в > 1. Выяснить, можно ли функцию 1" доопределить до детерминированной: [1х, если х 68, (1, если х = 01[0] х", если х Е 8., б) У(хч ) = 0", если х ' =00х(3)х(4)... х(1)... (т.е. входное слово начинаотся с двух нулей). Решение. а) Очевидно, что значение первого выходного символа у(1) не зависит от входного символа (у(1) = 1 и при хм = 01 [0]"', и при х Е 8). Однако у(2) является функцией от последовательности х(2) х(4) ... х(2в) ..., причем у(2) = х(1), если х(2в) = 1 при всяком в > 1, и у(2) = 1, если х"' = 01 [11]м.
Рассмотрим два входных слова: [01]" и 01 [0]". Имеем 1([01]") = = [10] ' и Д(01 [0]'') = 1 . Значит, у(2) = О, если хн = [01], и у(2) = 1, если хм = 01 [0] ', т.е. у(2) не является однозначной функцией от входных символов х(1) и х(2). 108 Гл. Ре'. Ограниченно-дегпернинированные функции Таким образом, рассматриваемая нами функция 7' не может быть «продолжена» до детерминированной (она уже сама недетерминиро- ванная, хотя и не является всюду определенной на множестве (О, Ц ).
б) Из приведенного описания функции у видно, что у(1) = х(1) и у(2) = х(2) как для х Е 8, так и для хы = ООх(3) х(4) ... х(1) ... Далее, если х(2) в рассматриваемых входных словах равно О, то у(1) = 0 при всяком 1 > 3, а если х(2) = 1, то д(1) = х(1), 1 > 3. Зна- чит, заданную функцию ( можно попытаться доопределить следующим образом; если х = х(1)1х(3)1х(5)1...
1х(2в — 1)Ох(2в+ 1)х(2в+ 2)..., где в ) 1, то ((х ) = х(1) 1х(3) 1 ... 1х(2в — 1) <0) (другими слова- ми, на «выходе» выдается д(1) = х(1) до тех пор, пока при некотором 1о = 2в на «вход» не поступит символ 0; после этого у(1) = 0 для всех 1 > 1о. Очевидно, что у (хй ) - - д. функция, являющаяся продолжением функции 1 (х '" ) .
11ри мер 7. Выяснить, является ли функция У(ххн ) = у(1) у(2)... ... у(1)... (из Р, ',) о.-д. функцией, и найти се вес: цз ') у%= х(1) при 1= 1, 2, х(<1/3<) при е ) 3; (1) 0 при в=1, х(т) — в у(1 — 1) при Г > 2; у 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~ ~ ~ ~ | <(1, если 1 --. нечетное число, в) у(1) = (х(1), если 1 четное число. Решение. а) Из приведенного описания функции 7 (х н ) следует, что для получения выходного символа при 1 = Зв (в > 1) необходимо «хранить в памяти» входной символ, поступивший в момент време- ни в, т.
с. этот входной символ надо «помнить» в течение 2в моментов времени. Значит, для «реализации» рассматриваемой д. функции нужно иметь бесконечную (растущу|о во времени) память, что соот- ветствует бесконечному множеству состояний. К такому же выводу можно прийти, строя для заданной функции фрагменты ео информативного дорева. (Однако потребуется постро- ить 8. 9 ярусов дерева, что весьма громоздко.) Для обоснования того, что данная функция не является ограни- ченно-детерминированной, рассмотрим остаточные функции, порож- денные словами 0' = 00... О, где в > 1, и сравним значения этих в рвв функций на входном слове 1 '.
Имеем у (О' 1ы) = 00... 0 <1< ', а следоЗв-~-2 вательно, 15,(1 ) = 00 ... 0 <1] . Значит, для разных значений в эти зв»2 функции попарно не эквивалентны. Таким образом, вес функции у' равен со, т.е. она не является о.-д. функцией. 3 б Отображения последовательностей б) Построив четыре яруса информативного дерева заданной функции (рис. 4.3), нетрудно высказать предположение, что все вершины Рис. 4.3 дерева разбиваются на три класса эквивалентности: первый класс содержит только вершину О, второй -- вершины 1, 2, 4, 6, 10, 14 и т.д., а третий --.
вершины 3., 5, 7, 8., 9, 11, 12, 13 и т.д. Вершинам из второго класса соответствуют остаточные функции )е(хн), Де-,(х") и др(хн), где е > 1., а вершинам из третьего класса остаточные функции (;. (х '), где о равно 0 или 1, е > 1 и х'ф1'. Убедимся в эквивалентности функций, входящих в один и тот же класс эквивалентности. Имеем ~(Ох(1) х(2)...х(4)... ) = 0(х(1) э 0)(х(2) -е (х(1) э 0))... ...
(х(1) — е (х(1 — 1) — е... — е х(1) э 0)... ))... = = 0 х(1) (х(1) Ч х(2))... (х(1)Ч... Ч х(4 — 1) У х(1))...., 1(01'х(1) х(2)... х(1)... ) = О 1 ... 1 х(1)(х(1)Ч е Ч х(2))... (х(1) М... М х(1 — 1) Ч х(у))..., 1"(1 х(1) х(2)... х(1)... ) = 0 1 ... 1 х(1)(х(1)Ч х(2))... ... (х(1) Ч...Чх(1 — 1) Мх(1))... (здесь 1 = 0 и при в > 1 слово 1 ... 1 пустое). е — 1 Отсюда заключаем, что каждая из остаточных функций Д(хб'"), 1е-. (хм) и Д.
(хи), где е > 1, эквивалентна функции д(хи) = = у(1) у(2)... у(1)..., где у(4) = х(Ц У... Чх(1 — 1)ух(1), 1 > 1. Далее, Дс х1 хз ... х х(1) х(2)... х(1)...) = = Охз (хз 'ехз) . ° ° (х1 хз " - " хе — 1)(х1 Ч хз М . ° ° Ч хе) Й 3е(х1 Ч хе... Мхов т(1))(т1 Мхе М... Ч хеЧ х(1)Ч х(2))... 110 Го.
1К Ограниченно-дегаерыинирооанные функции ... (хз Ч хз Ч... 'у х, Ч х(1) Ч х(2) Ч... Ч х(1))... = = Ох1(хз ~Гхз)...(х1 Ч хэ Ч ... Ч х,, з)11...1..., ибо х' ф 1' (а значит, хз Ч хз 'д... Ч х, = 1). Таким образом, ( я. (х(1) х(2)... ) = 1к. Из наших рассмотрений вытекает, что заданная функция ( является о.-д. функцией веса 3. в) Нарисовав пять полных ярусов и частично шестой ярус информативного дерева заданной функции (рис. 4.4), легко увидеть, на какие классы эквивалентности разбивается множество вершин этого дерева. Вершина 0 образует один класс эквивалентности, все вершины, принадлежащие дереву, растущему из вершины 1, образуют второй Ро Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
