Дискретная математика, Редькин Н.П., 2009

Дискретная математика, Редькин Н.П., 2009.

   В учебнике представлен основной материал обязательного курса «Дискретная математика», читающегося на механико-математическом факультете МГУ с 1998 г. В сжатой форме он содержит для первоначального ознакомления ряд важных разделов дискретной математики: комбинаторный анализ, графы и сети, важнейшие классы управляющих систем, тесты, алгоритмы, кодирование, дискретные экстремальные задачи. К каждой главе приведены задачи, самостоятельное решение которых будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену.
Для студентов и аспирантов.
Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика», 010200 «Математика. Прикладная математика», 011000 «Механика. Прикладная математика».




Двудольные графы. Паросочетания и трансверсали. Теорема Холла.
Граф называется двудольным, если существует такое разбиение множества его вершин на два непересекающихся подмножества (на две доли), что концы каждого ребра принадлежат разным подмножествам (разным долям; как и при рассмотрении деревьев, здесь мы ограничиваемся неориентированными графами).
Произвольное подмножество попарно несмежных рёбер графа (взятых вместе со своими вершинами) называется паросочетанием (или независимым множеством рёбер).

Отметим, что паросочетания могут рассматриваться в произвольных графах (не обязательно двудольных). Но весьма часто паросочетания естественным образом возникают и рассматриваются в двудольных графах. (С построением паросочетаний в двудольном графе связано много самых разных задач. Типичный пример — задача о назначении на должности.)
Установим критерий существования паросочетания, покрывающего долю вершин в двудольном графе.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава I. Элементы комбинаторики.
§1. Комбинаторные объекты и комбинаторные числа.
§2. Формула включения-исключения. Производящие функции и возвратные последовательности.
Глава II. Графы и сети.
§1. Элементы графа. Подграфы. Способы задания графов.
§2. Геометрическая реализация графов. Верхняя оценка числа неизоморфных графов с m рёбрами.
§3. Деревья. Характеристические свойства деревьев.
§4. Верхняя оценка числа неизоморфных корневых деревьев с m рёбрами.
§5. Теорема Кэли о числе деревьев с занумерованными вершинами.
§6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла.
§7. Сети. Потоки в сетях. Теорема Форда-Фалкерсона.
Глава III. Булевы функции и формулы.
§1. Булевы функции. Элементарные булевы функции.
§2. Формулы и функции, реализуемые формулами. Простейшие эквивалентности.
§3. Разложение булевых функций. Дизъюнктивные нормальные формы.
§4. Полнота систем булевых функций. Представление булевых функций полиномами Жегалкина.
§5. Функции k-значной логики
Глава IV. Предикаты.
§1. Высказывания, предикаты, кванторы. Геометрический смысл кванторов.
§2. Модель, сигнатура модели, формулы в модели. Свободные и связанные переменные.
§3. Истинность формулы в модели, на множестве. Тождественно истинные формулы.
§4. Эквивалентность формул. Правила преобразования формул с кванторами.
§5. Приведённые формулы.
§6. Нормальные формулы.
Глава V. Схемы из функциональных элементов. Синтез и оценки сложности схем.
§1. Схемы из функциональных элементов в базисе {&, V, -}.
§2. Синтез схем с использованием совершенных д.н.ф.
§3. Метод Шеннона.
§4. Асимптотически оптимальный метод синтеза схем (метод Лупанова).
§5. Мощностной метод получения нижней оценки для сложности схем.
Глава VI. Тесты.
§1. Полные диагностические тесты для таблиц. Оценки длины тестов.
§2. Тесты для схем. Построение минимальных тестов методом Яблонского.
§3. Верхние оценки длины единичных тестов для схем.
§4. Синтез легкотестируемых схем.
Глава VII. Ограниченно-детерминированные функции и реализация их автоматами.
§1. Детерминированные и ограниченно-детерминированные функции.
§2. Способы задания ограниченно-детерминированных функций.
§3. Схемы автоматов из функциональных элементов и элементов задержки.
Глава VIII. Алгоритмы.
§1. Алгоритмы. Машины Тьюринга. Задание машины системой команд.
§2. Композиции машин. Тезис Тьюринга.
§3. Проблема самоприменимости. Теорема о самоприменимости.
Глава IX. Кодирование.
§1. Алфавитное кодирование. Разделимые коды. Свойство префикса.
§2. Неравенство Крафта-Макмиллана.
§3. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена.
§4. Самокорректирующиеся коды. Коды Хэмминга.
§5. Геометрические свойства самокорректирующихся кодов.
Оценки Хэмминга и Гильберта.
Глава Х. Дискретные экстремальные задачи.
§1. Задача на покрытие. Точное решение задачи на покрытие.
§2. Градиентный алгоритм поиска приближённого решения. Оценка сложности градиентного покрытия.
§3. Задача о минимальном остовном дереве.
§4. Поиск кратчайшего и надёжного путей в графе.
§5. Точное решение задачи на покрытие методом динамического программирования.
§6. Приближённое решение задачи об упаковке в контейнеры.
§7. Классы Р и NP. Полиномиальная сводимость задач.
Задачи.
К главе I.
К главе II.
К главе III.
К главе IV.
К главе V.
К главе VI.
К главе VII.
К главе VIII.
К главе IX.
К главе Х.
Ответы, указания, решения.
К главе I.
К главе II.
К главе III.
К главе IV.
К главе V.
К главе VI.
К главе VII.
К главе VIII.
К главе IX.
К главе Х.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Дискретная математика, Редькин Н.П., 2009 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Редькин