СЕМИНАР «Кодирование информации» Подготовка к ЕГЭ Гурова Алла Александровна учитель информатики и ИКТ, ГБОУ СОШ с углубленным изучением информатики 1254. - презентация

1 СЕМИНАР «Кодирование информации» Подготовка к ЕГЭ Гурова Алла Александровна учитель информатики и ИКТ, ГБОУ СОШ с углубленным изучением информатики 1254

2 Контрольно-измерительные материалы (КИМ) Кодификатор СпецификацияДемоверсия

3 Номера заданий Проверяемые элементы содержания 1 Умение кодировать и декодировать информацию 4 Знания о системах счисления и двоичном представлении информации в памяти компьютера 9 Умение определять скорость передачи информации при заданной пропускной способности канала 10 Анализ последовательностей, системы счисления ЕГЭ 2015 (базовый уровень сложности)

4 Номера заданий Проверяемые элементы содержания 13 Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы 13 Умение подсчитывать информационный объем сообщения 16 Знание позиционных систем счисления ЕГЭ 2015 (повышенный уровень сложности)

5 Задание 4 Системы счисления и двоичное представлении информации в памяти компьютера

6 Необходимо знать: 1. Правила перевода чисел из 10-ной системы счисления в другие позиционные системы счисления и обратно. 2. Правила перевода чисел из двоичной системы счисления в 8-ную и 16-ную и обратно. 3. Для представления целых неотрицательных чисел используется следующая разрядная сетка: 4. Для представления целых чисел со знаком используется следующая разрядная сетка: где n = 16 или 32, положительное число кодируется «0», а отрицательное число кодируется «1». Код знака 2 n-1 2 n-2 …

7 Необходимо знать: 5. Отрицательные целые числа хранятся в памяти компьютера в дополнительном коде. 6. Для получения дополнительного кода отрицательного числа нужно сделать следующие операции: перевести число в двоичную систему счисления; записать прямой код полученного двоичного числа; записать обратный код, сделав инверсию всех битов, кроме знакового; к полученному обратному коду прибавить единицу.

8 Задача 1 Дано: а=D7 16 b=331 8 Найти: Какое из чисел c, записанных в двоичной системе, отвечает условию a

9 Задача 2 Дано: 169 х = С4 16 Найти: Чему равно значение основания системы счисления Х? 1) 10 2) 8 3) 9 4) 11 Решение: Системы счисления с основанием 8 и 9 исключаются. Если с основанием 10,тогда = А9 16 Если с основанием 11,тогда = 1* * *11 0 = = С4 16 Ответ: 4) 11

10 Задача 3 Дано: Число в системе счисления с основанием 32, содержит 6 цифр. Найти: Сколько цифр может содержать это число после перевода в систему счисления с основанием 8? 1) 18 2) 8 3) 5 4) 10 Решение: Для записи цифр от 0 до 31 в двоичной с/с потребуется 5 разрядов 5*6 = 30 (двоичных разрядов на число из 6 цифр). Для записи цифр от 0 до 7 в двоичной с/с требуется 3 разряда 30/3 = 10 (цифр в с/с с основанием 8). Ответ: 4) 10

11 Задача 4 Дано: десятичное число 257 Найти: Сколько единиц в двоичной записи десятичного числа 257? 1) 7 2) 9 3) 2 4)4 Решение: = = Ответ: 3) 2

12 Задача 5 Дано: десятичное число 129 Найти: Сколько значащих нулей в двоичной записи десятичного числа 129 ? 1) 5 2) 6 3) 7 4) 4 Решение: = = Ответ: 2) 6

13 Задача 6 Дано: Для хранения целого числа со знаком используется один байт. Найти: Сколько единиц содержит внутреннее представление числа (-35)? 1) 3 2) 4 3) 5 4) 6 Решение: = [ ]пк = [ ]ок = [ ]дк = Ответ: 4) 6

14 Задача 7 Укажите наименьшее четырёхзначное восьмеричное число, двоичная запись которого содержит 5 единиц. В ответе запишите только само восьмеричное число, основание системы счисления указывать не нужно Решение: Минимальное четырёхзначное восьмеричное число – это = Для решения задачи в конце этого числа нужно заменить четыре нуля на единицы: = Ответ: 1017

15 Задачи для тренировки: 1. Как представлено число 82 в двоичной системе счисления? 1) ) ) ) Как представлено число 263 в восьмеричной системе счисления? 1) ) ) ) Как записывается число в двоичной системе счисления? 1) ) ) ) Как записывается число A87 16 в восьмеричной системе счисления? 1) ) ) ) Сколько значащих нулей в двоичной записи числа 254? 1) 1 2) 23) 4 4) 8 6. Какое из чисел является наименьшим? 1) E6 16 2) ) ) Как записывается число в шестнадцатеричной системе счисления? 1) ) 1A4 16 3) 1EC 16 4) A56 16

16 Задачи для тренировки: 8. Какое из чисел является наибольшим? 1)9B 16 2) ) ) Дано: a=70 10, b= Какое из чисел С, записанных в двоичной системе счисления, удовлетворяет неравенству b< C C >b? 1) AA 16 2) B8 16 3) D6 16 4) F Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-78)? 1) 3 2) 4 3) 5 4) 6

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

18 Необходимо знать: 1. Кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите); 2. Кодирование может быть равномерное и неравномерное. при равномерном кодировании все символы кодируются кодами равной длины. При неравномерном кодировании разные символы могут кодироваться кодами разной длины; 3. Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова; 4. Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова; 5. Условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

19 Задача 1 Дано: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001,Г–011. Найти: Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. 1)002) 013) 114) 010 Решение: Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано. Если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, поэтому первый вариант не подходит. Если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, поэтому второй вариант тоже не подходит. Если Д = 11, кодовое слово А = 1 совпадает с началом кода буквы Д, третий вариант не подходит. Для четвертого варианта, Д = 010, условие Фано не нарушено. Ответ: 4) 010

20 Задача 2 Дано: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–00, Б–10, В–110, Г–111. Найти: Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. 1)1 2) 01 3) 010 4) 011 Решение: Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано. Если Д = 1, такая кодовая цепочка совпадает с началом Б = 10 и Г = 111, и является окончанием Г = 111, поэтому первый вариант не подходит. Для Д = 01, Д = 010 и Д = 011 условие Фано не нарушено. Из этих трех кодов наименьшей длиной обладает код 01. Ответ: 2) 01

21 Задача 3 Дано: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1110, Б–0, В–10, Г–110. Найти: Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. 1)00012) ) ) 1111 Решение: Если Д = 0001, тогда кодовая цепочка Б = 0 совпадает с началом Д = 0001 поэтому первый вариант не подходит. Если Д = 0011, тогда кодовая цепочка Б = 0 совпадает с началом Д = 0011 поэтому второй вариант тоже не подходит. Если Д = 0111, тогда кодовая цепочка Б = 0 совпадает с началом Д = 0111 поэтому третий вариант не подходит. Для четвертого варианта, Д = 1111, условие Фано не нарушено. Ответ: 4) 1111

22 Задача 4 Дано: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице: Найти: Определить, какой набор букв закодирован двоичной строкой ) EBCEA2) BDDEA3) BDCEA4) EBAEA Решение: Закодируем все ответы, используя приведенную таблицу кодов 1) EBCEA – ) BDDEA – ) BDCEA – ) EBAEA – Сравнивая эти цепочки с заданной, находим, что правильный ответ – 3) BDCEA – Ответ: 3) BCDEA ABCDE

23 Задача 5 Дано: Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый. Найти: Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода. 1) BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB Решение: Вытянем растровое изображение в цепочку: 1 строка 2 строка 3 строка 4 строка

24 Задача 5 (продолжение) Решение: Черные ячейки заполним единицами, а белые – нулями: 1 строка 2 строка 3 строка 4 строка Переведем полученную двоичную последовательность в шестнадцатеричную систему счисления: B D A 9 D 5 получаем цепочку BDA9D5 Ответ: 3) BDA9D

25 Задача 6 Дано: Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность ). Найти: Определите, какое число передавалось по каналу в виде ? 1) ) ) ) Решение: Из условия следует, четыре первых бита в каждой последовательности – это двоичный код цифры, а пятый бит (бит четности) используется для проверки и рассчитывается как «сумма по модулю два», то есть остаток от деления суммы битов на 2. Разобъем заданную последовательность на группы по 5 бит в каждой: 01010, 10010, 01111, Отбросим пятый (последний) бит в каждой группе: 0101, 1001, 0111, Это и есть двоичные коды передаваемых чисел: = 5, = 9, = 7, = 1. Ответ: 2) 5971

26 Задачи для тренировки: 1. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБВА и записать результат шестнадцатеричным кодом, то получится: 1) ) DBCA 16 3) D8 16 4) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице: a b c d e Определите, какой набор букв закодирован двоичной строкой ) baade2) badde3) bacde4) bacdb 3. Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится: 1) ) ) ) 12376

27 Задачи для тренировки: 4. Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится: 1) А ) 4С8 16 3) 15D 16 4) DE Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится: 1) ) ) ) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице: а b с d е Определите, какой набор букв закодирован двоичной строкой , если известно, что все буквы в последовательности – разные: 1) cbade2) acdeb3) acbed4) bacde

28 Задачи для тренировки: 7.Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый. Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода. 1) ) ) ) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код: A B C D E Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано: 1) ) ) )

29 Задачи для тренировки: 9. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше. Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г? 1) А:0, Б:10, В:110, Г:1112) А:0, Б:10, В:01, Г:11 3) А:1, Б:01, В:011, Г:0014) А:00, Б:01, В:10, Г: По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами: А 0, И 00, К 10, О 110, Т 111. Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту. 1) КАА2) ИКОТА3) КОТ4) ни одно из сообщений не подходит

30 Задание 13 Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы

31 Название Условное обозначение Соотношение с другими единицами Килобайт Кбайт (Кб) 1 Кбайт = 1024 байт = 2 10 байт = 2 13 бит Мегабайт Мбайт (Мб) 1 Мбайт = 1024 Кбайт = 2 20 байт = 2 23 бит Гигабайт Гбайт (Гб) 1 Гбайт = 1024 Мбайт = 2 30 байт = 2 33 бит Терабайт Тбайт (Тб) 1 Тбайт = 1024 Гбайт = 2 40 байт = 2 43 бит Петабайт Пбайт (Пб) 1 Пбайт = 1024 Тбайт = 2 50 байт = 2 53 бит Эксабайт Эбайт (Эб) 1 Эбайт = 1024 Пбайт = 2 60 байт = 2 63 бит Зеттабайт Збайт (Зб) 1 Збайт = 1024 Эбайт = 2 70 байт = 2 73 бит Йоттабайт Йбайт (Йб) 1 Йбайт = 1024 Збайт = 2 80 байт = 2 83 бит Необходимо знать:

32 Таблица степеней числа = 12 9 = = = = = = = = = = = = = = = Операции со степенями При умножении степени при одинаковых основаниях складываются 2 a 2 b = 2 a + b При делении степени при одинаковых основаниях вычитаются 2 a : 2 b = 2 a - b. Необходимо знать:

33 1. Все символы кодируются одинаковым числом бит (алфавитный подход). 2. Чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные). 3. При кодировании текста каждому символу ставится в соответствие свой код. 4.Символы-цифры в кодовой таблице идут подряд в порядке возрастания, от «0» до «9» (символ «0» имеет код 48, символ «9» – код 57). 5. Большие (прописные) латинские буквы в кодовой таблице идут подряд в алфавитном порядке от «A» до «Z». 6. Маленькие (строчные) латинские буквы в таблице кодировки идут подряд в алфавитном порядке, от «a» до «z». 7. В большинстве кодовых таблиц русские буквы, как заглавные, так и строчные, также расположены по алфавиту (за исключением буквы «Ё»). 8. Чтобы найти информационный объем текста ( I T), нужно умножить количество символов в тексте ( k) на число бит, которые отводятся на один символ (I). I T = k I 9. Число бит, которые отводятся на один символ (I ), вычисляется из формулы: N = 2 I, где N – количество символов в алфавите.

34 Задача 1 Дано: I 1 = 2 байт = 16 бит I 2 = 8 бит K = 20 символов Найти: I Т1 – I Т2 = ? бит Решение: I T1 = k I 1 = бит = 320 бит I T2 = k I 2 = 20 8 бит = 160 бит I Т1 – I Т2 = 320 бит бит = 160 бит Ответ: 160 Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной в 20 символов, первоначально записанного в 2-байтном коде Unicode, в 8-битную кодировку КОИ-8. На сколько бит уменьшилась длина сообщения? В ответе запишите только число.

35 Задача 2 Дано: I 1 = 8 бит = 1 байт I 2 = 2 байт K = 30 символов Найти: I Т2 – I Т1 = ? байт Решение: I T1 = k I 1 = 30 1 байт = 30 байт I T2 = k I 2 = 30 2 байт = 60 байт I Т2 – I Т1 = 60 байт - 30 байт = 30 байт Ответ: 30 Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной в 30 символов, первоначально записанного в 8-битной кодировке КОИ-8, в 2-байтную кодировку Unicode. На сколько байт увеличилась длина сообщения? В ответе запишите только число.

36 Задача 3 Дано: I 1 = 8 бит = 1 байт I 2 = 16 бит = 2 байт K = символов Найти: I Т2 – I Т1 = ? Кбайт Решение: I T1 = k I 1 = байт = байт = байт = 10 Кбайт I T2 = k I 2 = байт = байт = байт = 20 Кбайт I Т2 – I Т1 = 20 Кбайт - 10 Кбайт = 10 Кбайт Ответ: 10 Текстовый документ, состоящий из символов, хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode. Укажите, какое дополнительное количество Кбайт потребуется для хранения документа. В ответе запишите только число.

37 Задача 4 Дано: I = 16 бит = 2 байт K = 44 символа Найти: I Т = ? Решение: I T = k I = 44 2 байт = 88 байт Ответ: 88 байт Считая, что каждый символ кодируется 16-ю битами, оцените информационный объем следующей пушкинской фразы в кодировке Unicode: Привычка свыше нам дана: Замена счастию она.

38 Задача 5 Дано: I Т1 = I Т2 1,5 K 1 = K 2 = Х N 1 10, N 2 10 Найти: N 1 = ?, N 2 = ? Решение: I Т1 = I Т2 1,5 I 1 Х = 1,5 I 2 Х I 1 = 1,5 * I 2 8< 10 < 16 I 1 < =Log 2 16 < = 4 бит I 2 = 4 бит / 1,5 2,67 бит (2 бит) I 1 = 1,5 I 2 = 1,5 2 = 3 бит N = 2 I N 1 = 2 3 = 8 символов и N 2 = 2 2 = 4 символа Ответ: 8 символов и 4 символа Два сообщения содержат одинаковое количество символов. Количество информации в первом тексте в 1,5 раза больше, чем во втором. Сколько символов содержат алфавиты, с помощью которых записаны сообщения, если известно, что число символов в каждом алфавите не превышает 10, и на каждый символ приходится целое число битов?

39 Задача 6 Решение: Все заглавные латинские буквы A-Z и все строчные буквы a-z расставлены по алфавиту. Поэтому разница кодов букв «q» и «a» равна разнице кодов букв «Q» и «A», то есть, – = Тогда шестнадцатеричный код символа «q» равен коду буквы «a» плюс отсюда находим = Ответ: Символ 15ABQab Десятичный код Шестнадцатеричный код Каков шестнадцатеричный код символа «q»? В таблице ниже представлена часть кодовой таблицы ASCII:

40 Задачи для тренировки: 1. Текстовый документ хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode, при этом размер памяти, необходимой для хранения документа увеличился на 4 Кбайт. При этом хранится только последовательность кодов символов. Укажите, сколько символов в документе. В ответе запишите только число. 2. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 2-байтном коде Unicode, в 8-битную кодировку КОИ-8. При этом длина сообщения уменьшилась на 600 бит. Укажите, сколько символов было в сообщении. 3. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 240 бит. Какова длина сообщения в символах? 4.Считая, что каждый символ кодируется одним байтом, оцените информационный объем в битах следующего предложения: Белеет Парус Одинокий В Тумане Моря Голубом!

41 Задачи для тренировки: 5. Текст занимает 0,25 Кбайт памяти компьютера. Сколько символов содержит этот текст (для кодирования используется таблица кодировки ASCII)? 6. Объем сообщения, содержащего 2048 символов, составил 1/512 часть мегабайта. Каков размер алфавита, с помощью которого записано сообщение? 7. Текст занимает полных 5 страниц. На каждой странице размещается 30 строк по 70 символов в строке. Какой объем оперативной памяти займет этот текст (для кодирования используется 16-битная таблица кодировки Unicode)? 8. Если досье на преступников занимают 45 Мегабайт и каждое из них имеет объем 16 страниц (32 строк по 64 символа в каждой, 1 символ занимает 8 бит), то, каково количество досье? 9. Сообщение занимает 2 страницы и содержит 1/16 К байта информации. На каждой странице записано 256 символов. Какова мощность используемого алфавита?

42 Задачи для тренировки: Символ 15JKPjK Десятичный код Шестнадцатеричный код 31354A4B4B506A6A6B6B Символ СТУЯстУ Десятичный код Шестнадцатеричный код F9FE1E1E2E2E3E3 10. В таблице ниже представлена часть кодовой таблицы ASCII: Каков шестнадцатеричный код символа «p»? Каков шестнадцатеричный код символа «я»? 11. В таблице ниже представлена часть кодовой таблицы ASCII:

43 Задание 10 Анализ последовательностей, системы счисления

44 Задача 1 Решение: По условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию). Выпишем начало списка, заменив буквы на цифры: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 240-м месте от начала списка.

45 Задача 1 (продолжение) Решение: …… Это напоминает числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. Тогда легко понять, что на 240-м месте стоит число 239, записанное в троичной системе счисления. Переведем в троичную систему: = заменяем обратно цифры на буквы: УУУОУ Ответ: УУУОУ

46 Задача 2 Решение: Будем использовать пятеричную систему счисления с заменой А 0, К 1, Л 2, О 3 и Ш 4. Слово ШКОЛА запишется в новом коде так: Переводим это число в десятичную систему: = = Поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААЛ 4. ААААО 5. ААААШ 4. АААКА …… На каком месте от начала списка стоит слово ШКОЛА? Ответ: 2711

47 Задача 3 Решение: Буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов. В каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 3 4 = 81 вариант. Всего вариантов 5 · 81 = 405. Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? Ответ: 405

48 Задача 4 Решение: Различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А: АА*** А*А**А**А* А***А В каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций для каждого шаблона равно 3 3 = шаблона дают 4 · 27 = 108 комбинаций. Шаблоны, где первая по счёту буква А стоит на второй позиции: *АА** *А*А**А**А Они дают 3 · 27 = 81 комбинацию. Шаблона, где первая по счёту буква А стоит на третьей позиции: **АА* **А*А Они дают 2 · 27 = 54 комбинации. Шаблон, где сочетание АА стоит в конце:***АА. Они дают 27 комбинаций. Всего получаем = 270 комбинаций. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A? Ответ: 270

49 Задачи для тренировки: 1. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 450-м месте от начала списка. 2. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер первого слова, которое начинается с буквы У.

50 Задачи для тренировки: 3. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова РУКАА. 4. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 350-м месте от начала списка.

51 Задачи для тренировки: 5. Сколько слов длины 6, начинающихся и заканчивающихся согласной буквой, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. 6. Сколько слов длины 4, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв М, Е, Т, Р, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. 7. Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. 8. Сколько существует различных символьных последовательностей длины 5 в трёхбуквенном алфавите {К, О, T}, которые содержат ровно две буквы О?

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

53 Необходимо знать: 1. Если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной I равно N = M I ; для двоичного кодирования получаем известную формулу: N = 2 I 2. C помощью I бит можно закодировать N = 2 I различных вариантов (чисел) 3. Чтобы найти информационный объем текста ( I T), нужно умножить количество символов в тексте ( k) на число бит, которые отводятся на один символ (I). I T = k I 4. Соотношение между единицами измерения количества информации представляют собой степени двойки. 5. Число бит, которые отводятся на один символ (I ), вычисляется из формулы: N = 2 I, где N – количество символов в алфавите. 6. По формуле Шеннона количество информации в сообщении о произошедшем событии с номером i равно I i = - log 2 P i, где P i – вероятность этого события.

54 Задача 1 Решение: Всего используются = 34 символа. N = 2 I 34 = 2 I I = 6 бит (для кодирования 34 символов нужно выделить 6 бит памяти) бит = 66 бит 9 байт (для хранения всех 11 символов пароля ). Тогда 60 паролей занимают 9 байт 60 = 540 байт Ответ: 1) 540 байт Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который занимает хранение 60 паролей. 1) 540 байт 2) 600 байт 3) 660 байт 4) 720 байт

55 Задача 2 Решение: Всего используются = 62 символа. N = 2 I 62 = 2 I I = 6 бит (для кодирования 62 символов нужно выделить 6 бит памяти). 9 6 бит = 54 бит 7 байт (для хранения всех 9 символов пароля ). Тогда 100 паролей занимают 7 байт 100 = 700 байт Ответ: 3) 700 байт Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 9 символов. В качестве символов используются десятичные цифры и все буквы латинского алфавита (в латинском алфавите 26 букв, регистр букв не имеет значения). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который занимает хранение 100 паролей. 1) 600 байт 2) 675 байт 3) 700 байт 4) 720 байт

56 Задача 3 Решение: Всего используются = 29 символов. N = 2 I 29 = 2 I I = 5 бит (для кодирования 29 символов нужно выделить 5 бит памяти) бит = 50 бит 7 байт (для хранения всех 10 символов пароля ). Тогда 40 паролей занимают 7 байт 40 = 280 байт Ответ: 4) 280 байт В некоторой стране автомобильный номер длиной 10 символов составляют из заглавных букв (задействовано 19 различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти, отводимый этой программой для записи 40 номеров. 1) 160 байт 2) 200 байт 3) 240 байт 4) 280 байт

57 Задача 4 Решение: 64 < 100 < 128 I=Log 2 128= 7 бит 7 бит 80 = 560 бит = 70 байт Ответ: 70 байт Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

58 Задача 5 В классе 30 человек. За контрольную работу по математике получено 6 пятерок, 15 четверок, 8 троек и 1 двойка. Какое количество информации в сообщении о том, что Сидоров получил четверку? Ответ: 1 бит Решение: События разновероятные. Поэтому воспользуемся формулой: I=Log 2 (1/P)= - Log 2 P где I - количество информации, P - вероятность наступления события N = = 30 - всего оценок; Р ч = 15/30 = 1/2 вероятность получения четверки; I = - log 2 Р ч = - log 2 (1/2) = - (- 1) = 1 бит

59 Задача 6 Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено» «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 30 различных сигналов? Ответ: 4 лампочки Решение: Количество различных сигналов N = 3 I 30 = 3 I I = 4 лампочки

60 Задача 7 В коробке лежат три различных карандаша красного оттенка (розовый, малиновый, бордовый), три различных карандаша синего оттенка (голубой, лазурный, темно-синий) и несколько карандашей различных оттенков зеленого цвета. Сообщение о том, что достали бордовый карандаш, содержит 3 бита информации. Сколько карандашей зеленого оттенка находится в коробке? Ответ: 2 карандаша Решение: События равновероятные (все карандаши разного цвета) N = 2 I = 2 3 = 8 (карандашей, всего ) ­ 3 = 2 (карандаша зеленого оттенка)

61 Задача 8 В зелье Баба - яга положила: мухоморы и поганки. Всего 16 грибов. Сообщение о том, что положила мухомор, несет 2 бита информации. Сколько было поганок? Ответ: 12 поганок Решение: События разновероятные I=Log 2 (1/P)= - Log 2 P Х – мухоморы; 16-Х – поганки; Р м = Х/16 – вероятность того, что положили мухомор; I = - log 2 Р м = - log 2 (Х/16) 2 = - log 2 (Х/16) -2 = log 2 (Х/16) 2 -2 = Х/16 1/4 = Х/16 Х = 4 мухомора 16 – 4 = 12 поганок

62 Задачи для тренировки: 1. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов? 1) 642) 503) 324) Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля? 1) 42) 5 3) 6 4) 7 3. Для кодирования секретного сообщения используются 12 специальных значков-символов. При этом символы кодируются одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения длиной в 256 символов? 1) 256 бит 2) 400 бит 3) 56 байт 4) 128 байт 4. Мощность алфавита равна 64. Сколько Кбайт памяти потребуется, чтобы сохранить 128 страниц текста, содержащего в среднем 256 символов на каждой странице? 1) 82) 12 3) 24 4) 36

63 Задачи для тренировки: 5. В велокроссе участвуют 678 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 200 велосипедистов? 1) 200 бит 2) 200 байт 3) 220 байт 4) 250 байт 6. Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)? 7. В школе 800 учащихся, коды учащихся записаны в школьной информационной системе с помощью минимального количества бит. Каков информационный объем сообщения о кодах 320 учащихся, присутствующих на конференции? 1) 2560 бит 2) 100 байт 3) 6400 бит 4) 400 байт

64 Задачи для тренировки: 8. В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б? 1) 42) 16 3) 28 4) В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике? 1) 162) 243) 304) В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти? 1) 22) 3 3) 4 4) Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)? 12. Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в четыре секунды можно передать при помощи этого устройства?

65 Задание 16 Знание позиционных систем счисления

66 Необходимо знать: 1. Принципы кодирования чисел в позиционных системах счисления. 2. Чтобы перевести число из системы счисления с основанием N в десятичную систему, нужно умножить значение каждой цифры числа на N в степени, равной ее разряду. Например, N = 1·N 4 + 2·N 3 + 3·N 2 + 4·N 1 + 5·N 0 3. Последняя цифра записи числа в системе счисления с основанием N – это остаток от деления этого числа на N. 4. Две последние цифры – это остаток от деления числа на N 2, и т.д. 5. Число 2 N в двоичной системе записывается как единица и N нулей. 6. Число 2 N -1 в двоичной системе записывается как N единиц. 7. Число 2 N –2 K при K < N в двоичной системе записывается как N–K единиц и K нулей.

67 Задача 1 Ответ: 3 Запись числа в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Чему равно основание этой системы счисления N? Поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа на N равен 1, то есть при некотором целом k имеем k N + 1 = k N = следовательно, основание N – это делитель числа 66. С другой стороны, запись числа содержит 4 цифры, то есть 1000 N < N N < N 4 Выпишем кубы и четвертые степени первых натуральных чисел: 2 3 = 8, 3 3 = 27, 4 3 = 64, 5 3 = 125, … 2 4 = 16, 3 4 = 81, … Из этого списка только для числа N = 3 выполняется условие N < N 4 Сделаем проверку, переведя число в троичную систему = Решение:

68 Задача 2 Ответ: 7 Сколько существует различных систем счисления в которых число 40 оканчивается на 0. Поскольку запись в системе счисления с основанием N заканчивается на 0, то остаток от деления числа на N равен 0, то есть при некотором целом k имеем k N + 0 = k N = Следовательно, основание N – это делитель числа Запишем все делители числа: = 2 20 = 4 10 = 5 8 = 1 40 Из этого списка следует, что существуют системы счисления со следующими основаниями N = 2, 4, 5, 8, 10, 20, 40, то есть всего 7 различных систем счисления. Решение:

69 Задача 3 Ответ: 20 Решите уравнение Ответ запишите в троичной системе счисления. Основание системы счисления указывать не нужно. Переведём все числа в десятичную систему счисления: Соберём всё в одно уравнение: Это уравнение имеет два решения, 6 и -8; основание системы счисления – натуральное число, поэтому ответ – 6. Переведём ответ в троичную систему: 6 = Решение:

70 Задача 4 Ответ: 2015 Сколько единиц в двоичной записи числа – 15 Приведём все числа к степеням двойки: – 15 = (2 2 ) – = – Вспомним, что число 2 N -1 в двоичной системе записывается как N единиц, а число 2 N –2 K при K < N записывается как N–K единиц и K нулей: Тогда, число – 2 4 запишется как 2013 единиц и 4 нуля. Прибавление даст ещё одну единицу, всего получается = 2014 единиц. Прибавление 1 даст ещё одну единицу, всего получается = 2015 единиц. Решение:

71 Задачи для тренировки: 1. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на В саду 100 х фруктовых деревьев, из которых 33 х – яблони, 23 х – груши, 16 х – сливы, 16 х – вишни. В системе счисления с каким основанием вели счет? 3. Чему равно значение основания системы счисления Х, если известно, что 175 х = 7D 16 ? 4. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4 5. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на Запись числа 344 в некоторой системе счисления выглядит так: 1A8 q. Найдите основание системы счисления q. 7. К записи натурального числа в восьмеричной системе счисления справа приписали два нуля. Во сколько раз увеличилось число? Ответ запишите в десятичной системе счисления.

72 Задачи для тренировки: 8. Сколько единиц в двоичной записи числа – – Сколько единиц в двоичной записи числа – Запись числа в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N. 11. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17 в системе счисления с основанием Укажите наименьшее основание системы счисления, в которой запись числа 30 трёхзначная.

73 Задание 9 Скорость передачи информации при заданной пропускной способности канала (Подробно рассмотрено на семинаре О.Б. Богомоловой)

74 Необходимо знать: 1. Обмен информацией производится по каналам передачи информации. Общая схема передачи информации включает в себя отправителя информации, канал передачи и получателя информации. 2. Основной характеристикой каналов передачи информации является их пропускная способность (скорость передачи информации). Пропускная способность канала равна количеству информации, которое может передаваться по нему в единицу времени. 3. Пропускная способность измеряется в бит/с, байт/c, Кбит/c, Кбайт/c, и т.д. 4. Объем переданной информации вычисляется по формуле где v – пропускная способность канала (в битах в секунду или подобных единицах), t – время передачи. I = v t., Отправитель информации Получатель информации Канал передачи

75 Задача 1 Информационное сообщение объемом 2,5 Кбайт передается со скоростью 2560 бит/мин. За сколько минут будет передано данное сообщение? Дано: I = 2,5 Кбайт v = 2560 бит/мин Найти: t ( мин ) - ? Решение: время V = 2560 бит/мин t (мин) - ? I (байт ) – 2,5 Кбайт t = = = = = 0,5 2 = 8 мин I v 2,5 Кбайт 2560 бит/мин 10 2,5 2 2 бит бит/мин 9. 2, Ответ: 8

76 Задача 2 Файл размером 8 Кбайт передаётся через некоторое соединение со скоростью 4096 бит в секунду. Определите размер файла (в байтах), который можно передать за то же время через другое соединение со скоростью 256 бит в секунду. В ответе укажите одно число размер файла в байтах. Единицы измерения писать не нужно. Дано: I 1 = 8 Кбайт v 1 = 4096 бит/c v 2 = 256 бит/c Найти: I 2 ( байт ) - ? Решение: t = = = = = 8 2 = 16 с I1I1 v1v1 8 Кбайт 4096 бит/с бит бит/с I 2 = v 2 t = 256 бит/c 16 c = 2 8 бит/c 2 4 c = 2 12 бит = 2 9 байт = 512 байт 12 Ответ: 512

77 У Коли есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2 бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Коли по телефонному каналу со средней скоростью 2 бит в секунду. Сергей договорился, что Коля скачает данные объемом 9 Мбайт по высокоскоростному каналу и ретранслирует их Сергею по низкоскоростному каналу. Компьютер Коли может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Колей данных до полного их получения Сергеем? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно. Задача 3 Коля Сергей Интернет V А = 2 БИТ/С 20 V о = 2 БИТ/С

78 t V А = 2 БИТ/С V о = 2 БИТ/С Коля скачивает весь файл объемом 9 Мб Сергей получает весь файл от Коли t 1t 1 t 2 Время скачивания Колей первых 1024 Кбайт Время скачивания Сергеем всего файла объемом 9 Мбайт t = t 1 + t 2 Полное время передачи файла V о = 2 БИТ/С

79 Решение: t = t 1 + t 2 = + = = + = = 2312 (секунд) 1024 Кбайт 2 бит/с 20 9 Мбайт 2 бит/с бит бит/с бит бит/с Ответ: 2312

80 Задачи для тренировки: 1. Сколько секунд потребуется обычному модему, передающему сообщения со скоростью бит/с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами? 2. Скорость передачи данных через модемное соединение равна бит/с. Передача текстового файла через это соединение заняла 10 с. Определите, сколько символов содержал переданный текст, если известно, что он был представлен в 16-битной кодировке Unicode. 3. Модем передает данные со скоростью 7680 бит/с. Передача текстового файла заняла 1,5 мин. Определите, сколько страниц содержал переданный текст, если известно, что он был представлен в 16-битной кодировке Unicode, а на одной странице – 400 символов. 4. Передача данных через ADSL-соединение заняла 2 минуты. За это время был передан файл, размер которого Кбайт. Определите минимальную скорость (бит/c), при которой такая передача возможна. 5. Саша скачивает из сети файл размером 60 Мбайт. Скорость передачи первой половины данных составляет 256 Кбит в секунду, а второй – в два раза меньше. Сколько минут будет скачиваться файл?

81 Задачи для тренировки: 6. Документ объемом 10 Мбайт можно передать с одного компьютера на другой двумя способами: А) Сжать архиватором, передать архив по каналу связи, распаковать Б) Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если – средняя скорость передачи данных по каналу связи составляет 2 18 бит в секунду, – объем сжатого архиватором документа равен 30% от исходного, – время, требуемое на сжатие документа – 7 секунд, на распаковку – 1 секунда? В ответе напишите букву А, если способ А быстрее или Б, если быстрее способ Б. Сразу после буквы напишите количество секунд, насколько один способ быстрее другого. Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Слов «секунд», «сек.», «с.» к ответу добавлять не нужно.

82 Источники заданий: 1) Демонстрационные варианты ЕГЭ гг. 2) Е.М. Островская, Н.Н. Самылкина ЕГЭ Информатика. Сдаем без проблем! М.: Эксмо, ) Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ Информатика. Универсальные материалы для подготовки учащихся. Интеллект-Центр, ) Тренировочные и диагностические работы МИОО гг. 5) Задания для тренировки с сайта К. Полякова