 |
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк
[11]
2.2-7 Докажите по индукции формулу (2.15).
2.2-8 Докажите такую оценку для чисел Фибоначчи: -F8+2 <~рг при г 0 (здесь (р - отношение золотого сечения).
Задачи
2-1 Асимптотика многочленов
Пусть р(п) = ao + ain+.. .-\-adnd - многочлен степени d, причём
cid > 0. Докажите, что
а. | р | га) | = О | (пк] | при | к d. |
б. | р | га) | = п | (пк) | при | к d. |
в. | р | га) | = в | [пк] | при | к = d. |
г. | р | га) | = о( | пк) | при | к > d. |
д- | р | (га) | = UJ | (пк) | при | к < d. |
2-2 Сравнение асимптотик
Для всех клеток следующей таблицы ответьте «да» или «нет» на вопрос о том, можно ли записать А как О, о, Q, uj или в от В (к 1, е > 0, с > 1 - некоторые константы).
б
д
А | В | О | о | в | ||
\gk га | пе | |||||
пк | сп | |||||
sin п | ||||||
2п | 2?г/2 | |||||
nlgm | mlgn | |||||
lg(ra!) | lg(n") |
2-3 Сравнение скорости роста
а. Расположите следующие 30 функций в порядке увеличения скорости роста (каждая функция есть О (следующая)) и отметьте, какие из этих функций на самом деле имеют одинаковую скорость роста (одна есть в от другой):
2s*n | (2)1§n ra2 lg2 ra lg(ra!) | ra! | (lg га)! | |
(3/2)п | ra3 | 22" | nl/lgn | |
In In га | lg* ra | n . 2n rass™ | In ra | 1 |
2lgra | (lg ra)sn | (n + 1)! | \/lg ra | |
lg* lg га | 2\/21gn- | ra 2n | ra lg ra | 22"+1 |
б. Укажите неотрицательную функцию /(га), которая не сравнима ни с одной из функций §i этой таблицы (/(га) не есть 0(дг(га)) и дг(п) не есть 0(/(га))).
2-4 Свойства асимптотических обозначений
Пусть функции /(га) и д(п) положительны при достаточно больших га. Можно ли утверждать, что
а. если /(га) = 0{д{п)), то д(п) = 0(/(га))? б- f(n) +д(п) = 0(min(/(ra),#(ra)))?
в./(га) = 0(д(п)) влечёт lg(/(ra)) = 0(lg(#(ra))), если lg(g(n)) > О и f(n) 1 для достаточно больших га?
г./(га) = 0(д(п)) влечёт 2/(п) = 0(2д)1
д./(га)=0((/(га))2)?
е./(га) = 0(д(п)) влечёт д(га) = i7(/(ra))?
ж./(га) = в(/(га/2))?
з./(га) + о(/(га)) = в(/(га))?
2-5 Варианты асимптотических обозначений
В некоторых книгах -обозначение используется в ином смысле. Мы будем использовать обозначение для этого варианта, чтобы избежать путаницы. Пусть /(га) и д(п) - функции натурального аргумента. Говорят, что /(га) = Г2°°(д(га)), если найдётся положительное число с, при котором /(га) сд(п) 0 для бесконечно многих натуральных га.
а.Покажите, что для любых двух функций /(га) и д(га), положительных при больших значениях га, выполнено либо /(га) = 0(д(п)), либо /(га) = Г2°°(д(га)), и что для нашего прежнего определения £}(д(п)) этого утверждать нельзя.
б.Каковы возможные достоинства и недостатки применения оценок вида при исследовании времени работы алгоритмов?
Некоторые авторы в записи /(га) = 0(д(п)) не требуют, чтобы функция /(га) была асимптотически положительной. Будем использовать обозначение О1 и скажем, что /(га) = 0(д(п)), если \f(n)\ = 0(g(n)).
в.Что происходит при таком определении с утверждениями теоремы 2.1?
Некоторые авторы используют ещё один вариант определения: будем говорить, что /(га) = 0(д(п)), если найдутся положительные числа с и к, для которых 0 f(n) сд(п) lgk га для всех достаточно больших га.
г.Определите Q и О аналогичным образом и докажите аналог теоремы 2.1.
2-6 Итерации
Мы итерировали логарифмическую функцию, но аналогичная операция возможна и для других функций. Пусть /(га) - некоторая функция, причём /(га) < га. Определим /W(ra), положив f(°\n) = га и f{i){n) = fU{l-l\n)) приг>0.
Для фиксированного числа с определим функцию /*(га) как ми-
нимальное г О, для которого f(n) с. (Другими словами, /* - это сколько раз нужно применять функцию /, чтобы из га получить число, не превосходящее с.) Заметим, что f*(n) определено далеко не всегда.
Для каждой из следующих функций /(га) и значений с оцените /* возможно точнее:
/м | с | fc(n) | |
а. | lg га | 1 | |
б. | га - 1 | 0 | |
в. | га/2 | 1 | |
г. | га/2 | 2 | |
д- | \/п | 2 | |
е. | \/п | 1 | |
ж. | „1/3 | 2 | |
3. | га/ lg га | 2 |
Замечания
Как считает Кнут [121], использование О-обозначений восходит к учебнику по теории чисел (P. Bachmann, 1892). Обозначение о(д(п)) было использовано Ландау (Е. Landau) в 1909 году при обсуждении распределения простых чисел. Использование Q- и О-обозначений рекомендовано Кнутом [124]: эти обозначения позволяют избежать технически некорректного употребления О-обозначений для нижних оценок (хотя многие люди продолжают так делать). Подробнее об асимптотических обозначениях см. Кнут [121, 124] и Брассар и Бретли [33].
Одни и те же обозначения порой используются в различных смыслах, хотя разница, как правило, оказывается несущественной. В частности, иногда сравниваемые функции не предполагаются неотрицательными при больших га (и сравниваются модули).
Существует много справочников, содержащих сведения об элементарных функциях: Абрамович и Стегун [1], Бейер [27]. Можно также взять любой учебник по анализу (см., например, Апостол [12] или Томас и Финни [192]). Книга Кнута [121] содержит много полезных математических сведений, используемых при анализе алгоритмов.