Душанбе 2026.
Задачи зачета 

1. Рассмотрим алфавит {abcdef} с весами символов
   (пропорциональными их вероятностям)
    {a:11, b:4, c:3, d:6, e:10, f:2}.
   Построить статическое кодовое дерево Хаффмана и 
   по нему вычислить коды Хаффмана для этого алфавита.
   В ответе выписать коды Хаффмана для символов
   алфавита.

2. Дана битовая последовательность
   0000000000001010110111000000000001111111111
   Закодировать ее, используя битовый алгоритм RLE.

3. Последовательность битов
   0001010010001000100101100100111100001010
   представляет собой последовательность, закодированную
   с помощью битового алгоритма RLE. Раскодировать ее.
   
4. Пусть алфавит состоит из символов {0, 1, 2, 3}
   с вероятностями {0.05, 0.45, 0.3, 0.2}, символ 0
   обозначает конец последовательности. Применяется
   алгоритм арифметического кодирования.
   Исходная последовательность символов: 
        1, 2, 2, 1, 3, 0
   Определить закодированную последовательность битов.
   
5. Пусть алфавит состоит из символов {0, 1, 2, 3}
   с вероятностями {0.05, 0.45, 0.3, 0.2}, символ 0
   обозначает конец последовательности. Применяется
   алгоритм арифметического кодирования.
   Закодированная последовательность битов:
        1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1
   Определить исходную последовательность символов
   алфавита.
   
6. В рассматриваемом варианте алгоритма кодирования
   LZW начальный словарь содержит 256 однобайтовых
   последовательностей, соответствующих кодам байтов
   от 0 до 255. Исходная последовательность байтов:
        "love is love"
   (кавычки не входят в текст), или в кодах байтов
        108, 111, 118, 101, 32, 
        105, 115, 32, 108, 111, 118, 101   
   Получить последовательность, закодированную по
   алгоритму LZW.

7. В рассматриваемом варианте алгоритма кодирования
   LZW начальный словарь содержит 256 однобайтовых
   последовательностей, соответствующих кодам байтов
   от 0 до 255. Закодированная по алгоритму LZW 
   последовательность равна
    105, 116, 32, 105, 115, 32,
    119, 104, 97, 257, 256, 258, 115
   Получить исходную последовательность.

8. В алгоритме LZ77 размер скользящего окна равен 32768,
   размер буфера предварительного просмотра равен 258.
   Исходная последовательность байтов равна
        "an eye for an eye"
   (кавычки не входят в текст), или в кодах байтов
    97, 110, 32, 101, 121, 101, 32, 102, 111, 114, 32, 
    97, 110, 32, 101, 121, 101
   Получить закодированную последовательность (троек
   чисел) по алгоритму LZ77.

9. В алгоритме LZ77 размер скользящего окна равен 32768,
   размер буфера предварительного просмотра равен 258.
   Закодрованная по алгоритму LZ77 последовательность
   равна
    (0, 0, 'a'), (0, 0, 'b'), (2, 4, 'b'), (5, 4, 'a')
   или в кодах байтов
    (0, 0, 97), (0, 0, 98), (2, 4, 98), (5, 4, 97)
   Восстановить исходную последовательность.  

10. Алфавит состоит из следующих символов:
        {a, b, c, d, e, f, g, h}.
   Для него построены коды Хаффмана с двумя 
   дополнительными условиями (как в алгоритме Deflate):
    1) более короткие коды лексикографически
       предшествуют более длинным кодам;
    2) коды равной длины идут подряд последовательно
       и соответствуют порядку символов в алфавите
       (символ, соответствующий следующему коду,
       лексикографически больше, чем текущий символ).         
   Известны длины кодов, построенных для символов
   алфавита:
   {a: 3, b: 5, c: 1, d: 4, e: 3, f: 4, g: 5, h: 4}
   
   Вычислить по этой информации коды Хаффмана
   для символов этого алфавита.
   
11. Алфавит состоит из следующих символов:
        {a, b, c, d}.
   Коды Хаффмана, которые используются в алгоритме 
   Deflate, удовлетворяют следующим двум дополнительным
   условиям:
    1) более короткие коды лексикографически
       предшествуют более длинным кодам;
    2) коды равной длины идут подряд последовательно
       и соответствуют порядку символов в алфавите
       (символ, соответствующий следующему коду,
       лексикографически больше, чем текущий символ).         
   На входе имеем последовательность:
        "abbabddbac"  
   (кавычки не входят в текст). В соответствии с частотами
   символов строится дерево и коды Хаффмана для этого
   алфавита, удовлетворяющие приведенным выше двум
   условиям. Определить коды символов этого алфавита.

12. Алфавит состоит из следующих символов:
        {a, b, c, d, e, f}.
   Для него построены коды Хаффмана с двумя 
   дополнительными условиями (как в алгоритме Deflate):
    1) более короткие коды лексикографически
       предшествуют более длинным кодам;
    2) коды равной длины идут подряд последовательно
       и соответствуют порядку символов в алфавите
       (символ, соответствующий следующему коду,
       лексикографически больше, чем текущий символ).         
   Известны длины кодов, построенных для символов
   алфавита:
   {a: 2, b: 3, c: 3, d: 3, e: 2, f: 3}

   Вычислить по этой информации коды Хаффмана
   для символов этого алфавита и получить
   закодированную последовательность битов
   для исходной последовательности
   "bdface".
   
13. Алфавит состоит из следующих символов:
        {a, b, c, d, e, f}.
   Для него построены коды Хаффмана с двумя 
   дополнительными условиями (как в алгоритме Deflate):
    1) более короткие коды лексикографически
       предшествуют более длинным кодам;
    2) коды равной длины идут подряд последовательно
       и соответствуют порядку символов в алфавите
       (символ, соответствующий следующему коду,
       лексикографически больше, чем текущий символ).         
   Известны длины кодов, построенных для символов
   алфавита:
   {a: 3, b: 1, c: 3, d: 3, e: 4, f: 4}
   
   С помощь этих кодов Хаффмана получили закодированную
   последовательность битов:
    10001000010111111101110101
   Восстановить исходную последовательность символов.
   
14. В алгоритме LZ77 размер скользящего окна равен 32768,
   размер буфера предварительного просмотра равен 258.
   Закодированная по алгоритму LZ77 последовательность
   равна
    (0, 0, 'a'), (0, 0, 'b'), (0, 0, 'c'), 
    (3, 9, 'd'), (6, 3, 'd')
   или в кодах байтов
    (0, 0, 97), (0, 0, 98), (0, 0, 99),
    (3, 9, 100), (6, 3, 100)
   Восстановить исходную последовательность.