Дискретная математика - В учебнике представлен основной материал обязательного курса «Дискретная математика», читающегося на механико-математическом факультете МГУ с 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. Полиномиальная сводимость задач Задачи Ответы, указания, решения Литература
На ierixon.ru представлены учебники для разных классов, которые Вы можете скачать понравившийся учебник себе на компьютер. Здесь вы найдете последние новинки учебных пособий, а также всегда можете приобрести учебники уже вышедшие в продажу. Все учебники расположенные на сайте представлены абсолютно бесплатно и в ознакомительных целях. Также все пособия в хорошем качестве.
