Дискретная математика и комбинаторика

Предисловие
Таблицы истинности" логика, доказательства
1.1. Высказывания и логические связки
1.2. Условные высказывания
1.3. Эквивалентные высказывания
1.4. Аксиоматические системы: умозаключения
и доказательства
1.5. Полнота в логике высказываний
1.6. Карты Карно
1.7. Коммутационные схемы
Теория множеств
2.1. Понятие множества
2.2. Операции над множествами
2.3. Диаграммы Венна
2.4. Булевы алгебры
2.5. Отношения
2.6. Частично упорядоченные множества
2.7. Отношения эквивалентности
Логика, целые числа и доказательства из
3.1. Исчисление предикатов из
3.2. Основные положения теории
доказательств и теории целых чисел
3.3. Математическая индукция
3.4. Делимость
3.5. Простые числа
3.6. Сравнения
Функции и матрицы
4.1. Функции
4.2. Специальные функции
4.3. Матрицы
4.4. Мощность
4.5. Мощность (продолжение)
Алгоритмы и рекурсия
5.1. Циклы и алгоритмы для матриц
5.2. Рекурсивные функции и алгоритмы
5.3. Сложность алгоритмов
5.4. Алгоритмы сортировки
5.5. Префиксная и суффиксная записи
5.6. Двоичные и шестнадцатеричные числа
5.7. Числа со знаком
5.8. Дальнейшее изучение матриц
Графы, ориентированные графы и деревья
6.1. Графы
6.2. Ориентированные графы
6.3. Деревья
6.4. Мгновенное безумие
6.5. Пути и циклы Эйлера
6.6. Матрицы инцидентности и смежности
6.7. Гиперкубы и код Грея
Теория чисел
7.1. Решето Эратосфена
7.2. Метод выделения множителей Ферма
7.3. Алгоритмы деления и алгоритм Евклида
7.4. Цепные дроби
7.5. Подходящие дроби
Комбинаторика и вероятность
8.1. Основные комбинаторные принципы
8.2. Комбинаторный принцип сложения
8.3. Перестановки и сочетания
8.4. Формирование перестановок и сочетаний
8.5. Введение вероятности
8.6. Обобщенные перестановки и сочетания
8.7. Перестановки и сочетания с повторением
8.8. Принцип клеток
8.9. Снова о вероятности
8.10. Теорема Байеса
8.11. Цепи Маркова
Алгебраические структуры
9.1. Вновь о частично упорядоченных множествах
9.2. Полугруппы и полурешетки
9.3. Решетки
9.4. Группы
9.5. Группы и гомоморфизмы
Некоторые специальные вопросы теории чисел
10.1. Целочисленные решения линейных уравнений
10.2. Решения сравнений
10.3. Китайская теорема об остатках
10.4. Свойства функции ф
10.5. Порядок целого числа
Некоторые специальные вопросы теории рекурсии
11.1. Однородные линейные рекуррентные
отношения
11.2. Неоднородные линейные рекуррентные
отношения
11.3. Конечные разности
11.4. Факториальные многочлены
11.5. Суммирование разностей
Снова о комбинаторных подсчетах
12.1. Задачи о размещении
12.2. Числа Каталана
12.3. Общее включение-исключение и
разупорядочения
12.4. Ладейные полиномы и запрещенные позиции
Производящие функции
13.1. Определение производящей функции
13.2. Производящие функции и рекуррентные
отношения
13.3. Производящие функции и комбинаторные
подсчеты
13.4. Разбиения
13.5. Экспоненциальные производящие функции
Некоторые специальные вопросы теории графов
14.1. Алгебраические свойства графов
14.2. Пленарные графы
14.3. Раскраска графов
14.4. Пути и циклы Гамильтона
14.5. Взвешенные графы и алгоритмы поиска
кратчайшего пути
Деревья
15.1. Свойства деревьев
15.2. Бинарные деревья поиска
15.3. Взвешенные деревья
15.4. Обход бинарных деревьев
15.5. Остовные деревья
15.6. Минимальные остовные деревья
Сети
16.1. Сети и потоки
16.2. Паросочетание
16.3. Сети Петри
Теория вычислений
17.1. Регулярные языки
17.2. Автоматы
17.3. Грамматики
Теория кодов
18.1. Введение
18.2. Порождающие матрицы
18.3. Коды Хемминга
Перечисление цветов
19.1. Теорема Бернсайда
19.2. Теорема Пойа
Кольца, области целостности и поля
20.1. Кольца и области целостности
20.2. Области целостности
20.3. Полиномы
20.4. Алгебры и полиномы
Характеры групп и полугрупп
21.1. Комплексные числа
21.2. Характеры групп
21.3. Характеры полугрупп
Приложения теории чисел
22.1. Приложение: поиск по образу
22.2. Приложение: функции хеширования
22.3. Приложение: криптография
Литература
Ответы к упражнениям
Предметно-именной указатель
Список обозначений