4 Теория графов

Содержание

• Дискретная математика
• 6.050102 “Компьютерная инженерия” содержание
• 1 Теория множеств 7
• 2 Математическая логика 15
• 3 Формальные теории 35
• 4 Теория графов 47
• 5 Элементы теории чисел 80
• 6 Теория алгоритмов 121
• Введение
• 1 Теория множеств
• 1.1 Множества и подмножества
• 1.1.1 Элементы множества
• 1.2 Аксиомы теории множеств
• 1.3 Способы задания множеств
• 1.4 Операции над множествами
• 1.5 Элементы алгебры множеств
• 1.5.1 Определение алгебры множеств
• 1.5.2 Основные законы алгебры множеств
• 1.5.3 Принцип двойственности
• 2 Математическая логика
• 2.1 Функции алгебры логики (булевые функции)
• 2.1.1 Способы задания булевых функций
• 2.1.2 Логические функции одной переменной
• 2.1.3 Логические функции двух переменных
• 2.2.6 Функционально полные системы булевых функций
• 2.3 Алгебра буля
• 2.3.1 Определение алгебры. Теорема Стоуна
• 2.3.2 Законы алгебры логики
• 2.3.3 Разложения функций по переменным
• 2.3.4 Приведение логических функций
• 2.3.5 Импликанты и имплициенты булевых функций
• 2.3.6 Методы минимизации логических функций
• 2.4 Алгебра жегалкина
• 2.4.1 Преобразование функций в алгебре Жегалкина
• 2.4.2 Переход от булевой алгебры к алгебре Жегалкина
• 3 Формальные теории
• 3.1 Основные принципы построения формальных теорий исчисления
• 3.2 Определение исчисления высказываний
• 3.2.1 Метатеоремы исчисления высказываний
• 3.2.2 Схемы исчисления высказываний
• 3.3 Исчисление предикатов
• 3.3.1 Определение формальной теории pl
• 3.3.2 Принцип резолюции в исчислении предикатов
• 3.3.3 Схемы доказательств в исчислении предикатов
• 4 Теория графов
• 4.1 История теории графов
• 4.2 Основные определения
• 4.3 Способы представления графов
• 4.3.1 Матрицей смежности
• 4.3.2 Матрицей инцидентности
• 4.4 Пути в графах
• 4.4.1 Задача о кратчайшем пути
• 4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе
• 4.5 Транспортные сети
• 4.5.1 Потоки в транспортных сетях
• 4.5.2 Задача нахождения наибольшего потока в транспортной сети
• 4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети
• 4.5.4 Транспортная задача
• 4.6 Обходы в графах
• 4.6.1 Эйлеровы графы
• 4.6.2 Алгоритм Флёри нахождения эйлерова цикла
• 4. Если получился цикл, но не ейлеров, то отбрасываем данную последнюю вершину и повторяем пункт 2.
• 4.6.3 Гамильтоновы циклы
• 4.6.4 Метод ветвей и границ.
• 4.6.5 Метод ветвей и границ в задаче о коммивояжёре
• 4.7 Деревья
• 4.7.1 Построение экономического дерева
• 4.7.2 Алгоритм Краскала
• 5 Элементы теории чисел
• 5.1 Модулярная арифметика
• 5.1.1 Алгоритм Евклида для нахождения наибольшего общего делителя
• 5.1.2 Вычисление обратных величин
• 5.1.3 Основные способы нахождения обратных величин
• 5.1.4 Китайская теорема об остатках
• 5.2 Кодирование
• 5.2.1 Оптимальное кодирование
• 5.3 Обнаружение и исправление ошибок
• 5.3.1 Общие понятия
• 5.3.2 Линейные групповые коды
• 5.3.2 Код Хэмминга
• 5.3.3 Циклические коды
• 5.3.4 Построение и декодирование конкретных циклических кодов
• 5.4 Сжатие информации
• 5.4.1 Исключение повторения строк в последующих строках
• 5.4.2 Алгоритм lzw
• 6 Теория алгоритмов
• 6.1. Основные понятия
• 6.1.1 Основные требования к алгоритмам
• 6.1.2 Блок–схемы алгоритмов
• 6.1.3 Представление данных
• 6.1.4 Виды алгоритмов
• 6.1.5 Правильность программ
• 6.1.6 Эффективность алгоритмов
• 6.1.7 Сходимость, сложность, надежность
• 6.2 Универсальные алгоритмы
• 6.2.1 Основные понятия
• 6.2.2 Машины Тьюринга
• 6.2.3 Рекурсивные функции
• 6.2.5 Тезис Черча-Тьюринга
• 6.2.6 Проблема самоприменимости
• 6.3 Языки и грамматики
• 6.3.1 Общие понятия
• 6.3.2 Формальные грамматики
• 6.3.3 Иерархия языков
• 6.4 Параллельные вычисления
• Рекомендованная литература