Дискретная математика для программистов / Ф А. Новиков
Данная книга представляет собой конспективный учебник по дискретной математике, включающий в себя описания важнейших алгоритмов над объектами дискретной математики. Учебник ориентирован на студентов программистских специальностей и практикующих программистов, которым по роду их занятий приходится иметь дело с конструированием и анализом нетривиальных алгоритмов.
В настоящее время имеется масса доступной литературы, покрывающей обе эти темы. С одной стороны, существуют десятки прекрасных книг по дискретной математике, начиная с элементарных учебников для начинающих и кончая исчерпывающими справочниками для специалистов. С другой стороны, большое число монографий, многие из которых стали классическими, посвящены вопросам теории и технологии программирования. Как правило, такие монографии содержат детальное описание и анализ важнейших и известнейших алгоритмов. Однако книги, которые бы рассматривали обе эти темы одновременно и во взаимосвязи, практически отсутствуют. В качестве редкого исключения можно назвать книгу В. Липского «Комбинаторика для программистов» [14], перевод которой выдержал уже два издания в России. Данный учебник принадлежит именно к такому жанру математической литературы, в котором математическое изложение доводится до уровня практически исполнимых программ. Он отличается большей широтой, но, пожалуй, меньшей глубиной охвата материала.
Учебник основан на лекционном курсе, который автор уже в течение четырнадцати лет читает студентам кафедры «Прикладная математика» Санкт-Петербургского государственного технического университета, что наложило определенный отпечаток на состав материала.
Учебник охватывает почти все основные разделы дискретной математики: наивную теорию множеств, математическую логику, общую алгебру, комбинаторику и теорию графов. Из основных разделов отсутствуют теория алгоритмов и (машинная) арифметика, равно как и некоторые необходимые для программиста, но более специальные разделы, такие как теория формальных грамматик, вычислительная геометрия и теория конечных автоматов. Это объясняется тем, что данные разделы студенты изучают в специальных курсах.
