Приветствую всех, кто дошёл до этой темы и уже легко ориентируется в базовых понятиях информатики.
Понятно, что информатику сложно какими-то рамками обозначить, так как все явления жизни являются информационными потоками и практически не обходятся без автоматизированных технологий. На уроках информатики ребятам приходится с этим постоянно сталкиваться лбом и нередко критически, когда в очередной раз нужно вспомнить какие-то геометрические формулы площадей фигур, тригонометрию или свойства треугольника, либо теоремы или, например, расчёт дискриминанта с корнями, алгоритм Евклида и многое другое, чтобы написать программу. Т.е. умение программировать само по себе - это всего лишь половина дела и без знания других предметов, в частности, математики, многое практически становится невозможным в рамках школьной программы.
Я на прошлом, шестом уроке, который вызвал живой отклик, пыталась показать как знание, например, русского языка принципиально важно для корректного построения алгоритма в программе. Конечно, русский родной язык надо знать не только гуманитариям, а всем не зависимо от профиля. И это вообще не обсуждается,. Трудно представить инженера, не знающего грамматику своего языка или не умеющего грамотно говорить. Т.е. информатик по сути должен многое знать или же специализироваться в какой-либо отдельной прикладной сфере, например, экономике, строительстве, торговле… Нам, в группах подготовки к ОГЭ и ЕГЭ, порою дольше приходится в теме разбирать прикладную часть задания (чаще математическую или же русский, если формулировка задания написана на некой китайской азбуке), нежели сами способы программирования или формализации в редакторах, табличных процессорах или компиляторах. Получается, что в информатике ученик должен уметь формализовать любой информационный процесс или объект; при этом универсальность предмета делает его как популярным, так и сложным одновременно, вот и редеют группы желающих свершить подвиг и выбрать ЕГЭ по информатике. Поэтому я особо благодарна всем моим читателям и бесстрашным ученикам за ваш выбор.
Ну а теперь, смело идём дальше просто покорять непростые темы. Тема сегодняшнего урока уже частично была представлена, как теоретически, так и практически на предыдущих уроках.
Мы уже знаем, что код в ПК – уникальное явление, так как, по сути, является и формой подачи и мерой измерения информации. Благодаря чему? Тому, что в основе кода лежит бинар – 0,1, который имеет такие две функции, как единица измерения и единица хранения данных в компьютерных системах.
На практикумах 1 и 2 мы очень подробно рассмотрели, как измеряется информация на основе длины кода символьных, графических и звуковых объектов информации.
Давайте посмотрим и проанализируем , что характерно для всех этих объектов при их кодировании. То, что все коды данных объектов : вес символа, глубина цвета, шкала - глубина звука имеют одинаковую длину (разрядность) . Такая форма кодирования называется равномерной и она довольно эффективна, если вероятность использования всех кодов одинакова. Но представим с вами , что в некоем алфавите (на примере символьных объектов) какие-то символы практически не используются или применяются при автоматизации редко. Тогда возникает вопрос, а можно ли сделать в системе кодирования для таких кодов исключение и дать им одну длину, а тем, что встречаются чаще, минимальную для быстрого кодирования и декодирования в ПК. Вполне логично, так как чем короче код, тем меньше объём информации (данных) и тем выше скорость процесса. Но оказывается, что все не так однозначно, как казалось бы логически.
Разбираемся. При одинаковой длине кодов в равномерной кодовой системе коды записываются, обрабатываются и считываются по байтным адресам один за другим; порядок определяет адрес байта. А если мы изменяем длину кода до минимума – бита, например, то как разделить коды разной длины (разрядности) между собой в одной байтовой или многобайтовой записи, чтобы они были правильно интерпретированы (распознаны) в системе. Выход нашёлся. Ещё один мозг человечества придумал принцип префиксного и постфиксного неравномерного кодирования, названный в честь автора условием Фано.
Ни один код не может являться началом (префиксом) или концом (постфиксом) другого более длинного кода,
Например 01 и 010 не могут быть кодами одной системы кодирования, а коды 00 и 01 могут, хотя с нуля начинаются оба. Или, например, 001 и 0010 не могут быть кодами одной системы, а 000 и 001 могут. Т.е. одинаковый префикс (повторяющаяся начальная часть кода) в разных по длине кодах не допустим.
Система кодирования, использующая коды разной разрядности называется неравномерной.
Где в it-сфере применяется неравномерное кодирование? А прежде всего там, где необходима компрессия данных - сжатие или архивирование. В файлообменниках, где существенным является время трафика (гранзакции ) и объём пакетов передачи данных. Сжатие данных при этом - необходимый инструмент. Когда нам надо собрать разнокалиберную файловую отчётность и оправить на e-mail, архивация данных в один файл значительно упрощает передачу данных и практически незаменима. При сетевых операциях в обслуживании серверов и сетей также довольно часто используется неравномерная схема кодировки. Но в большинстве случаев всё же превалирует равномерная схема кодирования. Почему? Потому что байтовая адресация процессором считывается гораздо быстрее, чем распаковка и упаковка архивов и дешифрация неравномерных кодовых слов.
Так, например, при обратном условии Фано в схеме кодирования, код будет дешифрован лишь после полной загрузки в память, так как он считывается с конца в обратном порядке. Если при равномерном кодировании существуют индексные таблицы кодовых слов, то при неравномерном помимо таблиц анализ прямого или обратного условия кодовой записи . Поэтому не всегда короткий путь быстрее, так как он требует дополнительных временных затрат.
Скорость передачи данных канала, частота передачи, затрата на упаковку и распаковку данных, требования к трафику в сети - все это определяет рациональность использования равно или неравномерных схем кодирования. Оптимизация системы кодирования, криптография, кибер-безопасность - самые популярные направления в it и одни из самых сложных и важных в автоматизации процессов.
Итак, переходим к практикуму. Рассмотрим задания для 9 класса ОГЭ Зад.2 и 11 класса ЕГЭ Зад. 4 . На следующем 8 уроке перейдём к программированию в решении более сложных заданий по теме кодирование в среде Python для ЕГЭ 11 класса. Параллельно будем осваивать синтаксис языка программирования Python.
Задание 1. 9 класс ОГЭ.
· От разведчика было получено сообщение: 1010111010011010010
В этом сообщении зашифрован пароль – последовательность русских букв. В пароле использовались только буквы из А И К О С Т, каждая буква кодировалась двоичным словом по такой таблице. А- 10 И- 001 К- 00 О- 011 С- 101 Т- 111; расшифруйте сообщение, запишите в ответе пароль.
- Решение: 1) анализируем коды на условия Фано: сначала прямое, при котором не должны совпадать префиксы кодов разной длины: буквы А – 101 и С -10; И-001 и К-00 не могут быть при прямом кодировании; т.е. в 1010111010011010010 – 10101 можно прочитать как СА или как АС.
- Если прямое условие не подходит, значит используется в данной кодировке обратное шифрование; декодируем с конца: 10 – A; 00 –K; 101 – C; 001 – И; 101- C; 011-О; 101-C; получаем слово – СОСИСКА. Ответ: СОСИСКА
Обратите внимание, что в слове из шести предложенных букв кодовой таблицы использовались только пять, такое допустимо в подобных заданиях.
Задание 2. 9 класс ОГЭ.
· От разведчика было получено сообщение: 010011000111001
В этом сообщении зашифрован пароль – последовательность русских букв. В пароле использовались только буквы из А Б К О Р С, каждая буква кодировалась двоичным словом по такой таблице. А - 01 Б - 00 К - 110 О - 011 Р- 111 С- 010; расшифруйте сообщение, запишите в ответе пароль.
- Решение: 1) анализируем коды на условия Фано: сначала прямое, при котором не должны совпадать префиксы кодов разной длины: буквы А – 01 и О – 011; А - 01 и С- 010 не могут быть при прямом кодировании; т.е. в 010011000111001 могут быть неоднозначные дешифровки;
- Используем обратное условие Фано для дешифровки: 01 –А; 110 –К; 01-А; 00- Б; 011 –О; 010 –C, СОБАКА. Ответ: СОБАКА
Внимание! Старайтесь не угадывать шифровку в контексте, так как задание может представлять набор любых букв несуществующих слов.
Задания для 11 класса принципиально отличаются от 9 и ориентированы на создание из набора алфавита оптимизационной таблицы кодирования, дающей минимальную длину всех кодовых слов и требующей выполнения прямого условия Фано.
Для решения этих заданий самым удобным и безошибочным способом является графический, при котором используется бинарный граф-дерево. Подробней теорию графов и виды графов рассмотрим на других уроках по моделированию и формализации информационных объектов и процессов. А здесь коротко представим суть бинарного графа.. Это графическое изображение с вершинами, из которых выходит всего две вершины с весами (значениями)) 0 1. Каждая вершина уровнем выше (родитель) имеет два потомка 0 и 1; вершины без потомков – листья графа – дерева. Граф имеет иерархическую структуру.
· Задание 3. 11 класс ЕГЭ. Для кодирования некоторой последовательности, состоящей из букв А, В, С, D, E используется неравномерный двоичный код, удовлетворяющий прямому условию Фано. Кодовая таблица представлена: A-011, B-000, С-10, D-010, E-001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Запишите ответ в виде, рядом стоящих буквы и её кодового слова (кода).
· Решение: рекомендую решать графическим методом при помощи бинарного графа, но можно решить и логическим путём; 1) при логическом решении анализируем коды, начиная с самого короткого по длине, т.е. верхнего уровня; здесь это - 10. Какие ещё такой же длины коды могут быть. 00 для B – 000 и E – 001 и 01 для A-011 и D-010 не могут быть использованы по условию Фано. Так как код 10 не имеет нижестоящих кодов и веток, от него ничего не зависит и его можно сократить, заменив уровнем выше и длиной короче: c 10 на 1, тогда буква С будет иметь код 1. Ответ С1.
· графическое решение:
· Задание 4. 11 класс ЕГЭ. По каналу связи передаются зашифрованные сообщения, содержащие только пять букв: A, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Таблица кодовых слов для букв представлена: A-00, Б-01, В-100, Г-110. Укажите самое короткое кодовое слово для буквы Д, при котором код не будет удовлетворять условию Фано; при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из кодов букв A, Б, В, Г. Если таких слов несколько, то укажите слово с минимальным числовым значением.
· Решение: графическое решение: строим бинарный граф и анализируем ветки. Особенность задания в том, условие Фано не должно выполняться. Если Д присвоить 1, то условие Фано выполняется, а если присвоить 10 из незанятых вершин графа, то не выполняется, так как из этой вершины выходит код 100 буквы В с префиксом 10 ; Почему мы не выбрали 11, например? В условии задания требуется код с минимальным числовым значением. Числовые значения представляют собой переведённые из двоичных в десятичные числа. 10- это 2 в десятичной системе, а 11 -3, поэтому минимальным будет 10. Ответ: 10.
Подробно тему системы счисления рассмотрим на других уроках.
Задание 5. 11 класс ЕГЭ. По каналу связи передаются сообщения, содержащие только семь букв: A, Б, В, Г, Д. Е, Ж Для передачи используется неравномерный двоичный код. Таблица кодовых слов для букв представлена: A-00, Б-01, В-100, Г-1010, Д-10110. Укажите, какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв.
· Решение: графическое решение: строим бинарный граф и анализируем ветки. Для двух букв Е и Ж есть два варианта кодирования: 1) из свободной вершины 11 можно создать два кода: 110 и 111 для Е и Ж (в битах длина 3+3=6; 2) но можно использовать и другой метод: из вершины 1011 создать код для одной из букв - Ж, а вершину 11 присвоить Е; при этом в первом случае длина сумм кодов Е и Ж равна 6, а во втором 5; так как надо указать минимальное кол-во знаков, то выбираем второй способ. Ответ:5
· Задание 6. 11 класс ЕГЭ. По каналу связи передаются шифрованные сообщения, содержащие только девять букв: A, Б, В, Г, Д. Е, Ж, З, И. Для передачи используется неравномерный двоичный код. Таблица кодовых слов для букв представлена: A-000, Б-001, В-1110, Г-11111, Д-11000, Е-010, Ж-011, З-11001 Укажите, кратчайшее кодовое слово для буквы И, при котором соблюдается условие Фано. Если таких кодов несколько, то укажите код с наименьшим числовым значением.
· Решение: 1) решаем логически, так как графически процесс будет трудоёмким по времени для ЕГЭ; анализируем префиксы кодов, начинаем с минимального префикса 00; проверяя имеющиеся комбинации 00 в А-000; 01 в Е – 010; 11 в В- 1110; какой вариант кода из четырёх возможных (2^2) не задействован – 10; 2) может использоваться также и код 11, поскольку он стоит от кода В – 1110 и Г-11111 на ДВА и ТРИ уровня выше 3) при сравнении кодов 11 и 10 нужно выбрать минимальный по значению (при переводе из двоичной системы в десятичную); сравниваем 11 (3) и 10 (2). Ответ: 10
· Задание 7. 11 класс ЕГЭ. По каналу связи передаются шифрованные сообщения, содержащие только буквы из набора: A, Д. О, Р, С. Для передачи используется неравномерный двоичный код с условием Фано. Таблица кодовых слов для некоторых букв известна: О- 1101, Д-101. Для трёх оставшихся букв А, Р, С кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова РАССАДА, если известно, что оно закодировано минимальным количеством двоичных знаков.
· Решение: 1) при решении данного типа задач сперва анализируется слово кодирования – РАССАДА на кол-во повторов каждой буквы; так как в неравномерном кодировании, чем чаще встречается буква, тем короче должен быть её код. А-3; C-2; Д-1; Р-1;.2) затем строим бинарный граф и выделяем известные коды в нем О и Д.; 3) поскольку вершина с кодом 0 не занята в отличие от вершины 1, то А , как самой повторяющейся, даём код – 0. Следующей по частоте повтора – букве С присваиваем код 100 (длина - 3) . Присваиваем код рядом с С букве Д – 101 (длина -3); а Р присваиваем минимальный свободный код -111 (длина - 3);.4) теперь просчитаем сумму кодов слова РАССАДА: A(1*3)+C(2*3)+Д(3)+Р(3)=3+6+3+3=15. Ответ: 15
· Домашнее задание для самопроверки: По каналу связи передаются шифрованные сообщения, содержащие только семь букв: A, Б, В, Г, Д. Е, Ж. Для передачи используется неравномерный двоичный код c условием Фано. Таблица известных кодовых слов для букв представлена: A-01, Б-11, В-1010, Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв. В ответе запишите суммарную длину кодовых слов для букв: Г, Д. Е, Ж.
На следующем, 8 уроке, закончим тему кодирования разбором более сложных заданий с применением программирования на Python (ЕГЭ Зад.8) и затем, на 11-12 уроке, перейдём к нерассмотренному пока ещё нами такому типу объектов, как числа, завершив тем самым фундаментальный блок базы информатики нашего ликбеза.
Оставайтесь на канале, с нами просто постигать непростое. Спасибо за прочтение. До следующих встреч на уроках в школе Дзен.
Эта статья выходит накануне нового года, всего за несколько часов до следующей страницы нашей земной истории. Всем хочу пожелать мира, добра, энергии радости жизни, веры в невероятное и свершения всех жизненных планов!
С Новым 2025 годом!
