Алгоритмы - построение и анализ (1021735), страница 25
Текст из файла (страница 25)
* 4.4-3. Покажите, что в случае 3 основной теоремы одно из условий излишнее в том плане, что из условия регулярности а/ (и/Ь) < с/ (и) для некоторой константы с < 1 следует, что существует константа е > О, такая что /(и) = П (и~~а'~+'). Задачи 4-1. Примеры рекуррентных соотношений Определите верхнюю и нижнюю асимптотические границы функции Т (и) для каждого из представленных ниже рекуррентных соотношений. Считаем, что при и < 2Т(п) — константа. Попытайтесь сделать эту оценку как можно более точной и обоснуйте свой ответ.
а) Т(п) = 2Т(п/2) + па. б) Т (и) = Т (9п/10) + и. в) Т(п) = 16Т(п/4) +пг г) Т (п) = 7Т (п/3) + пз. д) Т(п) = 7Т(п/2) + па, е) Т(п) = 2Т(п/4)+ ~/и. ж) Т(п) = Т(п — 1) + и. з) Т(п) =Т(,/й)+1. 4-2. Поиск отсутствующего целого числа Массив А (1..п] содержит все целые числа от 0 до т1 за исключением одного. Отсутствующее число можно легко определить за время О (и), 134 Часть 1.
Основы располагая вспомогательным массивом В [1..п], предназначенным для записи имеющихся чисел из массива А. Однако в этой задаче мы лишены средств, позволяющих получить доступ к целому числу из массива А посредством одной операции. Элементы массива А представлены в двоичной системе счисления, и единственная операция, с помощью которой можно осуществлять к ним доступ, это "извлечение 3'-го бита элемента А [г]", юторая выполняется в течение фиксированного времени. Покажите, что, располагая только этой операцией, отсутствующее целое число все же можно определить за время О (и). 4-3. Время, затрачиваемое на передачу констант В этой книге предполагается, что передача параметров при вызове процедуры занимает фиксированное время, даже если передается И-элементный массив.
Для большинства вычислительных систем это предположение справедливо, поскольку передается не сам массив, а указатель на него. В данной задаче исследуются три стратегии передачи параметров. 1) Массив передается посредством указателя. Время выполнения этой операции Т = 6 (1).
й) Массив передается путем юпирования. Время выполнения этой операции Т = 9 ()т'), где Ж вЂ” размер массива. ш) Массив передается путем копирования только некоторого поддиапазона, к которому обращается вызываемая процедура. Время передачи подмассива А [р..о] равно Т = О (д — р+ 1). а) Рассмотрите рекурсивный алгоритм бинарного поиска, предназначенный для нахождения числа в отсортированном массиве (см. упражнение 2.3-5). Приведите рекуррентные соотношения, описывающие время бинарного поиска в наихудшем случае, если массивы передаются с помощью каждого из описанных выше методов, и дайте точные верхние границы решений этих рекуррентных соотношений.
Пусть размер исходной задачи равен Ф, а размер подзадачи — и. б) Выполните задание части а) для алгоритма Миксе Болт, описанного в разделе 2.3.1. 4-4. Примеры рекуррентных соотношений Дайте верхнюю и нижнюю асимптотические оценки функции Т (и) в каждом из приведенных ниже рекуррентных соотношений. Предполагается, что для достаточно малых значений и Т (и) — постоянная величина.
Постарайтесь, чтобы оценки были как можно более точными и обоснуйте ответы. а) Т(п) = ЗТ(п/2) + п1бп. Глава 4. Рекуррентные соотношения 135 4-5. Числа Фибоначчи В этой задаче раскрываются свойства чисел Фибоначчн, определенных с помощью рекуррентного соотношения (3.21). Воспользуемся для решения рекуррентного соотношения Фибоначчи методом генераторных функций. Определим производящую функцию (или формальный степенной ряд) У' как .к = ~ Р~з =О+а+а +2з +За +ба +8з +13е +21з +..., =о где Г, — г'-е число Фибоначчи.
а) Покажите, что г (г) = з + зУ'(з) + зз.к Я. б) Покажите, что где Ф = = 1.61803... 2 Ф = = -0.61803... 2 в) Покажите, что У'(з) = 2 -1 (фз ф1) 1 '=о г) Докажите, что Е, = ф'/~/5 (округленное до ближайшего целого) для всех 1 > О. (Указание: обратите внимание на то, что ~ф~ < 1.) б) Т(п) в) Т(п) г) Т(п) д) Т(п) е) Т(п) ж) Т(п) з) Т(п) и) Т(п) к) Т(п) = 5Т (п/5) + п/18 и.
= 4Т(п/2) + пз~lй. = ЗТ (п/3 + 5) + и/2. = 2Т (и/2) + и/18п. = Т (и/2) + Т (и/4) + Т (и/8) + п. = Т (и — 1) + 1/и. = Т(п — 1) + 1бп. = Т(п — 2) + 218п. =,/пТ (;/й) + п. Часть 1. Основы 136 д) докажите, что Р;.ьз ) фз для з' > О. 4-6. Тестирование СБИС В распоряжении профессора есть зз предположительно идентичных СБИС', которые в принципе способны тестировать друг друга.
В тестирующее приспособление за один раз можно поместить две микросхемы. При этом каждая микросхема тестирует соседнюю и выдает отчет о результатах тестирования. Исправная микросхема всегда выдает правильные результаты тестирования, а результатам неисправной микросхемы доверять нельзя. Таким образом, возможны четыре варианта результатов тестирования, приведенные в таблице ниже.
Отчет Отчет Вывод микросхемы А микросхемы Б Б исправна Либо обе микросхемы исправны, либо обе неисправны Неисправна хотя бы одна микросхема Неисправна хотя бы одна микросхема Неисправна хотя бы одна микросхема А исправна Б исправна Б неисправна Б неисправна А неисправна А исправна А неисправна а) Покажите, что если неисправно более зз/2 микросхем, то с помощью какой бы то ни было стратегии, основанной на попарном тестировании, профессор не сможет точно определить, какие микросхемы исправны.
(Предполагается, что неисправные микросхемы не смогут тайно сговориться, чтобы обмануть профессора.) б) Рассмотрим задачу о поиске одной исправной микросхемы среди и микросхем, если предполагается„что исправно более половины всех микросхем. Покажите, что ~п/2) попарных тестирований достаточно для сведения этой задачи к подзадаче, размер которой приблизительно в два раза меньше. в) Покажите„что можно найти все исправные микросхемы с помощью 9 (и) попарных тестирований, если предполагается, что более половины микросхем исправны. Сформулируйте и решите рекуррентное соотношение, описывающее количество тестирований.
1 СБИС вЂ” зто аббревиатура от "сверхбольшие интегральные схемы" (микросхемы, созданные по технологии, которая используется при производстве большинства современных микропропессоров). Глава 4. Рекуррентные соотношения 137 4-7. Массивы Монжа Массив А, состоящий из действительных чисел и имеющий размер т х х и, называется массивом Монжа (Мопйе апау), если для всех ю', ), lс и 1, таких что 1 < г < /с < тп и 1 < 7' < 1 < и, выполняется соотношение А[а,Я+ А [В,1] < А[т',1]+ А[1, 7'].
Другими словами, при любом выборе двух срок и двух столбцов из массива Монжа (при этом элементы массива на пересечении выбранных строк и столбцов образуют прямоугольник) сумма элементов в левом верхнем и правом нижнем углах полученного прямоугольника не превышает сумму элементов в левом нижнем и правом верхнем его углах. Приведем пример массива Монжа: 10 17 13 28 23 17 22 16 29 23 24 28 22 34 24 11 13 б 17 7 45 44 32 37 23 36 33 19 21 6 75 66 51 53 34 а) Докажите, что массив является массивом Монжа тогда и только тогда, когда для всех г = 1, 2,..., т — 1 и т' = 1, 2,..., и — 1 справедливо соотношение А [т, Я + А [г + 1, у + Ц < А [г, у + 1] + А [г + 1, ~] .
(Указание: для прямого доказательства воспользуйтесь методом математической индукции; индукцию нужно провести отдельно для строк и столбцов.) б) Приведенный ниже массив не является массивом Монжа. Измените в нем один элемент таким образом, чтобы он стал массивом Монжа. (Указание: воспользуйтесь результатами части а.) 37 23 22 32 21 6 7 10 53 34 30 31 32 13 9 6 43 21 15 8 Часть 1. Основы 13й в) Пусть 1 (1) — индекс столбца, содержащего крайний слева минимальный элемент в строке 1. Докажите, что для любого массива Монжа размером т х и справедливо соотношение 1 (1) < Г' (2) < «. 1(т). г) Ниже описан алгоритм разбиения, предназначенный для вычисления крайнего слева минимального элемента в каждой строке, входящей в состав массива Монжа А размером т х и.
Постройте подматрицу А' матрицы А, состоящую из ее нечетных строк. С помощью рекурсивной процедуры найдите в каждой строке матрицы А' крайний слева минимальный элемент. Затем найдите крайний слева минимальный элемент среди четных строк матрицы А. Объясните, как найти крайний слева минимальный элемент среди нечетных строк матрицы А (предполагается, что крайний слева минимальный элемент среди четных столбцов этой матрицы известен) за время О (т + и). д) Запишите рекуррентное соотношение, описывающее время работы алгоритма из части г.
Покажите, что его решение — О (т + и 1ок т). Заключительные замечания Рекуррентные соотношения изучались еще с 1202 года, со времен Леонардо Фибоначчи (1.. Нюпасс(). А. де Муавр (А. 13е Моите) впервые использовал метод производящих функций (см. задачу 4-5) для решения рекуррентных соотношений. Основной метод был принят на вооружение после появления работы Бентли (Вепг!еу), Хакена (Накеп) и Сакса (Бахе) [411, в которой был предложено расширение метода, обоснованного в упражнении 4.4-2.
Кнут (Кппг(з) и Лью (1.ш) [205) показали, каким образом можно решать линейные рекуррентные соотношения с использованием производящих функций. Подробное обсуждение методов решения рекуррентных соотношений можно найти в книгах Пурдома (Ригдош) н Брауна (Вгоип) [252), а также Грехема (Огалаш), Кнута и Паташника (Ра1авЬ- пйк) [132). Некоторые исследователи, в число которых входят Акра (А1сга) и Баззи (Вакх() [131, Роура (Коша) [2621 и Верма (Чепца) [306)„предложили методы решения более общих рекуррентных соотношений для алгоритмов разбиения. Ниже представлены результаты Акра и Баззи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
