Чашкин А.В. Лекции по дискретной математике

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