Косточка А.В. Дискретная математика. Часть 2

Новосибирск: НГУ, 2001. — 56 с.Вторая часть курса лекций по Дискретной математике, читаемый на физическом факультете, факультете информационных технологий Новосибирского государственного университета и техническом факультете ВКИ НГУ.Алгоритмы и их сложность.
Понятие сложности алгоритмов.
Поиск по графу.
Быстрая сортировка.
Идея динамического программирования на примере распределительной задачи и обратной к ней.
Задача о кратчайшем пути.
Метод ветвей и границ на примере задачи коммивояжёра.
Потоки в сетях.
Сети и потоки в них.
Теорема о максимальном потоке и минимальном разрезе.
Алгоритмы для нахождения максимального потока.
Использование сетевых моделей для нахождения связности графов. Теорема Менгера и теорема Уитни.
Задача о наибольшем паросочетании в двудольном графе как задача о максимальном потоке. Теорема Кёнига и Дилворта.
Симплекс-метод решения задач линейного программирования.
Матроиды.
Кодирование.
Задачи и понятия теории кодирования.
Проверка однозначности декодирования.
Префиксные коды.
Коды с минимальной избыточностью.
Самокорректирующие коды.