Редькин Н.П. Дискретная математика. - СПб, 2003. - 96 с.
Учебное пособие содержит основной материал обязательного курса "Дискретная математика", включающего 34 часа лекций и столько же практических занятий и читающегося на отделении механики механико-математического факультета МГУ с 1998 года. В нем в сжатой форме представлены для первоначального ознакомления несколько важных разделов дискретной математики: комбинаторный анализ; графы и сети; важнейшие классы управляющих систем - формулы алгебры логики, схемы из функциональных элементов, конечные автоматы; кодирование; примеры дискретных экстремальных задач и способов их решения. К каждой главе прилагаются задачи, самостоятельное решение которых, несомненно, будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену. Для студентов и аспирантов.
ОГЛАВЛЕНИЕ
Глава I. Элементы комбинаторики...........................5
§ 1. Комбинаторные объекты и комбинаторные числа...........5
§ 2. Формула включения-исключения.
Производящие функции и возвратные последовательности... 7
Глава II. Графы и сети.................................... 13
§ 1. Элементы графа. Подграфы. Способы задания графов...... 13
§ 2. Геометрическая реализация графов. Верхняя оценка числа
неизоморфных графов с n рёбрами...................... 16
§ 3. Деревья. Характеристические свойства деревьев.......... 17
§ 4. Верхняя оценка числа неизоморфных
корневых деревьев с n рёбрами......................... 19
§ 5. Теорема Кэли о числе деревьев
с занумерованными вершинами.........................20
§ 6. Двудольные графы. Паросочетания и трансверсали.
Критерий существования трансверсали (теорема Холла)..........22
§ 7. Сети. Потоки в сетях. Теорема Форда и Флакерсона о
максимальной величине потока в сети...................24
Глава III. Булевы функции и формулы.......................30
§ 1. Булевы функции. Табличное задание булевых функций. Существенные и фиктивные переменные булевых функций.
Элементарные булевы функции.........................30
§ 2. Формулы и функции, реализуемые формулами.
Простейшие эквивалентности..........................32
§ 3. Размножение булевых функций по переменным.
Дизъюнктивные нормальные формы.....................34
§ 4. Полнота систем булевых функций. Примеры полных систем.
Представление булевых функций полиномами Жегалкина........ 36
§ 5. Функции k-значной логики.............................37
Глава IV. Схемы из функциональных элементов.
Синтез и оценки сложности схем........................
§ 1. Схемы n функциональных элементов в базисе {&, V, -}......39
§ 2. Синтез схем с использованнем д.н.ф.....................41
§ 3. Метод Шеннона......................................43
§ 4. Асимптотически оптимальный метод синтеза схем
(метод Лупанова).....................................45
§ 5. Мощностный метод получения нижней оценки
для сложности схем...................................47
Глава V. Ограниченно-детерминированные функции
и реализация их автоматами............................50
§ 1. Детерминированные и ограниченно-детерминированные
функции............................................. 50
§ 2. Способы задания о.-д. функций.........................54
§ 3. Схемы автоматов из функциональных элементов
и элементов задержки.................................56
Глава VI. Кодирование ....................................57
§ 1. Алфавитное кодирование..............................57
§ 2. Неравенство Крафта-Макмиллана.......................60
§ 3. Коды с минимальной избыточностью. Оптимальное
кодирование Хаффмена................................62
§ 4. Самокорректирующиеся коды. Коды Хэмминга............67
§ 5. Геометрические свойства кодов Хэмминга. Оценки числа
кодовых слов в коде, исправляющем р ошибок............69
Глава VIL Дискретные экстремальные задачи................72
§ 1. Задача на покрытие. Точное решение задачи на покрытие ... 72
§ 2. Градиентный алгоритм поиска приближённого решения задачи на покрытие. Оценка сложности градиентного покрытия. Отклонение градиентного покрытия от
минимального........................................73
§ 3. Задача о минимальном остовном дереве..................77
§ 4. Поиск кратчайшего и надёжного путей в графе............78
Задачи..................................................82
Список литературы......................................96
