Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 269
Текст из файла (страница 269)
Например, таким способом можно получить границу 0(1я и) гармонического ряда (А.7): Идея заключается в разбиении диапазона от 1 до и на (18п) + 1 частей с ограничением каждой части единицей. 1-я часть (1 = О, 1,..., (18п)) состоит из членов, начинающихся с 1/2* и заканчивающихся членом 1/2*+' (исключая сам этот член). Последняя часть может содержать члены, не входящие в исходный гармо- )2 2 )2 ~~-' 2" ~~-' 2" и=о ь=о )сг <~' —, и=о = 0(1), ьг 2" ь=з 8~ (9) а=о Приложение А. Суммы и ряды !207 нический ряд, и, таким образом, имеем 2'+ 1 11яи) 2'-1 Е '.).
-,'. 1=0 1=0 (1я н) =О 1кп+ 1. 1 ~ — < й Ь=1 (А.10) (А. 11) Пояснение такой оценки показано на рис. А.1. На рисунке в прямоугольниках по- казаны их площади, а общая площадь прямоугольников представляет значение суммы. Когда Д(е) является монотонно убывающей функцией, можно использо- вать подобный метод для получения границ ~""1и)ю Елее~ Л*)л*. ял (А.12) Приближение интегралами (А.12) дает точную оценку и-го гармонического числа.
Нижнюю границу получаем как Ь=1 = 1п(п+ 1) (А.13) Чтобы получить верхнюю границу, воспользуемся неравенством Приближение интегралами Если сумма имеет вид ~,", )'(к), где )'(й) — монотонно возрастающая функция, можно оценить значение ряда с помощью интегралов: Часть РГП. Приложения: математические основы у(х) ! ,,сг "-*.;-".-- т -1 т т+1 т+2 и-2 н-1 л и+1 (ь) у (х) ;:у!',.;::, „.",;"",,':г! и-2 н-1 н и+1 ™ т -1 гн т+1 го+2 (6) которое даст границу 1 — < )пи+1 )с Ь=! (А. 14) Упражнении А.3.1 Покажите, что сумма 2 )", 1/)сз ограничена сверху константой. Рис.
А.1. Приблюкеыие ряда ~,", у()г) интегралами. В прямоугольниках показаны их площади, а общая вюшпдь прлмаугольнпкол представляет значение суммы. Интеграл представлен запприхоаанной областью под кривой. Сравнивая площади а части (а), получаем (", у(х) бх < г"()г), после чего, сдвигая прамаугольники на единицу апрзао, а части (б) получаем Е,"= У(/) <1""У(-)«- !209 Прилоясение А.
Суммы и ряды А.г.г Найдите асимптотическую верхнюю границу суммы Оя н) Е Г"/2"1 й=о А.2.3 Применив разбиение ряда, покажите, что и-е гармоническое число представляет собой Й(18п). А.2.4 Найдите приближенное значение 2 й, )сз с помощью интегралов. А.2.5 Почему для получения и-го гармонического числа мы не можем применить интегральное приближение (А.12) непосредственно к сумме 2 "й ! 1/к? Задачи А.1. Оценки сумм Дайте асимптотически точные оценки приведенных ниже сумм.
Считаем, что г > 0 и я > 0 представляют собой константы. а ~~г lс". ййп й ~ ~'18'й. й=1 lс 18 вс. й=! Заключительные замечания Книга Кнута (Кппгп) [208]' — отличное справочное пособие по изложенному здесь материалу. Основные свойства рядов можно найти во множестве книг, например в книге Апостола (Арой!о!) [18! или Томаса (ТЬощаз) и др. [332!. гннеегся русский перевод: Д. Кнуг. Искуссмво орогранмированшс т.
!. Основные алгорынмы, 3-е нгд.— мс и.д. "в ", зооо. Приложение Б. Множества и прочие художества Во многих главах этой книги нам приходилось сталкиваться с элементами дискретной математики. Здесь вы более подробно ознакомитесь с обозначениями, определениями и элементарными свойствами множеств, отношений, функций, графов и деревьев. Читатели, знакомые с этим материалом, могут пропустить данное приложение. Б.1.
Множества Множество (зе1) представляет собой набор различимых объектов, которые называются членами или элементами. Если объект х является членом множества 5, это записывается как х е 5 (читается "х принадлежит 5'*). Если х не принадлежит 5, записываем х ф 5. Множество можно описать путем явного перечисления его элементов в виде списка, заключенного в фигурные скобки. Например, можно определить множество 5 как содержащее числа 1, 2 и 3, и только их, записав 5 = (1, 2, 3). Поскольку 2 является элементом множества 5, можно записать 2 е 5, а так как 4 не является элементом 5, верна запись 4 ф 5.
Множество не может содержать один н тот же элемент дважды'; кроме того, элементы множества не упорядочены. Два множества, А и В, равны (что записывается как А = В), если они содержат одни и те же элементы. Например, (1, 2, 3) = (3, 2, 1). Для часто встречающихся множеств используются специальные обозначения. 6 обозначает ауснаое мнонсестео, т.е. множество, не содержащее ни одного элемента. д. обозначает множество целых чисел, те. множество (..., — 2, — 1, О, 1, 2,...). К обозначает множество действительных чисел. Модификация множества, которое может содержать несколько одииаковых элементов, иаэывается мульжммиотиестеои йло!тЫих )1П Приложение Б. )иножесяево и прочие «удожества Я обозначает множество иалзуральнмх чисел, те.
множество (1, 2,... )2. Если все элементы множества А содержатся в множестве В, т.е. из х е А вытекает х Е В, то мы записываем, что А С В, и говорим, что множество А является лодмнодгееством В. Множество А является истинным (собственным, строгим) лодмиооагесвавом (ргорег зпЬзе[) множества В (что записывается как А С В), если А С В, но А ~ В. (Многие авторы используют обозначение А С В не только для истинных подмножеств, но и для отношения обычного подмножества.) Для любого множества А справедливо А С А; для двух множеств, А и В, равенство А = В справедливо тогда и только тогда, когда А С В и В С А.
Для любых трех множеств, А, В и С, из А С В и В С С следует А С С. Для любого множества А справедливо соотношение 6 С А. Иногда множество определяется посредством другого множества. Так, для заданного мнвкества А, можно определить множество В С А, указав свойство, которым обладают элементы множества В.
Например, множество четных чисел можно определить следующим образом; (х: х е У и х/2 е Ж). Двоеточие в такой записи читается как "такой, что" (некоторые авторы вместо двоеточия используют вертикальную черту). Для двух заданных множеств, А и В, можно определить новые множества с помощью следующих операций над множествами. Пересечением множеств А и В является множество АПВ = (х: хе А их Е В) . Объединением множеств А и В является множество АОВ=(х:хе Аилихе В) Разностье множеств А и В является множество А — Вж(х:хеАихгрВ) . Операции над множествами обладают следующими свойствами. Свойства пустого множества: Аг)бж9, АО9= А. зв зарубежной литературе Гв частности, в американской) под натуральнымн числами подразумеваются числа (О, ),2,...).
Здесь мы придерживаемая принятого в отечественной математике понятия натуральных чисел. — Примеч, ри). 1г12 Чесма ГШ. 11риложенил матеиалмвеские основы Свойства ндемпотентности: АпА=А, АОА=А. Свойства коммутативности: АпВ=ВпА, АОВ = ВОА. Свойства ассониативности: А и (В и С) = (А и В) и С, А 0 (В и С) = (А О В) 0 С .
Своиства днстрибутивности: Ап(В ОС) = (АпВ) (.) (АпС), А(.) (ВпС) = (А(.) В) п(АОС) . (БА) Свойства поглощения: А и (А (.) В) = А, АО(АпВ) = А. Законы де Моргана: А — (ВпС) = (А — В) 0(А — С), А — (В (.) С) = (А — В) и (А — С) . (Б.2) А — (ВПС) = А — (ВПС) = (А — В) 0 (А — С) Рис. Б.1. Диаграмма пенна, игопостриругогпал первый закон де Моргана (Б.Д). Каждое ив множеств А, В и С представлено крутом. На рис. БЛ первый закон де Моргана проиллюстрирован с помощью диаграмм Бенно (тгепп Йабгаш), графического представления множеств в виде областей на плоскости. Зачастую исе рассматриваемые мнглкества являются подмножествами некоторого большего множества У, называемого универсумом (ппгтегве), илн генеральной совокупностью. Например, если мы работаем с различными множествами Приложение д Множества и лроние вудожесмеа целых чисел, то в качестве универсума можно рассматривать множество е'..
Для заданного универсума У можно определить дополнение (сошр!ешепг) множества А как А = У вЂ” А = (х: х е У и х ф А). Для любого множества А С У выполняются следующие соотношения: А=А, АпА=9, АОА=У. Можно переписать законы де Моргана (Б.2) с дополнениями множеств. Для лю- бых двух множеств В, С С У имеют место равенства ВПС = ВОС, В ОС = ВПС.
Два множества, А и В, являются иеиересекающимися (гйя)огпг), если они не имеют общих злементов, т.е. если А гг В = 9. Семейство Я = (Я,) непустых множеств образует разбиение (раг6ггоп) множества Я, если множества иоиарно не иересекаются, т.е. из Я„Я Е 8 и г ~ г следует Яг Гг Вз =9' ° их объединение равно Я, т.е. Другими словами, Я образует разбиение множества Я, если каждый элемент множества Я принадлежит ровно одному из множеств Яг Е 8. Количество злементов множества называется его мощностью (сатгйпайгу), или размером, и обозначается как Д. Два множества имеют одинаковую мощность, если между их злементами можно установить взаимно однозначное соответствие. Мощность пустого множества ~9~ = О. Если мощность множества представляет собой целое неотрицательное число, то такое множество называется конечным; в противном случае множество является бесконечным. Бесконечное множество, элементы которого могут быть поставлены во взаимно однозначное соответствие натуральным числам )Ч, называются счатиымн (соолгаЫу штшгге), в противном случае мы имеем дело с несчетными (ипсошпаЫу) множествами.
Множество целых чисел е', счетно, в то время как множество действительных чисел К вЂ” нет. Для любых двух конечных множеств, А и В, справедливо тождество )АОВ! = (А)+ )В( — (АПВ(, (Б.З) из которого следует неравенство )АОВ( < (А)+)В) . Чисти»711 Прилежеиил: математические ссиоеы Если А и В являются непересекающимися множествами, то ~А П В~ = О, и, таким образом, )А»» В~ = (А) + (В!. Если А С В, то (А) < )В!. Конечное множество из и элементов иногда называется еызлементньен. В англоязычной литературе одноэлементное множество имеет специальное название з1нфегоп, а подмножество из lс элементов иногда именуется »е-знЬзег.
Множество всех подмножеств множества Я, включая пустое подмножество и само множество Я, обозначается как 2~ и называется степенным мнапсестван (роюег зег) я. Например, 21'Л» = (й, (а), (Ь), (а, 6)). Мощность степенного множества конечного множества Я имеет мощность 2РО (см. упр. Б.1.5). Иногда мы сталкиваемся с множествоподобными структурами, элементы которых упорядочены. Упорядоченная пара (огс»егеб ра»г) состоит из двух элементов, а и Ь, обозначается как (а, 6) и формально может быть определена как множество (а, Ь) = (а, (а, 6)). Таким образом, упорядоченные пары (а, Ь) и (Ь, а) различны.
Декартово произведение (саггегйап ргодпсг) двух множеств, А и В, обозначается А х В и представляет собой множество всех упорядоченных пар, в которых первый элемент пары является элементом А, а второй — элементом В. Говоря более строго, А х В = ((а, Ь): а Е А и Ь Е В) . Например, (а, 6) х (а, Ь,с) = ((а,а),(а,Ь),(а,с),(Ь,а),(6,Ь),(Ь,с)). Если и А, и В являются конечными множествами, то мощность их декартова произведения равна )А х В! = )А) )В) (БА) Декартово произведение и множеств Аы Аз,..., А„представляет собой множество кортюкей из п элементов (л-пзр1ея) Аг х Аз х . х А„= ((аыаз,...,а„): а, Е А,, 1 = 1.2,...,п) мощность которого в случае, если все множества конечны, равна (Аг х Аз х х А„! = (Аг( )Аз(..)Аи( Мы обозначаем и-кратное декартово произведение единственного множества А на себя как множество А"=АхАх .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
