«Конкретная математика. Основание информатики» — книга Дональда Кнута, Роналда Грэхема и Орена Паташника по математике, рассматривающая математические основы информатики, особенно анализа алгоритмов. Вынесеный в заглавие книги термин конкретная математика произошёл от слияния двух других — КОНтинуальная и дисКРЕТНАЯ. Так подчёркивается, что в книге читателю представляется техника оперирования с дискретными объектами, сходная с традиционными методами математического анализа. Кроме того, конкретная математика противопоставляется традиционной абстрактной, в предисловии авторы замечают:

В книге содержится более 500 различных упражнений различного уровня сложности.

Прообразом книги послужил раздел «Математическое введение» из другого труда Д. Кнута «Искусство программирования».

В противоположность большинству «сухих» книг по математике, изложение ведётся в неформальном стиле и сопровождается «заметками на полях» (т. н. «граффити») от первых редакторов книги — студентов Стэнфорда.

Основные темы

• Суммы
• Рекуррентность
• Целочисленные функции
• Элементы теории чисел
• Биномиальные коэффициенты
• Специальные числа
• Производящие функции
• Дискретная вероятность
• Асимптотические методы

Интересные факты

• Книга набрана в ΤΕΧе шрифтом под названием Concrete Roman
• Дизайн обложки книги обыгрывает слово Concrete (бетон) и изображает бетонную стену с выдавленной в ней греческой буквой Σ

Литература

• Рональд Л. Грэхем, Дональд Э. Кнут, Орен Паташник Конкретная математика. Математические основы информатики = Concrete Mathematics: A Foundation for Computer Science. — 2-е. — М.: «Вильямс», 2009. — С. 784. — ISBN 978-5-8459-1588-7 (англ. 0-201-55802-5)
• Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний, 1998 - 2009. — С. 703. — ISBN 5-94774-560-7 (англ. 0-201-55802-5)