Конкретная математика. Основание информатики. Р. Грэхем, Д. Кнут, О. Паташник

Пер. с англ. —М.: Мир, 1998. —703 с.

Название этой оригинальной как по содержанию, так и по форме книги знаменитых американских математиков можно расшифровать как КОНтинуальная и дисКРЕТНАЯ математика. Прообразом книги послужил раздел „Математическое введение" первого тома фундаментальной монографии Д. Кнута „Искусство программирования для ЭВМ" (М.: Мир, 1976). Ее назначение — дать читателю технику оперирования с дискретными объектами, аналогичную технике для непрерывных объектов. Название книги можно понимать и буквально — обучение общим методам ведется на многочисленных конкретных примерах и упражнениях разной степени сложности. Все упражнения снабжены ответами.

Настоящая книга представляет собой попытку учебного изложения ряда действительно фундаментальных математических фактов. Издание ориентировано на потребителя, хотя и теоретики, несомненно, найдут в нем много полезного. Очевидная неполнота курса, отражающая личные вкусы авторов, является скорее достоинством, чем недостатком.

Книгу, без сомнения, можно рекомендовать всем работающим математикам и всем студентам и пользователям математики. Она раскрывает тайну одного феномена американского образования — как превращать малограмотных школьников в прекрасных математиков.

Формат: djvu

Размер: 8,8 Мб

Скачать: drive.google

Из предисловия:

В ОСНОВУ ЭТОЙ КНИГИ положен одноименный курс лекций, который ежегодно читается в Станфордском университете, начиная с 1970 года. Каждый год его слушателями становятся около пятидесяти человек — студентов предпоследнего и последнего курсов, но, в основном, дипломников,—а ряд наших выпускников уже начал насаждать подобные курсы и в других местах. Так что настала, видимо, пора ознакомить с материалами курса более широкую аудиторию (включая младшекурсников).

На первый взгляд, содержание конкретной математики может показаться беспорядочным нагромождением уловок, но на деле — это упорядоченный набор инструментов. Более того, методы конкретной математики обладают не только внутренним единством, но и внешней привлекательностью. Когда другой автор этой книги (Р. Л. Г.) впервые прочитал данный курс в 1979г., студенты пришли в такой восторг, что договорились продлить это удовольствие на следующий год.

Но что же в действительности представляет собой КОНКРЕТНАЯ математика? Это смесь континуальной и ДИСКРЕТНОЙ математики. Еще более конкретно: это осмысленное оперирование математическими формулами с использованием определенного набора методов решения задач. После того как вы, читатель, изучите материал этой книги, все, что вам потребуется,—это ясная голова, большой лист бумаги и сносный почерк для вычисления ужасных сумм, решения запутанных рекуррентных соотношений и выявления коварных закономерностей в данных. Вы овладеете алгебраической техникой в такой степени, что зачастую вам будет проще получить точные результаты, нежели удовлетвориться приближенными ответами, которые справедливы лишь в пределе.

Исчисление сумм, рекуррентные соотношения, элементарная теория чисел, биномиальные коэффициенты, производящие функции, дискретная теория вероятностей и асимптотические методы — вот наиболее важные темы этой книги. При этом предпочтение отдается технической стороне дела, а не теоремам существования или комбинаторным рассуждениям: наша цель состоит в том, чтобы сделать каждого читателя настолько осведомленным в дискретных операциях (типа вычисления функции „наибольшего целого" или конечной суммы), насколько изучающие анализ знакомы с непрерывными операциями (типа вычисления функции „абсолютной величины" или определенного интеграла).

Заметим, что этот перечень тем совершенно отличается от того, что в наши дни обычно читается в качестве спецкурсов под названием „Дискретная математика" Поэтому наш предмет нуждается в отличительном наименовании, и название „Конкретная математика", право, не хуже любого другого.

Первоначальным руководством по конкретной математике для станфордского курса служил раздел „Математическое введение" из Искусства программирования для ЭВМ [139]. Но изложение на тех 110 страницах было слишком сжатым, поэтому еще один автор книги (О. П.) загорелся желанием составить длинный ряд дополнений. Настоящая книга выросла на их почве: она одновременно предваряет и дополняет материал „Математического введения" Некоторые вопросы повышенной сложности были опущены; в то же время в книгу включено несколько тем, которых не было раньше и без которых изложение было бы неполным.

Поскольку книга родилась в университетской среде, мы попытались передать дух аудитории наших дней, выбрав неформальный стиль изложения. Есть люди, полагающие, что математика—это нудное занятие, которое всегда уныло и скучно; мы же находим математику развлечением и не стыдимся признаться в этом. К чему проводить четкую грань между делом и игрой? Конкретная математика полна тому примеров: действия не всегда доставляют удовольствие, но результаты могут быть удивительно приятны. Радости и горести математической работы явно присутствуют в этой книге, поскольку являют собой части нашего бытия.

СОДЕРЖАНИЕ
От Фибоначчи до Эрдёша 7
Предисловие 8
К русскому изданию 14
Значения обозначений 15
1 Возвратные задачи 17
1.1 Задача о ханойской башне 17
1.2 Задача о разрезании пиццы 21
1.3 Задача Иосифа Флавия 25

Упражнения 34
2 Исчисление сумм 39
2.1 Обозначения сумм 39
2.2 Суммы и рекуррентности 43
2.3 Преобразование сумм 48
2.4 Кратные суммы 52
2.5 Общие методы суммирования 60
2.6 Исчисление конечного и бесконечного 66
2.7 Бесконечные суммы 76 Упражнения 83
3 Целочисленные функции 88
3.1 Пол/потолок: определения 88
3.2 Пол/потолок: применения 91
3.3 Пол/потолок: рекуррентности 101
3.4 'mod': бинарная операция 104
3.5 Пол/потолок: суммы 108

Упражнения 117
4 Элементы теории чисел 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
5 Биномиальные коэффициенты 178
5.1 Основные тождества 178
5.2 Необходимые навыки 199
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

О том, как читать книги в форматах pdf, djvu - см. раздел "Программы; архиваторы; форматы pdf, djvu и др."