Диф. зачет
Список вопросов:
- Множества и перестановки. Мультимножества и перестановки. Строки. Операции над строками.
- Комбинаторная энтропия и энтропия по Шеннону.
- Нетривиальные преобразования строк: BWT, MTF.
- Энумеративное кодирование. Общий подход.
- Энумеративное кодирование перестановок.
- Энумеративное кодирование битовых строк с фиксированной статистикой.
- Энумеративное кодирование произвольных строк с фиксированной статистикой: два подхода (мультиномиальные коэффициенты).
- Кодирование полиномом.
- Кодирование Хаффмана и его обобщение для произвольных деревьев.
- Арифметическое кодирование. Принцип.
- Арифметическое кодирование. Барицентрические координаты. Симплексы.
- Связь между системами счисления и сжатием данных.
- Словарные методы кодирования: LZ77, LZ78, LZW
- Подходы к сжатию изображений (преобразование из RGB в YUV, предикторы, квантование и т.д)
Полезную информацию для подготовки можно найти в книге «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео».