Новиков Ф.А. Дискретная математика для программистов (860615), страница 2
Текст из файла (страница 2)
Комбинаторика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.3. Биномиальные коэффициенты5.3.1. Элементарные тождества7147147147148149149150150150151152153153154156159160161161163164165166167168168170171171172173174175175176177178179180180180181182182183184184•. .1851861881881888Содержание 85.3.2. Бином Ньютона5.3.3. Свойства биномиальных коэффициентов5.3.4.
Треугольник Паскаля1891901915.3.5. Генерация подмножеств1925.3.6. Мультимножества и последовательности1935.3.7. Мультиномиальные коэффициенты1945.4. Разбиения1955.4.1. Определения1955.4.2. Числа Стирлинга второго рода1965.4.3. Числа Стирлинга первого рода1975.4.4. Число Белла1975.5. Включения и исключения1975.5.1. Объединение конфигураций1985.5.2. Формула включений и исключений1985.5.3.
Число булевых функций, существенно зависящих от всех своих переменных . .2005.6. Формулы обращения2005.6.1. Теорема обращения2005.6.2. Формулы обращения для биномиальных коэффициентов2015.6.3. Формулы для чисел Стирлинга2025.7. Производящие функции2035.7.1. Основная идея2035.7.2.
Метод неопределённых коэффициентов2035.7.3. Числа Фибоначчи2045.7.4. Числа Каталана205Комментарии207Упражнения207Глава 6 . Кодирование6.1. Алфавитное кодирование6.1.1. Таблица кодов6.1.2. Разделимые схемы6.1.3. Префиксные схемы6.1.4. Неравенство Макмиллана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.4. Сжатие данных6.4.1. Сжатие текстов6.4.2.
Предварительное построение словаря6.4.3. Алгоритм Лемпела-Зива6.5. Шифрование6.5.1. Криптография6.5.2. Шифрование с помощью случайных чисел6.5.3. Криптостойкость6.5.4. Модулярная арифметика208210210210211211214214215216217219221221223224225227227228229231231232233233Содержание96.5.5. Шифрование с открытым ключом6.5.6. Цифровая подписьКомментарииУпражнения235237238238Глава 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.2.6. Эксцентриситет и центр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. Транзитивное замыканиеКомментарииУпражнения240240240242243243244244246246246247249249249250250250252252255255255256257257258260260261262263263Глава 8 . Связность8.1. Компоненты связности8.1.1.
Объединение графов и компоненты связности8.1.2. Точки сочленения, мосты и блоки8.1.3. Вершинная и рёберная связность8.1.4. Оценка числа рёбер8.2. Теорема Менгера8.2.1. Непересекающиеся цепи и разделяющие множества8.2.2. Теорема Менгера в «вершинной форме»8.2.3. Варианты теоремы Менгера8.3. Теорема Холла8.3.1. Задача о свадьбах8.3.2. Трансверсаль8.3.3. Совершенное паросочетание26526526526626726826927027127327327327327410Содержание 108.3.4. Теорема Холла — формулировка и доказательство8.4. Потоки в сетях8.4.1. Определение потока8.4.2.
Разрезы8.4.3. Теорема Форда-Фалкерсона8.4.4. Алгоритм нахождения максимального потока8.4.5. Связь между теоремой Менгера и теоремой Форда-Фалкерсона8.5. Связность в орграфах6.5.1. Сильная, односторонняя и слабая связность8.5.2. Компоненты сильной связности6.5.3. Выделение компонент сильной связности8.6. Кратчайшие пути6.6.1. Длина дуг6.6.2. Алгоритм Флойда6.6.3. Алгоритм Дейкстры8.6.4. Дерево кратчайших путей6.6.5.
Кратчайшие пути в бесконтурном орграфеКомментарииУпражнения274275276277277279281281282282283284264285286286289291291Глава 9 . Деревья9.1. Свободные деревья9.1.1. Определения9.1.2. Основные свойства деревьев9.1.3. Центр дерева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.3.5. Представление бинарных деревьев9.3.6. Обходы бинарных деревьев9.3.7. Алгоритм симметричного обхода бинарного дерева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.4.11. Балансировка деревьев9.5. Кратчайший остов9.5.1. Определения9.5.2. Схема алгоритма построения кратчайшего остова292292292293297297297299300302303303305307306309312313313314314315316317316320321322323325327327328Содержание19.5.3. Алгоритм Краскала9.5.4. Алгоритм ПримаКомментарииУпражнения329330331332Глава 1 0 . Циклы, независимость и раскраска33310.1.
Фундаментальные циклы и разрезы33310.1.1. Циклы и разрезы10.1.2. Фундаментальная система циклов и циклический ранг10.1.3. Фундаментальная система разрезов и коциклический ранг10.1.4. Подпространства циклов и коциклов10.2. Эйлеровы циклы10.2.1. Эйлеровы графы10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе10.2.3. Оценка числа эйлеровых графов10.3. Гамильтоновы циклы10.3.1.
Гамильтоновы графы10.3.2. Задача коммивояжёра33333533733834034034134234334334410.4. Независимые и покрывающие множества34510.4.1. Покрывающие множества вершин и рёбер34510.4.2. Независимые множества вершин и рёбер34610.4.3. Связь чисел независимости и покрытий34710.5. Построение независимых множеств вершин34810.5.1. Постановка задачи отыскания наибольшего независимого множества вершин 34810.5.2. Поиск с возвратами34910.5.3. Улучшенный перебор35010.5.4. Алгоритм построения максимальных независимых множеств вершин35210.6.
Доминирующие множества35310.6.1. Минимальное и наименьшее доминирующее множество35310.6.2. Доминирование и независимость35310.6.3. Задача о наименьшем покрытии35410.6.4. Связь задачи о наименьшем покрытии с другими задачами35510.7. Раскраска графов35510.7.1. Оценки хроматического числа35610.7.2. Хроматические числа графа и его дополнения35710.7.3. Точный алгоритм раскрашивания .35810.7.4. Приближённый алгоритм последовательного раскрашивания35910.7.5.
Улучшенный алгоритм последовательного раскрашивания36010.8. Планарность36110.8.1, Укладка графов36110.8.2, Эйлерова характеристика36110.8.3, Теорема о пяти красках363Комментарии364Упражнения364Указатель основных обозначений365Список литературы368Предметный указатель370Предисловие к третьемуизданиюВ 2000 году издательство «Питер» выпустило первое издание этого учебника.В то время выбор учебной литературы по дискретной математике был небогат.За последние годы ситуация резко изменилась.
Переведено достаточное количество добротных американских учебников и несколько отличных книг написанороссийскими авторами. Тем не менее предлагаемый учебник по-прежнему имеетморальное право на существование, поскольку комбинация основных отличительных особенностей (компактность изложения, плюс широта охвата материала,плюс внимание к деталям программной реализации), по мнению автора, остаётсяпривлекательной для широкой категории читателей.Третье издание книги имеет ту же структуру, последовательность изложения исистему обозначений, что и второе издание. В книгу внесено несколько десятков не очень объёмных, по существенных добавлений, уточнений и определений.Обновлены упражнения, библиография и комментарии к ней.Кроме того, исправлено несколько сотен опечаток, упущений и ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
