Дискретная математика. Алгоритмы: теория и практика

                 С. М. Авдошин, А. А. Набебин



Дискретная математика.
      Алгоритмы:
   теория и практика





                    Москва, 2019

УДК 510.6+519.1+519.7
ББК 22.12
     А18


                      Р е ц е н з е н т ы:
   Калягин В. А. — доктор физико-математических наук, профессор НИУ ВШЭ
           Петренко А. К. — доктор технических наук, профессор,
          заведующий отделом «Технологии программирования»
     Института системного программирования им. В. П. Иванникова РАН

               Н а у ч н ы й р е д а к т о р:
            Захаров В. А. — доктор физико-математических наук,
                  профессор МГУ им. М. В. Ломоносова





     Авдошин С. М., Набебин А. А.
А18  Дискретная математика. Алгоритмы: теория и практика. – М.: ДМК Пресс,
      2019. – 282 с.: ил. 
    ISBN 978-5-97060-688-9

         Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики.
       Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые вари       анты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста,
       нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов
       (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы,
       паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто
       используемые в практике алгоритмы на графах. Рассматриваются классические комбинаторные
       конфигурации и их производящие функции, рекуррентные последовательности.
       В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная
       математика» на факультете бизнес-информатики, на факультете компьютерных наук Националь       ного исследовательского университета Высшая школа экономики и на факультете автоматики
      и вычислительной техники Национального исследовательского университета Московский энер       гетический институт.
         Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01
      «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии»,
        09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ       специалистов и разработчиков программных продуктов.

                              УДК  510.6+519.1+519.7
                               ББК  22.12

         Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
      бы то ни было форме и какими бы то ни было средствами без письменного разрешения вла       дельцев авторских прав.

                                         ©  Авдошин С. М., Набебин А. А., 2019
                                         ©  Оформление, издание, ДМК Пресс, 2019

       Содержание




Предисловие.............................................................................................................................9

Введение.................................................................................................................................... 11
1. Множество................................................................................................................................. 11
2. Функция..................................................................................................................................... 12
3. Отношение................................................................................................................................. 14
4. Отношение эквивалентности.............................................................................................. 15
5. Каноническое разложение функции................................................................................. 16
6. Мощность множества. Счетные и несчетные множества.......................................... 17
7. Мощность континуума.......................................................................................................... 18
8. Кардинальные числа. Сравнение мощностей................................................................ 19

Часть I. ТЕОРИЯ АЛГОРИТМОВ............................................................................... 23

Глава 1. Частично рекурсивные функции...................................................... 24
1.1. Арифметические функции и операции над ними..................................................... 24
1.2. Примитивно рекурсивные функции............................................................................. 25
1.3. Функции, представимые термами.................................................................................. 27
1.4. Конечная сумма и произведение..................................................................................... 29
1.5. Примитивно рекурсивные предикаты.......................................................................... 31
1.6. Ограниченные кванторы................................................................................................... 31
1.7. Ограниченный оператор µ................................................................................................ 32
1.8. Подстановка функций в предикат.................................................................................. 33
   1.8.1. Кусочное задание функции....................................................................................... 34
   1.8.2. Примитивная рекурсивность некоторых функций и предикатов.............. 35
1.9. Частично рекурсивные функции.................................................................................... 36

Глава 2. Машины Тьюринга........................................................................................ 38
2.1. Вычисления на машинах Тьюринга............................................................................... 38
2.2. Синтез машин Тьюринга................................................................................................... 40
   2.2.1. Композиция машин..................................................................................................... 40
   2.2.2. Ветвление машин......................................................................................................... 41
   2.2.3. Итерация машины....................................................................................................... 43
2.3. Машины Тьюринга в однобуквенном алфавите........................................................ 45
2.4. Правильно вычислимые функции................................................................................. 49
   2.4.1. Суперпозиция правильно вычислимых функций............................................ 49
   2.4.2. Примитивная рекурсия правильно вычислимых функций.......................... 50

4    Содержание

   2.4.3. Минимизация правильно вычислимых функций............................................ 50
   2.4.4. Правильная вычислимость частично рекурсивных функций...................... 51
2.5. Частичная рекурсивность правильно вычислимых функций.............................. 51
   2.5.1. Геделева нумерация ситуаций машины Тьюринга........................................... 52
   2.5.2. Функции программы машины Тьюринга............................................................ 53
   2.5.3. Функции вычисления по программе машины Тьюринга.............................. 53
   2.5.4. Функция ситуаций машины Тьюринга................................................................ 55
2.6. Универсальная частично рекурсивная функция....................................................... 57
   2.6.1. Геделева нумерация машин Тьюринга.................................................................. 57
   2.6.2. Функции ситуации машины Тьюринга с номером k....................................... 58
   2.6.3. Построение универсальной функции................................................................... 60
2.7. Теорема Клини о неподвижной точке и теорема Райса.......................................... 63
2.8. Сложность алгоритмов....................................................................................................... 64

Глава 3. Рекурсивная перечислимость и разрешимость................. 68
3.1. Общерекурсивные функции и предикаты................................................................... 68
3.2. Нумерации наборов натуральных чисел...................................................................... 70
   3.2.1. Нумерации пар натуральных чисел....................................................................... 70
   3.2.2. Нумерация наборов натуральных чисел длины k............................................. 72
   3.2.3. Нумерация конечных последовательностей натуральных чисел............... 73
3.3. Рекурсивно перечислимые множества......................................................................... 74
3.4. Рекурсивно перечислимые множества наборов натуральных чисел................. 76
3.5. Общерекурсивные предикаты......................................................................................... 78
3.6. Общерекурсивные множества наборов натуральных чисел................................. 80
3.7. Функции с рекурсивно перечислимым графиком................................................... 81
3.8. Примеры алгоритмически неразрешимых проблем................................................ 87
3.9. Варианты уточнения понятия алгоритма.................................................................... 89
   3.9.1. Ассоциативные исчисления..................................................................................... 89
   3.9.2. Системы подстановок Туэ......................................................................................... 90
   3.9.3. Алгоритмическая неразрешимость проблемы тождества
  полугрупп и логики предикатов........................................................................................ 91
   3.9.4. Грамматики..................................................................................................................... 95
   3.9.5. Продукции Поста......................................................................................................... 96
   3.9.6. Нормальные алгоритмы Маркова.......................................................................... 97
   3.9.7. Операторные алгоритмы........................................................................................... 98

Глава 4. Гедель о неполноте формальных систем.................................. 99
4.1. Аксиоматическая арифметика......................................................................................... 99
4.2. Алгоритмическая неразрешимость содержательной арифметики...................103
4.3. Алгоритмическая неразрешимость логики предикатов второго порядка......107
4.4. Нумерическая выразимость...........................................................................................108

                                                     Содержание    5

Часть II. АЛГОРИТМЫ НА ГРАФАХ.......................................................................112
Глава 5. Способы задания графов......................................................................113
5.1. Графы, мультиграфы, псевдографы.............................................................................113
5.2. Задание графов....................................................................................................................115
5.3. Операции над графами.....................................................................................................117
5.4. Маршруты, цепи, циклы, связность.............................................................................117
   5.4.1. Алгоритм построения кратчайшей цепи в графе ...........................................119
   5.4.2. Алгоритм поиска кратчайшего пути в ориентированном графе...............120

Глава 6. Обходы графов..............................................................................................127
6.1. Эйлеровы графы.................................................................................................................127
6.2. Алгоритм построения эйлерова цикла........................................................................128
6.3. Полные циклы и последовательности де Брюйна..................................................132
6.4. Гамильтоновы графы.........................................................................................................134
6.5. Коды Грея..............................................................................................................................135

Глава 7. Деревья................................................................................................................137
7.1. Деревья и лес........................................................................................................................137
7.2. Характеристические свойства деревьев.....................................................................137
7.3. Каркасы и хорды в связном графе................................................................................140

Глава 8. Циклы в графах..............................................................................................142
8.1. Линейное пространство двоичных наборов..............................................................142
8.2. Линейное пространство подграфов данного графа................................................143
8.3. Подпространство четных подграфов...........................................................................144
8.4. Циклический ранг графа.................................................................................................147
8.5. Матричная теорема о деревьях......................................................................................150

Глава 9. Двудольные графы и паросочетания.........................................151
9.1. Двудольные графы.............................................................................................................151
9.2. Паросочетания.....................................................................................................................152
9.3. Алгоритм построения совершенного паросочетания
для двудольного графа.............................................................................................................154
9.4. Системы различных представителей..........................................................................155
9.5. Сети Петри...........................................................................................................................159
   9.5.1. Описание сети Петри................................................................................................159
   9.5.2. Определение сети Петри.........................................................................................160

Глава 10. Планарные графы....................................................................................165
10.1. Плоские графы..................................................................................................................165
10.2. Формула Эйлера для плоских графов......................................................................166

6    Содержание

10.3. Критерий планарности Понтрягина–Куратовского............................................168
10.4. Алгоритм построения плоского изображения графа..........................................168

Глава 11. Раскраска графов....................................................................................172
11.1. Хроматическое число и хроматический класс.......................................................172
11.2. Раскраска вершин............................................................................................................172
11.3. Верхняя и нижняя оценки хроматического числа...............................................173
   11.3.1. Внутренне устойчивые множества вершин графа.......................................173
   11.3.2. Алгоритм вычисления всех наибольших внутренне
  устойчивых множеств вершин графа.............................................................................174
   11.3.3. Внешне устойчивые множества вершин графа.............................................175
   11.3.4. Алгоритм вычисления всех наименьших внешне устойчивых
  множеств вершин графа......................................................................................................176
11.4. Оптимальная раскраска вершин графа....................................................................177
11.5. Раскрашивание планарных графов............................................................................178

Глава 12. Потоки в транспортных сетях.........................................................181
12.1. Двухполюсные сети.........................................................................................................181
12.2. Дивергенция......................................................................................................................182
12.3. Потоки в сетях...................................................................................................................183
12.4. Сечения в сетях.................................................................................................................184
12.5. Величина потока и пропускная способность сети................................................185
12.6. Максимальный поток.....................................................................................................186
   12.6.1. Алгоритм Форда–Фалкерсона ..........................................................................187
   12.6.2. Помечивающий алгоритм Форда–Фалкерсона............................................191

Глава 13. Перечисление графов..........................................................................196
13.1. Число помеченных графов............................................................................................196
13.2. Графы и группы подстановок.......................................................................................197
   13.2.1. Группы подстановок и лемма Бернсайда.........................................................197
   13.2.2. Теорема Пойа.............................................................................................................201
   13.2.3. Раскраска вершин куба..........................................................................................204
   13.2.4. Составление ожерелий..........................................................................................206

Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ.......................................................209
Глава 14. Порождение комбинаторных конфигураций
и их пересчет........................................................................................................................210
14.1. Размещения, перестановки, сочетания.....................................................................210
14.2. Правило суммы и правило произведения...............................................................211
14.3. Подсчет числа размещений, перестановок, сочетаний.......................................211
   14.3.1. Число размещений и перестановок без повторений...................................211

                                                     Содержание    7

   14.3.2. Число размещений с повторениями..................................................................212
   14.3.3. Число сочетаний без повторений.......................................................................212
   14.3.4. Число сочетаний с повторениями......................................................................212
   14.3.5. Число перестановок данной спецификации..................................................213
   14.3.6. Число размещений данной спецификации.....................................................213

Глава 15. Производящие функции для комбинаторных
конфигураций и для их чисел.................................................................................215
15.1. Аппарат формальных степенных рядов...................................................................215
15.2. Производящие функции для сочетаний..................................................................216
   15.2.1. Сочетания без повторений...................................................................................216
   15.2.2. Сочетания с повторениями с ограничениями
  на число повторений............................................................................................................217
   15.2.3. Сочетания с повторениями без ограничений
  на число повторений............................................................................................................218
15.3. Производящие функции для размещений с повторениями.............................219
15.4. Числа Стирлинга, Белла, Каталана...........................................................................221

Глава 16. Комбинаторно-логический аппарат.........................................223
16.1. Включения и исключения.............................................................................................223
16.2. Приложения формулы включений и исключений...............................................226
   16.2.1. Задача о беспорядках..............................................................................................226
   16.2.2. Задача о встречах.....................................................................................................227

Глава 17. Рекуррентные последовательности........................................228
17.1. Конечные разности..........................................................................................................228
17.2. Рекуррентные уравнения..............................................................................................230
17.3. Линейные рекуррентные уравнения с переменными
коэффициентами........................................................................................................................231
17.4. Метод Лагранжа вариации произвольных постоянных вычисления
частного решения неоднородного уравнения..................................................................238
17.5. Линейные рекуррентные уравнения с постоянными
коэффициентами........................................................................................................................243

Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры.........................................................................................249
18.1. Отношение частичного порядка.................................................................................249
18.2. Топологическая сортировка вершин бесконтурного орграфа..........................252
18.3. Решетки...............................................................................................................................253
18.4. Изоморфизм решеток.....................................................................................................255
18.5. Булевы алгебры................................................................................................................256

8    Содержание

Приложения...........................................................................................................................261
1. Графы.........................................................................................................................................261
2. Комбинаторика.......................................................................................................................268

Литература.............................................................................................................................276

Обозначения.........................................................................................................................279

Предисловие





Теория алгоритмов имеет древнюю историю. Одна из основных задач математики – поиски алгоритмов для решения класса однотипных задач. Интуитивно алгоритм есть правило, способ, рекомендация, предписание, инструкция, программа
для решения любой задачи из данного класса однотипных задач. Известен, например, алгоритм поиска наибольшего общего делителя двух натуральных чисел,
алгоритм решения системы линейных алгебраических уравнений, другие алгоритмы. Задачи по разысканию алгоритмов продолжаются и поныне. Безуспешные
длительные поиски некоторых алгоритмов привели к мысли, что дело тут не в недостатке изобретательности человеческого ума, а в отсутствии этих алгоритмов.
Исследование вопроса об алгоритмически неразрешимых проблемах предполагает уточнение понятия алгоритма, его точное определение. Анализ уже известных
алгоритмов позволил выделить его основные черты: 1) массовость, то есть алгоритм должен решать бесконечную серию однотипных задач; 2) детерминированность, то есть при любых обстоятельствах один и тот же алгоритм, примененный
к одному и тому же объекту, должен давать один и тот же результат; 3) эффективность, то есть число шагов работы алгоритма конечно; при этом мы принимаем
абстракцию потенциальной осуществимости: вычислительный процесс может
продолжаться как угодно долго, но он обязан остановиться через конечное число
шагов. На основании этих черт было дано точное определение алгоритма.
 Мы подробно опишем два наиболее часто используемых уточнения понятия
алгоритма: частично рекурсивная функция и машина Тьюринга. Будет построена
частично рекурсивная функция, универсальная для класса всех частично рекурсивных функций, и приведены некоторые примеры алгоритмически неразрешимых проблем.
  Книга написана по материалам лекций авторов по дисциплинам «Дискретная
математика» и «Математическая логика и теория алгоритмов», читаемых на факультете бизнес-информатики, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете
автоматики и вычислительной техники Национального исследовательского университета Московский энергетический институт. Эти курсы (или им аналогичные) начинали в МЭИ Д. А. Поспелов, В. Н. Вагин, В. П. Кутепов, А. А. Болотов,
А. Б. Фролов, Е. А. Щегольков, повлиявшие на выбор и характер излагаемого авторами материала.
  Настоящая книга является третьей в серии задуманных авторским коллективом книг по дискретной математике. Она предназначается студентам бакалавриата, изучающим академический курс «Дискретная математика».
  В предлагаемой книге авторы сосредоточились на изложении основ теории алгоритмов, комбинаторики, теории графов и связанных с ними практических алгоритмов.

10    Предисловие

  Основные теоретические и практические положения, изложение и анализ практических алгоритмов, иллюстрируемых большим числом примеров, позволят
сформировать прочную теоретическую базу, необходимую для дальнейшей работы практикующих программистов и ИТ-специалистов.
  В приложении предлагаются задачи, которые могут быть использованы как для
проведения практических занятий, так и для самостоятельной работы.
  Авторы выражают глубокую  благодарность рецензентам  В. А.  Калягину,
А. К. Петренко и научному редактору книги Захарову В. А. за замечания, позволяющие существенно улучшить качество книги. Мы также благодарны преподавателям департамента программной инженерии НИУ ВШЭ Р. З. Ахметсафиной,
Е. Н. Бересневой, М. К. Горденко, Е. М. Гринкругу, Л. В. Дворянскому, К. Ю. Дегтяреву, А. А. Каленковой, И. А. Ломазовой, В. В. Подбельскому, В. В. Шилову, а также
А. А. Амосову, В. Н. Вагину, Ю. А. Дубинскому, А. Б. Фролову из НИУ МЭИ за
стимулирующие беседы. Авторы благодарят студентов Е. Д. Сапожкова, Н. И. Чичелеву за активное участие в составлении и апробации задач и упражнений приложения.