Этот учебник написан Сюзанной Эпп(Susanna S. Epp) в 2010 году.
Когда я искал себе книгу по дискретной математике, чтобы подтянуть то, что было безвозвратно утеряно(или не было приобретено) со времени студенчества, мой выбор пал именно на иностранный учебник. Выбор мой был обусловлен следующими причинами: на мой взгляд западные учебники лучше адаптированы под самостоятельное обучение, в то время как наши лучше всего подходят именно для занятий с преподавателем. Они, банально, - проще.
Второй причиной является объем охватываемого материала – я не видел нашего учебника в котором бы рассматривался столько широкий набор тем, как зачастую бывает в зарубежных учебниках. Discrete Mathematics with Applications не является в этом плане исключением – в одном учебнике рассмотрено действительно много различных тем, что позволяет охватить довольно много различных тем сразу. Давайте посмотрим, что за темы затрагиваются в книге.
Книга начинается с рассмотрение такой большой темы как, логика. Ей посвящено две части и, на мой взгляд, это наиболее подробно рассмотренная тема книги. Помимо теории, в виде основ булевой логики, утверждений и предикатов приводится несколько приложений логики к бренному, программистскому миру. К примеру, есть глава которая описывает связь логических схем с, собственно, булевой логикой. Вообще, приземленность описываемого материала является, на мой взгляд, одной из сильнейших черт данного учебника. Так, все темы описанные в книги содержат примеры, которые связывают теорию с применением в реальном мире.
Освоив логику книга предлагает нам ознакомится с различными способами доказательств теорем и не только. Все темы посвящённые различным доказательствам существуют не в вакууме, а тесно переплетены с теорией чисел. По окончании рассмотрения методик доказательств книга подводит нас к алгоритмам, показывая, что же является алгоритмом и как понимать и писать оные.
После чего мы переходим к краткому рассмотрению последовательностей, которые являются базисом для следующей важной темы – математической индукции. Математическая индукция обозревается на протяжение 3-х глав и, на мой взгляд, она рассмотрена со всех возможных сторон. Применение математической индукции приводится тут же – доказательство корректности алгоритма. Итак, к настоящему моменту мы уже можем составить алгоритм и проверить его корректность, осталось только понять как сравнивать разные алгоритмы, которые посвящены решению одной и той же задач. Данная часть книги оканчивается описанием рекурсии, рекуррентных уравнений и тем, как применять математическую индукцию к рекуррентным алгоритмам.
Следующей большой темой являются множества, функции и отношения: рассматриваются их свойства и то, как они между собой связаны. Конечно, рассмотреть всю теорию множеств в рамках одной-двух частей не предоставляется возможным, на мой взгляд. Всё же то, что есть в книге является базовым минимумом для работы с множествами. Если говорить об отношениях, то рассматриваются следующие темы: отношения на множествах, отношение эквивалентности, а также отношение частичного порядка. Всё это составляет фундамент реляционной алгебры, которая является краеугольным камнем баз данных.
Покончить с множествами не удается и в следующей части, т.к. следующая тема так же их затрагивает. Следующей темой является комбинаторика и теория вероятностей. Этой большой теме посвящено аж 9 глав, но вы же понимаете, что это ничто по сравнение с тем, сколько эти темы заслуживают. Тем не менее основы даются довольно хорошо и данная часть не выглядит чересчур поверхностной. Разумеется, всё что описано в этой части сдобрено довольно большим количеством примеров, как это всё использовать в повседневной жизни программиста.
Далее книга предлагает нам окунуться в теорию графов и посмотреть, что это и с чем это едят. Тут рассматриваются азы графов: что это такое, циклы, пути, деревья, графическое и матричное представление графов, а также, что имеют общего Эйлер и Гамильтон с теорией графов.
В понимании алгоритмов нам не хватало только одного – анализа эффективности, критерия по которому можно сравнить разные алгоритмы. И ему посвящены следующие 5 глав. В данной книге приведено наиболее полное и всестороннее объяснение того, как в современном мире принято оценивать эффективность различных алгоритмов, из тех, что я видел. Так, что если у вас возникают проблемы с пониманием сложности алгоритмов – эти главы для вас.
Завершает книгу краткий обзор конечных автоматов и как они связаны с регулярными выражениями.
Что хотелось бы сказать о книге в целом: она представляет собой довольно краткий обзор широко перечня тем, с которыми, так или иначе, программисту лучше бы быть знакомым. При этом краткость скорее является плюсом данной книги – она не погрязает в избыточных деталях. Те, кому интересна та или иная тема глубже, смогут найти более узкоспециализированные учебники по конкретной теме. Это же скорее учебник для тех кто по какой-то причине не знает или забыл, что такое дискретная математика.
Как я уже говорил, книга изобилует примерами. Кроме того, в конце каждой главы приведены задачи для самопроверки, что позволяет укрепить пройденный материал на практике. Также, на мой взгляд, данная книга является отличным подспорьем в понимании более сложных книг об алгоритмах. Ведь, как правило, они подразумевают наличие некоторых базовых знаний. Поэтому, я бы рекомендовал данную книгу всем, кто не блещет знаниями по дискретной математике(и\или алгоритмам), но хотел бы это изменить. Discrete Mathematics with Applications будет хорошим стартом.