XXI Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Кодирование информации. Номера 4, 7 и 11 из ЕГЭ по информатике

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Черкасина Е.А. 1

---

1МБОУ ОЦ "ФЛАГМАН"

Лашина Т.С. 1

---

1МБОУ ОЦ "ФЛАГМАН"

Работа в формате PDF

161.8 KB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

ВВЕДЕНИЕ

Проблема: кодирование информации важная тема для понимания и дальнейшей работы в сфере IT, также знания данной темы понадобиться для решения 3-х заданий из ЕГЭ по информатике, и формулы из тем по кодированию информации понадобятся в комбинаторике. Поэтому знание темы «Кодирование информации» важно для специалиста в заданной сфере, и нужно для успешной сдачи ЕГЭ (так как, чтобы получить 100 баллов на ЕГЭ по информатике, нужно решить все задания без исключения (в отличии от таких экзаменов как профильная математика, где есть возможность ошибиться)).

Цель: Изучить тему «Кодирование информации» и разобрать задания из ЕГЭ по информатике, связанные с этой темой.

Задачи:

• Самостоятельно изучить раздел «Кодирование информации»

• Научиться решать сначала базовые задания, связанные с это темой

• Начать работу с более сложными заданиями (из ЕГЭ и Статград)

• Разобрать и отсортировать все виды заданий

• Изучить информацию по решению данных номеров

• Сделать подробный разбор некоторых видов этого задания

• Собрать всю информацию и отсортировать

• Сделать презентацию по итогам работы, продемонстрировать ее сдающим ЕГЭ

Актуальность: без знаний темы «Кодирование информации» не будет возможности решить три номера из ЕГЭ, и следовательно можно упустить возможность получить максимальный балл.

Этапы:

• Сентябрь-октябрь 2022, этап 1 – мотивационный.

Результатом этого этапа является формулирование темы и цели проекта.

• Ноябрь-декабрь 2022, этап 2 – теоретико-исследовательский.

Результатом этого этапа стал сбор, анализ, и обобщение материала про ЕГЭ по информатике и разновидности 27 задания.

• Апрель 2023, этап 3 – практический.

Гипотеза: В действительности задания на кодирование информации не являются сложными, их решение требует только знания формул и алгоритма решения.

Объект исследования: задачи на тему «Кодирование информации».

Предмет исследования: применение задач на тему «Кодирование информации» в рамках ЕГЭ по информатике (в заданиях №4, №7, №11).

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Структура и изменения ЕГЭ 2023 по информатике

1. 1. Изменения в ЕГЭ по информатике 2023

Последние 2 года ЕГЭ по информатике проводился в компьютерной форме, что предоставляло сдающим большое право выбора, как решать то или иное задание, благодаря чему появлялись лазейки, упрощающие решения некоторых номеров из экзамена. 

В связи с этим, ФИПИ ежегодно вносят изменения в КИМ по информатике, чтобы внести больше разнообразия и избавиться от шаблонных решений. В 2023 году полностью претерпят структуру 2 задания, но это не все изменения, что ФИПИ представили в новой демоверсии ЕГЭ. 

1. 2. Долой переборное решение!

В блоке «Программирование» даже после перехода на компьютерную форму было два задания, в которых программа уже представлена в условии, а задача сдающего — проанализировать ее — задания №6 и 22. Но многие справедливо подумали – зачем анализировать код, если я могу его переписать и запустить переборное решение. Благодаря этому, почти все, кто знал о таком варианте решения заданий, законно получали 2 балла за них. ФИПИ такой способ решения вряд ли понравился. 

Официальный список изменений выглядит следующим образом: 

1. Задание 6 в 2023 году будет посвящено анализу алгоритма для конкретного исполнителя, определению возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов.

2. Задание 22 призвано привлечь внимание к параллельному программированию, технологиям организации многопроцессорных / многопоточных вычислений.
   Это задание будет выполняться с использованием файла, содержащего информацию, необходимую для решения задачи.

ФИПИ об изменениях в ЕГЭ по информатике 2023:

«Задание №6 теперь мы будем относить к блоку «Алгоритмизация», так как теперь оно предоставляет нам работу с исполнителем и анализом алгоритма. В демоверсии вам предлагают проанализировать «Черепашку», которая многим знакома из ОГЭ по информатике»

«Задание №22 пополняет ряды блока «Информационные модели», а также заданий, к которым прилагаются дополнительные файлы, если быть точнее — электронная таблица. В условии затрагивается новая для экзамена тема – многопоточность (довольно важная тема для многих IT-специалистов и затрагивается на определенных предметах в университете), а решение требует анализа таблицы и зависимостей процессов»

Кроме двух новых заданий, некоторые номера также претерпели изменения: 

Задание №14 все еще направлено на работу с системами счисления, но теперь нужно искать неизвестную цифру числа. Такого прототипа ранее на ЕГЭ мы не видели.

Задание №12, ​судя по демоверсии, станет сложнее — это уже знакомый для экзамена исполнитель «Редактор», но с необычным вопросом (раньше, в основном, требовалось назвать получившуюся после обработки программой строку/сумму цифр строки).

Задание №16 на рекурсию из демоверсии намекает нам на то, что не стоит забывать про аналитическое решение. Это происходит из-за больших аргументов у функции, гораздо проще поразмыслить, что же считает функция.

1. 3. О структуре экзамена

В ЕГЭ по-прежнему осталось 27 заданий с кратким ответом. За задания 1-25 можно получить по 1 первичному баллу, а за задания 26 и 27 — по 2 балла. Максимальный возможный результат — 29 первичных баллов.

Все задания школьникам нужно решить за 3 часа 55 минут.

На экзамене встретятся задания по программированию, логике, алгоритмизации, на работу с информационными моделями, а также на кодирование информации.

В каждом блоке есть определенные темы, которые нужно знать:

Программирование

Программирование встречается в шести заданиях — а именно в 16, 17, 24, 25, 26 и 27. Чтобы справиться с ними достаточно хорошо знать только один язык программирования. Нужно уметь работать с массивом, строками, файлами, знать алгоритмы сортировки и другие не менее важные алгоритмы работы с числами.

Логика

Логика встречается в заданиях 2 и 15. Чтобы успешно справиться с этими заданиями, нужно знать основные логические операции и их таблицы истинности, уметь преобразовывать и анализировать выражения.

Алгоритмизация

В данный блок входят семь заданий (5, 6, 12, 19, 20, 21 и 23). Для решения этих заданий нужно уметь работать с различными алгоритмами и исполнителями. Важно понимать теорию игр — определять выигрывающего игрока, выигрышную позицию, различать понятия заведомо проигрышной и выигрышной позиций.

Благодаря возможности использовать инструменты компьютера, многие из этих заданий также можно решать с помощью написания программы или построения электронной таблицы.

Информационные модели

С заданиями 1 и 13 ученики обычно справляются хорошо. Чтобы их решить, нужно уметь работать с графами и таблицами и знать пару простых методов. С заданием 10 проблемы возникают редко, так как от вас требуется найти количество определенных слов в текстовом документе. Задания 3, 9 и 18 требуют работы с электронными таблицами, при решении вам помогут знания про ссылки, функции и фильтры. К этому же блоку добавляется новое задание 22. 

Информация и ее кодирование

Задания этого блока достаточно разнообразны. Вы встретите алгоритмы перевода чисел в различные системы счисления, условие Фано, формулы, единицы измерения информации и комбинаторику. Все это разнообразие встречается в заданиях 4, 7, 8, 11, 14, а также может пригодится в заданиях на программирование.  А новый прототип задания 14 на работу с системами счисления и вовсе можно решить с помощью программы.

1. 4. Шкала оценивания

На самом деле шкала перевода баллов составляется после проведения экзаменов, так как в формуле есть параметр «среднее значение». То есть то, что мы называем шкалой — это результат перевода баллов прошлого года. ФИПИ переводит баллы по формуле, а не по шкале. Поэтому шкала меняется, если меняется экзамен или массово меняются результаты его прохождения. Мы полагаем, что в 2023 году проходной балл будет 40 вторичных баллов, но это может измениться.

1. 5. Какой формат заданийна ЕГЭ по информатике 2023?

На ЕГЭ 2023, как и в 2021 году, все задания будут с кратким ответом, больше не нужно писать подробные объяснения по теории игр и сдавать программный код на проверку на бумаге. Но это не значит, что все задания идентичны. Посмотрим, какие именно типы заданий встретятся на экзамене.

Задания, которые можно решить «вручную»

Хотя ЕГЭ по информатике и проходит в компьютерной форме, в КИМах по-прежнему остаются задания, которые можно решать, как на бумаге, так и на компьютере. Это задания 1, 2, 4-8, 11-15, 19-23, в них необходимо получить число или последовательность букв в ответе. Можно написать программу на компьютере или использовать электронные таблицы, а затем записать в ответ получившееся значение. За каждое задание можно получить 1 балл.

Задания, которые решаются с помощью компьютера

Все такие задания бывают трех типов:

1. Работа с предложенным файлом

2. Создание программы

3. Написание программы и получение ответа, используя предложенный файл

Работать только с предложенным файлом нужно в заданиях №3, №9, №10, №18 и №22. Чтобы решить эти задания, нужно знать, какие функции есть у текстовых редакторов и редакторов электронных таблиц, а также теория по реляционным базам данных. За каждое задание можно получить по 1 баллу.

Задание №25 заключается в том, чтобы написать код и получить на выходе ответ. Даны начальные данные, которые будут указаны в самом задании.

Задания, где нужно написать программу и считать информацию из файла — это 17, 24, 26 и 27. Эффективность и способ решения, который вы использовали, не проверяется. Главное — получить верный численный ответ. За задания 17 и 24 вы можете получить по 1 баллу, а за задания 26 и 27 — по 2 первичных балла.

В некоторых прототипах заданий 17, 24, 25, 26 и 27 программу можно не писать, если ты знаешь, как решить эти задания другим способом — это не запрещено.

3. ПРАКТИЧЕСКАЯ ЧАСТЬ

   1. ГЛАВА 1

      1. Кодирование информации

1 бит – наименьшая единица измерения информации

1 байт = 8 бит = 2³ бит

1 Кбайт = 1024 байта = 2¹⁰ байта = 2¹³ бит

1 Мбайт = 1024 Кбайта = 2¹⁰ Кбайт = 2²³ бит

1 Гбайт = 1024 Мбайта = 2¹⁰ Мбайт = 2³³ бит

Кодирование — это преобразование инструкции в форму, удобную для хранения, передачи, обработки. Алфавит, которым обычно кодируют информацию содержит не большое количество символов, но за счет комбинирования этих символов можно получить большее количество вариантов.

Алфавит — это набор знаков.

Мощность — это количество символов в алфавите.

Бит — это двоичная цифра (Binary digit – двоичная цифра).

ВАЖНО! Код не является числом! Следовательно в кодах нет незначащих нулей. Все символы важны. Незначащие нули (которые можно отбросить), бывают только у чисел. Коды - это не числа (хоть и похожи). Поэтому коды 00101 и 101 не будут одинаковыми (хотя числа 00101=101).

Формула количества целых чисел в отрезке от a до b.

n = b – a + 1

Основная формула информатики.

Смотря на таблицу можно сделать вывод:

Если i=1 бит, то N=2;

Если i=2 бит, то N=4;

Если i=3 бит, то N=8;

Исходя из этих данных можно вывести формулу:

N=2ⁱ

где:

i – длина кода, бит

N – количество кодов/мощность алфавита (количество цветов в палитре, количество уровней звука, количество сигналов)

2 — так как двоичная система счисления

ПРИМЕРЫ:

1. i=5 бит, следовательно N=32

2. N=256, следовательно i=8 бит

3. N=10, следовательно i=4 бита (берем с запасом)

4. Закодировать 10 цифр двоичным кодом: тогда N=10; i=4.

0 — 0000

1 — 0001

2 — 0010

3 — 0011

4 — 0100

5 — 0101

6 — 0110

7 — 0111

8 — 1000

9 — 1001

С помощью составленной кодировки можно будет закодировать:

25 — 00100101

или декодировать:

01110001 — 71

5. Сколько различных комбинаций можно построить, используя четыре двоичных разряда?

Двоичный разряд = двоичная цифра = бит

Следовательно i=4, тогда N=2ⁱ=2⁴=16

6. В соревнованиях участвуют 215 атлетов. Какое минимальное количество бит необходимо, чтобы закодировать номер каждого атлета?

N=215, тогда 215=2ⁱ, тогда i=8

7. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно бы было передать 200 разных сигналов?

А=2; N=200, следовательно 200=2ⁱ, тогда i=8 (лампочек)

Расширенная формула.

N=Aⁱ

где:

N – что (количество символов в алфавите, который кодируем)

А – чем (количество символов в алфавите, которым кодируем)

i – длина кода

ПРИМЕР:

Световое табло состоит из лампочек, каждая из которых может находиться в одном из состояний: «включено», «выключено» или «мигает». Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно бы было передать 84 разных сигнала?

А=3; N=84, следовательно 84=3ⁱ, тогда i=5 (лампочек)

1. 1. 2. Информационный объем сообщений.

Формула информационного объема сообщения.

Кодирую буквы А, Б, В, Г:

N=2ⁱ; N=2, следовательно i=2 бита:

А – 00

Б – 01

В – 10

Г – 11

Кодирую слово ББВА:

Б – 01; Б – 01; В – 10; А – 00, тогда:

01011000

Можно сделать вывод и вывести формулу:

4 (кол-во букв (ББВА)) * 2 бита = 8 (длина кода слова)

Следовательно:

I = k*i

Где:

I – информационный объем сообщения

i – информационный вес одного элемента сообщения

k – количество элементов

ПРИМЕР:

1. Каков информационный объем в байтах сообщения из 20 символов в знаковой системе, содержащей только символы русского алфавита (33 буквы)?

N = 33, следовательно i = 6 бит

k = 20 символов , следовательно I = k*i= 20*6=120 бит =120/8 байт= 15 байт.

2. Для передачи секретного сообщения используется код, состоящий из десятичных цифр. При этом все цифры кодируются одним и тем же (минимально возможным) количеством бит. Определите информационный объем сообщения длиной в 150 символов. Ответ выразить в битах.

N = 10, следовательно i = 4 бита

k = 150 символов, следовательно I = k*i= 150*4=600 бит =600/8 байт= 75 байт.

Составной код.

1. Пароль длинной 5 символов. Символы от А до Я. Пароль записывается минимально возможным целым количеством байт. Кроме пароля еще 10 байт дополнительных сведений.

N=33, следовательно i=6 бит

6

6

6

6

6

доп. инфа. (10 байт)

I_пароля = 5*6 бит = 30 бит = 30/8 байт = 4 байта

I_{сообщения} = 4 (пароль) +10 (дополнительные сведения) = 14 байт.

2. В некоторой стране автомобильный номер длиной 6 символов составляют из заглавных букв (задействовано 17 различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти в байтах, отводимый этой программой для записи 70 номеров.

5

5

5

5

5

5

N = 17+10 = 27

N = 2ⁱ, следовательно i = 5 бит

I _номера = 6*5 бит= 30 бит = 30/8 байт= 4 байта (на 1 номер)

I _{сообщения} = 70*4 байт = 280 байт.

1. 1. 3. Кодирование изображений.

Пример кодирования изображений. Вывод формул.

N = 2ⁱ

где:

N – количество цветов в палитре

i – длина кода, бит (глубина цвета)

I = k*i

где:

k – количество пикселей (разрешение)

I – размер изображения (объем изображения)

i – глубина цвета

K = k₁ * k₂

где:

k₁ – строки

k₂ – столбцы

ПРИМЕРЫ:

1. K = 160 * 1280; N = 32, найти I - ?Кбайт:

N = 2ⁱ; 32 = 2ⁱ, следовательно i = 5

I = k * i = (160 * 1280 * 5)/(1024 *8) = 125 Кбайт.

2. Для хранения растрового изображения размером 64 ×32 пикселя отвели 1 Кбайт памяти. Каково максимально возможное число цветов в палитре изображения?

K = 64 * 32 = 2048

I = 1 Кбайт = 1024 * 8 бит

N = ?

i = I/k = 8192/2048 = 4 бит

N = 2ⁱ, следовательно N = 2⁴ = 16.

Схема «ДО – ПОСЛЕ».

I = k * i

- если i уменьшиться в 2 раза, то I тоже уменьшится в 2 раза

- если k уменьшится в 3 раза, то I тоже уменьшится в 3 раза

- если k уменьшиться в 3 раза и i уменьшиться в 2 раза, то I уменьшится в 6 раз

- если k увеличится в 3 раза и i уменьшится в 2 раза, то I увеличится в 1.5 раза

ПРИМЕР:

Автоматическая фотокамера с 450 Кбайт видеопамяти производит растровые изображения с фиксированным разрешением и 8-цветной палитрой. Сколько цветов можно будет использовать в палитре, если увеличить видеопамять до 1800 Кбайт?

Р

*4

ешение:

Ответ: 4096

Разрешение сканирования (dpi – dotsperineh)

dpi – это количество точек на один дюйм, эти точки могут быть разного размера и образовываются они с помощью строк и столбцов.

3 dpi – 9 точек/дюйм

4 dpi – 16 точек/дюйм

6 dpi – 36 точек/дюйм

Следовательно, при увеличении dpi в x раз – K увеличивается в x² раз.

Пример задачи:

Для хранения в информационной системе документа сканируется с разрешением 600 взш и цветовой системой, содержащей 2²⁴ = 16777216 цветов. Методы сжатия изображений не используются. Средний размер отсканированного документа составляет 108 Мбайт. В целях экономии было решено перейти на разрешение 200 dpi и цветовую систему, содержащую 2¹² = 4096 цветов. Сколько Мбайт будет составлять средний размер документа, отсканированного с измененными параметрами.

Решение:

Было 600 dpi, стало 200 dpi. Следовательно количество dpi уменьшилось в 3 раза.

N = 2ⁱ , следовательно i₁ = 24, а i₂ = 12. Следовательно i уменьшилось в 2 раза.

Тогда:

= 108/(2*3²) = 6 Мб

1. 1. 4. Кодирование звука.

Дискретизация – разбитие чего-то непрерывного на элементы.

Временная дискретизация – измерение звука в определенный момент времени (разбиение звуковой волны на точки).

Квантование – разбиение по уровням.

I = k * i

где:

I – информационный объем звука

K – количество замеров

i – информационный вес каждого замера (глубина звука)

N = 2ⁱ

где:

N – количество уровней звука

i – длина кода одного замера (разрешение звука)

K = V * c * t

где:

V – частота дискретезации, Гц

t – длительность записи, сек

c – количество каналов

Следовательно:

I = V * t * c * i

Заметим что: 1 Кбайт = 1024 байт, НО 1 КГц = 1000 Гц

Пример 1:

Производится одноканальная (моно) звукозапись с частотой дискретизации 64 Гц. При записи испольвалось 64 уровня дискретизации. Запись длиться 5 минут 20 секунд, ее результаты записываются в файл, причем каждый сигнал кодируется минимальным целым минимально возможным и одинаковым количеством битов. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?

1. 10

2. 15

3. 32

4. 64

Решение:

c = 1

V = 64 Гц

N = 64, следовательно i = 6

t = 5 минут 20 секунд = 320 секунд = 2⁵ *10 секунд

I = ? Кбайт

I = V * t * c * i = 64 * 32* 10*1*6 = 2¹¹*10*6 бит = 15 Кбайт

Следовательно верный ответ под номером 2.

Пример 2:

Дано:

C = 2

V = 64 Кгц

i = 24 бит

I = 48 Мбайт

Найти:

t = ?

Решение:

I = V * t * c * i

t = I/(V*c*i) = 48 * 2²³/(2⁶*1000*2*24) = 2,18 минуты = примерно 2 минуты.

Схема До-После.

Пропускная способность – как много информации можно передать за единицу времени.

Чем выше пропускная способность, тем меньшн времени нужно. (так как чем выше скорость передачи, тем меньше времени нужно)

Темп воспроизведения обратно–пропорционален времени, то есть если темп увеличить в 2 раза, то время уменьшится в 2 раза.

1. 1. 5. Неравномерные коды.

Пример равномерного кода:

А – 000

Б – 001

В – 010

Пример неравномерного кода:

А – 01

Б – 10

В – 110

Чтобы система кодов удовлетворяла условию однозначного декодирование, нужно чтобы для нее выполнялось правило Фано ИЛИ обратное правило Фано.

Правило Фано – ни один код не является началом другого.

Пример, который не удовлетворяет условию Фано:

А – 01

Б – 100

В – 1

Г – 00

Пример, который удовлетворяет условию Фано:

А – 11

Б – 101

В – 1001

Г – 10001

Обратное условие Фано – ни один код не может являться концом другого.

Пример, который не удовлетворяет обратному условию Фано:

А – 11

Б – 100

В – 001

Г – 00

Пример, который удовлетворяет обратному условию Фано:

А – 00

Б – 111

В – 1011

Г – 10001

Префиксный код – это код, который удовлетворяет условию Фано.

Постфиксный код – это код, который удовлетворяет обратному условию Фано.

Учёт частности букв при составлении системы кодов: чем чаще буква встречается, тем наиболее короткий код ей нужен.

При передачи кодов иногда могут случаться помехи, для борьбы с которыми придумали:

Методы борьбы с шумом (за счёт избыточной информации):

1. Дублирование.

Метод дублирования заключается в повторной отправке одного и того же кода. И если в двух кодах будут отличаться позиции, это значит, что код пришел с ошибками.

2. Контрольные суммы.

Контрольная сумма – число характеризующее код.

Бит четности – бит, дополняющий код до четного количества единиц.

То есть, код дополняется 0 или 1, в зависимости от количества единиц. Если количество единиц в коде нечетное, то добавляется единица в конце кода (которая никак не относиться к самому коду) для того, чтобы в коде стало четное количество единиц. Если же в коде изначально четное количество единиц, то в конце кода добавляется ноль.

Таким образом, если получатель получит код, в котором код с нечетным количеством единиц (учитывая бит четности), он поймет, что в коде ошибка и запросят его снова.

Пример:

Имеется код 10011, так как в коде нечетное количество единиц, тогда бит четности будет равен 1. И будет выглядеть так: 10011[1]. И если получатель получит следующий код: 11011[1], то значит при передаче возникли помехи.

Также иногда могут добавлять сразу 2 бита четности, для наиболее точной передачи.

Расстояние между кодами – это количество позиций, в которых коды различаются. Расстояние считается по количеству различных знаков кода.

3. Помехоустойчивый код (изучается в ВУЗах)

1. 2. ГЛАВА 2

Практическое применение темы «Кодирование информации» в задачах ЕГЭ.

1. 2. 1. Задачи на тему «Информационный объем сообщений» (11 номер ЕГЭ)

Задача 1:

Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, номер подразделения и некоторая дополнительная информация.

Личный код состоит из 20 символов, каждый из которых может быть заглавной латинской буквой (используется 13 различных букв) или одной из цифр от 0 до 5. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством бит.

Номер подразделения - целое число от 1 до 406, он записан на пропуске как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 20 байт данных.

Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число - количество байт.

Решение:

Для начала нужно найти информационный объем личного кода сотрудника:

k = 20 символов

N = 13 + 6 = 19, следовательно i = 5

I1 = k * i = 20 * 5 = 100 бит

Так как «для записи кода на пропуске отведено минимально возможное целое число байт»:

I1 = 100 бит = 100/8 = 13 байт (округляем в большую сторону)

Далее следует найти информационный объем номера подразделения:

k = 1

N = 406, следовательно i = 9

Тогда:

I2 = k * i = 9 бит

Так как «занимает минимально возможное целое число байт»:

I2 = 9 бит = 2 байта

Далее нужно вычислить сколько байт информации отведено для хранения информации об одном сотруднике:

I_общее = I1 + I2 + I3

Следовательно:

I3 = I_общее– I1 – I2 = 20 – 15 = 5 байт.

Задача 2:

Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация.

Личный код состоит из 8 символов, каждый из которых может быть одной из 10 допустимых заглавных букв или одной из 9 цифр. Для записи личного кода используют посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством бит.

Код подразделения состоит из двух натуральных чисел, не превышающих 700, каждое из которых кодируется как двоичное число и занимает минимально возможное целое число бит. Личный код и код подразделения записываются подряд и вместе занимают минимально возможное целое число байт. Всего на пропуске хранится 20 байт данных.

Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число - количество байт.

Решение:

Для начала нужно найти информационный объем личного кода сотрудника:

k = 8 символов

N = 10 + 9 = 19, следовательно i = 5

I1 = k * i = 8 * 5 = 40 бит

Так как «для записи кода на пропуске отведено минимально возможное целое число байт»:

I1 = 40 бит = 40/8 = 5 байт (округляем в большую сторону)

Далее следует найти информационный объем номера подразделения:

k = 2

N = 700, следовательно i = 10

Тогда:

I2 = k * i = 20 бит

Так как «занимает минимально возможное целое число байт»:

I2 = 20 бит = 3 байта

Далее нужно вычислить сколько байт информации отведено для хранения информации об одном сотруднике:

I_общее = I1 + I2 + I3

Следовательно:

I3 = I_общее– I1 – I2 = 20 – 5 - 3 = 12 байт.

Задача 3:

Каждый объект, зарегистрированный в информационной системе, получает уникальный код, состоящий из двух частей.

Первая часть определяет категорию объекта и состоит из 9 символов, каждый из которых может быть одной из 26 заглавных латинских букв.

Вторая часть кода определяет уникальный идентификатор объекта и состоит из 6 символов, каждый из которых может быть латинской буквой (строчной или заглавной) или одной из 9 цифр (цифра 0 не используется). Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для данной части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 108 байт для хранения содержательной информации.

Сколько байтов потребуется для хранения данных (код и содержательная информация) о 25 объектах? В ответе запишите только целое число - количество байтов.

Решение:

Первая часть кода:

k = 9 символов

N = 26, следовательно i = 5

I1 = 9 * 5 = 45 бит

Вторая часть кода:

k = 6 символов

N = 26 + 26 + 9 = 61, следовательно i = 6

I2 = 6 *6 = 36 бит

Так как «для кода в целом выделяется минимально возможное целое количество байтов»:

I кода = I1 + I2 = 36 + 45 = 81 бит = 11 байт

I общее = I кода + I доп инфы = 11 + 108 = 119 байт

Информация о 25 объектах:

119 * 25 = 2975 байт.

Задача 4 (ЕГЭ 2022):

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 141 символа и содержащий только десятичные цифры и символы из 700-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.

Определите объём памяти (в Кбайт), необходимый для хранения 4096 идентификаторов. В ответе запишите только целое число - количество Кбайт.

Решение:

K = 141 символ

N = 10 + 700 = 710, следовательно i = 10

I = 141 * 10 = 1410 бит

Так как «целое число байт»:

I = 1410 бит = 177 байт

Для хранения 4096 идентификаторов:

177 * 4096 = 724992 байта = 724992/1024 Кбайта = 708 Кбайт.

Задача 5 (Статград 2023 – 4):

В информационной системе хранится информация об объектах определённой структуры. Описание каждого объекта включает в себя идентификатор объекта, описание структуры объекта и дополнительную информацию.

Идентификатор объекта состоит из 10 заглавных латинских букв. Каждая буква идентификатора кодируется минимально возможным числом битов, а для хранения всего идентификатора отводится минимально возможное целое число байтов.

Структура объекта описывается как последовательность простых элементов. Всего существует 1925 различных простых элемента. Каждый простой элемент кодируется одинаковым для всех элементов минимально возможным количеством битов. Для описания структуры объекта выделяется одинаковое для всех объектов минимальное количество байтов, достаточное для записи 50 простых элементов.

Для хранения дополнительной информации выделяется одинаковое для всех объектов целое число байтов.

Известно, что для хранения данных о 16384 объектах потребовалось 8 Мбайт. Сколько байтов выделено для хранения дополнительной информации об одном объекте? В ответе запишите целое число - количество байт.

Решение:

Идентификатор объекта:

k = 10

N = 26, следовательно i = 5

I1 = 50 бит

Так как «отводится минимально возможное целое число байтов»:

I₁ = 50 бит = 7 байт

Структура объекта:

N = 1925, следовательно i = 11 бит

k = 50

I2 = 11 *50 = 550 бит = 69 байт

Вычисление размера дополнительной информации:

8 Мбайт = 67108864 бита

Тогда на 1 объект:

67108864/16384 = 4096 бит на 1 объект = 512 байт на 1 объект

Тогда размер доп инфоомации равен:

512 – 69 – 7 = 436 байт.

1. 2. 2. Задачи на тему «Кодирование изображений» (7 номер ЕГЭ)

Задача 1:

Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 640х1280 пикселей при условии, что в изображении могут использоваться 128 различных цветов?

В ответе запишите только целое число, единицу измерения писать не нужно.

Решение:

k = 640 * 1280 = 819200 пикселей

N = 128, следовательно i = 7 бит

I = k*i = 819200 * 7 = 5734400 бит = 700 Кбайт.

Задача 2:

Автоматическая фотокамера производит растровые изображения размером 1280×2560 пикселей. При этом объём файла с изображением не может превышать 3.1 Мбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?

Решение:

k = 1280 * 2560

I <= 3.1 Мбайт (=3.1 * 1024 * 1024 *8 бит)

Вычисление количества цветов в палитре:

I = k * i

1280 * 2560 * i <= 3.1 * 1024 * 1024 *8

i <= (3.1 * 1024 * 1024 *8)/ (1280 * 2560)

i <= 7.936 бит, следовательно i = 7 бит

N = 2ⁱ = 2⁷ = 128 цветов в палитре.

Задача 3:

Автоматическая фотокамера каждые 6 с создаёт черно-белое растровое изображение, содержащее 256 оттенков. Размер изображения - 512 × 256 пикселей. Все полученные изображения и коды пикселей внутри одного изображения записываются подряд, никакая дополнительная информация не сохраняется, данные не сжимаются. Сколько Мбайтов нужно выделить для хранения всех изображений, полученных за сутки?

В ответе укажите только целое число - количество байтов, единицу измерения указывать не надо.

Решение:

k = 512 * 256

N = 256 цветов, следовательно i = 8 бит

I = k * i = 512 * 256 * 8 бит = 0.125 Мбайт

Количество снимков за сутки:

24 часа = 86400 секунд

86400/6 = 14400 снимков

Тогда инф объем за сутки:

14400 * 0.125 = 1800 Мбайт за сутки.

Задача 4 (ЕГЭ 2022):

Для хранения произвольного растрового изображения размером 340х320 пикселей отведено 70 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. После сохранения информации о пикселях изображение сжимается. Размер оригинального файла больше сжатого на 50%.

Какое максимальное количество цветов можно использовать в изображении?

Решение:

I сжатого <= 70 Кбайт (= 70*1024 *8)

Информационный объем исходного изображения будет на 150% больше информационного объема преобразованного, тогда:

I оригинального = 1.5 * I сжатого

I сжатого = I оригинального/1.5

70 *1024*8 <= (340 * 320 * i)/1.5

Отсюда i = 7 бит, тогда N = 128 цветов.

Задача 5 (Статград 2023-5):

Камера наблюдения делает фотографии и передаёт их по каналу связи в виде сжатых изображений размером 640×480 пикселей и разрешением 16 бит. Пропускная способность канала позволяет передать 12 фотографий в секунду. Для повышения качества наблюдения камеру заменили на новую.

Новая камера передаёт фотографии размером 1280×960 пикселей разрешением 24 бит, при этом коэффициент сжатия изображения не изменился. Сколько фотографий в секунду сможет передать новая камера, если в два раза увеличить пропускную способность канала связи?

Решение:

Сначала нужно найти пропускную способность в битах первой камеры:

k = 640*480

i = 16 бит

I = i * k = 16 * 640 * 480 бит

Так как пропускная способность 12 фото в секунду, то:

I * 12 = 16 * 640 * 480 * 12 бит

В условии сказано, что пропускная способность второй камеры в 2 раза больше, следовательно:

16 * 640 * 480 * 12 * 2 – это пропускная способность второй камеры

Вычислим количество фотографий:

(16 * 640 * 480 * 12 * 2)/(1280 * 960 *24) = 4 фотографии.

1. 2. 3. Задачи на тему «Кодирование звука» (7 номер ЕГЭ)

Задача 1:

Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза меньше и частотой дискретизации в 3.5 раз выше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 4 раз выше, чем канала связи с городом А. Передача файла в город Б длилась 35 секунд. Сколько секунд длилась передача файла в город А? В ответе запишите только целое число, единицу измерения писать не нужно.

Решение:

Так как разрешение становиться в 2 раза меньше, частота дискретизации стала в 3.5 раза выше, а пропускная способность выше в 4 раза, то чтобы получить время, за которое пройдет файл в город Б, нужно время, за которое файл пройдет в город А, уменьшить в 2 и в 4 раза, и увеличить в 3.5 раза.

Обозначим время передачи в город А за x, тогда:

(x * 3.5)/(2 * 4) = 35

Тогда x отсюда равен 80 секундам.

Задача 2:

Музыкальный фрагмент был записан в формате стерео (двухканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла - 15 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно с частотой дискретизации в 1.5 раза меньше, чем в первый раз. При этом при повторной записи темп воспроизведения был уменьшен в 2 раза. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи.

Решение:

Было стерео, стало моно, значит размер файла нужно делить на 2.

Частота дискретизации уменьшилась в 1.5 раза, значит нужно делить размер исходного файла на 1.5.

Темп воспроизведения обратно–пропорционален времени, то есть если темп уменьшить в 2 раза, то время увеличиться в 2 раза, значит нужно будет умножить на 2 размер исходного файла.

Исходя из написанного выше:

I2 = (I1*2)/(2*1/5) = (15 * 2) / 3 = 10 Мбайт.

Задача 3 (Статград 2023 – досрок):

Голосовое сообщение, записанное в стерео формате, передается со скоростью 64000 бит/с. Файл был записан с такими параметрами: глубина кодирования - 8 бит на отсчет, частота дискретизации - 32000 отсчетов в секунду, время записи - 80 с. Сколько секунд будет передаваться голосовое сообщение?

Решение:

Для начала нужно найти размер исходного файла:

i = 8 бит

c = 2

V = 32000 Гц

t = 80 сек

I = 8 * 32000 * 80 *2 = 40960000 бит

Теперь нужно вычислить за сколько секунд оно передалось:

40960000/64000 = 640 секунд.

Задача 4 (Статград 2023-1):

Музыкальный фрагмент был записан в формате квадро (четырехканальная запись), оцифрован с частотой дискретизации 22 кГц и разрешением 24 бит и сохранён без использования сжатия данных. Получился файл размером 192 Мбайт. Затем тот же фрагмент был записан в формате стерео (двухканальная запись) с частотой дискретизации 44 кГц и тоже сохранён без сжатия, при этом получился файл размером 64 Мбайт. С каким разрешением проводилась вторая запись? В ответе укажите целое число - разрешение в битах, единицу измерения писать не нужно.

Решение:

Решение задачи схемой до-после.

Изначально было квадро, потом стало стерео, то есть уменьшилось в 2 раза.

Было 22 кГц, а стало 44 кГц, то есть увеличилось в 2 раза.

Чтобы найти разрешение измененного файла, нужно найти во сколько раз будет меньше размер измененного файла по сравнению с исходным, учитывая действия, написанные выше.

То есть:

192*2/2 = 192 Мбайта

192/64 = 3, следовательно разрешение уменьшилось в 3 раза:

24/3 = 8 бит.

1. 2. 4. Задачи на тему «Неравномерный код» (4 номер ЕГЭ)

Задача 1

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово ООО, для буквы Б - кодовое слово 1. Какова наименьшая возможная суммарная длина всех 6 кодовых слов?

Решение:

С помощью дерева Хаффмана.

Б

1 + 3 + 3 + 3 + 4 + 4 = 18.

В

Г

А

Е

Д

Задача 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 0000110, Б: 01111011, В: 001100101.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

Это задание можно решать с помощью дерева Хаффмана, но я считаю, что это долго. Есть способ быстрее. Это метод подбора.

Так как в условии сказано «код будет допускать однозначное декодирование», значит нужно смотреть, чтобы значение удовлетворяла ЛИБО условию Фано ЛИБО обратному условию Фано.

То есть нужно подобрать кратчайшее кодовое слово, которое будет допускать однозначное декодирование. Начиная с кодовых слов «0, 1» продолжая словами «00, 01, 10, 11» и так далее мы подбираем нужное значение, которое будет с наименьшим числовым значением (сказано в условии).

В этой задаче кратчайшим словом с наименьшим значением будет кодовое слово – 1.

Задача 3

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова некоторых букв: Я - 00, Н - 011, 3 - 111. Какое наименьшее число двоичных знаков может содержать код слова БАРАБАН?

Решение:

С помощью дерева Хаффмана.

БАРАБАН:

2 - буквы Б

3 - буквы А

1 - буква Р

1 - буква Н

1 – другие буквы алфавита

А

Я

Н

Б

Р

З

Остальные буквы алфавита

Так как: чем чаще буква встречается, тем наиболее короткий код ей нужен, то букве, которая встречается чаще нужно дать меньший код, поэтому из оставшихся мест для буквы А нужно выбрать наименьшее, соответственно с остальными буквами.

Также после построения дерева можно увидеть, что нужно добавить еще одну ветку, чтобы было место для кодирования остальных букв алфавита. Для ответвления можно использовать свободную ветвь с наибольшим кодом.

Таким образом после расстановки всех букв видно, что слово БАРАБАН содержит 3 * 2 + 2 * 3 + 3 + 4 = 19 двоичных знаков.

4. Заключение

Итак, проведя исследования в разделе информатики «Кодирование информации» мне удалось систематизировать разделы, выделить основные направления и проанализировать задачи, входящие в соответствующие разделы.

В результате работы я получила:

Расширенные знания в кодировании информации

Знание формул

Навык решения задач по теме «Кодирование информации»

Опыт работы заданиями разной сложности

Многих сверстников пугает тема «Кодирование информации», но я, проведя свое исследование, подтвердила гипотезу: в действительности задания на кодирование информации не являются сложными, а их решение более фундаментально, чем кажется.

Поэтому можно, прорешав, поняв алгоритмы решения задач по этой теме, получить баллы за задания по кодированию информации на ЕГЭ, а также попробовать свои силы на олимпиадах.

Дальнейшие перспективы проекта:

Участие в различных конкурсах

Успешное решение заданий у других учеников, которые увидят мой проект.

Список литературы.

1. Сайт «РЕШУ ЕГЭ по информатике» URL: https://inf-ege.sdamgia.ru/prob_catalog

2. Сайт «Фоксфорд. Кодирование информации» URL: https://foxford.ru/wiki/informatika/kodirovanie-informatsii?utm_referrer=https%3A%2F%2Fyandex.ru%2F

3. Сайт «Википедия. Кодирование информации» URL: https://ru.wikipedia.org/wiki/Кодирование

4. Сайт «Википедия. Единий государственый экзамен» URL: https://ru.wikipedia.org/wiki/Единый_государственный_экзамен

5. Сайт «4ЕГЭ. Демоверсия ЕГЭ по информатике» URL: https://4ege.ru/informatika/65775-demoversija-ege-2023-po-informatike.html