URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Редькин Н.П. Дискретная математика
Id: 108097
 
510 руб.

Дискретная математика

2009. 264 с. Твердый переплет. ISBN 978-5-9221-1093-8.

 Аннотация

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

Для студентов и аспирантов.

Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика», 010200 «Математика. Прикладная математика», 011000 «Механика. Прикладная математика».


 Оглавление

Предисловие

Глава I. Элементы комбинаторики

§ 1. Комбинаторные объекты и комбинаторные числа

§2. Формула включения-исключения. Производящие функции и возвратные последовательности

Глава П. Графы и сети

§1. Элементы графа. Подграфы. Способы задания графов

§2. Геометрическая реализация графов. Верхняя оценка числа неизоморфных графов с та рёбрами

§3. Деревья. Характеристические свойства деревьев

§4. Верхняя оценка числа неизоморфных корневых деревьев с т рёбрами

§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. Геометрические свойства самокорректирующихся кодов. Оценки Хэмминга и Гильберта

Глава X. Дискретные экстремальные задачи

§ 1. Задача на покрытие. Точное решение задачи на покрытие

§2. Градиентный алгоритм поиска приближённого решения. Оценка сложности градиентного покрытия

§3. Задача о минимальном остовном дереве

§4. Поиск кратчайшего и надёжного путей в графе

§5. Точное решение задачи на покрытие методом динамического программирования

§6. Приближённое решение задачи об упаковке в контейнеры

§7. Классы Р и NP. Полиномиальная сводимость задач

 
© URSS 2016.

Информация о Продавце