Новиков Ф.А. Дискретная математика для программистов (860615)
Текст из файла
УЧЕБНИКйДЛЯ ВУЗОВФ. А. НовиковДИСКРЕТНАЯМАТЕМАТИКАДЛЯ ПРОГРАММИСТОВ3-е изданиеДопущено Министерством образования и науки Российской Федерациив качестве учебного пособия для студентов высших учебных заведений,обучающихся по направлению подготовки дипломированныхспециалистов «Информатика и вычислительная техника»С^ППТЕРМосква • Санкт-Петербург • Нижний Новгород • ВоронежРостов-на-Дону • Екатеринбург • Самара • НовосибирскКиев • Харьков • Минск2009ББК 22.174я7УДК 519.1(075) .* Н73Рецензенты:Кафедра прикладной математикиСанкт-Петербургского государственного технического университетаС. С. Лавров], доктор технических наук, профессор,член-корреспондент Российской академии наукНовиков Ф. А.Н 7 3 Д и с к р е т н а я м а т е м а т и к а д л я п р о г р а м м и с т о в : У ч е б н и к д л я вузов. 3 - е изд.СПб.: Питер, 2009. —3 8 4 е.: и л .
——(Серия «Учебник д л я вузов»),ISBN 978-5-91180-759-7В учебнике изложены основные разделы дискретной математики и описаны важнейшие алгоритмына дискретных структурах данных. Основу книги составляет материал лекционного курса, который авторчитает в Санкт-Петербургском государственном техническом университете последние полтора десятилетия. Третье издание имеет ту же структуру и последовательность изложения, что и второе.
В книгувнесено несколько десятков не очень объемных, но существенных добавлений, уточнений и определений.Обновлены упражнения, библиография и комментарии к ней.Для студентов вузов, практикующих программистов и всех желающих изучить дискретнуюматематику,Допущено Министерством образования и науки Российской Федерации в качестве учебного пособиядля студентов высших учебных заведений, обучающихся по направлению подготовки дипломированныхспециалистов «Информатика и вычислительная техника»,ББК 22,174я7УДК 619,1(076)Bee права защищены, Никакая чаоть данной книги на может быть воспроизведена в какой бы то ни былоформе без письменного разрешения владельцев авторских прав,Информация, содержащаяся в данной книге, получена из источников, рассматриваемых издательством какнадежные, Тем не менее, имея в виду возможные человеческие или технические ошибки, иэдательотво неможет гарантировать абоолютную точнооть и полноту приводимых сведений и не неоет ответотвеннооти завозможные ошибки, связанные с использованием книги,ISBN078-B-91180-760-7@ ООО «Питер Пресс», 2009Краткое содержаниеПредисловие к третьему изданию12Предисловие ко второму изданию13Вступительное слово к первому изданию14Введение15Глава 1 .
Множества и отношения23Глава 2 . Алгебраические структуры. \ . . 75Глава 3 . Булевы функции107Глава 4 . Логические исчисления142Глава 5 . Комбинаторика179Глава 6 . Кодирование208Глава 7 . Графы240Глава 8 . Связность265Глава 9. Деревья292Глава 1 0 . Циклы, независимость и раскраска333Указатель основных обозначений365Список литературы368Предметный указатель370СодержаниеПредисловие к третьему изданию12Предисловие ко второму изданию13Вступительное слово к первому изданию14Введение15Глава 1 .
Множества и отношения231.1. Множества1.1.1. Элементы и множества1.1.2. Задание множеств1.1.3. Парадокс Рассела1.1.4. Мультимножества1.2. Алгебра подмножеств1.2.1. Сравнение множеств1.2.2. Равномощные множества1.2.3. Конечные и бесконечные множества1.2.4. Добавление и удаление элементов1.2.5. Мощность конечного множества1.2.6. Операции над множествами1.2.7.
Разбиения и покрытия1.2.8. Булеан1.2.9. Свойства операций над множествами1.3. Представление множеств в программах1.3.1. Битовые шкалы1.3.2. Генерация всех подмножеств универсума1.3.3. Алгоритм построения бинарного кода Грея1.3.4. Представление множеств упорядоченными списками1.3.5. Проверка включения слиянием1.3.6. Вычисление объединения слиянием1.3.7. Вычисление пересечения слиянием1.3.8. Представление множеств итераторами1.4. Отношения1.4.1.
Упорядоченные пары и наборы1.4.2. Прямое произведение множеств1.4.3. Бинарные отношения1.4.4. Композиция отношений1.4.5. Степень отношения1.4.6. Свойства отношений23232526272828293132323435363738383940414243444548484950525353Содержание51.4.7. Ядро отношения1.4.8. Представление отношений в программах1.5. Замыкание отношений1.5.1. Транзитивное и рефлексивное замыкание1.5.2. Алгоритм Уоршалла1.6. Функции1.6.1.
Функциональные отношения1.6.2. Инъекция, сюръекция и биекция1.6.3. Образы и прообразы1.6.4. Суперпозиция функций1.6.5. Представление функций в программах1.7. Отношения эквивалентности1.7.1. Классы эквивалентности1.7.2. Фактормножества1.7.3. Ядро функционального отношения и множества уровня1.8. Отношения порядка1.8.1. Определения1.8.2. Минимальные элементы1.8.3. Алгоритм топологической сортировки1.8.4. Верхние и нижние границы1.8.5.
Монотонные функции1.8.6. Вполне упорядоченные множества1.8.7. Индукция1.8.8. Алфавит, слово и языкКомментарииУпражнения5556575758595961626363646466666767686970707172737374Глава 2 . Алгебраические структуры2.1. Алгебры и морфизмы2.1.1. Операции и их носитель2.1.2. Замыкания и подалгебры2.1.3. Система образующих2.1.4. Свойства операций2.1.5. Гомоморфизмы2.1.6. Изоморфизмы2.2. Алгебры с одной операцией2.2.1. Полугруппы2.2.2. Определяющие соотношения2.2.3. Моноиды2.2.4. Группы2.2.5. Группа перестановок2.3. Алгебры с двумя операциями2.3.1. Кольца2.3.2.
Области целостности2.3.3. Поля2.4. Векторные пространства и модули2.4.1. Векторное пространство2.4.2. Линейные комбинации2.4.3. Базис и размерность2.4.4. Модули2.5. Решётки2.5.1. Определения2.5.2. Ограниченные решётки75757576777879808181828485878888899091919394959696976Содержание2.5.3. Решётка с дополнением2.5.4. Частичный порядок в решётке2.5.5.
Булевы алгебры2.6. Матроиды и жадные алгоритмы2.6.1. Матроиды2.6.2. Максимальные независимые подмножества2.6.3. Базисы2.6.4. Жадный алгоритм2.6.5. Примеры матроидовКомментарииУпражнения979899100100101101102105105106Глава 3 . Булевы функции3.1. Элементарные булевы функции3.1.1. Функции алгебры логики3.1.2. Существенные и несущественные переменные3.1.3. Булевы функции одной переменной3.1.4.
Булевы функции двух переменных3.2. Формулы3.2.1. Реализация функций формулами3.2.2. Равносильные формулы3.2.3. Подстановка и замена3.2.4. Алгебра булевых функций3.3. Двойственность3.3.1. Двойственная функция3.3.2. Реализация двойственной функции3.3.3. Принцип двойственности3.4. Нормальные формы3.4.1. Разложение булевых функций по переменным3.4.2. Совершенные нормальные формы3.4.3. Эквивалентные преобразования3.4.4. Минимальные дизъюнктивные формы3.4.5. Геометрическая интерпретация3.4.6.
Сокращённые дизъюнктивные формы3.5. Полнота3.5.1. Замкнутые классы3.5.2. Полные системы функций3.5.3. Полнота двойственной системы3.5.4. Теорема Поста3.6. Представление булевых функций в программах3.6.1. Табличные представления3.6.2. Строковые представления3.6.3. Алгоритм вычисления значения булевой функции3.6.4. Деревья решенийКомментарииУпражнения107107107109110110111111114115116118118118119120120121123124125126128128130131131133133135136137140140Глава 4 .
Логические исчисления4.1. Логические связки4.1.1. Высказывания4.1.2. Формулы4.1.3. Интерпретация4.1.4. Логическое следование и логическая эквивалентность142143143144144145Содержание4.1.5. Подстановка и замена4.2. Формальные теории4.2.1. Определение формальной теории4.2.2. Выводимость4.2.3. Интерпретация4.2.4. Общезначимость и непротиворечивость4.2.5. Полнота, независимость и разрешимость4.3. Исчисление высказываний4.3.1. Классическое определение исчисления высказываний4.3.2. Частный случай формулы4.3.3. Алгоритм унификации4.3.4. Конструктивное определение исчисления высказываний4.3.5.
Производные правила вывода4.3.6. Дедукция4.3.7. Некоторые теоремы исчисления высказываний4.3.8. Множество теорем исчисления высказываний4.3.9. Другие аксиоматизации исчисления высказываний4.4. Исчисление предикатов4.4.1. Определения4.4.2. Интерпретация4.4.3. Общезначимость4.4.4. Непротиворечивость и полнота чистого исчисления предикатов4.4.5. Логическое следование и логическая эквивалентность4.4.6. Теория равенства4.4.7. Формальная арифметика4.4.8.
Неаксиоматизируемые теории4.4.9. Теоремы Гёделя о неполноте4.5. Автоматическое доказательство теорем4.5.1. Постановка задачи4.5.2. Доказательство от противного4.5.3. Сведёние к предложениям4.5.4. Правило резолюции для исчисления высказываний4.5.5. Правило резолюции для исчисления предикатов4.5.6. Опровержение методом резолюций4.5.7. Алгоритм метода резолюцийКомментарииУпражненияГлава 5 .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
