Описание:1. Оценки сумм биномиальных коэффициентов. Энтропийное неравенство. Неравенство Чернова.
2. Метод производящих функций. Решение линейных рекуррентных соотношений. Число неприводимых многочленов над конечным полем. Производящие
функции множеств и действия с ними. Теорема Пойа о сумме весов классов
эквивалентности.
3. Графы. Основные понятия и определения. Перечисление графов. Асимптотика числа графов на n вершинах. Теорема Холла. Теорема Менгера. Теорема
Дилуорса.
4. Раскраски графов. Теорема Брукса. Теорема Визинга.
5. Булевы функции. Реализация функций формулами. Нормальные формы. Полные системы булевых функций. Критерий Поста полноты системы булевых
функций.
6. Схемы из функциональных элементов. Вычисление булевых функций схемами.
Простейшие оценки сложности и глубины функций. Сложность систем линейных булевых функций.
7. Метод Лупанова синтеза схем. Оценка числа схем с данными сложностью, числом входов и выходов. Мощностной метод получения нижних оценок сложности
схем. Сложность вычисления частичных булевых функций.
8. Средняя сложность вычисления булевых функций. Простейшие оценки средней
сложности булевых функций. Средняя сложность почти всех булевых функций
n переменных. Сравнение средней и схемной сложности.
9. Алфавитное кодирование. Метод Хаффмана. Оценки стоимости побуквенного
кодирования. Блочное кодирование. Оценки стоимости блочного кодирование.
Универсальное блочное кодирование и его стоимость.
10. Коды, исправляющие ошибки. Линейные коды. Код Хемминга. Оценки мощности и скорости максимального кода. Граница Варшамова–Гилберта.
11. Прямая и обратная теоремы Шеннона о кодировании в двоичном симметричном
канале.
12. Двоичные БЧХ-коды. Исправление ошибок в БЧХ-кодах. Полиномиальные коды. Скорость и размерность БЧХ-кодов.
13. Недвоичные БЧХ-коды. Коды Рида-Соломона. Граница Синглтона. Каскадные
коды.