ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ КОДИРОВАНИЯ ИНФОРМАЦИИ ПРИ РЕШЕНИИ ЗАДАЧ ЕГЭ ПО ИНФОРМАТИКЕ

Подробнее

Размер

401.64K

Добавлен

04.08.2021

Скачиваний

21

Добавил

Tat
Текстовая версия:

Курсовая работа

ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ КОДИРОВАНИЯ ИНФОРМАЦИИ ПРИ РЕШЕНИИ ЗАДАЧ ЕГЭ ПО ИНФОРМАТИКЕ


Введение

Первые эффективные средства и методы формального кодирования информации оказались разработанными именно в математике. Информатика естественно восприняла их. Более того, соображения чисто технического характера привели к тому, что в алфавите формального языка, предназначенного для фиксации произвольной информации, осталось всего два символа, которые традиционно обозначают цифрами 0 и 1. Но информатика поставила в вопросах кодирования принципиально новые задачи: разработка кодов, предотвращающих искажение информации во время передачи по каналам связи, создание экономичных кодов (т.е. таких, которые для передачи или сохранения информации требуют минимального числа кодирующих символов), разработка методов кодирования, защищающих информацию от несанкционированного проникновения. Отвечая на эти вызовы, математики начали развивать методы, позволяющие решить эти задачи.

Автоматизация процесса обработки информации также требовала формального представления обрабатываемой информации. Формальную обработку информации естественно представлять себе как преобразование одного сообщения, записанного на формальном языке, в другое сообщение, записанное на том же языке. Для нас запись «14 + 17» полна содержательно смысла: она показывает, что к каким-то 14 предметам надо добавить еще 17. И ответ мы можем получить разными способами. Важно же, однако, то, что преобразовывать это сообщение в ответ, т. е. в сообщение 31, можно поручить автоматическому устройству, для которого составлена соответствующая инструкция. Как известно, такая инструкция обычно состоит из указания последовательности производимых действий и называется алгоритмом. Именно в математике, в действиях над числами появляются первые алгоритмы.

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

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

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

Объект исследованиярешение задач ЕГЭ по информатике.

Предмет исследованияиспользование математических методов кодирования информации при решении задач ЕГЭ по информатике.

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

При выполнении курсовой работы были использованы следующие методы исследования: изучение учебно-методической литературы по теме исследования, анализ и синтез полученной информации.

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

В §1 указываются математические методы решения задач, дается основная теория по математическому кодированию, рассматриваются базовые понятия и формулы, необходимые для решения задач.

В §2 приведена структура ЕГЭ, и представлены основные различия между ЕГЭ 2020 года и 2021 года.

Подборка примеров и задач 2021 года, решаемых методами математического кодирования приводятся в §3.

Все выводы по проделанной работе сформулированы в «Заключении».

§ 1. Информация и ее кодирование математическими методами

Для простого обывателя понятие «Информатика» ассоциируется с набором навыков использования компьютерной техники, то есть изучать информатику – это значит учиться пользоваться различными прикладными программами. Но на самом деле информатика – это сложная наука, использующая различные методы работы с информацией, в основе которых лежат математические инструменты.

Теоретическая база всякого научного направления строится на математических методах исследования. Этот подход имеет прямое отношение и к информатике.

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

Данные методы используются при решении задач по темам: математическая логика, вычислительная математика, информация и ее кодирование, моделирование.

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

Отличие вычислительной математики от обычной заключается в системах счисления. Машины используют двоичную, восьмеричную и шестнадцатеричную. Это связано с первыми компьютерами, в которых кодирование информации происходило посредством индукции катушек (есть индуктивность — 1, нет — 0). Единицей измерения информации является бит. Последовательность из 8 последних называется байтом.

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

Десятичная применяется в повседневной жизни. Она состоит из множества действительных чисел, которое обозначается литерой "R". К нему принадлежат целые и дробные значения. Обозначается в информатике число в десятичной системе следующим образом: 2310.

Вторая, третья и четвертая применяются в вычислительной технике для кодирования информации. В двоичной существует только 2 значения: 0 или 1. Величина записывается следующим образом: 00010110012. Следует отметить, что иногда запись индекса "2" можно опускать, поскольку восьмеричная и шестнадцатеричная записывается совершенно другим способом. В восьмеричной всего 8 цифр, т. е. от 0 до 7. Для представления величины в этой форме нужно десятичное число перевести в двоичное, а затем, воспользовавшись определенной методикой, конвертировать в искомое значение.

Иначе обстоят дела с шестнадцатеричной системой счисления. Она состоит из цифр от 0 до 9, а также литер, обозначающих определенное число, т. е. A = 10, B = 11, C = 12, D = 13, E = 14 и F = 15. Однако для получения искомого значения требуется также определенная методика.

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

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

Рассмотрим некоторые базовые понятия:

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

Бит (Binary digIT) — это единица измерения количества информации, равная количеству информации, содержащемуся в опыте, имеющем два равновероятных исхода.

Кодирование информации — это процесс однозначного преобразования информации с одного языка на другой. Однозначный процесс, значит имеющий правило/систему правил для обратного преобразования информации в первоначальный вид. Неоднозначный процесс, значит не позволяющий вернуться к первоначальному виду информации, искажающий ее.

Декодирование информации — это процесс преобразования информации обратный кодированию.

Равномерное кодирование — это кодирование, при котором все символы кодируются кодами равной длины.

Неравномерное кодирование — это кодирование, при котором разные симолы могут кодироваться кодами разной длины.

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

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

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

Глубина кодирования цвета — это количество бит, необходимых для хранения и представления цвета при кодировании одного пикселя растровой графики.

Граф это набор вершин и соединяющих их ребер; он описывается в виде таблицы (матрицы смежности или весовой матрицы).

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

Степень вершины это количество ребер, которые соединены с этой вершиной.

Инверсия операция логического отрицания, обозначают F = .

Конъюнкция операция логического умножения, обозначают значком «&» либо «^»: F = А ^ В.

Дизъюнкция операция логического сложения, обозначают «v» либо «+»: F = AB

Логическое следование (импликация) — это логическая функция, которую можно описать помощью оборота «если..., то...», и обозначается: А → В

Логическое равенство (эквивалентность) — это логическая функция, которую можно описать помощью оборота «тогда и только тогда, когда ...» и обозначается А↔В. [5]

Базовые формулы:

N = 2i, где N — это количество различных символов в алфавите, i — это минимальное количество информации (бит), которое требуется для кодирования одного символа в алфавите.

I = K · i, где I — это информационный объем сообщения в битах (байтах, Кбайтах…),

K — это количество символов в сообщении (для текстового сообщения К — это количество всех знаков в сообщении; для графического изображения: К — это количество пикселей в растровом изображении; для звукового файла: в формуле есть дополнительные множители, подробнее в других уроках),

iэто количество бит на кодирование одного символа (в терминологии кодирования графической информации i — глубина кодирования цвета). [5]

Необходимо четко знать:

- значения степеней числа 2;

- правила перевода из различных систем счисления в десятичную и обратно;

- единицы измерения информации

1 байт = 23 бит

1 Кбайт = 210 байт = 213 бит

1Мбайт = 210 Кбайт = 220 байт = 223 бит

1Гбайт = 210 Мбайт = 220 Кбайт = 230 байт = 233 бит

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

Пример. Вычислим, сколько бит содержится в МБайт.

Решение.

1-ый способ:

.

Любую арифметическую операцию умножения или деления всегда надо проверять. Здесь работаем с большими числами, высока вероятность ошибки.

2-ой способ (более простой):

Или еще короче:

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

Для хранения информации о звуке длительностью t секунд, закодированном с частотой дискретизации f Гц и глубиной кодирования B бит требуется B f t бит памяти.

количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) при мощности алфавита М.

Закон тождества. Всякое высказывание тождественно самому себе:

А = А.

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным: А ^ = 0.

Закон исключенного третьего Высказывание может быть либо истинным, либо ложным: A = 1.

Закон двойного отрицания. Двойное отрицание дает в итоге исходное высказывание: = А.

Законы де Моргана: = ^ ; = .

Закон коммутативности: А ^ В = В ^ А; A B = B A.

Закон ассоциативности:

(А ^ В) ^ С = А ^ (В ^ С); (A B) C = A (B C).

Закон дистрибутивности. Отличаетя от подобного закона в алгебре — за скобки можно выносить не только общие множители, но и общие слагаемые:

(A ^ B) (A ^ C) = A ^ (B C); (A B) ^ (A C) = A (B ^ C).

§ 2. Структура ЕГЭ

В 2020 г., как и в предыдущие годы, вариант КИМ ЕГЭ по информатике и ИКТ состоит из двух частей, различающихся типом ответа на предложенные задания – в первой части собраны задания с кратким ответом, во второй – с развёрнутым ответом. Задания каждой части расположены по возрастанию сложности, поэтому различающиеся уровнем сложности задания по одним и тем же разделам курса информатики и ИКТ в КИМ могут находиться не рядом друг с другом. [10]

В 2021 г., проведение ЕГЭ предусматривает использование компьютеров. При выполнении заданий доступны на протяжении всего экзамена текстовый редактор, редактор электронных таблиц, системы программирования. Многие задания КИМ прошлых лет убраны (таблица 1), например, знаменитая задача 23 на логические уравнения (1, 7, 9.2, 12, 17, 19, 21, 23, 24 и 25 в старой нумерации). Добавлены новые практические задания, которых не было в КИМ предыдущих лет (задания 10, 18 и 26 нового КИМ). Новое задание 18 – двумерная задача на динамическое программирование. При выполнении некоторых заданий (9, 10, 18, 24, 26, 27) используются дополнительные файлы, входящие в КИМ. Некоторые теоретические задания можно решить с помощью программы. Задание 26 по теории игр превратилось в три задания 19, 20 и 21. Максимальный первичный балл теперь равен 30 (было – 35). В заданиях на программирование нет языка Бэйсик. [10]

Таблица 1Соответствие заданий ЕГЭ-2021 и ЕГЭ-2020

ЕГЭ-2021

ЕГЭ-2020

Материал

1

3

Анализ информационных моделей (графов)

2

2

Таблицы истинности логических функций

3

4-1

Поиск и сортировка в базах данных

4

5

Кодирование и декодирование

5

6-1

Выполнение и анализ простых алгоритмов

6

8

Анализ программы с циклом

7

9-1

Кодирование растровых изображений

8

10

Кодирование данных, комбинаторика

9

– (К10)

Встроенные функции в электронных таблицах

10

Поиск слов в текстовом документе

11

13

Вычисления информационного объёма

12

14

Выполнение алгоритмов для исполнителя

13

15

Поиск количества путей в графе

14

16

Позиционные системы счисления

15

18

Основные понятия математической логики.

16

11 (К11)

Вычисление значений рекурсивной функции.

17

К4

Проверка делимости

18

Динамическое программирование

19

26

Теория игр

20

26

Теория игр

21

26

Теория игр

22

20

Анализ программы с циклами и ветвлениями

23

22

Динамическое программирование

24

К7, К8

Обработка символьных строк

25

К5

Количество делителей числа

26

Обработка массива целых чисел

27

27

Обработка последовательностей

При подготовке обучающихся к ЕГЭ можно выделить задания, связанные с математическими методами, следующих тем «Информация и кодирование», «Моделирование», «Системы счисления», «Основы логики».

Рассмотрим распределение заданий по каждому тематическому блоку (таблица 2). [10]

Таблица 2 Распределение заданий по тематическим блокам

Название тематического блока

Номер задания

Что проверяется

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

4

Умение кодировать и декодировать информацию.

7

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

8

Знание о методах измерения количества информации.

11

Умение подсчитывать информационный объём сообщения.

Моделирование

1

Умение сопоставить таблицу и схему, соответствующие одному и тому же графу.

13

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

Системы счисления

14

Знание о записи целых чисел в позиционных системах счисления с различными основаниями.

Основы логики

2

Умение строить и анализировать таблицы истинности.

15

Знание основных понятий и законов математической логики.

Рассмотрим подробнее выполнение заданий каждого тематического блока экзаменационной работы и типичные ошибки, которые могут допустить участники ЕГЭ (таблица 3).

Таблица 3 Рекомендации по выполнению заданий

Номер заданий

Рекомендации по выполнению

Типичные ошибки и рекомендации по их предотвращению

4

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

Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением. Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить.

7

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

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

8

Для выполнения этого задания необходимо овладеть алфавитным подходом к измерению количества информации и операциями с числами в различных системах счисления. Один из способов выполнения задания, похожего на приведённое в демоварианте: пронумеровать буквы цифрами от 0 до N–1 (где N – это число используемых букв) и дальше работать в системе счисления с основанием N, при этом не забыть перевести результат в десятичную систему счисления.

При использовании способа решения со системой счисления с основанием N следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0 будет соответствовать первое слово.

11

Для выполнения этого задания также необходимо овладеть алфавитным подходом к измерению количества информации и повторить единицы измерения количества информации.

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

1

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

Как и в большинстве простых заданий, основные ошибки происходят из-за торопливости и невнимательности.

13

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

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

14

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

Основные ошибки связаны с невнимательностью при выполнении арифметических действий в недесятичных системах счисления. Например, вычитания единицы в ситуации типа: 10100002 – 1.

2

Необходимо повторить темы «Логические значения, операции и выражения», «Таблица истинности», особенно таблицы истинности для конъюнкции и дизъюнкции.

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

15

Необходимо также повторить свойства импликации и, если эта операция содержится в выражении, избавиться от неё, заменив на комбинацию отрицания и дизъюнкции.

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

§ 3. Решение задач ЕГЭ по информатике

Задача 1.(№ 4 в ЕГЭ) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110 Какова наименьшая возможная суммарная длина всех четырёх кодовых слов? [1]

1) 7; 2) 8; 3) 9; 4) 10.

Решение (способ 1, исключение вариантов):

Условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова. Поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0 поскольку есть код 110, запрещены кодовые слова 1, 11. Кроме того, ни одно другое кодовое слово не может начинаться с 110. Таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения. Есть одно допустимое кодовое слово из двух символов: 10. Если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г. Таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов, если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110. При выборе любых двух из них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9. Поэтому выбираем вариант 3 (9 символов).

Ответ: 3.

Решение (способ 2, построение дерева):

Условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова. При этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков. Построим дерево для заданных кодовых слов А – 0 и Б – 110 (рис.1):

Рисунок 1

штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111) (рис. 2):

Рисунок 2

Таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов.

Ответ: 3.

Задача 2. (№ 4 в ЕГЭ) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1; 2) 1110; 3) 111; 4) 11.

Решение (метод подбора):

Рассмотрим все варианты в порядке увеличения длины кода буквы Г начнем с Г = 1. При этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит. Следующий по длине вариант – Г = 11, в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит. Третий вариант, Г = 111, дает однозначное раскодирование во всех сочетаниях букв, поэтому правильный ответ – 3.

Ответ: 3.

Возможные проблемы: при переборе можно ошибиться и «просмотреть» какой-нибудь вариант.

Задача 3. (№ 7 в ЕГЭ) Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 30 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 4 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.[1]

Решение (способ 1, использование формулы):

Объём музыкального файла вычисляется по формуле , где f – частота дискретизации, r – разрешение (глубина кодирования), k – количество каналов, t – время звучания. При повышении разрешения (количества битов на хранения одного отсчёта) в 2 раза объём файла (при прочих равных условиях) увеличивается в 2 раза, поэтому время тоже увеличится в 2 раза. При снижении частоты дискретизации (количества хранимых отсчётов за 1 секунду) в 1,5 раза объём файла (при прочих равных условиях) уменьшается в 1,5 раза, поэтому время тоже уменьшится в 1,5 раза. При увеличении пропускной способности канала связи (здесь это то же самое, что и скорость передачи данных) в 4 раза время передачи (при прочих равных условиях) уменьшится в 4 раза, поэтому исходное время передачи файла нужно: умножить на 2; разделить на 1,5; разделить на 4; получается ((30 · 2) / 1,5) / 4 = 10 сек.

Ответ: 10

Решение (способ 2, составление уравнения):

Примем объём первого музыкального файла за x, тогда скорость передачи в город А равна x/30. При увеличении разрешения в 2 раза на один отсчёт отводится в памяти в 2 раз больше места, то есть объём файла увеличится в 2 раза (1). При уменьшении частоты дискретизации в 1,5 раза объём файла уменьшается в 1,5 раза (за 1 с берём в 1,5 раз меньше отсчётов) (1). Объединяя (1) и (2), получаем, что объём файла, полученного после второй оцифровки, равен . Пропускная способность (подразумевается – и скорость передачи!) канала связи с городом Б в 4 раза выше, то есть скорость равна Время передачи находим как отношение объёма файла к скорости: сек.

Ответ: 10

Задача 4. (№ 7 в ЕГЭ) Для хранения произвольного растрового изображения размером 128×320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении? [1]

Решение (представление чисел через степени двойки):

Находим количество пикселей, используя для вычисления степени числа 2: N = 128 · 320 = 27 · 25 · 10 = 213 · 5. Объём файла переводим из Кбайт в биты: 20 Кбайт = 20 · 213 бит. Глубина кодирования (количество битов, выделяемых на 1 пиксель): 20 · 213 : (5 · 213) = 4 бита на пиксель. Максимальное возможное количество цветов 24 = 16.

Ответ: 16.

Задача 5. (№ 8 в ЕГЭ) Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?

Решение (способ 1, метод перебора):

Рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:

АА*** А*А** А**А* А***А

Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов. Итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27. Всего 4 шаблона, они дают 4 · 27 = 108 комбинаций. Теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:

*АА** *А*А* *А**А

они дают 3 · 27 = 81 комбинацию. Два шаблона, где первая по счёту буква А стоит на третьей позиции:

**АА* **А*А

они дают 2 · 27 = 54 комбинации. И один шаблон, где сочетание АА стоит в конце ***АА. Они дают 27 комбинаций. Всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций.

Ответ: 270.

Решение (способ 2, использование формул комбинаторики):

В последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой сначала найдём количество перестановок из двух букв А и трёх звёздочек используем формулу (1) для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:

Здесь – количество букв А, – количество звёздочек и восклицательный знак обозначает факториал натурального числа, то есть произведение всех натуральных чисел от 1 до n : n!12n. В нашем случае 2 и 3 , так что получаем:

Теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 33 = 27 вариантов распределения остальных символов на месте звёздочек. Таким образом, получаем всего 10 · 27 = 270 вариантов.

Ответ: 270.

Задача 6. (№ 8 в ЕГЭ) Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение (способ 1, формулы комбинаторики):

Первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя. Общее число различных слов равно 233 3 3 = 162.

Ответ: 162

Решение (способ 2, через формулы мощности алфавита):

Дано слово длиной 5 символов типа *****, где первая звездочка – гласная буква (Е или Э), а остальные - любая из трёх заданных букв. Общая формула количества вариантов: , где М – мощность алфавита, а L – длина кода. Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: . Тогда M1 = 2 (алфавит гласных букв), а L1 = 1 (только 1 позиция в слове). M2 = 3 (алфавит всех букв), а L2 = 4 (оставшиеся 4 позиции в слове). В итоге получаем: N = 21 ∙ 34 = 2 ∙ 81 = 162.

Ответ: 162.

Задача 7. (№ 11 в ЕГЭ) В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

Решение (способ 1, использование формулы вероятности):

Красные клубки шерсти составляют 1/8 от всех, поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов. Выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки).

Ответ: 3

Решение (способ 2, использование формулы Шеннона):

Красные клубки шерсти составляют 1/8 от всех, поэтому вероятность pk того, что первый вынутый клубок шерсти – красный, равна 1/8. По формуле (3) Шеннона находим количество информации в битах:

бита. (3)

Ответ: 3.

Задача 8. (№ 11 в ЕГЭ) В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

Решение (способ 1, рассуждение):

Информация в 4 бита соответствует выбору одного из 16 вариантов. Поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!). Всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны. Поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян.

Ответ: 30.

Возможные ловушки: можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3). После пункта, описанного выше, можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2).

Решение (способ 2, использование формулы Шеннона):

Заболевшая обезьяна может жить в вольере А (событие 1) или в вольере Б (событие 2) количество информации в сообщении о произошедшем событии с номером i равно , где – вероятность этого события. Таким образом, получаем вероятность того, что заболевшая обезьяна живет в вольере А (4):

У нас не было никакой предварительной информации о том, где живет заболевшая обезьяна, поэтому можно считать, что вероятность определяется количеством обезьян в вольере – если вероятность равна 1/16, то в вольере живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны. Поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян.

Ответ: 30.

Задача 9. (№ 1 в ЕГЭ) На рисунке 3 справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15 Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Рисунок 3

Решение:

Сложность этой задачи в том, что схема симметрична. Легко понять, что без дополнительных данных (используя только степени вершин – количество связанных с ними ребёр) мы не сможем различить вершины А и В, Г и Е, Д и Ж. Определим степени вершин (рис. 4):

Рисунок 4

как и видно из рисунка , у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с двумя вершинами степени 2. Для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ. Мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута

П3 П1 П7 = 7 + 12 = 19

П3 П6 П5 = 10 + 6 = 16

П4 П1 П7 = 5 + 12 = 17

П4 П6 П5 = 9 + 6 = 15

из дополнительного условия. (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15). Находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А. В итоге получается кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ длиной 19.

Ответ: 19

Задача 10. (№ 1 в ЕГЭ) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице (рис. 5). (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Рисунок 5

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение (способ 1, использование схемы):

Построим граф – схему, соответствующую этой весовой матрице. Из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4) (рис. 6):

Рисунок 6

для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом. Все остальные рёбра уже были рассмотрены ранее например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7) (рис. 7):

Рисунок 7

новые маршруты из С – в D и E (длины путей соответственно 3 и 4) (рис.8):

Рисунок 8

новый маршрут из D – в E (длина пути 3) (рис.9):

Рисунок 9

новый маршрут из E – в F (длина пути 2) (рис. 10):

Рисунок 10

нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2. Таким образом, остается найти оптимальный маршрут из A в E. Попробуем перечислить возможные маршруты из А в Е:

А – В – Е

длина 9

А – В – С – Е

длина 7

А – В – C – D – Е

длина 9

А –C – Е

длина 8

А –C – B – Е

длина 12

А –C – D – Е

длина 10

из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9. Таким образом, правильный ответ – 9.

Ответ: 9.

Решение (способ 2, составление схемы с начала маршрута):

Составим граф (рис. 11), который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A:

Рисунок 11

видно, что напрямую в пункт F из A не доехать. Строим граф возможных путей дальше (рис. 12): определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно). Из B можно ехать только в A (обратно), в C и в E; узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»; при движении по дороге B-E длина увеличивается на 7:

Рисунок 12

строим маршруты из пункта C (рис. 13): кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем:

Рисунок 13

из пункта D, кроме как в С и E, ехать некуда (рис. 14); путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7. Из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9.

Рисунок 14

Ответ: 9.

Возможные ловушки и проблемы: можно не заметить, что маршруты, проходящие через большее число пунктов, оказываются короче (A-B-C короче, чем A-C, A-B-C-E короче, чем A-B-E).

Задача 11. (№ 13 в ЕГЭ) На рисунке 15 представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В? [1]

Рисунок 15

Решение (способ 1):

Нас интересуют пути, проходящие через город В, поэтому на первом этапе отсекаем все ребра, которые позволяют на пути от А к М обойти город В (рис. 16): это рёбра БЕ, ГЗ и ДЗ. Получается, что вершину Е тоже можно убрать, потому что в неё не ведёт ни одна стрелка. Начальную вершину помечаем единицей (1 путь из А в А, никуда не ехать):

Рисунок 16

В вершины Б и Д можно ехать только из А, поэтому помечаем их тоже единицами (рис.17); в вершину Г можно приехать из А (метка 1) и из Д, поэтому метка вершины Г – 2:

Рисунок 17

в вершину В можно приехать из Б (метка 1), А (метка 1) и Г (метка 2), так что метка вершины В равна 1 + 1 + 2 = 4 (рис.18):

Рисунок 18

в вершину З можно ехать только из В, поэтому её метка тоже равна 4 (рис.19); для вершины Ж складываем метки В и З (4 + 4 = 8), а для И – складываем метки Ж и З (8 + 4 = 12);

Рисунок 19

для вершин К и М получаем по 12 путей, а для М – 24.

Ответ: 24.

Решение (способ 2):

Нас интересуют пути, проходящие через город В, поэтому на первом этапе отсекаем все ребра, которые позволяют на пути от А к М обойти город В: это рёбра БЕ, ГЗ и ДЗ (рис. 20). Получается, что вершину Е тоже можно убрать, потому что в неё не ведёт ни одна стрелка:

Рисунок 20

Рассмотрим все пути из А в В, просматривая вершины сверху вниз. Их всего 4: АБВ, АВ, АГВ и АДГВ. Теперь рассмотрим все пути из В в И (узловая точка через которую проходят все дороги в направлении М). Из В в И ведут 3 дороги: ВЖИ, ВЗЖИ, ВЗИ. Теперь остается определить дороги из и в М. Их 2: ИКМ и ИЛМ. Остается определить общее количество возможных путей. По правилу произведения комбинаторики N= 4*3*2=24.

Ответ: 24.

Задача 12. (№ 14 в ЕГЭ) Сколько единиц в двоичной записи числа 42015 + 8405 – 2150 – 122 ?

Решение (способ 1):

Приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 27 – 22 – 21: 42015 + 8405 – 2150 – 122 = (22)2015 + (23)405 – 2150 – 27 + 22 + 21 = = 24030 + 21215 – 2150 – 27 + 22 + 21. Вспомним, число 2N–2K при K < N записывается как NK единиц и K нулей: 2N 2K 1100. Для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2N–2K, причём в этой цепочке степени двойки нужно выстроить по убыванию. В нашем случае в выражении 24030 + 21215 – 2150 – 27 + 22 + 21 стоит два знака «минус» подряд, это не позволяет сразу использовать формулу. Используем теперь равенство 2N 2N1 2N , так что – 2150 = – 2151 + 2150, получаем 24030 + 21215 – 2151 + 2150 – 27 + 22 + 21. Здесь две пары 2N–2K , а остальные слагаемые дают по одной единице. Общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210.

Ответ: 1210.

Решение (способ 2):

Приведём все числа к степеням двойки,учитывая,что 122 = 128 – 4 – 2 = = 27 – 22 – 21: 42015 + 8405 – 2150 – 122 = (22)2015 + (23)405 – 2150 – 27 + 22 + 21 = = 24030 + 21215 – 2150 – 27 + 22 + 21. Ищем в разности крайнюю левую степень двойки и крайнюю правую 21215 – 27, при этом 2150 на время «теряем». Определяем количество единиц в разности 21215 – 27, получаем 1215 – 7 = 1208 единиц. Так как «внутри» этой разности есть еще 2150, то просто вычитаем одну единицу: 1208 – 1 = 1207. Итого в разности 21215 – 2150 – 27 ровно 1207 единиц. Осталось прибавить по одной единицы от чисел 24030, 22, 21.

Ответ: 1210.

Задача 13. (№ 2 в ЕГЭ) Логическая функция F задаётся выражением . Определите, какому столбцу таблицы истинности (рис.21) функции F соответствует каждая из переменных x, y, z?

Рисунок 21

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение (способ 1, через СКНФ и сопоставление таблиц истинности):

Запишем заданное выражение в более простых обозначениях: . Функция задана в виде КНФ (конъюнктивной нормальной формы), которую можно привести к СКНФ, используя известные тождества алгебры логики: a 0 a, , распределительный закон для операции «И» a b c (a b) (a c) . Вторую дизъюнкцию дополним недостающей переменной z:

.

СКНФ: Каждая дизъюнкция в СКНФ соответствует строке таблицы истинности (рис. 22), в которой F = 0. Используя полученную СДНФ, делаем вывод: в таблице истинности имеется 3 строки, где F = 0, заполним их:

Рисунок 22

В таблице, приведенной в задании, рассмотрим строки, где F = 0 (рис.23):

Рисунок 23

Сравнивая столбцы этих таблиц, делаем выводы:

a) во втором столбце таблицы находится y (одна единица),

b) в первом столбце таблицы находится z (в двух строках z = y),

c) в третьем столбце таблицы находится x (где z = y, там x = ).

Ответ: zyx.

Решение (способ 2, через уравнение):

Так как между скобками стоит операция И, решим уравнение: . Чтобы функция была равна 1, нужно чтобы каждая скобка была равна 1. Уравнение имеет 3 решения (рис.24):

Рисунок 24

Подставим найденные решения в первую скобку и найдем полный набор решений уравнения (рис.25):

Рисунок 25

Сопоставляем найденное решение со строками исходной таблицы, в которых функция F = 1 (рис.26):

Рисунок 26

Есть одна строка, где две переменных равна 1, а одна – нулю, это строка 3 в последней таблице и строка 4 в предпоследней, поэтому первый столбец соответствует z. Далее видим, что в столбце у в предпоследней таблице три единицы, а в последней таблице три единицы только во втором столбце, поэтому второй столбец – y, а третий – x.

Ответ: zyx.

Задача 14. (№ 15 в ЕГЭ) Укажите наименьшее целое значение А, при котором выражение (5k + 6n > 57) ((kA) (n < A)) истинно для любых целых положительных значений k и n.

Решение (способ, построение графика):

Особенность этой задачи – «уход» от привычных обозначений переменных, x и y. Поскольку мы будем работать с графиками на плоскости, удобнее всё же вернуться к стандартным переменным x и y (понятно, что результат от этого не изменится): (5x + 6y > 57) ((xA) (y < A)). Первое выражение (5x + 6y > 57) не зависит от выбора A. Таким образом, нам нужно выбрать значение A так, чтобы условие (x < A) and (y ≤ A) выполнялось при всех x и y, для которых ложно (5x + 6y > 57), то есть истинно (5x + 6y 57).

Нужно также учесть, что x и y положительны и добавить ещё два ограничения: (x 1) and (y 1), таким образом, получаем треугольник (рис.27), ограниченный линиями (5x + 6y = 57) and (x 1 ) and (y 1).

Рисунок 27

Для всех точек этого треугольника с целочисленными координатами должно выполняться условие (xA) (y < A). Это значит, что треугольник (точнее, все его точки с целочисленными координатами) должен оказаться внутри квадрата со стороной A (рис.28), причем в силу нестрогого неравенства (xA) правая граница квадрата (она выделена жирной линией) может совпадать с точками треугольника:

Рисунок 28

Находим точку пересечения прямых 5x + 6y = 57 и x = 1: y 8,67. Поскольку нужно выполнить условие (y < A) , получаем A > 8. Находим точку пересечения прямых 5x + 6y = 57 и y = 1: x = 10,2. Поскольку нужно выполнить условие (x A) , получаем A 10. Оба условия нужно выполнить одновременно, поэтому выбираем наиболее жёсткое: A 10, что даёт Amin = 10.

Ответ: 10.

Решение (способ 2, аналитический):

Заметим, что эту простую задачу можно было решать и аналитически, учитывая, что нам достаточно рассматривать не все точки треугольника, а только отрезок прямой 5x + 6y = 57, ограниченный прямыми x = 1 и y = 1: если все точки этого отрезка окажутся внутри красного квадрата, то и все остальные точки треугольника тоже будут внутри красного квадрата. Поэтому находим максимальную целочисленную координату y на отрезке: 5x + 6y = 57 и x = 1: y 8,67 ymax = 8. Затем – максимальную целочисленную координату x на отрезке: 5x + 6y = 57 и y = 1: x = 10,2 xmax = 10. И выбираем наименьшее A, при котором (ymax < A) и (xmax A), то есть Amin = 10.

Ответ: 10.

Заключение

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

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

Проанализированы задачи ЕГЭ прошлого и нынешнего года. Выявлены различия и сходства в заданиях, соответствиях номеров.

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

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