Дискретная математика - В учебнике представлен основной материал обязательного курса «Дискретная математика», читающегося на механико-математическом факультете МГУ с 1998 г. В сжатой форме он содержит для первоначального ознакомления ряд важных разделов дискретной математики: комбинаторный анализ, графы и сети, важнейшие классы управляющих систем, тесты, алгоритмы, кодирование, дискретные экстремальные задачи. К каждой главе приведены задачи, самостоятельное решение которых будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену. Для студентов и аспирантов. Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика», 010200 «Математика. Прикладная математика», 011000 «Механика. Прикладная математика».
Название: Дискретная математика Автор: Редькин Н. П. Издательство: Физматлит Год: 2009 Страниц: 262 Формат: PDF Размер: 11,0 МБ ISBN: 978-5-9221-1093-8 Качество: Отличное Язык: Русский
Содержание:
Предисловие Глава 1. Элементы комбинаторики § 1. Комбинаторные объекты и комбинаторные числа § 2. Формула включения-исключения. Производящие функции и возвратные последовательности Глава 11. Графы и сети § 1. Элементы графа. Подграфы. Способы задания графов § 2. Геометрическая реализация графов. Верхняя оценка числа неизоморфных графов с m рёбрами § 3. Деревья. Характеристические свойства деревьев § 4. Верхняя оценка числа неизоморфных корневых деревьев с m рёбрами § 5. Теорема Кэли о числе деревьев с занумерованными вершинами § 6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла § 7. Сети. Потоки в сетях. Теорема Форда-Фалкерсона Глава III. Булевы функции и формулы § 1. Булевы функции. Элементарные булевы функции §2. Формулы и функции, реализуемые формулами. Простейшие эквивалентности § 3. Разложение булевых функций. Дизъюнктивные нормальные формы § 4. Полнота систем булевых функций. Представление булевых функций полиномами Жегалкина § 5. Функции k-значной логики Глава IV. Предикаты § 1. Высказывания, предикаты, кванторы. Геометрический смысл кванторов § 2. Модель, сигнатура модели, формулы в модели. Свободные и связанные переменные § 3. Истинность формулы в модели, на множестве. Тождественно истинные формулы § 4. Эквивалентность формул. Правила преобразования формул с кванторами § 5. Приведённые формулы § 6. Нормальные формулы Глава У. Схемы из функциональных элементов. Синтез и оценки сложности схем § 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. Полиномиальная сводимость задач Задачи Ответы, указания, решения Литература
