Похожие презентации:
Презентация_Занятие5_Кодирование_Фано
1.
И Н Ф О Р М АТ И К А · 1 1 К Л А С С · П О Д Г О Т О В К А К Е Г ЭЗанятие 5
Кодирование и декодирование информации. Условие Фано
Задание 4 ЕГЭ · теория и практика для занятия
От азбуки Морзе до студенческой работы, обогнавшей профессора
2.
ПЛАН ЗАНЯТИЯДве части одного рассказа
①
Часть 1. Теория
②
Часть 2. Практика
Общий алгоритм решения задания
Морзе, Шеннон, Фано и студент Хаффман
Тип А: явное условие Фано
Где эта тема встречается в профессии
Тип Б: условие не названо явно
Условие Фано: прямое и обратное
Тип В: минимальная сумма длин
Двоичное дерево как инструмент решения
Как устроено современное задание 4
Тип Г: кодирование слова и перевод в другую
систему
Ошибки, самопроверка, лайфхаки и чек-лист
2
3.
ТЕОРИЯ · ДО СТРОГОЙ ТЕОРИИОт азбуки Морзе до предела Шеннона
1837: Сэмюэл Морзе и Альфред Вейл — частым буквам короткие
сигналы, редким — длинные. Но однозначность держится только на
паузах между буквами.
1948: Клод Шеннон в «Математической теории связи» ставит вопрос
строго — и доказывает предел экономии (энтропию источника), но
не даёт способа его достичь.
Слабое место кода Морзе: однозначность обеспечивают паузы — свойство
передачи, а не свойство самого кода.
E
T
—
A
•—
Q
——•—
частые буквы — короче, редкие — длиннее
3
4.
ТЕОР ИЯ · 1949 ГОД · ПОВОРОТНЫЙ МОМЕНТРоберт Фано и условие однозначности
Профессор MIT, коллега Шеннона, предложил практический метод
построения кода «сверху вниз».
Условие Фано: ни один код буквы не является началом
кода другой буквы — сообщение читается однозначно
слева направо, без пауз.
Метод: делим алфавит на две группы равной суммарной частоты, 0 и 1 — и
повторяем рекурсивно внутри каждой группы.
«Ни одно кодовое слово не
является началом другого»
формулировка условия Фано, MIT, 1949
Условие названо в честь Фано, хотя сам
метод построения кода вскоре обгонит его
же студент.
4
5.
Т Е О Р И Я · 1 9 5 1 – 1 9 5 2 · С Т УД Е Н Т П Р О Т И В П Р О Ф Е С С О Р АДэвид Хаффман обгоняет своего учителя
1951: Фано предлагает студентам выбор — сдать экзамен или доказать (либо опровергнуть), что его метод «сверху вниз» даёт
самый короткий код.
Хаффман почти сдаётся — и в последний момент находит другой путь: строить дерево «снизу вверх», начиная с двух самых
редких букв.
Результат — код Хаффмана: строго доказуемо оптимальный, в отличие от метода его профессора.
Метод Фано (сверху вниз)
Код Хаффмана (снизу вверх)
Делим алфавит пополам рекурсивно. Даёт условие однозначности,
но не гарантирует минимальную длину.
Объединяем две самые редкие буквы, повторяем. Доказуемо даёт
минимальную среднюю длину кода.
Условие однозначности по-прежнему носит имя Фано — он первым его сформулировал; Хаффман лишь предложил, как дешевле строить код, ему удовлетворяющий.
5
6.
Т Е О Р И Я · З АЧ Е М Э Т О И Н Ж Е Н Е Р УГде эта тема встречается в профессии
1
Сжатие данных
2
Символы кодируются 1–4 байтами переменной длины; первые
биты байта однозначно говорят декодеру, где начинается
следующий символ — то же условие Фано.
ZIP, gzip, JPEG используют код Хаффмана или его развитие —
арифметическое кодирование.
3
Сетевые протоколы
Потоковая передача данных требует мгновенно понимать конец
одной команды и начало следующей — без пауз и без взгляда
вперёд.
Кодировка UTF-8
4
История телекоммуникаций
Азбука Морзе — прямой предок всей современной кодировки
данных: сравнение показывает, почему современным протоколам
паузы уже не по карману.
6
7.
ТЕОРИЯ · ДВА УСЛОВИЯПрямое и обратное условие Фано
Прямое условие
Обратное условие
Ни одно кодовое слово не является НАЧАЛОМ
другого.
Ни одно кодовое слово не является ОКОНЧАНИЕМ
другого.
читаем СЛЕВА НАПРАВО
Пример нарушения: коды «01» и «011» — «01» является
началом «011».
читаем СПРАВА НАЛЕВО
Пример: коды «1» и «10» нарушают прямое (1 — начало 10),
но обратное выполняется (10 не оканчивается на 1).
7
8.
ТЕОРИЯ · ИНСТРУМЕНТ РЕШЕНИЯДвоичное дерево вместо перебора в уме
Занятый узел блокирует не только себя, но и всё, что растёт из него глубже — рисуйте дерево, а не держите его в уме.
старт
0
1
А (0)
1
0
10
0
Б (100)
1
11
1
своб.
«0» занимает всю левую половину — букве А отдан целиком корень поддерева
Условие Фано на дереве: если узел занят буквой — все узлы под ним закрыты для остальных букв
8
9.
Т Е О Р И Я · Ф О Р М АТ З А Д А Н И Я 4Как устроено современное задание 4
Алфавит из 4–8 букв, неравномерный двоичный код, часть кодовых слов уже дана. Нужно найти недостающий код, сумму длин или
результат кодирования целого слова.
1
Найти код буквы
кратчайшее кодовое слово при заданном (или невыясненном) условии
2
Сумма длин
минимальная суммарная длина нескольких ещё не закодированных букв
3
Кодирование слова
закодировать слово целиком и перевести результат в другую систему счисления
Не вычисление, а дисциплинированный перебор ограничений — чем длиннее код, тем важнее внешняя опора в виде рисунка.
9
10.
П Р А К Т И К А · О Б Щ А Я С Т Р АТ Е Г И ЯАлгоритм решения задания 4
1
Нарисовать дерево
отметить уже занятые ветки от заданных кодовых слов
2
Определить условие
прямое или обратное выполняется для уже заданных кодов
3
Перебрать длины
от меньшей к большей, проверяя свободные узлы
4
Выбрать наименьшее
если свободных узлов несколько — по числовому значению
5
Для суммы длин
считать общее число вырезаемых поддеревьев, а не по одной букве
Записать ответ в требуемом формате: двоичное слово, число или результат в другой системе счисления.
10
11.
П РА К Т И К А · Т И П А · Я В Н О Е УС Л О В И Е ФА Н ОКратчайшее кодовое слово
А, Б, В, Г, Д — код Фано. А=0, Б=100. Кратчайшее слово для В?
«0» занимает всю левую половину дерева. «100» — один узел третьего уровня справа.
Длина 1: «1» — начало «100», не подходит.
Длина 2: «10» — тоже начало «100», блокирован. «11» свободен и ничего не блокирует.
Ответ: 11
не является ни началом, ни продолжением слов «0» и «100»
Методический акцент: перебирайте длины строго по возрастанию — от единицы, а не наугад.
11
12.
П РА К Т И К А · Т И П Б · УС Л О В И Е Н Е Н А З В А Н О Я В Н ОПроверяем оба варианта
А, Б, В — код допускает однозначное декодирование. А=1, Б=10. Кратчайшее для В?
«1» — начало «10»: прямое условие нарушено. Проверяем обратное: «10» не оканчивается на «1» — обратное выполняется.
Значит весь код строится по обратному условию. Длина 1 не подходит («0» — окончание «10»). Длина 2: «00» не создаёт конфликтов.
Ответ: 00
код строится по обратному условию Фано
Методический акцент: без явного слова «Фано» сначала проверьте, какому условию подчиняются уже данные коды — и держитесь его.
12
13.
П РА К Т И К А · Т И П В · М И Н И М А Л Ь Н А Я С У М М А Д Л И НСчитаем место, а не буквы по очереди
А, Б, В, Г, Д, Е — код Фано. А=00, Б=01, В=100. Мин. сумма длин Г+Д+Е?
«00» и «01» полностью занимают левую половину дерева.
«100» занимает один из двух узлов третьего уровня справа — сосед «101» свободен, и вся ветка «11» (110, 111) тоже свободна.
Свободных узлов третьего уровня ровно три — их и нужно ровно три. Меньше не получится: более короткий узел «11» вместил бы только одну
букву вместо двух.
Ответ: 9
101 + 110 + 111 = 3 + 3 + 3 = 9
13
14.
П РА К Т И К А · Т И П Г · КОД И Р О В А Н И Е С Л О В АКодируем слово и переводим в другую систему
А=0, Б=100, В=101, Г=110, Д=1110, Е=1111. Слово БАГАД → восьмеричное число?
Кодируем и склеиваем без разделителей: 100+0+110+0+1110 = 100011001110 (12 бит).
12 кратно 3 — дополнять нулями не нужно. Группируем по три: 100, 011, 001, 110.
Переводим каждую группу: 100→4, 011→3, 001→1, 110→6.
Ответ: 4316
100011001110₂ = 4316₈
Частая ошибка: сбиться при группировке битов — если длина не кратна 3 (или 4 для hex), дополните нулями слева.
14
15.
П Р А К Т И К А · Ф О Р М УЛ И Р О В К И И О Ш И Б К ИФормулировка ФИПИ и типичные ошибки
«Допускает однозначное декодирование» без слова «Фано» — сигнал проверить оба условия.
!
Держать занятые и свободные узлы дерева в уме вместо того, чтобы нарисовать его
!
Забыть, что занятый узел блокирует всё дерево, растущее из него глубже
!
Подбирать буквы по очереди в задаче на сумму длин вместо оценки места целиком
!
Забыть про требование «наименьшее числовое значение» среди вариантов одной длины
!
Сбиться при группировке битов для перевода в восьмеричную/шестнадцатеричную систему
15
16.
П РА К Т И К А · С А М О П Р О В Е Р К АКак убедиться, что дерево заполнено без противоречий
Постройте полный список кодовых слов и сверьте каждую пару — вручную при небольшом алфавите, программно при большом.
def is_prefix(a, b): return b.startswith(a) and a != b
def is_suffix(a, b): return b.endswith(a) and a != b
codes = {'А':'00','Б':'01','В':'100','Г':'101','Д':'110','Е':'111'}
values = list(codes.values())
pryamoe_ok = not any(is_prefix(a,b) for a in values for b in values if a!=b)
obratnoe_ok = not any(is_suffix(a,b) for a in values for b in values if a!=b)
print('Прямое:', pryamoe_ok, ' Обратное:', obratnoe_ok)
Если условие нарушено — программа сразу покажет конкретную конфликтующую пару, а не заставит искать ошибку с нуля.
16
17.
ИТОГИ ЗАНЯТИЯЛайфхаки и чек-лист
★
Лайфхаки
✓
Чек-лист перед сдачей
Дерево, а не память — рисуйте всегда
Занятый узел блокирует всё, что глубже
☐ Дерево нарисовано, занятые узлы отмечены
Условие не названо — проверьте оба варианта
☐ Определено, какое условие выполняется
Сумма длин — считайте место целиком, не по
буквам
☐ Длины проверены по возрастанию, не наугад
Несколько вариантов — берите наименьшее
значение
Перевод в другую систему — проверьте кратность
длины
☐ Выбрано наименьшее числовое значение
☐ Для суммы длин учтено место в дереве целиком
☐ Итоговый код проверен на непротиворечивость
17
18.
СЛЕДУЮЩЕЕ ЗАНЯТИЕЗадание 8
Кодирование данных, комбинаторика, системы счисления
Снова будем считать, сколько уникальных комбинаций помещается в отведённое место — только уже без
деревьев и без условия Фано, через прямой комбинаторный подсчёт.
Спасибо за внимание!
18
Информатика