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

2-e изд. — М.: Вильямс, 2010. — 786 c. — ISBN: 9785845915997.Эта книга основана на одноименном курсе лекций, который ежегодно читается в Станфордском университете начиная с 1970 года. Каждый год его прослушивают около пятидесяти человек— студентов как средних, так и старших курсов, но в первую очередь дипломников (а многие из наших выпускников уже начали вводить такого рода курсы и в других местах). По-видимому, настала пора представить материалы курса более широкой аудитории (включая студентов младших курсов).
Конкретная математика зарождалась в смутное и неспокойное десятилетие. В те бурные годы подвергалось сомнениям все, включая казавшиеся до этого незыблемыми ценности.Рекуррентные задачи
Ханойская башня
Прямые на плоскости
Задача Иосифа Флавия
УпражненияСуммы
Обозначения
Суммы и рекуррентности
Преобразование сумм
Кратные суммы
Общие методы
Исчисление конечного и бесконечного
Бесконечные суммы
УпражненияЦелочисленные функции
Полы и потолки
Применения пола и потолка
Рекуррентности с полом и потолком
'mod': бинарная операция
Суммы с полами и потолками
УпражненияТеория чисел
Делимость
Простые числа
Простые примеры простых чисел
Факториальные факты
Взаимная простота
'mod': отношение сравнимости по модулю
Независимые остатки
Дополнительные приложения
Фи и мю
УпражненияБиномиальные коэффициенты
Основные тождества
Необходимые навыки
Специальные приемы
Производящие функции
Гипергеометрические функции
Гипергеометрические преобразования
Частичные гипергеометрические суммы
Механическое суммирование
УпражненияСпециальные числа
Числа Стирлинга
Числа Эйлера
Гармонические числа
Гармоническое суммирование
Числа Бернулли
Числа Фибоначчи
Континуанты
УпражненияПроизводящие функции
Теория домино и размен
Основные манипуляции
Решение рекуррентных соотношений
Специальные производящие функции
Свертки
Экспоненциальные производящие функции
Производящие функции Дирихле
УпражненияДискретная вероятность
Определения
Математическое ожидание и дисперсия
Вероятностные производящие функции
Бросание монет
Хеширование
УпражненияАсимптотика
Иерархия
О-обозначения
Работа с О
Два асимптотических приема
Формула суммирования Эйлера
Завершающее суммирование
УпражненияОтветы к упражнениям
Библиография
Первоисточники упражнений
Предметный указатель
Список таблиц