М.: МГУ Мехмат, 2007. -259 с.
Учебное пособие содержит материалы лекций и семинарских занятий, составивших обя-
зательный полугодовой курс дискретной математики, прочитанный автором студентам
четвертого курса механико-математического факультета Московского государственного
университета им. М.В. Ломоносова. Для студентов и аспирантов.
Содержание
Комбинаторные числа и тождества
Перестановки, размещения, сочетания
Бином Ньютона
Формула включений и исключений
Факториальные степени
Метод траекторий
Задачи
Оценки комбинаторных функций
Оценки n!
Формула Стирлинга
Биномиальные коэффициенты
Суммы биномиальных коэффициентов
Задачи
Производящие функции
Линейные рекуррентные последовательности
Число неприводимых многочленов
Производящие функции множеств
Задачи
Теорема Пойа
Действие групы на множестве
Лемма Бернсайда
Цикловой индекс
Функции и их классы эквивалентности
Основная теорема
Задачи
Графы
Основные понятия и определения
Теорема Холла
Теорема Менгера
Теорема Дилуорса
Раскраски вершин
Раскраски ребер
Задачи
Булевы функции
Булев куб
Булевы функции
Формулы
Нормальные формы
Задачи
Полные системы булевых функций
Замкнутые классы булевых функций
Монотонные булевы функции
Критерий полноты
Задачи
Сложность булевых функций
Программы и схемы
Схемы
Свойства минимальных схем
Примеры
Задачи
Быстрые схемы
Сложение
Вычисление суммы нескольких целых чисел
Умножение
Сортировка
Задачи
Универсальные методы синтеза схем
Метод Шеннона
Метод Лупанова
Нижние мощностные оценки
Частичные функции
Монотонные функции
Задачи
Средняя сложность булевых функций
Неветвящиеся программы с условной остановкой
Примеры
Средняя сложность почти всех функций
Средняя vs. максимальная сложность
Задачи
Алфавитное кодирование
Разделимые и префиксные коды
Оптимальные коды
Стоимость кодирования
Блочное кодирование
Универсальное блочное кодирование
Задачи
Коды, исправляющие ошибки
Двоичный симметричный канал
Параметры и простейшие свойства кодов
Линейные коды
Теорема Шеннона
Хорошие коды
Задачи
Линейные коды
Коды Хемминга
Коды Рида–Маллера
Декодирование кодов Рида–Маллера
Коды Боуза–Чоудхури–Хоквингема
Декодирование БЧХ-кодов
Задачи
Полиномиальные коды
Полиномиальные БЧХ-коды
Размерность примитивных БЧХ-кодов
Скорость примитивных БЧХ-кодов
Задачи
Недвоичные коды
Определения и свойства
Недвоичные БЧХ-коды
Коды Рида–Соломона
Каскадные коды
Задачи
Конечные поля
Циклические группы
Кольца
Кольцо многочленов
Поле многочленов
Структура конечного поля
Литература
