|
Эта книга - элементарное введение в дискретную математику, без знания которой невозможно успешно заниматься информатикой и программированием. Ни одно из немногочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики – о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает её доступной даже школьнику. После каждой главы ( начиная со второй) рассматривается приложение описанных методов к информатике.
Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов – практиков.
400 стр.; ISBN: 978-5-94836-016-4; 2005 г.; Техносфера. Содержание
Предисловие Введение 1. Моделирование - Псевдокод
- Набор упражнений 1
- Краткое содержание главы
2. Логика и доказательство - Высказывания и логика
- Предикаты и кванторы
- Методы доказательств
- Математическая индукция
- Набор упражнений 2
- Краткое содержание главы
- Приложение: Корректность алгоритмов
3. Теория множеств - Множества и операции над ними
- Алгебра множеств
- Дальнейшие свойства множеств
- Набор упражнений 3
- Краткое содержание главы
- Приложение: Система с базой знаний
4. Отношения - Бинарные отношения
- Свойства отношений
- Отношения эквивалентности и частичного порядка
- Набор упражнений 4
- Краткое содержание главы
- Приложение: Системы управления базами данных
5. Функции - Обратные отношения и композиция отношений
- Функции
- Обратные функции и композиция функций
- Принцип Дирихле
- Набор упражнений 5
- Краткое содержание главы
- Приложение: Языки функционального программирования
6. Комбинаторика - Правила суммы и произведения
- Формулы для вычислений
- Бином Ньютона
- Набор упражнений 6
- Краткое содержание главы
- Приложение: Эффективность алгоритмов
7. Графы - Графы и терминология
- Гамильтоновы графы
- Деревья
- Набор упражнений 7
- Краткое содержание главы
- Приложение: Сортировка и поиск
8. Ориентированные графы - Ориентированные графы
- Пути в орграфах
- Кратчайший путь
- Набор упражнений 8
- Краткое содержание главы
- Приложение: Коммуникационные сети
9. Булева алгебра - Булева алгебра
- Карта Карно
- Логическая схема
- Набор упражнений 9
- Краткое содержание главы
- Приложение: Проектирование 2-битного сумматора
- Решения
Дополнение к первому изданию - Д.1. генератор случайных графов
- Д.1.1. Алгоритм построения случайного неориентированного графа
- Д.1.2. Алгоритм построения случайного ориентированного графа
- Д.1.3. Алгоритм построения случайного неориентированного бесконтурного графа
- Д.2. Связность в графах
- Д.2.1. Алгоритм Уоршелла, вычисляющий матрицу связности
- Д.2.2. Выделение компонент связности
- Д.3. Эйлеровы циклы
- Д.3.1. Алгоритм построения эйлерова цикла в графе
- Д.3.2. Алгоритм Терри
- Д.4. Операции над множествами
- Д.4.1. Объединение множеств
Дополнение ко второму изданию - Предисловие
- Д.5. Дополнительные главы дискретной математики
- Д.5.1. Исчисление и оценка конечных сумм
- Набор упражнений
- Д.5.2. Элеиенты теории рекурсии
- Набор упражнений
- Д.5.3. Конечные разности. Разностный и суммирующий операторы
- Набор упражнений
- Д.5.4. Производящие функции и комбинаторные подсчеты
- Набор упражнений
- Д.6. Общая проблема перебора и некоторые точные методы решения задач целочисленного программирования
- Введение
- Д.6.1. Понятие m -мерного евклидова целочисленного пространства
- Д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования
- Д.6.3. NP -полные задачи и проблема перебора
- Д.6.4. Обзор точных методов решения задач целочисленного программирования
- Д.6.5. Точное решение задачи одномерной упаковки методом динамического программирования
- Д.6.6. Метод ветвей и границ и задача коммивояжера
- Набор упражнений
Литература Предметный указатель
|
