Дискретная математика
Покупка
Основная коллекция
Тематика:
Дискретная математика
Издательство:
Физматлит
Автор:
Редькин Николай Петрович
Год издания: 2009
Кол-во страниц: 264
Дополнительно
В учебнике представлен основной материал обязательного курса
«Дискретная математика», читающегося на механико-математическом
факультете МГУ с 1998 г. В сжатой форме он содержит для первона-
чального ознакомления ряд важных разделов дискретной математики:
комбинаторный анализ, графы и сети, важнейшие классы управляющих
систем, тесты, алгоритмы, кодирование, дискретные экстремальные
задачи. К каждой главе приведены задачи, самостоятельное решение
которых будет способствовать более глубокому усвоению теоретиче-
ского материала и лучшей подготовке к экзамену.
Для студентов и аспирантов.
Рекомендовано УМО по классическому университетскому образо-
ванию в качестве учебника для студентов высших учебных заведе-
ний, обучающихся по направлениям подготовки 010100 «Математика»,
010200 «Математика. Прикладная математика», 011000 «Механика.
Прикладная математика».
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.04: Прикладная математика
- ВО - Магистратура
- 01.04.01: Математика
- 01.04.04: Прикладная математика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
УДК 519.95 (075.8) ББК 22.18 Р 33 Р е д ь к и н Н. П. Дискретная математика. — М.: ФИЗМАТЛИТ, 2009. — 264 с. — ISBN 978-5-9221-1093-8. В учебнике представлен основной материал обязательного курса «Дискретная математика», читающегося на механико-математическом факультете МГУ с 1998 г. В сжатой форме он содержит для первоначального ознакомления ряд важных разделов дискретной математики: комбинаторный анализ, графы и сети, важнейшие классы управляющих систем, тесты, алгоритмы, кодирование, дискретные экстремальные задачи. К каждой главе приведены задачи, самостоятельное решение которых будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену. Для студентов и аспирантов. Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика», 010200 «Математика. Прикладная математика», 011000 «Механика. Прикладная математика». ISBN 978-5-9221-1093-8 c⃝ ФИЗМАТЛИТ, 2009 c⃝ Н. П. Редькин, 2009
ОГЛАВЛЕНИЕ Предисловие . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . Г л а в а I. Элементы комбинаторики . . . . . . . . . . . . . . . . . . . . 9 § 1. Комбинаторные объекты и комбинаторные числа . . . . . . . . 9 § 2. Формула включения-исключения. Производящие функции и возвратные последовательности . . . . . . . . . . . .. . . . . . . . . 12 Г л а в а II. Графы и сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 § 1. Элементы графа. Подграфы. Способы задания графов . . . . 19 § 2. Геометрическая реализация графов. Верхняя оценка числа неизоморфных графов с m рёбрами . . . . . . . . . . . . . . . . . . . 22 § 3. Деревья. Характеристические свойства деревьев . . . .. . . . . 23 § 4. Верхняя оценка числа неизоморфных корневых деревьев с m рёбрами . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 26 § 5. Теорема Кэли о числе деревьев с занумерованными вершинами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 § 6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 29 § 7. Сети. Потоки в сетях. Теорема Форда–Фалкерсона . . . . . . 32 Г л а в а III. Булевы функции и формулы . . . . . . . . . . . . . . . . 40 § 1. Булевы функции. Элементарные булевы функции. . . . . . . . 40 § 2. Формулы и функции, реализуемые формулами. Простейшие эквивалентности . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 42 § 3. Разложение булевых функций. Дизъюнктивные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 § 4. Полнота систем булевых функций. Представление булевых функций полиномами Жегалкина . . . . . . . . . . . . . . . . . . . . 47 § 5. Функции k-значной логики . . . . . . . . . . . . . . . . . . . . . . . . 49
Оглавление
Г л а в а IV.
Предикаты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 1. Высказывания,
предикаты,
кванторы.
Геометрический
смысл кванторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 2. Модель, сигнатура модели, формулы в модели. Свободные
и связанные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 3. Истинность формулы в модели, на множестве. Тождественно истинные формулы . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
56
§ 4. Эквивалентность формул. Правила преобразования формул
с кванторами. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
57
§ 5. Приведённые формулы . . . . . . . . . . . . . . . .. . . . . . . . . . . .
60
§ 6. Нормальные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
Г л а в а V.
Схемы из функциональных элементов. Синтез и
оценки сложности схем. . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
§ 1. Схемы из функциональных элементов в базисе {&, ∨,− } . .
65
§ 2. Синтез схем с использованием совершенных д.н.ф. . . . .. . .
69
§ 3. Метод Шеннона . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
70
§ 4. Асимптотически оптимальный метод синтеза схем (метод
Лупанова) . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
72
§ 5. Мощностной метод получения нижней оценки для сложности схем . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
75
Г л а в а VI.
Тесты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 1. Полные диагностические тесты для таблиц. Оценки длины
тестов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 2. Тесты для схем. Построение минимальных тестов методом
Яблонского . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
§ 3. Верхние оценки длины единичных тестов для схем . . . . .. .
88
§ 4. Синтез легкотестируемых схем . . . . . . . . . . . .. . . . . . . . . .
89
Г л а в а VII.
Ограниченно-детерминированные
функции
и
реализация их автоматами . . . . . . . . . . . . . . . . . . . . . . . . .
92
§ 1. Детерминированные
и
ограниченно-детерминированные
функции . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
92
§ 2. Способы задания ограниченно-детерминированных функций. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .
97
§ 3. Схемы автоматов из функциональных элементов и элементов задержки . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
99
Оглавление Г л а в а VIII. Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 § 1. Алгоритмы. Машины Тьюринга. Задание машины системой команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 § 2. Композиции машин. Тезис Тьюринга . . . . . . . . . . . . . . . . . 105 § 3. Проблема самоприменимости. Теорема о самоприменимости 106 Г л а в а IX. Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 § 1. Алфавитное кодирование. Разделимые коды. Свойство префикса . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 109 § 2. Неравенство Крафта–Макмиллана. . . . . . . . . . .. . . . . . . . . 112 § 3. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 115 § 4. Самокорректирующиеся коды. Коды Хэмминга. . . . . . . . . . 120 § 5. Геометрические свойства самокорректирующихся кодов. Оценки Хэмминга и Гильберта . . . . . . . . . . . . . . . . . . . . . . 123 Г л а в а X. Дискретные экстремальные задачи . . . . . . . . . . . . 127 § 1. Задача на покрытие. Точное решение задачи на покрытие 127 § 2. Градиентный алгоритм поиска приближённого решения. Оценка сложности градиентного покрытия. . . . . . . . .. . . . . . 129 § 3. Задача о минимальном остовном дереве. . . . . . . . .. . . . . . . 133 § 4. Поиск кратчайшего и надёжного путей в графе . . . . . . . . . 135 § 5. Точное решение задачи на покрытие методом динамического программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 § 6. Приближённое решение задачи об упаковке в контейнеры 141 § 7. Классы P и NP. Полиномиальная сводимость задач . . . . . 143 Зaдачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 151 К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 155 К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 160 К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 164 К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 171
Оглавление Ответы, указания, решения . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 175 К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 186 К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 203 К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 224 К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 254 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Светлой памяти моего учителя Олега Борисовича Лупанова посвящается Предисловие Эта книга возникла на основе годового обязательного курса лекций по дискретной математике, читающегося автором на механико-математическом факультете Московского государственного университета им. М. В. Ломоносова для студентов четвёртого курса отделения механики. Главная задача курса — обучение характерным для дискретной математики методам решения основных задач и соответствующему мышлению. Необходимость такого обучения диктуется научно-техническим прогрессом, поставившим перед математиками две крупные проблемы, которые часто оказываются взаимосвязанными. Одна из них — изучение сложных управляющих систем, разработка методов анализа и синтеза таких систем. Другая проблема — необходимость решения ряда новых задач, главной спецификой которых является дискретность. Такие задачи в настоящее время сплошь и рядом возникают как в теории, так и на практике — в экономике, технике, исследовании операций и т. п., а решение их даже с использованием мощной вычислительной техники часто наталкивается на принципиальные, порой непреодолимые затруднения, связанные с неприемлемо большими затратами машинного времени и памяти. Вошедший в курс материал достаточно условно можно разбить на две части. Одну из них составляют основные понятия, описания изучаемых объектов и доказательства ключевых фактов, теорем, ставших большей частью уже классическими. Сюда относятся: элементы комбинаторики, графы и сети, булевы функции и формулы, предикаты, алгоритмы, кодирование, частично — дискретные экстремальные задачи. Эта часть составляет основу того математического аппарата, владение которым в настоящее
Предисловие время представляется совершенно необходимым для выпускников математических факультетов. В другой части представлены важнейшие классы управляющих систем — схемы из функциональных элементов и автоматы, а также типовые задачи, связанные с синтезом и диагностикой состояния этих систем, и основные способы решения таких задач; здесь часто используются понятия, математические модели и теоремы из первой части. Приведены и типичные, наиболее известные дискретные экстремальные задачи, точные и приближенные решения этих задач, примеры получения оценок качества приближенных решений. Успешное, пусть даже начальное изучение дискретной математики вряд ли возможно без приобретения навыков решения подходящих задач, связанных с основными математическими моделями и теоремами. Для приобретения таких навыков освоение теоретического материала должно сопровождаться практическими занятиями. Для занятий к каждой главе книги прилагаются задачи различной степени трудности. Решение этих, а также, возможно, и других подходящих задач необходимо для глубокого и прочного усвоения теоретического материала. Содержание данной книги, стиль изложения материала в значительной степени определяются научно-педагогической школой кафедры дискретной математики механико-математического факультета МГУ им. М. В. Ломоносова, основателем и бессменным руководителем которой на протяжении четверти века был выдающийся математик и педагог, академик РАН Олег Борисович Лупанов.
Г л а в а I
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
§ 1. Комбинаторные объекты и комбинаторные числа
В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества A = {a1, ... , an},
и числовые характеристики этих объектов. Часто рассматриваются, например, упорядоченные или неупорядоченные подмножества множества A, подмножества с повторяющимися элементами
из множества A и т. п. Вместе с классами таких комбинаторных объектов естественным образом вводятся и так называемые
комбинаторные числа, задающие число объектов в том или ином
классе и зависящие от некоторых параметров, например, от мощностей исходного множества A и рассматриваемых подмножеств
множества A.
Размещения элементов. Пусть A = {a1, ... , an}. Размещением элементов из A по k (или размещением из n элементов
по k) называется упорядоченное подмножество из k элементов
множества A.
Для A = {a1, a2, a3, a4} размещениями из A по 3 будут, например, {a1, a3, a4}, {a3, a4, a1}, {a2, a3, a4}.
Обозначим число размещений из n элементов по k через (n)k.
При построении конкретного размещения первым элементом в
нём можно взять любой из n элементов множества A, вторым
элементом — любой из n − 1 оставшихся в A элементов и т. д.
Поэтому
(n)k = n(n − 1) ... (n − k + 1) при 1 ⩽ k ⩽ n.
При k > n не существует размещений из n по k, следовательно,
(n)k = 0 при k > n; при k = 0 полагаем (0)0 = (n)0 = 1. Нетрудно
заметить, что для чисел (n)k выполняются тождества:
(n)k =n(n − 1)k−1,
(n)k =(n)k−1 · (n − k + 1).
Гл. I. Элементы комбинаторики
Перестановки элементов. Перестановками элементов множества A = {a1, ... , an} (или перестановками из n элементов)
называются всевозможные упорядоченные множества из n элементов a1, ... , an.
Для A = {a1, a2, a3} перестановками будут, например, {a1, a3,
a2}, {a2, a1, a3}, {a2, a3, a1}.
Перестановки из n элементов — частный случай размещений
из n элементов по n. Поэтому
(n)n = n(n − 1) ... 2 · 1 = n!
Как обычно, полагаем 0! = 1.
Сочетания элементов. Сочетанием элементов из A = {a1, ...
... , an} по k (или сочетанием из n элементов по k) называется
неупорядоченное подмножество из k элементов множества A.
Для A = {a1, a2, a3} всевозможными сочетаниями по 2 элемента будут {a1, a2}, {a1, a3}, {a2, a3}.
В сочетании, в отличие от размещения, порядок следования
элементов не учитывается. Поэтому из одного сочетания (из n
элементов по k) получается k! размещений. Отсюда для числа
n
k
сочетаний из n элементов по k получается формула
n
k
= (n)k
k!
= n(n − 1) ... (n − k + 1)
k!
=
n!
k!(n − k)!
(0 ⩽ k ⩽ n; вместо
n
k
часто используется также обозначение Ck
n). Из последней формулы следует
0
0
=
n
0
=
n
n
= 1 и
n
k
=
n
n − k
.
Для случая k > n полагаем
n
k
= 0, поскольку при k > n не существует сочетаний из n элементов по k.
Числа
n
k
фигурируют в функциональном тождестве, называемом формулой для бинома Ньютона:
(1 + x)n =
n
0
+
n
1
x + ... +
n
k
xk + ... +
n
n
xn.
(1)
В правой части данного тождества коэффициент при xk есть количество способов, которыми можно выбрать из k скобок (1 + x)
переменную x, а из остальных скобок 1, что даёт ровно
n
k
слагаемых.
§ 1. Комбинаторные объекты и комбинаторные числа
Полагая в (1) x = 1, получим тождество
n
0
+
n
1
+ ... +
n
k
+ ... +
n
n
= 2n;
(2)
при x = −1 получим
n
0
−
n
1
+ ... + (−1)n
n
n
= 0.
(3)
Из соотношений (2) и (3) следуют тождества
n
0
+
n
2
+ ... +
n
n
=
n
1
+
n
3
+ ... +
n
n − 1
= 2n−1
при чётном n и
n
0
+
n
2
+ ... +
n
n − 1
=
n
1
+
n
3
+ ... +
n
n
= 2n−1
при нечётном n.
Сочетания с повторениями элементов. Сочетанием с повторениями элементов из A = {a1, ... , an} по k (или сочетанием
с повторениями из n элементов по k) называется неупорядоченный набор из k элементов множества A, в котором элементы
могут повторяться.
Для A = {a1, a2, a3} всевозможными сочетаниями с повторениями по 2 элемента будут (a1, a1), (a1, a2), (a1, a3), (a2, a2),
(a2, a3), (a3, a3).
Обозначим через Hk
n число сочетаний с повторениями из n
элементов по k; найдём это число.
Пусть a — произвольное сочетание с повторениями элементов
из A = {a1, ... , an} по k. Этому сочетанию поставим в соответствие набор α(a) длины n + k − 1 из n − 1 нулей и k единиц.
В наборе α(a) число единиц, находящихся между (i − 1)-м и i-м
нулями (i = 2, ... , n − 1), равно числу элементов ai, входящих
в сочетание a, а число единиц, стоящих перед первым нулём (после последнего нуля), равно числу элементов a1 (соответственно
элементов an), входящих в сочетание a. Указанное соответствие
между сочетаниями a и наборами α(a) взаимно однозначно.
Различных наборов длины n + k − 1, содержащих n − 1 нулей
и k единиц, имеется ровно
n+k−1
k
штук, поскольку каждому
такому набору можно взаимно однозначно сопоставить сочетание
из n + k − 1 элементов по k. В итоге получаем
Hk
n =
n + k − 1
k
.