5 книг о комбинаторике

Математик Александр Дайняк рекомендует пять книг для знакомства с разными гранями современной комбинаторики

1

Н.Я. Виленкин, «Комбинаторика»

Первое издание этой книги, адресованной интересующимся старшеклассникам, вышло еще в 1969 году за единоличным авторством Наума Яковлевича Виленкина. Самое свежее на настоящий момент издание, вышедшее в 2017-м, имеет уже трёх авторов, принадлежащих трём разным поколениям: к Н.Я. Виленкину присоединились А.Н. Виленкин и П.А. Виленкин. То же верно и в отношении читателей этой книги: уже не для одного поколения школьников это один из основных учебников по комбинаторике. Эта книга остаётся до сих пор беспроигрышной рекомендацией ребятам, которым интересно продвинуться дальше того не слишком обширного круга вопросов комбинаторики, который входит в обязательную школьную программу. Несомненные достоинства книги: разумный темп подачи материала на примерах и с обсуждениями, достойный набор задач для закрепления материала. Всё то, что мы ожидаем увидеть в хорошей школьной книге для внеклассного чтения.

Математика, развиваясь на протяжении многих веков, стала необозримой для одного человека. Хотя комбинаторика является относительно молодой областью математики, но и она разрослась настолько, что сегодня говорят о разных «комбинаториках»: алгебраической, экстремальной, аналитической и так далее. Перечисленные ниже книги, рассчитанные на студентов и исследователей, позволяют ознакомиться с разными, но одинаково ярко сверкающими гранями современной комбинаторики.

2

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

Название книги имеет двойное толкование. С одной стороны, оно противопоставляет предмет книги «абстрактной» математике. Подобное противопоставление чаще звучит как «чистая или прикладная математика». Поскольку авторы книги — специалисты в области информатики, то и материал, включаемый в книгу, представляет те разделы математики, которые особенно богаты на приложения в информатике. Об этом говорит и подзаголовок книги: «основания информатики». Второй вариант толкования слова «конкретная» в названии книги — комбинация слов континуальная (непрерывная) и дискретная — пожалуй, даже больше подходит к содержанию книги. Понятие непрерывности является центральным в математическом анализе, цикл которого входит едва ли не в каждую естественно-научную или инженерную программу современного университета. В противоположность областям математики, работающим с «непрерывными» объектами, выделяется дискретная математика — та часть математики, которая понятием непрерывности не пользуется. С точки зрения профессиональных математиков, это противопоставление достаточно условное. Очень часто методы из «непрерывных» областей находят применение в «дискретных», да и наоборот, не является ли самой сутью математического анализа приручение «настоящей бесконечности» за счёт сведения её к конечным (дискретным) последовательностям! «Конкретная математика» на хорошем уровне знакомит читателя с инструментами высшей математики, которые особенно полезны для анализа алгоритмов. Чтение этой книги можно сравнить с прохождением обряда инициации — переходом от школьного уровня понимания комбинаторики как науки о подсчёте количеств к «взрослой комбинаторике», в которой не гнушаются ни повсеместным применением операторов суммирования, ни асимптотическими переходами, ни рассмотрением специальных функций. Авторы постарались, чтобы этот обряд инициации не был простым, включив в книгу множество задач для проработки. Однако, будучи требовательной к читателю, эта книга всё же будет вполне доступна младшекурсникам технических вузов, а после её прочтения вряд ли захочется делить математику на «континуальную» и «дискретную» или тем более на «комбинаторику и не-комбинаторику».

3

Н. Алон, Дж. Спенсер, «Вероятностный метод»

Если нужно было бы назвать лишь один метод, дающий наибольшую силу исследователю в области современной комбинаторики, то это, пожалуй, именно вероятностный метод. Правильнее даже было бы говорить не об одном методе, а о целой россыпи приёмов, связанных с применением вероятностного мышления в комбинаторике. Базовый приём можно было бы описать так: «Если вам нужен обладающий какими-то специфическими свойствами объект, постройте его случайным образом, и с хорошей вероятностью он как раз окажется таким, как требуется». Конечно, часто всё оказывается не так просто, но даже указанный рецепт на удивление плодотворен. Иногда стоявшие десятилетиями проблемы поддавались решению таким образом. В книге Алона и Спенсера приводится множество ярких примеров, когда использование вероятностных подходов приводит к красивым результатам и лаконичным доказательствам в комбинаторике. В первую очередь эта книга предназначена для тех, кто собирается профессионально работать в дискретной математике и комбинаторике, однако даже тем, кто воспринимает комбинаторику и дискретную математику в целом лишь как шаг на пути к изучению алгоритмов, книгу можно порекомендовать, поскольку мимо понятия «вероятностного алгоритма» сложно пройти, изучая современную информатику.

4

P. Flajolet, R. Sedgewick, «Analytic Combinatorics»

Вероятностный метод работает тогда, когда задача может быть сведена к вопросу о существовании какой-то конфигурации. А как быть в случае, когда нужно именно точное количество конфигураций? Здесь одним из классических инструментов являются производящие функции. На самом деле многими комбинаторщиками-исследователями XX века словосочетание «классическая комбинаторика» воспринималось почти синонимичным «методу производящих функций». Если вероятностный метод обрушивает на трудные комбинаторные задачи мощь теории вероятностей, то книга “Analytic combinatorics” научит воевать со строптивыми задачами при помощи методов комплексного анализа, теории матриц и других классических разделов математики.

5

S. Jukna, «Extremal combinatorics. With applications in computer science»

Название «экстремальная комбинаторика» объясняется тем, что этот раздел комбинаторики изучает методы нахождения экстремальных (наибольших или наименьших) значений параметров комбинаторных объектов. Книга С. Юкны предназначена для студентов и специалистов в теоретической информатике, которые хотели бы ознакомиться с важными результатами из экстремальной комбинаторики, многие из которых находят применение в построении и анализе алгоритмов и вычислительных моделей. Круг тем, представленных в книге, довольно разнообразен, а требования к читателю, пожалуй, меньше, чем у книг Алона — Спенсера и Флажоле — Седжвика, так что книга хорошо подойдёт в качестве источника материала для спецкурса для бакалавров. В книге затронуты и некоторые темы, не относящиеся, на мой взгляд, непосредственно к экстремальной комбинаторике: например, есть главы о вероятностном методе, о теории Рамсея, линейно-алгебраических методах. Книга является во многом самодостаточным экскурсом в современную комбинаторику, граничащую с информатикой, и наряду с книгой Грэхема — Кнута — Паташника является хорошей рекомендацией для тех младшекурсников, которые ещё не решили, хотят они больше стать специалистами в дискретной математике или в computer science или желают подольше задержаться на границе этих двух миров, любуясь лучшими жемчужинами из них обоих.

Источник: postnauka.ru

Комментарии: