Читать онлайн «Дискретная математика для программистов : учебное пособие для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов "Информатика и вычислительная техника"»

УЧЕБНИК 11 ДЛЯ ВУЗОВ Ф. А. Новиков ДИСКРЕТНАЯ МАТЕМАТИКА ДЛЯ ПРОГРАММИСТОВ 3-е издание Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов «Информатика и вычислительная техника» [^ПИТЕР Москва • Санкт-Петербург • Нижний Новгород • Воронеж Ростов-на-Дону ■ Екатеринбург • Самара - Новосибирск Киев • Харьков ■ Минск 2009 ББК 22. 174я7 УДК 519. 1(075) ' Н73 Рецензенты: Кафедра прикладной математики Санкт-Петербургского государственного технического университета С. С. Лавров], доктор технических наук, профессор, член-корреспондент Российской академии наук Новиков Ф. А. Н73 Дискретная математика для программистов: Учебник для вузов. 3-е изд. — СПб. : Питер, 2009. — 384 с: ил. — (Серия «Учебник для вузов»). ISBN 978-5-91180-759-7 В учебнике изложены основные разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных. Основу книги составляет материал лекционного курса, который автор читает в Санкт-Петербургском государственном техническом университете последние полтора десятилетия. Третье издание имеет ту же структуру и последовательность изложения, что и второе. В книгу внесено несколько десятков не очень объемных, но существенных добавлений, уточнений и определений. Обновлены упражнения, библиография и комментарии к ней, Для студентов вузов, практикующих программистов и всех желающих изучить дискретную математику, Допушоно Министерством образования и науки Российской Федерации в качество учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов «Информатика и вычислительная техника», ББК 22,174*7 УДК 619,1(076) Вов права защищены. Никакая часть данной книги на может быть воспроизведена в какой бы то ни было форма без письменного разрешении владельцев авторских прав. Информация, оодержащаяая в данной книга, получена из источников, рассматриваемых издательством как надежные. Там на менее, имея в виду возможные человечеокие или технические ошибки, издательство на можат гарантировать абсолютную точнооть и полноту приводимых сведений и не неоет ответотвеннооти за возможные ошибки, связанные о использованием книги. ISBN978-5-91160-759-7 Ф ООО «Питер Пресс», 2009 Краткое содержание Предисловие к третьему изданию 12 Предисловие ко второму изданию 13 Вступительное слово к первому изданию 14 Введение 15 Глава 1. Множества и отношения 23 Глава 2. Алгебраические структуры . V . . 75 Глава 3. Булевы функции 107 Глава 4. Логические исчисления 142 Глава 5. Комбинаторика 179 Глава 6. Кодирование 208 Глава 7. Графы 240 Глава В. Связность 265 Глава 9. Деревья 292 Глава 10. Циклы, независимость и раскраска 333 Указатель основных обозначений 365 Список литературы 368 Предметный указатель 370 Содержание Предисловие к третьему изданию 12 Предисловие ко второму изданию 13 Вступительное слово к первому изданию 14 Введение 15 Глава 1.