Читать онлайн «Конкретная математика. Математические основы информатики»

Р. Грэхем, Д. Кнут, О. Паташник КОНКРЕТНАЯ МАТЕМАТИК А Основание информатики Перевод с английского \В. В. Походзея\ и А. В. Ходулёва под редакцией А. В. Ходулёва МОСКВА «МИР» 1 CONCRETE MATHEMATICS A Foundation for Computer Science Second Edition This printing incorporates the final corrections made in 1998 Ronald L. Graham AT&T Bell Laboratories Donald E. Б. Походзей| (предисловие, значения обозначе- обозначений, гл. 1-6, приложения А, С), А. Б. Ходулёв (гл. 7-9, приложе- приложения А, С) Грэхем Р. , Кнут Д. , ПаташникО. Г75 Конкретная математика. Основание информатики: Пер. с англ. — М. : Мир, 1998. —703 с, ил. ISBN 5-03-001793-3 Название этой оригинальной как по содержанию, так и по форме книги знаменитых американских математиков можно расшифровать как КОНти- нуальная и дисКРВТНАЯ математика. Прообразом книги послужил раз- раздел „Математическое введение" первого тома фундаментальной моногра- монографии Д. Кнута „Искусство программирования для ЭВМ" (М. : Мир, 1976). Бе назначение — дать читателю технику оперирования с дискретными объ- объектами, аналогичную технике для непрерывных объектов. Название книги можно понимать и буквально — обучение общим методам ведется на много- многочисленных конкретных примерах и упражнениях разной степени сложно- сложности. Все упражнения снабжены ответами. При переводе на русский язык учтены исправления авторов 1998 года. Книгу, без сомнения, можно рекомендовать всем изучающим и применя- применяющим дискретную математику и информатику. Она раскрывает тайну одно- одного феномена американского образования — как превращать малограмотных школьников в прекрасных математиков. ББК 22. 19 Издание осуществлено при поддержке Российского фонда фундаментальных исследований по проекту № 97-01-14010 Редакция литературы по математическим наукам ISBN 5-03-001793-3 (русск. ) ISBN 0-201-55802-5 (англ. ) © 1994, 1989 by Addison-Wes! Company, Inc. © перевод, jB. В. Походзей|, А. В. Ходулёв, 1998 © оформление, «Мир», 1998 Оглавление От Фибоначчи до Эрдёша 7 Предисловие 8 К русскому изданию 14 Значения обозначений 15 Возвратные задачи 17 1. 1 Задача о ханойской башне 17 1. 2 Задача о разрезании пиццы 21 1. 3 Задача Иосифа Флавия 25 Упражнения 34 Исчисление сумм 39 2. 1 Обозначения сумм 39 2. 2 Суммы и рекуррентности 43 2. 3 Преобразование сумм 48 2. 4 Кратные суммы 52 2. 5 Общие методы суммирования 60 2. 6 Исчисление конечного и бесконечного 66 2. 7 Бесконечные суммы 76 Упражнения 83 Целочисленные функции 88 3. 1 Пол/потолок: определения 88 3. 2 Пол/потолок: применения 91 3. 3 Пол/потолок: рекуррентности 101 3. 4 'mod': бинарная операция 104 3. 5 Пол/потолок: суммы 108 Упражнения 117 Элементы теории чисел 125 4. 1 Отношение делимости 125 4. 2 Простые числа 129 4. 3 Простые примеры 131 4. 4 Факториальные факты 135 4. 5 Взаимная простота 139 4. 6 Отношение сравнимости 148 4. 7 Независимые остатки 151 4. 8 Дополнительные примеры 154 4. 9 Фи- и мю-функции 157 Упражнения 169 Биномиальные коэффициенты 178 5. 1 Основные тождества 178 5. 2 Необходимые навыки 199 6 ОГЛАВЛЕНИЕ 5. 3 Специальные приемы 213 5. 4 Производящие функции 224 5. 5 Гипергеометрические функции 232 5. 6 Гипергеометрические преобразования 245 5. 7 Частичные гипергеометрические суммы 252 5. 7 Механическое суммирование 259 Упражнения 271 6 Специальные числа 287 6. 1 Числа Стирлинга 287 6. 2 Числа Эйлера 297 6. 3 Гармонические числа 303 6. 4 Гармоническое суммирование 309 6. 5 Числа Бернулли 313 6. 6 Числа Фибоначчи 322 6. 7 Континуанты 333 Упражнения 341 7 Производящие функции 353 7. 1 Теория домино и размен 353 7. 2 Основные маневры 364 7. 3 Решение рекуррентных соотношений 371 7. 4 Специальные производящие функции 385 7. 5 Свертки 387 7. 6 Экспоненциальные производящие функции 399 7. 7 Производящие функции Дирихле 405 Упражнения 407 8 Дискретная вероятность 418 8. 1 Определения 418 8. 2 Математическое ожидание и дисперсия 424 8. 3 Производящие функции случайных величин 432 8. 4 Бросание монеты 438 8. 5 Хеширование 448 Упражнения 464 9 Асимптотика 477 9. 1 Иерархия 478 9. 2 Символ О 481 9. 3 Операции с О 488 9. 4 Два асимптотических приема 502 9. 5 Формула суммирования Эйлера 508 9. 6 Завершающее суммирование 515 Упражнения 529 А Ответы к упражнениям 537 В Список литературы 651 С Первоисточники упражнений 684 Указатели 689 Именной указатель 689 Предметный указатель 695 Указатель таблиц 703 От Фибоначчи до Эрдёша ТЕРМИН CONCRETE (означающий также „бетонный") образо- образован слиянием слов cONtinous и disCRETE.