Редькин Н.П. Дискретная математика ОНЛАЙН

Редькин Н.П. Дискретная математика. — СПб, 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

загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: