|
Книги: [Классика] [Базы данных] [Internet/WWW] [Сети] [Программирование] [UNIX] [Windows] [Безопасность] [Графика] [Software Engineering] [ERP-системы] [Hardware]
Содержание
Вступительное слово
Введение
ГЛАВА 1. Множества и отношения
1.1. Множества
1.1.1. Элементы и множества
1.1.2. Задание множеств
1.1.3. Парадокс Рассела
1.2. Операции над множествами
1.2.1. Сравнение множеств
1.2.2. Операции над множествами
1.2.3. Разбиения и покрытия
1.3. Алгебра подмножеств
1.3.1. Булеан.
1.3.2. Свойства операций над множествами
1.4. Представление множеств в ЭВМ
1.4.1. Реализация операций над
подмножествами заданного универсума U
1.4.2. Генерация всех подмножеств универсума
1.4.3. Алгоритм построения бинарного кода Грея
1.4.4. Представление множеств упорядоченными списками
1.4.5. Проверка включения слиянием
1.4.6. Вычисление объединения слиянием
1.4.7. Вычисление пересечения слиянием
1.5. Отношения
1.5.1. Упорядоченные пары
1.5.2. Прямое произведение множеств
1.5.3. Отношения
1.5.4. Композиция отношений
1.5.5. Степень отношения
1.5.6. Ядро отношения
1.5.7. Свойства отношений
1.5.8. Представление отношений в ЭВМ
1.6. Функции
1.6.1. Определения
1.6.2. Инъекция, сюръекция и биекция
1.6.3. Индуцированная функция
1.6.4. Представление функций в ЭВМ
1.7. Отношения эквивалентности
1.7.1. Определения
1.7.2. Классы эквивалентности
1.7.3. Фактор множества
1.7.4. Ядро функции
1.8. Отношения порядка
1.8.1. Определения
1.8.2. Минимальные элементы
1.8.3. Алгоритм топологической сортировки
1.8.4. Монотонные функции
1.9. Замыкание отношений
1.9.1. Замыкание отношения относительно свойства
1.9.2. Транзитивное и рефлексивное транзитивное замыкания
1.9.3. Алгоритм Уоршалла
Комментарии
Упражнения
ГЛАВА 2. Алгебраические структуры
2.1. Операции и алгебры
2.1.1. Алгебраические структуры
2.1.2. Замыкания и подалгебры
2.1.3. Алгебра термов
2.1.4. Система образующих
2.1.5. Свойства операций
2.2 Морфизмы
2.2.1. Гомоморфизм
2.2.2. Изоморфизм
2.3. Алгебры с одной операцией
2.3.1. Полугруппы
2.3.2. Моноиды
2.3.3. Группы
2.4. Алгебры с двумя операциями
2.4.1. Кольца
2.4.2. Области целостности
2.4.3. Поля
2.5. Векторные пространства
2.5.1. Определения
2.5.2. Свойства нуль-вектора
2.5.3. Линейные комбинации
2.5.4. Базис и размерность
2.6. Решетки
2.6.1. Определения
2.6.2. Ограниченные решетки
2.6.3. Решетка с дополнением
2.6.4. Частичный порядок в решетке
2.6.5. Булевы алгебры
2.7. Матроиды
2.7.1. Определения
2.7.2. Максимальные независимые подмножества
2.7.3. Базисы
2.7.4. Ранг
2.7.5. Жадный алгоритм
2.7.6. Примеры матроидов
Комментарии
Упражнения
ГЛАВА 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.4. Нормальные формы
3.4.1. Разложение булевых функций по переменным
3.4.2. Совершенные нормальные формы
3.4.3. Построение СДНФ
3.4.4. Алгоритм вычисления значения булевой функции
3.4.5. Эквивалентные преобразования
3.5. Замкнутые классы
3.5.1. Замыкание множества булевых функций
3.5.2. Некоторые замкнутые классы
3.6. Полнота
Комментарии
Упражнения
ГЛАВА 4. Логические исчисления
4.1. Логические связки
4.1.1. Высказывания
4.1.2. Формулы
4.1.3. Интерпретация
4.1.4. Логическое следование и логическая эквивалентность
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. Некоторые теоремы теории L
4.3.8. Множество теорем теории L
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. Комбинаторика
5.1. Комбинаторные конфигурации
5.1.1. Комбинаторные задачи
5.1.2. Размещения
5.1.3. Размещения без повторений
5.1.4. Перестановки
5.1.5. Сочетания
5.1.6. Сочетания с повторениями
5.2. Подстановки
5.2.1. Группа подстановок
5.2.2. Графическое представление подстановок
5.2.3. Циклы
5.2.4. Подстановки и перестановки
5.2.5. Инверсии
5.2.6. Генерация перестановок
5.3. Биномиальные коэффициенты
5.3.1. Элементарные тождества
5.3.2. Бином Ньютона
5.3.3. Свойства биномиальных коэффициентов
5.3.4. Треугольник Паскаля
5.3.5. Генерация подмножеств
5.4. Разбиения
5.4.1. Определения
5.4.2. Числа Стирлинга второго рода
5.4.3. Числа Стирлинга первого рода
5.4.4. Число Белла
5.5. Принцип включения и исключения
5.5.1. Объединение конфигураций
5.5.2. Принцип включения и исключения
5.5.3. Число булевых функций, существенно
зависящих от всех своих переменных
5.6. Формулы обращения
5.6.1. Теорема обращения
5.6.2. Формулы обращения для биномиальных коэффициентов
5.6.3. Формулы для чисел Стирлинга
5.7. Производящие функции
5.7.1. Основная идея
5.7.2. Метод неопределенных коэффициентов
Комментарии
Упражнения
ГЛАВА 6. Кодирование
6.1. Алфавитное кодирование
6.1.1. Префикс и постфикс слова
6.1.2. Таблица кодов
6.1.3. Разделимые схемы
6.1.4. Префиксные схемы
6.1.5. Неравенство Макмиллана
6.2. Кодирование с минимальной избыточностью
6.2.1. Минимизация длины кода сообщения
6.2.2. Цена кодирования
6.2.3. Алгоритм Фано
6.2.4. Оптимальное кодирование
6.2.5. Алгоритм Хаффмена
6.3. Помехоустойчивое кодирование
6.3.1. Кодирование с исправлением ошибок
6.3.2. Классификация ошибок
6.3.3. Возможность исправления всех ошибок
6.3.4. Кодовое расстояние
6.3.5. Код Хэмминга для исправления одного замещения
6.4. Сжатие данных
6.4.1. Сжатие текстов
6.4.2. Предварительное построение словаря
6.4.3. Алгоритм Лемпела-Зива
6.5. Шифрование
6.5.1. Криптография
6.5.2. Шифрование с помощью случайных чисел
6.5.3. Криптостойкость
6.5.4. Модулярная арифметика
6.5.5. Шифрование с открытым ключом
6.5.6. Цифровая подпись
Комментарии
Упражнения
ГЛАВА 7. Графы
7.1. Определения графов
7.1.1. История теории графов
7.1.2. Основное определение
7.1.3. Смежность
7.1.4. Диаграммы
7.1.5. Другие определения
7.1.6. Изоморфизм графов
7.2. Элементы графов
7.2.1. Подграфы
7.2.2. Валентность
7.2.3. Маршруты, цепи, циклы
7.2.4. Расстояние между вершинами
7.2.5. Связность
7.3. Виды графов и операции над графами
7.3.1. Тривиальные и полные графы
7.3.2. Двудольные графы
7.3.3. Направленные орграфы и сети
7.3.4. Операции над графами
7.4. Представление графов в ЭВМ
7.4.1. Требования к представлению графов
7.4.2. Матрица смежности
7.4.3. Матрица инциденций
7.4.4. Списки смежности
7.4.5. Массив дуг
7.4.6. Обходы графов
7.5. Орграфы и бинарные отношения
7.5.1.Графы и отношения
7.5.2. Достижимость и частичное упорядочение
7.5.3. Транзитивное замыкание
Комментарии
Упражнения
ГЛАВА 8. Связность
8.1. Компоненты связности
8.1.1. Объединение графов и компоненты связности
8.1.2. Точки сочленения
8.1.3. Оценка числа ребер через число
вершин и число компонент связности
8.2 Вершинная и реберная связность
8.2.1. Мосты и блоки
8.2.2. Меры связности
8.3. Теорема Менгера
8.3.1. Непересекающиеся цепи и разделяющие множества
8.3.2. Теорема Менгера в "вершинной форме"
8.3.3. Варианты теоремы Менгера
8.4. Теорема Холла
8.4.1.Задача о свадьбах
8.4.2.Трансверсаль
8.4.3. Совершенное паросочетание
8.4.4. Теорема Холла - формулировка и доказательство
8.5. Потоки в сетях
8.5.1. Определение потока
8.5.2. Разрезы
8.5.3. Теорема Форда и Фалкерсона
8.5.4. Алгоритм нахождения максимального потока
8.5.5. Связь между теоремой Менгера
и теоремой Форда и Фалкерсона
8.6. Связность в орграфах
8.6.1. Сильная, односторонняя и слабая связность
8.6.2. Компоненты сильной связности
8.6.3. Выделение компонент сильной связности
8.7. Кратчайшие пути
8.7.1. Длина дуг
8.7.2. Алгоритм Флойда
8.7.3. Алгоритм Дейкстры
Комментарии
Упражнения
ГЛАВА 9. Деревья
9.1. Свободные деревья
9.1.1. Определения
9.1.2. Основные свойства деревьев
9.2. Ориентированные, упорядоченные и бинарные деревья
9.2.1. Ориентированные деревья
9.2.2. Эквивалентное определение ордерева
9.2.3. Упорядоченные деревья
9.2.4. Бинарные деревья
9.3. Представление деревьев в ЭВМ
9.3.1. Представление свободных,
ориентированных и упорядоченных деревьев
9.3.2. Представление бинарных деревьев
9.3.3. Обходы бинарных деревьев
9.3.4. Алгоритм симметричного обхода бинарного дерева
9.4. Деревья сортировки
9.4.1. Ассоциативная память
9.4.2. Способы реализации ассоциативной памяти
9.4.3. Алгоритм бинарного (двоичного) поиска
9.4.4. Алгоритм поиска в дереве сортировки
9.4.5. Алгоритм вставки в дерево сортировки
9.4.6. Алгоритм удаления из дерева сортировки
9.4.7. Вспомогательные алгоритмы для дерева сортировки
9.4.8. Сравнение представлений ассоциативной памяти
9.4.9. Выровненные деревья
9.4.10. Сбалансированные деревья
9.5. Кратчайший остов
9.5.1. Определения
9.5.2. Схема алгоритма построения кратчайшего остова
9.5.3. Алгоритм Краскала
Комментарии
Упражнения
ГЛАВА 10. Циклы
10.1. Фундаментальные циклы и разрезы
10.1.1. Циклы и коциклы
10.1.2. Независимые множества циклов и коциклов
10.1.3. Циклический и коциклический ранг
10.2. Эйлеровы циклы
10.2.1. Эйлеровы графы
10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе
10.2.3. Оценка числа эйлеровых графов
10.3. Гамильтоновы циклы
10.3.1. Гамильтоновы графы
10.3.2. Задача коммивояжера
Комментарии
Упражнения
ГЛАВА 11. Независимость и покрытия
11.1. Независимые и покрывающие множества
11.1.1. Покрывающие множества вершин и ребер
11.1.2. Независимые множества вершин и ребер
11.1.3. Связь чисел независимости и покрытий
11.2. Построение независимых множеств вершин
11.2.1. Постановка задачи отыскания наибольшего
независимого множества вершин
11.2.2. Поиск с возвратами
11.2.3. Улучшенный перебор
11.2.4. Алгоритм построения максимальных
независимых множеств вершин
11.3. Доминирующие множества
11.3.1. Определения
11.3.2. Доминирование и независимость
11.3.3. Задача о наименьшем покрытии
11.3.4. Эквивалентные формулировки ЗИП
11.3.5. Связь ЗИП с другими задачами
Комментарии
Упражнения
ГЛАВА 12. Раскраска графов
12.1. Хроматическое число
12.2. Планарность
12.2.1. Укладка графов
12.2.2. Эйлерова характеристика
12.2.3. Теорема о пяти красках
12.3. Алгоритмы раскрашивания
12.3.1. Точный алгоритм раскрашивания
12.3.2. Приближенный алгоритм
последовательного раскрашивания
12.3.3. Улучшенный алгоритм последовательного
раскрашивания
Комментарии
Упражнения
Литература
Алфавитный указатель
Начало
Краткое содержание
Предисловие
Введение
Структура книги
Заказать книгу в магазине "Мистраль"
|
|
Виртуальные VPS серверы в РФ и ЕС
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
