Конкретная математика. Математические основы информатики, 2-е издание
Год издания: 2010
Автор: Грэхем Р.Л., Кнут Д.Э., Паташник О.
Издательство: Вильямс
ISBN: 978-5-8459-1588-7
Язык: Русский
Формат: PDF/DjVu
Качество: Отсканированные страницы (в Djvu: + распознанный текст)
Количество страниц: 784
Описание: Эта книга основана на одноименном курсе лекций, который ежегодно читается в Станфордском университете начиная с 1970 года. Каждый год его прослушивают около пятидесяти человек— студентов как средних, так и старших курсов, но в первую очередь дипломников (а многие из наших выпускников уже начали вводить такого рода курсы и в других местах). По-видимому, настала пора представить материалы курса более широкой аудитории (включая студентов младших курсов). Конкретная математика зарождалась в смутное и неспокойное десятилетие. В те бурные годы подвергалось сомнениям все, включая казавшиеся до этого незыблемыми ценности. Студенческие городки превращались в арены жарких баталий. Оспаривались сами учебные программы, и математика не могла быть исключением. Как раз в те годы Джон Хаммерсли (John Hammersley) написал свою полемическую статью "О снижении уровня математической подготовки в школах и университетах благодаря 'современной математике' и подобной ей жидкой интеллектуальной похлебке"; другие обеспокоенные математики даже задавались вопросом "А можно ли спасти математику?" Когда один из авторов этой книги (Д.Э.К.) задумал серию книг под названием Искусство программирования, то при написании первого тома он обнаружил, что в его арсенале отсутствуют самые важные инструменты. Математика, которую он изучал в колледже в качестве профильной дисциплины, разительно отличалась от той математики, которая требовалась для досконального, обоснованного понимания компьютерных программ. Поэтому он ввёл новый курс, содержащий материал, который хотел бы в свое время прослушать сам.
Оглавление
Рекуррентные задачи
Ханойская башня
Прямые на плоскости
Задача Иосифа Флавия
Упражнения
Суммы
Обозначения
Суммы и рекуррентности
Преобразование сумм
Кратные суммы
Общие методы
Исчисление конечного и бесконечного
Бесконечные суммы
Упражнения
Целочисленные функции
Полы и потолки
Применения пола и потолка
Рекуррентности с полом и потолком
'mod': бинарная операция
Суммы с полами и потолками
Упражнения
Теория чисел
Делимость
Простые числа
Простые примеры простых чисел
Факториальные факты
Взаимная простота
'mod': отношение сравнимости по модулю
Независимые остатки
Дополнительные приложения
Фи и мю
Упражнения
Биномиальные коэффициенты
Основные тождества
Необходимые навыки
Специальные приемы
Производящие функции
Гипергеометрические функции
Гипергеометрические преобразования
Частичные гипергеометрические суммы
Механическое суммирование
Упражнения
Специальные числа
Числа Стирлинга
Числа Эйлера
Гармонические числа
Гармоническое суммирование
Числа Бернулли
Числа Фибоначчи
Континуанты
Упражнения
Производящие функции
Теория домино и размен
Основные манипуляции
Решение рекуррентных соотношений
Специальные производящие функции
Свертки
Экспоненциальные производящие функции
Производящие функции Дирихле
Упражнения
Дискретная вероятность
Определения
Математическое ожидание и дисперсия
Вероятностные производящие функции
Бросание монет
Хеширование
Упражнения
Асимптотика
Иерархия
О-обозначения
Работа с О
Два асимптотических приема
Формула суммирования Эйлера
Завершающее суммирование
Упражнения
Ответы к упражнениям
Библиография
Первоисточники упражнений
Предметный указатель
Список таблиц
