Алгоритмы - построение и анализ (1021735), страница 247
Текст из файла (страница 247)
обзор [1161), поиск разреженных разрезов (зратзе сщз) для использования в алгоритмах разбиения [1991, а также применение полуопределенного программирования [115]. Как упоминалось в заключительных замечаниях к главе 34, последние достижения в области вероятностно проверяемых доказательств позволяют найти нижние границы аппроксимируемости многих задач, в том числе некоторых из тех, которые рассматриваются в настоящей главе.
В дополнение к приведенным здесь ссылкам заметим, что глава из книги Ароры и Ланда (Ьши1) [221 содержит хорошее описание отношения между вероятностно проверяемыми доказательствами и степенью сложности приближенных алгоритмов решения различных задач. Введение Анализ алгоритмов требует использования серьезного математического аппарата. Иногда достаточно знаний из простейшего курса высшей математики, но зачастую используемые в данной книге математические концепции и методы могут оказаться новыми для вас. В части 1 мы уже познакомились с асимптотическимн обозначениями и решением рекуррентных соотношений; в этой части вы найдете ряд других математических концепций и методов, используемых при анализе алгоритмов.
Как упоминалось во введении к части 1, вы могли быть знакомы со многими рассматриваемыми здесь вопросами еще до того, как приступили к чтению данной книги, так что материал, поданный в приложениях, носит в первую очередь справочный характер. Тем не менее, здесь, как и в обычных главах, приведены упражнения и задачи, которые помогуг вам повысить свою квалификацию в рассматриваемых областях математики. В приложении А рассматриваются методы вычисления и оценки рядов, часто встречающихся при анализе тех или иных алгоритмов. Многие из приводимых здесь формул можно найти в различных учебниках по математике, но гораздо удобнее, когда все эти формулы собраны в одном месте. В приложении Б приведены основные определения и обозначения, используемые при работе с множествами, отношениями, функциями, графами и деревьями. В этом приложении вы также найдете некоторые основные свойства этих математических объектов.
Приложение В начинается с элементарных принципов комбинаторики — перестановок, сочетаний и т.п. Остальной материал приложения посвящен основам теории вероятности. Большинство алгоритмов в этой книге не требуют использования теории вероятности прн анализе, так что вы можете пропустить эту часть приложения. Вы сможете вернуться к нему позже, при желании детально разобраться с вероятностным анализом алгоритмов. В этом случае вы убедитесь, что данное приложение можно рассматривать и как хорошо организованный справочник. Часть ЧИ1. Приложения: математические основы 1192 А.1 Суммы и их свойства Для данной последовательности чисел аы аз,...
конечная сумма а1 + аз + + . + а„, где п — неотрицательное целое число, кратко записывается как ~ аь. а=1 Если и = О, значение суммы считается равным О. Значение конечного ряда всеща определено и не зависит от порядка слагаемых. Для данной последовательности чисел аы аз,... бесконечная сумма а1+ аз+ +... кратко записывается следующим образом: ,'~ аь, я=г что рассматривается как Ыпз ~ аь. а=1 Если данный предел не существует„ряд расходщася (йтегдез); в противном случае ряд сходилгся (соптегдез).
Члены сходящегося ряда не могут быть суммированы в произвольном порядке. Однако можно переставлять члены абсолютно сходящегося ряда, те. ряда ~,ь аь, для которого сходится также ряд ,'> ь 1 ~аь~. Линейность Для любого действительного числа с и любых конечных последовательностей ам аз,..., а„и Ьы Ьз,..., Ь„ ь и ть ~~> (саь+ Ьь) = с~~> аь+ ~~~ Ьь. /с=1 а=1 а=1 Свойство линейности справедливо также для бесконечных сходящихся рядов. Это свойство может использоваться при работе с суммами, в которые входят асимптотические обозначения. Например, и и , 'оу®)=е '„«,'у(~) а=1 а=1 В этом уравнении 9-обозначение в левой части применяется к переменной Й, а в правой — к и.
Аналогичные действия применимы и к бесконечным сходящимся рядам. Приложение А. Ряды 1193 Арифметическая прогрессия Сумма а=1+2+ ° ° ° +и я=1 называется арифметической лрогресскей и равна к = — п(п+ 1) = 1 а=1 =~( з) (А. 1) (А.2) Суммы квадратов и кубов Для сумм квадратов и кубов справедливы следующие формулы: п(п+ 1) (2п+ 1) б я=о ~~~йз п (п+ 1) а=о 4 (А.З) (А.4) Геометрическая прогрессия Для действительного х ф 1 сумма ,'~ х =1+х+х + +х" в=о называется геометрической прогрессией и равна я=о (А.5) 1 я=о (А.б) В случае бесконечного ряда и ~х~ < 1 получается бесконечно убывающая геомет- рическая прогрессия„сумма которой равна Часть Ч!!!.
Приложения: математические основы 1194 Гармонический ряд Для натурального и, и-е гармоническое число представляет собой 1 1 1,~". 1 Н„= 1+ — + — +. + — = ~ — = )пп+0(1). 2 3 и ~-,)с (А.7) (Мы докажем зто соотношение в разделе А.2.) Интегрирование и дифференцирование рядов Новые формулы могут быть получены путем интегрирования или дифференцирования приведенных выше формул. Например, дифференцируя обе части уравнения суммы бесконечной геометрической прогрессии (А.б) и умножая на х, мы получим для !х! < 1 lсхь = (1 — х) (А.8) Суммы разностей Для любой последовательности ао, аы..., а„справедливо соотношение ,') (аь — аь з) = а„— ао, 1-1 (А.9) ь-1 ,') (аь — аь+1) = ао — а„.
г=о В качестве примера такого ряда рассмотрим сумму ь-1 1 Ей(+ ) Поскольку каждый ее член можно записать как 1 1 1 !с (!с+ 1) !с й+ 1' мы получаем поскольку каждый из членов а1, аз,..., а„1 прибавляется и вычитается ровно один раз.
Такие ряды именуют телескопическими (!е!езсорез). Аналогично, Приложение А. Ряды 1195 Произведения Конечное произведение а|аз... а„может быть кратко записано следующим образом: и П оь. Если п = О, значение произведения считается равным 1. Мы можем преобразовать формулу с произведением в формулу с суммой при помощи тождества я п 1к П аь = ~ 15аь. а=1 ью1 Упражнения А.1-1. Найдите простое выражение для ~а~, (2й — 1). * А.1-2. Покажите, используя формулу для гармонического ряда, что 1/(2/с — 1) = 1п (~Я + 0 (1).
А.1-3. Покажите, что для О < )х) < 1 справедливо соотношение ~"~ с Йзх" = = х (1 + х)/(1 — х) . * А.1-4. Покажите, что ~~~ о (Й вЂ” 1) /2" = О. *А.1-5. Вычислите сумму 2 ~~, 1(27с+ 1) х~~. А.1-6. Используя свойство линейности суммирования, докажите, что ,'~ О(/ь(п)) = 0(~~> /ь(п)) . А.1-7. Вычислите произведение Пь 12. 4". * А.1-8. Вычислите произведение Пь з (1 — 1/Й ). А,2 Оценки сумм Имеется множество методов оценки величин сумм, которые описывают время работы того или иного алгоритма. Здесь мы рассмотрим толью наиболее распространенные из них. 1196 Часть Ч!П.
Приложения: математические основы Математическая индукция Основным путем для вычисления сумм рядов является метод математической индукции. В качестве примера докажем, что сумма арифметической прогрессии 2 "„, )с равна п (и + 1)/2. Можно легко убедиться, что эта формула верна для и = = 1. Сделаем предположение, что эта формула верна для некоторого и и докажем, что в этом случае она верна и для п + 1: ьЧ-1 и 1 1 ~~> Й = ~> )с+ (и+1) = — п(и+ 1) + (и+1) = — (и+1) (и+ 2). а=1 ь=з Математическая индукция может использоваться не толью для точных значений сумм, но и для того, чтобы показать корректность оценок. В качестве примера рассмотрим доказательство того, что сумма геометрической прогрессии 2 "„о Зь равна 0(З"). Точнее, докажем, что 2 ь 3" < сЗ" для некоторой константы с.
При и = О формула имеет вид 2 ь р 3" = 1 < с 1, что справедливо при с > 1. о Полагая, что граница верна для и, докажем ее справедливость для и+ 1. Имеем: и+1 и г1 Е 3" = ~~~ 3" + 3"+ < сЗ" + 3"+~ = — + — сЗ"+ < сЗ"+ 1,3 с) ь=о а=о что справедливо прн (1/3 + 1/с) < 1 или, что то же самое, при с > 3/2. Таким образом, ~ ,", 3" = 0 (3"), что и требовалось показать.
При использовании асимптотических обозначений для доказательства по индукции следует быть предельно внимательным и осторожным. Рассмотрим следуюшее "доказательство" того, что 2',,",, к = 0 (и). Очевидно, что 2 „', )с = 0(1). Исходя нз справедливости оценки для п, докажем ее для и+ 1: в+1 и ,'~ к=~~ )с+(и+1) = "0(п)+0(п+1) =0(п+1). ь=1 ь=1 Ошибка в том, что "константа", скрытая в 0(п), растет вместе с и, а значит, константой не является. Мы не смогли показать, что одна и та же константа работает для всех и.
Почленное сравнение Иногда можно получить неплохую верхнюю оценку ряда, заменив каждый его член ббльшим (иногда для этого можно воспользоваться наибольшим членом). Например, вот как можно оценить верхнюю границу арифметической прогрессии (А.1): ь ь 2 Приложение А. Ряды 1197 В общем случае аь < пат Е а=1 где аы,, = шахз<ь<„аь. Если ряд в действительности может быть ограничен геометрической прогрессией, можно получить более точную оценку его суммы.
Итак, пусть ряд 2 ~", о аь обладает тем свойством, что для всех й > О аь+з/аь < т, где О < т < 1 — неюторая константа. В таком случае, т.к. аь < аот, сумма ряда ограничивается сверху ь суммой бесконечной геометрической прогрессии: ~~> аь < ,'~ аот~ =ао~~ т~ =— 1 — т к=о к=О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
