Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 27
Текст из файла (страница 27)
Приведем пример массива Монжа: 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)„предложили методы решения более общих рекуррентных соотношений для алгоритмов разбиения.
Ниже представлены результаты Акра и Баззи. Их метод подходит для решения рекуррентных соотношений вида (4. 15) Т (и) = ~~~ а;Т ([™(Ь~ ) + ~ (и), Глава 4. Рекуррентные соотношения 139 где Й > 1; все коэффициенты а; положительны, и в сумме содержится хотя бы одно слагаемое; все 6; больше 1; функция /(и) ограниченная, положительная и неубывающая. Кроме того, для любой константы с > 1 существуют константы по и Ы > О, такие что для всех и > по справедливо соотношение / (и/с) > цГ' (и).
Этот метод позволяет найти решение рекуррентного соотношения Т (и) = Т (1п/31') + Т ((2п/31') + О (и), для которого неприменим основной метод. Чтобы решить рекуррентное соотношение (4.15), сначала найдем такое значение р, при котором 2 ', а;6, " = 1. (Такое р всегда существует, причем оно всегда единственное и положительное.) Решением рекуррентного соотношения является Т(п) = ст(тР)+ тз пг ~ — Нх ! У(х) ~ хя+1 и' где и' — достаточно большая константа. Метод Акры-Баззи на практике может оказаться слишком сложным в применении, однако он позволяет решать рекуррентные соотношения, моделирующие разбиение задачи на существенно неравные подзадачи. Основной метод более прост в использовании, однако он применим только в случае подзадач одинаковых размеров.
ГЛАВА 5 Вероятностный анализ и рандомизированные алгоритмы Эта глава знакомит читателя с вероятностным анализом и рандомизированными алгоритмами. Тем, кто не знаком с основами теории вероятности, следует обратиться к приложению В, в котором представлен обзор этого материала. В данной книге мы будем несколько раз возвращаться к вероятностному анализу и рандомизнрованным алгоритмам. 5.1 Задача о найме сотрудника Предположим, предприниматель хочет взять на работу нового офис-менеджера.
Сначала он попытался найти подходящую кандидатуру самостоятельно, но неудачно, поэтому решил обратиться в агентство по трудоустройству. Согласно договоренности, агентство должно присылать работодателю по одному кандидату в день. Предприниматель проводит с каждым из этих кандидатов собеседование, после чего принимает окончательное решение, брать его на работу илн нет. За каждого направленного ему кандидата предприниматель платит агентству небольшую сумму. Однако наем выбранного кандидата на работу фактически стоит дороже, поскольку при этом необходимо уволить офис-менеджера, работающего в данное время, а также уплатить агентству более значительную сумму за выбранного кандидата. Предприниматель пытается сделать так, чтобы должность всегда занимал наиболее достойный из всех кандидатов. Как только квалификация очередного претендента окажется выше квалификации офис-менеджера, который работает в данное время, этот офис-менеджер будет уволен, а его место займет более Глава 5.
Вероятностный анализ и рандомизированные алгоритмы 141 подходящий кандидат. Работодатель готов понести все необходимые расходы, но хочет оценить, во что обойдется ему подбор нового сотрудника. В представленной ниже процедуре Нщн Азз1зтлнт эта стратегия найма представлена в виде псевдокода.
В ней предполагается, что кандидаты на должность офис-менеджера пронумерованы от ! до п. Предполагается также, что после собеседования с 1-м кандидатом есть возможность определить, является ли он лучшим, чем все предыдущие. В процессе инициализации процедура создает фиктивного кандидата номер О, квалификация которого ниже квалификации всех остальных: Нщв АзязтАнт(гт) 1 Веа1 — О с Кандидат Π— наименее квалифицированный 1> фиктивный кандидат 2 1огт — 11оп 3 бо Собеседование с кандидатом 1 4 11 кандидат 1 лучше кандидата Вез1 5 Феп Веа1 — 1 6 Нанимаем кандидата 1 Модель стоимости этой задачи отличается от модели, описанной в главе 2.
Если ранее в качестве стоимости алгоритма мы рассматривали время его работы, то теперь нас интересует денежная сумма, затрачиваемая на собеседование и наем при использовании данного алгоритма найма работника. На первый взгляд может показаться, что анализ стоимости этого алгоритма очень сильно отличается, например, от анализа времени работы алгоритма сортировки методом слияния.
Однако оказывается, что при анализе стоимости и времени выполнения применяются одинаковые аналитические методы. В обоих случаях подсчитывается, сюлько раз выполняется та или иная операция. Обозначим стоимость собеседования через с;, а стоимость найма — через сы Пусть тп — количество нанятых сотрудников. Тогда полная стоимость, затраченная при работе этого алгоритма, равна 0 (пс, + гпса). Независимо от того, сюлько сотрудников было нанято, интервью нужно провести с п кандидатами, поэтому суммарная стоимость всех интервью является фиксированной и равна поь Таким образом, нас интересует анализ величины тсь — стоимости найма, которая, как нетрудно понять, меняется при каждом выполнении алгоритма.
Этот сценарий служит моделью распространенной вычислительной парадигмы. Часто встречаются ситуации, когда нужно найти максимальное или минимальное значение последовательности„для чего каждый ее элемент сравнивается с текущим "претендентом" на звание подходящего. Задача о найме моделирует частоту, с которой придется заново присваивать метку "победителя" текущему элементу. Часть !. Основы 142 Анализ наихудшего случая В наихудшем случае работодателю приходится нанимать каждого кандидата, с которым проведено собеседование. Эта ситуация возникает, когда кандидаты приходят в порядке возрастания их квалификации. При этом процедура найма повторяется п раз, а полная стоимость найма равна О (пса).
Однако маловероятно, чтобы кандидаты поступали в указанном порядке. Фактически мы не имеем представления о том, в каком порядке они будут приходить, и никак не можем повлиять на этот порядок. Таким образом, возникает закономерный вопрос, чего следует ожидать в типичном (или среднем) случае. Вероятностный анализ Вероятностный анализ — это анализ задачи, при котором используются вероятности тех или иных событий. Чаще всего он используется при определении времени работы алгоритма. Иногда такой анализ применяется и для оценки других величин, таких как стоимость найма в процедуре Н!ке Азз!атлет.
Для проведения вероятностного анализа необходимо располагать знаниями (или сделать предположение) о распределении входных данных. При этом в ходе анализа алгоритма вычисляется математическое ожидание времени его работы. На эту величину влияет распределение входных величин, поэтому производится усреднение времени работы по всем возможным входным данным. Делая предположение о распределении входных величин, нужно быть очень осторожным. В неюторых задачах такие предположения вполне оправданны и позволяют воспользоваться вероятностным анализом как методом разработки эффективных алгоритмов и как средством для более глубокого понимания задачи.
В других задачах разумное описание распределения входных величин не удается, и в таких случаях вероятностный анализ неприменим. В задаче о найме сотрудника можно предположить, что претенденты приходят на собеседование в случайном порядке. Что это означает в контексте рассматриваемой задачи? Предполагается, что любых двух кандидатов можно сравнить и решить, кто из них квалифицированнее, т.е. в принципе всех кандидатов можно расположить в определенном порядке. (Определение полностью упорядоченных множеств приведено в приложении Б.) Таким образом, каждому кандидату можно присвоить уникальный порядковый номер от 1 до п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
