- Артикул:00-01057719
- Автор: Б.Н. Иванов
- ISBN: 978-5-9221-0787-7
- Тираж: 1500 экз.
- Обложка: Твердая обложка
- Издательство: Физматлит (все книги издательства)
- Город: Москва
- Страниц: 408
- Формат: 60х90 1/16
- Год: 2007
- Вес: 585 г
- Серия: Учебное пособие для ВУЗов (все книги серии)
Развернуть ▼
Учебное пособие по курсу дискретной математики. Изложение носит достаточно полный и строгий характер. Теоретические основы курса сопровождаются практически значимыми алгоритмами, реализованными в конкретных компьютерных программах. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко применяемых в практическом программировании.
Пособие рассчитано на студентов специальностей, учебные планы которых предполагают изучение каких-либо разделов курса дискретной математики, в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения.
Содержание
Предисловие
Глава 1. Введение в математическую логику
§ 1.1. Системы счисления
1.1.1. Системы счисления
1.1.2. Смешанные системы счисления
1.1.3. Задача оптимального кодирования
1.1.4. Системы счисления с основаниями 2. 8 и 16
§ 1.2. Введение в булеву алгебру
1.2.1. Булевы функции
1.2.2. Формулы, реализация функций формулами
1.2.3. Замена переменных и суперпозиция
1.2.4. Существенные и фиктивные переменные
1.2.5. Интерпретация булевых функций
1.2.6. Алгебра Буля
1.2.7. Совершенные дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ) булевых функций
§ 1.3. Минимизация булевых функций
1.3.1. Классификация двоичных наборов
1.3.2. Геометрическая интерпретация задачи минимизации булевых функций
1.3.3. Метод Карно минимизации булевых функций 4-х переменных
1.3.4. Аналитический метод Куайна минимизации булевых функций
§ 1.4. Функциональная полнота булевых функций
1.4.1. Алгебра Жегалкина
1.4.2. Классы Поста булевых функций
1.4.3. Теоремы Поста о функциональной полноте
§ 1.5. Исчисление высказываний
1.5.1. Основные понятия
1.5.2. Задачи исчисления высказываний
1.5.3. Соотношение булевой алгебры и исчисления высказываний. Содержательный аспект
1.5.4. Содержательный аспект тождественно истинных формул
1.5.5. Формальное введение в исчисление высказывания
§ 1.6. Исчисление предикатов
1.6.1. Понятие предиката
1.6.2. Операции над предикатами
1.6.3. Определение кванторов
1.6.4. Строение исчисления предикатов
1.6.5. Предикаты свойств
1.6.6. Исчисление одноместных предикатов, исчисление классов
1.6.7. Техника преобразования формул в исчислении предикатов
1.6.8. Формализация некоторых отношений средствами узкого исчисления предикатов
Глава 2. Комбинаторные схемы
§ 2.1. Правило суммы
§ 2.2. Правило прямого произведения
§ 2.3. Размещения с повторениями
§ 2.4. Размещения без повторений
§ 2.5. Перестановки
§ 2.6. Сочетания
§ 2.7. Сочетания с повторениями
§ 2.8. Перестановки с повторениями, мультимножества
§ 2.9. Упорядоченные разбиения множества
§ 2.10. Неупорядоченные разбиения множества
§ 2.11. Полиномиальная формула
§ 2.12. Бином Ньютона
§ 2.13. Инверсии
§ 2.14. Обратные перестановки
Глава 3. Представление абстрактных объектов
§ 3.1. Представление последовательностей
3.1.1. Смежное представление
3.1.2. Характеристические векторы
3.1.3. Связанное размещение
§ 3.2. Представление деревьев
3.2.1. Представление деревьев на связанной памяти
3.2.2. Представление деревьев на смежной памяти
§ 3.3. Представление множеств
Глава 4. Методы подсчета и оценивания
§ 4.1. Производящие функции
4.1.1. Линейные операции
4.1.2. Сдвиг начала вправо
4.1.3. Сдвиг начала влево
4.1.4. Частичные суммы
4.1.5. Дополнительные частичные суммы
4.1.6. Изменение масштаба
4.1.7. Свертка
§ 4.2. Линейные рекуррентные соотношения
§ 4.3. Неоднородные линейные рекуррентные соотношения
§ 4.4. Обобщенное правило произведения
§ 4.5. Принцип включения и исключения
§ 4.6. Ладейные многочлены и многочлены попаданий
4.6.1. Ладейные многочлены
4.6.2. Многочлены попаданий
Глава 5. Генерация комбинаторных объектов
§ 5.1. Поиск с возвращением
§ 5.2. Перестановки различных элементов
§ 5.3. Эффективное порождение перестановок
§ 5.4. Порождение подмножеств множества
§ 5.5. Генерация размещений с повторениями
§ 5.6. Порождение сочетаний
§ 5.7. Порождение композиций и разбиений
§ 5.8. Генерация случайных перестановок
Глава 6. Сортировка и поиск
§ 6.1. Сортировка вставками
§ 6.2. Пузырьковая сортировка
§ 6.3. Сортировка перечислением
§ 6.4. Сортировка всплытием Флойда
§ 6.5. Последовательный поиск
§ 6.6. Логарифмический поиск
§ 6.7. Сортировка с вычисляемыми адресами
Глава 7. Теория графов. Алгоритмы на графах
§ 7.1. Основные понятия и определения
§ 7.2. Представления графов
7.2.1. Матрица смежности графа
7.2.2. Матрица инцидентности графа
7.2.3. Матрица весов графа
7.2.4. Список ребер графа
7.2.5. Структура смежности графа
§ 7.3. Метод поиска в глубину
§ 7.4. Отношение эквивалентности
§ 7.5. Связные компоненты
§ 7.6. Выделение компонент связности
§ 7.7. Эйлеровы графы
§ 7.8. Остовные деревья
7.8.1. Жадный алгоритм построения минимального остовного дерева
7.8.2. Алгоритм ближайшего соседа построения остовного дерева
§ 7.9. Кратчайшие пути на графе
§ 7.10. Потоки в сетях
§ 7.11. Клики, независимые множества
§ 7.12. Циклы, фундаментальные множества циклов
§ 7.13. Листы и блоки
7.13.1. Листы
7.13.2. Блоки
7.13.3. Поиск блоков в глубину
§ 7.14. Двудольные графы
7.14.1. Условия существования двудольных графов
7.14.2. Паросочетания
7.14.3. Алгоритм определения максимального паросочетания
7.14.4. Системы различных представителей
7.14.5. Связь системы различных представителей и двудольных графов
7.14.6. Задача о назначениях
§ 7.15. Хроматические графы
§ 7.16. Диаметр, радиус и центры графа
Глава 8. Введение в теорию групп. Приложения
§ 8.1. Определение группы
§ 8.2. Гомоморфизм групп
§ 8.3. Смежные классы
§ 8.4. Строение коммутативных (абелевых) групп
§ 8.5. Строение некоммутативных групп
§ 8.6. Симметрическая группа подстановок
§ 8.7. Действие групп на множестве
§ 8.8. Цикловой индекс группы
§ 8.9. Теория перечисления Пойа
§ 8.10. Цикловая структура групп подстановок
8.10.1. Цикловой индекс группы, действующей на себе
8.10.2. Цикловой индекс циклической группы
8.10.3. Цикловой индекс симметрической группы
Глава 9. Элементы теории чисел
§ 9.1. Наибольший общий делитель
§ 9.2. Наименьшее общее кратное
§ 9.3. Простые числа
§ 9.4. Сравнения, свойства сравнений
§ 9.5. Полная система вычетов
§ 9.6. Приведенная система вычетов
§ 9.7. Функция Эйлера
§ 9.8. Функция Мёбиуса Формула обращения Мёбиуса
Задачи и упражнения
Ответы
Список литературы
Предметный указатель
Рекомендуем
