09042001 (1109971)

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

Текст из файла

9 апреля 2001 г.

Покажем же наконец, как строить СФЭ методом каскадов. Если на очередном шаге имеет место следующее разложение для какой-нибудь функции из : , то на уже построенные и добавляем ФЭ, как показано на рисунке:

Таким образом, на шаге, на котором из функций от переменных получаем функции от переменных, можно обойтись функциональными элементами - одним для отрицания переменной и тремя (две конъюнкции и одна дизъюнкции) для каждой новой функции. Следовательно, для любой схемы из функциональных элементов , построенной методом каскадов, справедлива оценка . Напомним, что для КС метод каскадов дает .

В прошлой лекции мы сказали, что это в некотором смысле экономный метод построения СФЭ. Действительно, он позволяет дать очень точную аппроксимацию максимальной сложности любой функции, когда число переменных этой функции стремится к бесконечности. Однако в отдельных случаях он может не дать схему наименьшей сложности, т.е. он не есть универсальный метод построения минимальных схем. Например, если построить с помощью этого метода СФЭ для , то сложность получится , где - константа, в то время как имеется СФЭ для этой функции, сложность которой не превосходит (она может быть получена, постепенно реализуя одно сложение за другим, т.к. при этом сложность каждый раз будет увеличиваться на 4).

Итак, приступим к оценке суммы . При любом , , имеем , где значок обозначает “асимптотически меньше” (при отброшенная часть выражения меньше оставшейся в бесконечное число раз). Последняя сумма принимает свое наименьшее возможное значение, когда слагаемые примерно равны, а это имеет место тогда, когда соответствующие показатели примерно равны, т.е. (на самом деле, точнее было бы сказать, что должно быть как можно ближе к решению (единственному) уравнения , что приводит к тому же результату. – Прим. Наб.). В качестве можно выбрать , и тогда будем иметь . Второе слагаемое значительно меньше первого при , так что можно считать справедливыми оценки для СФЭ и для КС. На самом деле можно показать, что обе функции асимптотически ведут себя, как (с коэффициентом 1), при (иными словами, они эквивалентны в духе математического анализа).

Здесь это не будет доказано полностью, но покажем, что эту оценку нельзя улучшить, в том смысле что существуют функции, сложность которых близка к , при любом . Доказательство этого факта будет от противного и несколько напоминает доказательство того теоретико-числового факта, что трансцендентных чисел континуум (а алгебраических счетное число). Рассмотрим такие числа: пусть равно числу всех функций от переменных, которые реализуются схемой сложности ; равно числу всех функций, которые реализуются схемой сложности ровно ; равно числу всех схем сложности . Докажем грубую оценку в случае СФЭ, а затем воспользуемся очевидными отношениями между этими числами, а именно (первое следует из того, что любую схему сложности, меньше , можно дополнить ничего не делающими элементами до нужной сложности, а второе – из того, что разные функции заведомо не могут реализовываться одинаковыми схемами):

Всего у нас имеется входов и выходов, каждый вход может быть присоединен к любому выходу; каждый из функциональных элементов может быть либо , либо , либо ( возможностей). Еще каждый выход может быть помечен * (она одна на всю схему) - возможностей. Поэтому приведенная выше оценка справедлива.

Понятно, что если для некоторого , то , ибо всего функций от переменных . . Как оказывается, достаточно положить , и при достаточно больших будем иметь

.

Следовательно, , т.е. для некоторого имеет место неравенство при . Как было сказано ранее, в самом деле . В случае же КС при тех же обозначениях можно показать, что (для каждого контакта существуют возможностей ( и ); всего концов, способов их соединения ), а дальше так же, как и в предыдущем случае, получаем абсолютно то же самое:

Подведем итоги. Имеет место

Утверждение. ; .

АВТОМАТЫ

Рассмотрим два алфавита – конечные множества и – и бесконечные последовательности букв из - и из - , а также отображения (функции) множества первых последовательностей во множество вторых. Пусть теперь .

Сначала посмотрим на пример такой функции, а также одну из неприятностей, которые могут возникнуть при попытке определить образ какой-нибудь последовательности. А именно, пусть переводит последовательность в (т.е. оставляет на месте), а все остальные в . Для такой функции существует последовательность, а именно, состоящая из одних нулей, для которой, чтобы определить ее образ, недостаточно знать конечное (как бы большим оно ни было) число членов. Это причиняет неудобства при вычислениях значений функций, почему вводится понятие детерминированности.

Определение. Функция называется детерминированной, если однозначно определяется первыми членами , , ..., .

Примеры.

Функция детерминирована (“ ” означает, что на этом месте может стоять что угодно).

Функция детерминирована.

Функция единичной задержки детерминирована.

Функция детерминирована.

Детерминированные функции можно задавать на бесконечных деревьях. А именно, на ребрах будем записывать компоненты выходной последовательности для той входной, которая получается, если, например, для функций, область определения которых , записывать 0 при движении влево и 1 – вправо, причем движение происходит по тем же ребрам. (Ясно, что для таких функций нужно брать бинарные (двоичные) деревья, которые характеризуются тем, что есть ровно одна вершина степени 2 (как бы начало), а степень остальных 3. Степенью вершины называется количество ребер, концом которых она является. Такие деревья допускают естественную ориентировку: из начальной вершины выходят два ребра; во все остальные входит одно и выходят два. В общем же случае дерево должно быть таким, чтобы можно было его ориентировать так, чтобы из каждой вершины выходило столько же ребер, сколько букв в алфавите , а в каждую вершину за исключением начальной входило ровно одно. – Прим. Наб.) Для начала рассмотрим несколько примеров:

- первая функция из примеров; -сумма , она же функция четности (вторая функция из примеров).

Определение. Конечно детерминированные функции или автоматы – детерминированные функции, в деревьях которых содержится лишь конечное число различных (не изоморфных между собой) поддеревьев.

Здесь изоморфизм понимается в расширенном смысле, а именно, с учетом букв, записанных на ребрах: биекция, устанавливающая изоморфизм графов, должна сохранять эти буквы.

Подробнее о конечно детерминированных функциях на следующей лекции.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций