Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 28
Текст из файла (страница 28)
4]. а Рассмотрите рекурсивный алгоритм бинарного поиска, предназначенный для нахождения числа в отсортированном массиве (см. упр. 2.3.5). Приведите рекуррентные соотношения, описывающие время бинарного поиска в наихудшем случае, если массивы передаются с помощью каждого из описанных выше методов, и дайте точные верхние границы решений этих рекуррентных соотношений.
Пусть размер исходной задачи равен Х, а размер подзадачи — и. 6. Выполните задание части (а) для алгоритма Мннсн-Зонт из раздела 2.3.1. 4.3. Другие примеры ренуррентнык соотношений Дайте верхнюю и нижнюю асимптотические оценки функции Т(л) в каждом нз приведенных ниже рекуррентных соотношений. Предполагается, что Т(п) для достаточно малых значений и является постоянной величиной. Постарайтесь, чтобы оценки были как можно более точными и обоснуйте ответы. зь Т(п) = 4Т(п/3) + и 18 и.
б. Т(и) = ЗТ(п/3) + и/1к п. а Т(п) = 4Т(п/2) + пз ъl п. г. Т(п) = ЗТ(п/3 — 2) + и/2. д. Т(п) = 2Т(и/2) + и/ 1к и. е. Т(п) = Т(и/2) + Т(п/4) + Т(п/8) + п. нс. Т(и) = Т(и — 1) + 1/и. з. Т(и) = Т(п — 1) + 18 и. и. Т(п) = Т(п — 2) + 1/ 18 п. зс Т(п) = л/йТ(з/п) + и.
4.4. Числа Фнбоначчн В этой задаче раскрываются свойства чисел Фибоначчи, определенных с помощью рекуррентного соотношения (3.22). Воспользуемся для решения рекуррентного соотношения Фибоначчи методом производящих функций. Определим Часть 1 Основы !34 производяи4ую функцию (или формальный степенной ряд) У' как у(г) = ~р',г' в=о = О+ с+ с~+ 2гз+ Зс~+ ба~+ 8га+ 13а~+ 21га+ где Р; представляет собой г'-е число Фибоначчи. а. Покажите, что.Т(г) = г+ сУ'(г) + с~.с'(г). б.
Покажите, что У'(с) = г (1 — фа)(1 — фг) 1 ( 1 1 Л(1-фг 1 ф, где ф= = 1.61803.. 1+Я 2 1 — Я Ф = = — 0.61803 .. 2 в. Покажите, что 1 б ,, ~Л г. Воспользуйтесь п. (в) для доказательства того, что Г; = ф'/~Л (округленное до ближайшего целого) для всех г > О. (Указание: обратите внимание, что Я <1.) 4.5, Тестирование микросхем В распоряжении профессора есть п предположительно идентичных микросхем ("чипов"), которые в принципе способны тестировать друг друга. В тестирующее приспособление за один раз можно поместить две микросхемы. При этом каждая микросхема тестирует соседнюю и выдает отчет о результатах тестирования.
Исправная микросхема всегда выдает правильные результаты тестирования другой микросхемы, а результатам неисправной микросхемы доверять нельзя. Таким образом, возможны четыре варианта результатов тестирования, приведенные в таблице ниже. 155 Глава В. Рввдаисв и вввсмвэвс Отчет А Отчет В Заключение Либо обе исправны, либо обе неисправны Неисправна как минимум одна микросхема Неисправна как минимум одна микросхема Неисправна как минимум одна микросхема сь Покажите, что, если как минимум и/2 микросхем неисправны, профессор не сможет точно определить исправные микросхемы, какой бы стратегией попарных испытаний он не пользовался. (Предполагается, что неисправные микросхемы не договариваются между собой, чтобы обмануть профессора.) сь Рассмотрим задачу о поиске одной исправной микросхемы среди п микросхем, если предполагается, что исправно более половины всех микросхем.
Покажите, что [и/2] попарных тестирований достаточно для сведения этой задачи к подзадаче, размер которой приблизительно в два раза меньше. ж Покажите, что можно найти все исправные микросхемы с помощью 6(п) по- парных тестирований в предположении, что исправны более половины микросхем. Сформулируйте и решите рекуррентное соотношение, описывающее количество тестирований. 4.б. Массивы Монжа Массив А размером т х и, состоящий из действительных чисел, является массивом Монжа (Мопйе апау), если для всех с, 5, lс и 1, таких, что 1 < с < lс < т и 1 <5 <1<и, мы имеем А[с,5] + А[/с,1] < А[с,1] + А[1с,5] .
Другими словами, при любом выборе двух строк и двух столбцов из массива Монжа (при этом элементы массива на пересечении выбранных строк и столбцов образуют прямоугольник) сумма элементов в левом верхнем и правом нижнем углах полученного прямоугольника не превышает сумму элементов в левом нижнем и правом верхнем его углах. Приведем пример массива Монжа. 10 17 13 17 22 16 24 28 22 11 13 6 45 44 32 36 33 19 75 66 51 В исправна А исправна В исправна А неисправна В неисправна А исправна В неисправна А неисправна 28 23 29 23 34 24 17 7 37 23 21 6 53 34 Часть 1 Основы 13б а Докажите, что массив является массивом Монжа тогда и только тогда, когда для всех 1 = 1, 2, ..., гп — 1 и 1 = 1, 2, ..., п — 1 выполняется условие А [1, 1] + А[1 + 1, 3 + Ц < А[и, 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(1) представляет собой индекс столбца, содержащего крайний слева минимальный элемент в строке г. Докажите, что ((1) < ((2) « . Дт) для любого массива Монжа размером т х и. а Далее приведено описание алгоритма "разделяй и властвуй", предназначенного для вычисления крайнего слева минимального элемента в каждой строке, входящей в состав массива Монжа А размером т х и. Постройте подматрицу А' матрицы А, состояшую из четных строк матрицы А.
С помощью рекурсивной процедуры найдите в каждой строке матрицы А' крайний слева минимальный элемент. Затем найдите крайний слева минимальный элемент среди нечетных строк матрицы А. Объясните, как найти крайний слева минимальный элемент среди нечетных строк матрицы А (предполагается, что крайний слева минимальный элемент среди четных столбцов этой матрицы известен) за время 0(го + и).
д. Запишите рекуррентное соотношение, описывающее время работы алгоритма из п. (г). Покажите, что его решение имеет вид О(т + и 1о8 т). Заключительные замечания Применение метода "разделяй и властвуй" для разработки алгоритмов датируется как минимум 1962 годом, когда вышла статья Карацубы (Кага1зпЬа) и Офмана (Ойпап) [193]. Однако в действительности он мог применяться намного ранее; согласно Хайдеману (Не16ешап), Джонсону (1оЬпзоп) и Баррасу (Вштлз) [162], К.Ф.
Гаусс (С.г. Оапаз) разработал первый алгоритм быстрого Фурье-преобразования в 1805 году, причем в формулировке Гаусса задача разбивается на меньшие подзадачи, решения которых затем объединяются. Гпава К Разделяй а впаслявуй !з7 Задача поиска максимального подмассива в разделе 4.1 представляет собой вариацию задачи, изучавшейся Бентли (Вел!!еу) [42, глава 7]. Алгоритм Штрассена [323] вызвал большой ажиотаж после его опубликования в 1969 году. До этого мало кто представлял себе возможность существования алгоритма, асимптотически более быстрого, чем базовая процедура Я!)иякнМхтк!х-Мцьт!Рьу. С того времени асимптотнческая верхняя граница ддя матричного умножения быка улучшена.
На сегодня наиболее эффективный асимптотнчески алгоритм для перемножения матриц размером и х и, разработанный Копперсмитом (Соррегяпйй) и Виноградом (%1пойгаб) [77], имеет время работы 0(и~ ~~~). Наилучшей известной нижней границей, совершенно очевидно, является Й(п ) (очевидно, поскольку мы должны заполнить и элементов произведения матриц). С практической точки зрения алгоритм Штрассена часто неприменим по следующим причинам. !. Постоянный множитель, скрытый во времени работы алгоритма лэ(п'Я"), оказывается гораздо больше постоянного множителя во времени Сэ(пз) процедуры Б!20Аке-Мятк!х-М1п.т!Рьу.
2. В случае разреженных матриц имеются специализированные более эффективные методы умножения. 3. Алгоритм Штрассена не настолько численно устойчив, как простой алгоритм умножения матриц Я!7иякв-Мятк! х-Мц ьтпчх. Другими словами, нз-за ограниченной точности компьютерных вычислений с действительными числами в случае алгоритма Штрассена накапливаются ббльшие ошибки, чем при использовании алгоритма БОцхкв-Мятк!Х-Мцьтюгьу, 4. Построение подматриц на каждом шаге рекурсии приводит к повышенному расходу памяти. Последние две причины потеряли актуальность в 1990-х годах.
Хайем (Н!8Ъшп) [166] показал, что отличия в численной устойчивости преувеличены; хотя алгоритм Штрассена для ряда приложений действительно слишком численно неустойчив, все же его устойчивости вполне достаточно для большого количества приложений. Бейли (Ва!1еу), Ли (Ьее) и Саймон (8!пюп) [31] рассмотрели методы снижения требующейся для работы алгоритма Штрассена памяти. На практике реализации быстрого умножения плотных матриц с использованием алгоритма Штрассена имеют "точку пересечения'* (в смысле размера перемножаемых матриц) с обычным алгоритмом умножения и переключаются на использование простого алгоритма при перемножении матриц с размером, меньшим точки пересечения.
Точное значение точки пересечения сильно зависит от реализации и используемой вычислительной системы. Анализ, учитывающий количеспю операций, но игнорирующий кеширование и конвейерную обработку, дает для точки пересечения достаточно низкие оценки: и = 8 у Хайема (Н!8Ъаш) [166] и п = 12 у Хасс-Ледермана (Низа-Ьег(еппап) н др. [185]). Д'Альберто (О'А(Ъепо) и Николау (!л!!со!ап) [80] разработали адаптивную схему, которая определяет точку пересечения при инсталляции пакета программного обеспечения. В различ- Часть 1 Основы г38 ных вычислительных системах эта точка находится в диапазоне от и = 400 до и = 2150, а для ряда систем они так и не смогли ее найти. Рекуррентные соотношения изучались еще с 1202 года, со времен Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
