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