Что проверяется:
Умение кодировать и декодировать информацию.
2.1. Двоичное кодирование. Равномерные и неравномерные коды. Декодирование сообщений, записанных с помощью неравномерных кодов. Условие Фано. Построение однозначно декодируемых кодов с помощью дерева
2.4. Умение строить код, обеспечивающий наименьшую возможную среднюю длину сообщения при известной частоте символов
Что нужно знать:
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
· выполнение одного из условий Фано достаточно, но не необходимо для однозначного декодирования;
· если в условии задачи утверждается, что код удовлетворяет условию Фано, имеется в виду прямое условие Фано: ни одно кодовое слово не совпадает с началом другого кодового слова; если утверждается, что код допускает однозначное декодирование, то нужно проверять как прямое, так и обратное условия Фано.