Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 23

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Полагаем Рьа, = () Рь'~™'. Если 1 = й, то вместо двух индексов внизу будем п>з ш>1 писать один (например, Рь „). Функции уз и уз из множества Рл в „называются различимыми, если существует такое слово х~', (е > 1), что ~л(хо) т'- Ь(хе). Если же уз (х') = 5(х") для любых слов х' (е = 1, 2, ... ), т, е. если равенство уз(х ) = )з(х' ) выполняется при всяком входном слове х, то функции )~ и уз называются эквивалентными (или неразличимыми) д. функциями. Пусть э' и д . функции из Рл и .

Если существует такое слово хо с А*, что )'(хох' ) = У(хо)д(х"'') для любого слова х с А (здесь через Д(х') обозначен префикс длины в выходного слова Д(х'х )), то функция д называется остаточной функцией (или остаточным оператором) функции у, порожденной (порожденным) словом хо, и обозначается через )-.. Множество Я(у, х') всех остаточных функций функции у, эквивалентных функции ~в., образует класс эквива,лентностп, называемый состоянием функции Э, содержащим остаточную функцию );;. Состояние, содержащее функцию ), называется начальным. Функция у называется ограниченно-детерминированной (сокращенно о.-д. функцией или о.-д. операгеюром), если она имеет 104 Гл, Ре'.

Ограниченно-детерминированные функции консчнос число попарно различных состояний. Число различных состояний о.-д. функции называется вс весом. Если множество попарно различных состояний функции 1 бесконечное, то считают, что вес ее равен со. Множество всех о.-д. функций, принадлежащих множеству Рл и „(соотвстстввнно множествам Р, ',, Р, ', Ря ~ „и Ря л), обозначается через Рд и, (соотвстственно через Р„"',"",, Р„"'„"', Рь ~ и Рь„).

При описании д. функций бывает удобно пользоваться теоретикографовым языком (а имснно бесконечными информативными деревьями). Пусть А алфавит, состоящий из 1 букв (1 > 1). Через Рл обозначим бесконочное ориентированное корневое дерево *), удовлетворяющее следующим условиям: а) из каждой вершины дерева, включая и корень, выходят ровно 1 дуг (т. с.

ориентированных ребер); б) в каждую вершину дерева, отличную от корня, входит только одна дуга, а в корень дерева нс входит ни одной; в) каждой дуге дерева Рл приписана некоторая буква алфавита А, причем разным дугам, выходящим из одной и той же вершины дерева (в частности, из корня), приписаны разные буквы. Корень дерева Рл считается вершиной нулевого ранга; если вершина дерева Рл является концом дуги, выходящей из вершины ь'-го ранга (1 > 0), то она называется вершиной (1+ 1)-гег ранга.

Лугой (ребром) у-го яруса 0 > Ц называется всякая дуга, выходящая из вершины 0 — 1)-го ранга. Каждой бесконечной оривнтированной цепи в дереве Рл соответствует вполне определенное слово из множества А . Па рис. 4.1 изображен фрог- 0 Рис. 4.1 Рис. 4.2 лент дерева Рл (где А = (О, 1)), состоящий из трах первых ярусов этого дерева (здесь и в дальнейшем мы предполагаем, что символу 0 соответствует левое ребро (дуга), выходящее из вергпины, а символу 1 правое); жирными ребрами выделена цепь, соответствующая слову 101. Нагруженное дерево Рл в получается из дерева Рл приписыванием каждой дуге некоторой буквы из алфавита В.

Всякой бесконечной ") Определение корневого дерева см. в гл. У1. у д Осаобрансенин последовательностей 105 ориентированной цепи в дереве Рл и отвечает слово из множества В', составленное из букв, приписанных дугам этой цепи. Поэтому можно считать, что нагруженное дерево Вл н задает, (реализует) вполне определенное отображение у: А'' -э В", являющееся д.

функцией из множества Рл д . На рис. 4.2 изображен фрагмент нагруженного дерева Вл н, где А = (О, 1) и В = (О, 1, 2); д. функция, соответствующая этому дереву, «перерабатывает», например, слово 1010 в слово 2012. Пусть Вл н — нагруженное дерево, реализующее д, функцию 1. Остаточной функции 5„-,. (в > 0) отвечает поддерево Вл д(хо), растущее из такой вершины о(х') в-го ранга, в которой оканчивается цепь, выходящая из корня дерева и содержащая ровно в ребер; 1-е по порядку ребро этой цепи принадлежит 1-му ярусу дерева и помечено символом хо(1) ч А. Если остаточные функции Д1 и (я эквивалентны, то соответствующие им вершины о(х') и о(х"), а также растущие из этих вершин поддеревья называются эквивалентнеллси.

Вес дерева, реализующего д, функцию, равен весу этой функции, а следовательно, равен жаксилсальноду числу попарно неэквивалентных вершин (или поддеревьев) данного дерева. 2. Типовые примеры. Пример 1. Выяснить, является ли д. функцией отображение у" = 1(х"') Е Р,', где х" = х(1)х(2)... х(1) ..., у" = у(1) у(2)... ...у(с)... и у(е) = х(1) — э х(1) при 1 > 1. Решение. Из описания функции следует, что значение «выхода» у(с) в момент времени 1 однозначно определяется значениями «входа» в моменты времени 1 и 1, т.е. в-й символ выходного слова у' при всяком в > 1 является однозначной функцией первых в символов входного слова х". Значит, рассматриваемая функция детерминированная. Пример 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...

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

Список файлов книги