РЕЦЕНЗИИ
Андерсон Дж. Дискретная математика и комбинаторика. Пер. с англ. М.: ИД "Вильямс", 2003. - 960 с.
Интерес к дискретной математике непрерывно растет в связи с развитием цифровой техники, дискретным представлением информации и широким использованием дискретных моделей в биологии, экономике, геологии и других науках.
Первое время после выделения понятия "дискретная математика" к ней в основном относили вопросы, связанные с дискретными управляющими системами: булевы и многозначные дискретные функции, кодирование, схемы, автоматы, а также графы. Однако и в уже сформировавшихся областях математики (теории множеств, математической логике, теории чисел, теории вероятностей, алгебре) имелись большие разделы дискретного характера. Поэтому появилась тенденция - расширять понятие "дискретная математика", и вопрос о предмете этой науки трактуется разными авторами по-разному.
В рецензируемой книге Джеймса Андерсона, с одной стороны, принята, пожалуй, самая широкая трактовка термина "дискретная математика": в книгу включены разделы из теории множеств, логики, теории графов, теории чисел, теории вероятностей, алгебры, теории кодирования, теории вычислений и алгоритмов. Только комбинаторику автор счел необходимым выделить. С другой стороны, в книге отсутствует стандартное для дискретной математики определение многозначной дискретной функции. Нет в ней также и строгой модели общего понятия алгоритма (например, машины Тьюринга или частично-рекурсивной функции). Последнее следует отнести к недостаткам, хотя Андерсон, по-видимому, счел это понятие слишком сложным для читателей, поскольку книга ориентирована на студентов технических вузов.
Цель книги - познакомить студентов с широким кругом тем, которые автор относит к дискретной математике, рассмотреть некоторые важные утверждения, связанные с ними, привести примеры методов и алгоритмов для решения ряда задач. Книга объемом 950 стр. содержит больше примеров и пояснений, чем доказательств. А доказательства даются в основном не для очень сложных утверждений, ставших уже классическими.
Указанные выше разделы в книге разбиты на части, которые перемешаны с учетом их взаимосвязей и сложности. Так, вопросы математической логики, теории доказательств и теории вычислений представлены в главах 1 "Таблицы истинности, логика, доказательства", 3 "Логика, целые числа и доказательства", 17 "Теория вычислений". В них рассмотрены исчисление высказываний, исчисление предикатов, математическая индукция, коммутационные схемы, автоматы, грамматики. Для булевых функций затронуты вопросы их представления в виде дизъюнктивных и конъюнктивных нормальных форм, упрощения этих форм. К сожалению, изложение здесь ведется в основном на языке логики. Поэтому не представлена общая теория булевых функций, другие формы их представления (полиномы Жегалкина), нет теоремы Поста о полноте.
Основам теории множеств посвящены главы 2 "Теория множеств" и 4 "Функции и матрицы". Специальные алгебраические структуры (булевы алгебры, частично упорядоченные множества, матрицы, полугруппы, полурешетки, решетки, группы, кольца, алгебры, комплексные числа, характеры) разбираются в главах 2, 4, а также 9 "Алгебраические структуры", 20 "Кольца, области целостности и поля", 21 "Характеры групп и полугрупп".
Большое внимание уделено теории чисел: главы 3, 5 "Алгоритмы и рекурсия", 7 "Теория чисел", 10 "Некоторые специальные вопросы теории чисел". Здесь кроме стандартных вопросов делимости и представления целых чисел рассматриваются решение линейных уравнений в целых числах, решение сравнений, цепные дроби. В главе 22 "Приложения теории чисел" описано применение теории чисел к проблемам поиска, хеширования, криптографии.
Много места в книге отведено комбинаторике. Если в главе 8 "Комбинаторика и вероятность" приведены основные комбинаторные объекты, то в главах 12 "Снова о комбинаторных подсчетах", 13 "Производящие функции" и 19 "Перечисление цветов" представлены основные методы подсчета комбинаторных объектов. В последней, в частности, излагаются теоремы Бернсайда (с доказательством) и Пойа (без доказательства). В главе 8 также рассмотрено определение вероятности (дискретное), приведены примеры, излагается теорема Байеса и цепи Маркова. Подробно разобраны графы: главы 6 "Графы, ориентированные графы и деревья", 14 "Некоторые специальные вопросы теории графов", 15 "Деревья", 16 "Сети". В основном здесь читателей знакомят со стандартными вопросами теории графов (деревья, эйлеровы и гамильтоновы циклы, планарные графы, раскраски графов, кратчайшие пути, минимальные остовные деревья, потоки в сетях, паросочетания). Но включены и такие специфические вопросы, как гиперкубы и коды Грея (раздел 6.7) и сети Петри (раздел 16.3).
Небольшая глава 18 посвящена теории кодирования. В ней рассмотрены коды, исправляющие ошибки (коды Хэмминга и общие линейные коды). К сожалению, автор совсем не затрагивает вопросы взаимной однозначности произвольных кодирований и построения оптимальных кодов.
Важными для студентов-прикладников являются проблемы построения быстрых алгоритмов на дискретных структурах, которые представлены в главах 5, 11 "Некоторые специальные вопросы теории рекурсии", 16, а также в некоторых разделах других глав: 7.3 "Алгоритмы деления и алгоритм Евклида", 10.2 "Решение сравнений", 14.5 "Взвешенные графы и алгоритмы поиска кратчайшего пути", 15.4 "Обход бинарных деревьев", 15.6 "Минимальные остовые деревья".
Книга хорошо написана и содержит много примеров, что позволяет освоить материал неподготовленному читателю, никаких предварительных знаний (кроме знаний школьной математики) для ее чтения не требуется. К достоинствам данного издания следует отнести также большое число упражнений. Об их количестве можно судить по тому, что только ответы к упражнениям занимают 85 страниц.
Книга может служить хорошим учебным пособием как для самообразования, так и для преподавания различных разделов дискретной математики в широком понимании.
