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