Решение задач. БЛОК « ИНФОРМАЦИЯ И ЕЕ КОДИРОВАНИЕ » - презентация

1 Решение задач

2 БЛОК « ИНФОРМАЦИЯ И ЕЕ КОДИРОВАНИЕ »

3 Теоретический материал : - единицы измерения информации ; - понятие о кодировании различной информации ; - системы счисления. По данному тематическому блоку необходимо продемонстрировать следующие умения : - подсчитывать информационный объем сообщения ; - осуществлять перевод из одной системы счисления в другую ; - осуществлять арифметические действия в двоичной, восьмеричной и шестнадцатеричной системах счисления. Задания занимают следующие позиции в вариантах КИМ : А 1- А 5, А 13, В 1, В 5.

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

5 При выполнении этого задания иногда возникают вопросы : « Как точно узнать количество пробелов в фразе ? Считать ли точку в конце частью задания или частью оцениваемой фразы ?» В точном подсчете символов в данном случае нет необходимости, поскольку в задании требуется оценить информационные фразы, т. е. из предложенных вариантов ответа выбрать наиболее близкий к полученному учащимся. Если полученный результат существенно отличается от всех предложенных вариантов, то это означает либо арифметическую ошибку, либо то, что надо выразить полученное значение в битах через байты или наоборот.

6 Пример 1. Каждый символ в Unicode закодирован двухбайтным словом. Оцените информационный объем следующего предложения в этой кодировке : Без труда не вытащишь рыбку из пруда. 1) 37 бит 2) 592 бита 3) 37 байт 4) 592 байта

7 Пример 1. Каждый символ в Unicode закодирован двухбайтным словом. Оцените информационный объем следующего предложения в этой кодировке : Без труда не вытащишь рыбку из пруда. 1) 37 бит 2) 592 бита 3) 37 байт 4) 592 байта Решение : Длина фразы составляет 37 символов ( вместе с точкой ). Следовательно, ее объем можно оценить в 37 * 2 = 74 байт. Такого варианта ответа нет, попробуем перевести результат в биты : 74 байт * 8 = 592 бит. Ответ : 2.

8 « Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100%, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений ». Следует пользоваться формулой алфавитного подхода к измерению количества информации I = M*log 2 N, где N количество символов ( мощ ­ ность ) алфавита, в котором записано сообщение, М количество символов в записи сообщения ( длина сообщения ), l количество бит информации, содержащееся в сообщении. Если log N не является целым числом, то l округляется в большую сторону. Информационный объем сообщения, выраженный в битах и минимальное количество двоичных разрядов, требуемое для записи сообщения в двоичном алфавите совпадают. Из приведенной формулы легко получить следующее следствие : с помощью п двоичных разрядов ( бит ) можно закодировать двоичным кодом все элементы множества мощностью 2 n ( т. е. состоящего из 2 n элементов ). Информационный объем одного символа алфавита, обозначающего элемент данного множества, будет равен n. Пример 2.

9 Решение Способ 1 Воспользуемся приведенной выше формулой. Алфавитом в данном случае является множество целочисленных значений влажности от 0 до 100. Таких значений 101. Поэтому, информационный объем результатов одного измерения l = log Это значение не будет целочисленным. Не вычисляя его, сразу найдем округленное в большую сторону целое значение. Заметим, что ближайшая к 101 целая степень двойки, большая 101, есть число 128 = 2 7. Поэтому принимаем l = log 2 128=7 бит. Учитывая, что станция сделала 80 измерений, общий информационный объем равен 80 * 7= 560 бит = 70 байт. Ответ : 70 байт.

10 Решение Способ 2 Воспользуемся следствием из формулы. Заметим, что 2 6 < 101 < 2 7, поэтому минимально необходимое количество двоичных разрядов ( бит ) равно 7. Далее аналогично получаем, что общий информационный объем равен 80 * 7=560 бит = 70 байт. Ответ : 70 байт.

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

12 Пример Скорость передачи данных через ADSL- соединение равна бит / с. Передача файла через данное соединение заняла 3 мин. Определите размер файла в килобайтах.

13 Решение Размер файла = скорость * время передачи. Выразим время в секундах, а скорость в килобайтах в секунду.

14 Пример Скорость передачи данных через ADSL- соединение равна бит / с. Передача файла через данное соединение заняла 3 мин. Определите размер файла в килобайтах. Решение Размер файла = скорость время передачи. Выразим время в секундах, а скорость в килобайтах в секунду. Размер файла = /(8 1024) 3 60 Кбайт. Прежде чем выполнять действия, выделим в явном виде, там, где это очень просто, степени двойки. Размер файла = /( ) = / ( ) = /2 13 = = 5625 Кбайт. Ответ : 5625.

15 Пример Сколько секунд потребуется модему, передающему сообщения со скоростью бит / с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами ?

16 Пример Сколько секунд потребуется модему, передающему сообщения со скоростью бит / с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами ? Решение Поскольку на кодирование каждого пикселя приходится 3*8=24 бита, то общий объем передаваемой информации составляет 640*480*24 бита. Таким образом время передачи информации ( в секундах ) равно 640 * 480 * 24/28800 = 64 * 4 = 256 с. Ответ : 256 с.

17 Для быстрого и правильного решения заданий необходимо знать : наизусть значения целых степеней числа 2 от 2 0 до 2 10, представление чисел от 0 до 16 в системах счисления с основаниями 2, 8, 10, 16, Свойства систем счисления с основаниями вида Р = Q" ( в этом случае одной цифре в записи числа в системе с основанием Р соответствует п цифр в системе с основанием Q).

18

19

20 Пример Количество значащих нулей в двоичной записи десятичного числа 126 равно : 1) 1 2) 2 3) 3 4) 0

21 Решение Способ 1 Преобразуем число 126 в двоичную систему с помощью известного алгоритма деления « уголком » с выделением остатков : 126 : 2 = 63 ( ост. 0 ) 63 : 2 = 31 ( ост. 1 ) 31 : 2 = 15 ( ост. 1 ) 15 : 2 = 7 ( ост. 1 ) 7 : 2 = 3 ( ост. 1 ) 3 : 2 = 1 ( ост. 1 ) Выписав остатки от деления, получим = В двоичной записи один значащий нуль. Ответ : 1.

22 Способ 2 Заметим, что = = = Ответ : 1.

23 БЛОК « АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ »

24 Данный блок содержит самый объемный и сложный материал курса информатики, знания и умения по которому представлены на всех трех уровнях сложности. На уровне воспроизведения знаний проверяется фундаментальный теоретический материал, такой как : - понятие алгоритма, его свойств, способов записи ; - основные алгоритмические конструкции ; - основные элементы программирования. Материал на проверку сформированности умений применять свои знания в стандартной ситуации входит во все три части экзаменационной работы. По данному тематическому блоку это следующие умения : - использовать стандартные алгоритмические конструкции при программировании ; - формально использовать алгоритмы, записанные на естественных и алгоритмических языках, в том числе на языках программирования. Материал на проверку сформированности умений применять свои знания в новой ситуации входит во вторую и третью части работы. Это следующие сложные умения : - анализировать текст программы с точки зрения соответствия записанного алгоритма поставленной задаче и изменять его в соответствии с заданием ; - реализовывать сложный алгоритм с использованием современных систем программирования. Задания занимают следующие позиции в вариантах КИМ : А 6, А 7, А 8, А 20, В 3, В 6, С 1- С 4.

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

26 Пример : Цепочки символов ( строки ) создаются по следующему правилу. Первая строка состоит из одного символа цифры «1». Каждая из последующих цепочек создается такими действиями : в очередную строку дважды записывается цепочка цифр из предыдущей строки ( одна за другой, подряд ), а в конец приписывается еще одно число номер строки по порядку ( на i- м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу : 1)1 2)112 3) ) Какая цифра стоит в седьмой строке на 121- м месте ( считая слева направо )?

27 Решение : Найдем длину седьмой строки. По условию, длина каждой последующей строки увеличивается в 2 раза, по сравнению с предыдущей, плюс еще один символ цифра, обозначающая порядковый номер самой строки. Получается, что длина строк составит : 1) 1 элемент в строке ; 2) 1*2 + 1 = 3 элемента в строке ; 3) 3*2 + 1 = 7; 4) 7*2 + 1 = 15; 5) 15*2+1 = 31; 6) 31*2 + 1=63; 7) 63*2 + 1 = 127 элементов в строке. Требуется найти 121- й элемент в строке длиной в 127 симво ­ лов. Это означает, что нам нужен седьмой элемент с конца. По ­ скольку в конец строки на каждом шаге добавляется его номер ( совпадающий с номером формируемой строки ), то последние семь символов 7- й строки будут Таким образом, седьмой символ с конца единица. Ответ : 1.

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

29 Пример : Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды: Вперед n, вызывающая передвижение Черепашки на п шагов в направлении движения. Направо т, вызывающая изменение направления движения на т градусов по часовой стрелке. 0 т 180. (Вместо п и т должны стоять целые числа). Запись: Повтори 5 [Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторится 5 раз. Какое число необходимо записать вместо п в следующем алгоритме: Повтори 6 [Вперед 40 Направо п], чтобы на экране появился правильный пятиугольник.

30 Решение : Сумма внутренних углов правильного пятиугольника вычисляется по формуле ( р - 2) * 180 / р, где р =5. Поэтому величина одного внутреннего угла будет равна (5 - 2) * 180 / 5 = 108°. А угол поворота Черепашки в вершине пятиугольника будет равен углу, смежному с внутренним углом, т. е. 180 – 108 = 72°. Черепашка прочертит на экране 6 отрезков, но последний отрезок полностью совпадет с первым, так как после пятого выполнения цикла Черепашка полностью обернется вокруг своей оси (72 * 5 = 360°) и окажется в той же точке, что и изначально. Так что на экране появится правильный пятиугольник. Ответ : 72.

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

32 Пример : Определите значение переменной т после выполнения фрагмента алгоритма : Примечание : знаком := обозначена операция присваивания. 1) 1 2) 2 3) 3 4) 33

33 Решение Способ 1 Составим таблицу переменных, добавив в нее для удобства результаты вычисления логических выражений. Ответ : 3.

34 Способ 2 Внимательно проанализировав блок - схему, можно сделать вывод, что она реализует известный алгоритм Евклида нахождения наибольшего общего делителя двух чисел, который для 81 и 48 равен трем. (81 = 3 4, 48 =3 * 16.) Ответ : 3.

35 БЛОК « ОСНОВЫ ЛОГИКИ »

36 В соответствии с обобщенным планом экзаменационной работы по информатике на уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как основные элементы математической логики. Материалы на проверку сформированности умений применять свои знания в стандартной ситуации входит в первый две части экзаменационной работы. Это умения : - составлять и преобразовывать логические выражения ; Формировать для логической функции таблицу истинности и логическую схему. Материал на проверку сформированности умений применять свои знания в новой ситуации входит во вторую часть работы. Это умение преобразовывать сложные логические высказывания. Задания занимают следующие позиции в варианте : А 9- А 11, В 2, В 4. Для успешного выполнения заданий по основам логики, учащиеся должны твердо усвоить символику и определения ( таблицы истинности ) трех основных логических операций ( инверсия, конъюнкция, дизъюнкция ), а также импликации. Кроме того, необходимо знать и уметь применять при работе с логическими выражениями основные законы логики. Полезно знать законы логики и свойства конъюнкции, дизъюнкции и импликации.

37 Задание Символом F обозначено одно из указанных логических выражений от трех аргументов : X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

38 Способ 1 Пример : Символом F обозначено одно из указанных ниже логических выражений от трех аргументов : X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1) 2) 3) 4)

39 Решение : 1. Последовательно подставим первую строку таблицы истинности во все варианты ответов. 2. Сравним полученные результаты со значениями столбца F таблицы истинности. « Отбросим » строки в которых полученные значения не совпадают со значениями в таблице истинности. 3. Последовательно подставим вторую строку таблицы истинности во все варианты ответов, оставшиеся после п.2…. 4. И т. д. 5. Единственная оставшаяся строка ( из всех строк с приведенными ответами ), значения в которой совпали со всеми значениями столбца F таблицы истинности, и есть решение задания.

40

41 Способ 2 Пример : Символом F обозначено одно из указанных ниже логических выражений от трех аргументов : X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1) 2) 3) 4)

42 Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z: Заметим, что значения истинности одинаковы для логических выражений F и при любых значениях аргументов X, Y, Z из данного фрагмента, следовательно, эти логические выражения равносильны. Ответ 3.

43 Рассмотрим приемы решения текстовой логической задачи. Пример : Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на красном « Рено », Джон сказал, что нарушитель уехал на синей « Тойоте », а Сэм показал, что машина была точно не красная и, по всей видимости, это был « Форд ». Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля, а в другом ошибся. Какая и какого цвета была машина у нарушителя ? Ответ запишите в виде двух слов, разделенных пробелом : МАРКА ЦВЕТ. Например : ЖИГУЛИ БЕЛЫЙ.

44

45 Способ 2 Решим задачу методом рассуждений. Предположим, что Боб правильно сообщил цвет, но ошибся в марке. Следовательно, машина красная, и не « Рено ». Тогда получается, что Джон ошибся в цвете, но верно сообщил марку - « Тойота ». Итак, предварительный вывод красная « Тойота ». Но при этом получается, что вопреки условиям задачи Сэм ошибся и в цвете, и в марке. Мы пришли к противоречию, значит, исходное предположение было неверным. Отсюда мы заключаем, что Боб верно указал марку « Рено », но ошибся в цвете. Итак, машина « Рено », но не красного цвета. Учитывая, что машина точно не « Тойота », из показаний Джона вытекает, что машина была синей. При этом также выполняется условие для показаний Сэма. Ответ : « РЕНО СИНИЙ ».

46 БЛОК « ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ И СИСТЕМЫ »

47 Целью не является проверка знаний и умений учащихся применительно к конкретным программным продуктам, операционным системам или технологиям определенных фирм - производителей компьютерного оборудования и программного обеспечения. В связи с этим контрольные измерительные материалы по данной теме ориентированы на проверку их знаний об общих, инвариантных закономерностях тех или иных информационных технологий. Задания занимают следующие позиции в варианте : А 16- А 19, В 7, В 8.

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

49 Пример : Для хранения растрового изображения размером 128x128 пикселей отвели 4 килобайта памяти. Каково максимально возможное число цветов в палитре изображения ? 1) 8 2) 2 3) 16 4) 4.

50 Решение : Подсчитаем количество пикселей в изображении : 128 * 128 = 2 7 * 2 7 = Вычислим объем памяти в битах : 4 Кб = 4 * 2 10 байт = 2 2 * 2 10 * 23 = 2 15 бит. Таким образом, на один пиксель изображения приходится 2 15 / 2 14 = 2 бита. Как известно, двумя двоичными разрядами можно закодировать четыре разных состояния объекта, в данном случае четыре цвета пикселя. Ответ : 4.

51 Еще раз обратите внимание на необходимость использовать свойства степенной функции вместо вычисления « в лоб ». Приведем пример решения обратной задачи.

52 Пример : Укажите минимальный объем памяти ( в килобайтах ), достаточный для хранения любого растрового изображения размером 32 х 32 пикселя, если известно, что в изображении используется палитра из 256 цветов. Саму палитру хранить не нужно. 1) 1 2) 2 3) 64 4) 1024

53 Решение : Исходя из количества цветов в палитре определим минимальное количество двоичных разрядов, необходимое для хранения одного пикселя. Для представления 256 различных состояний требуется log = 8 двоичных разрядов, т. е. 1 байт. Поэтому для представления изображения размером 32 x 32 пикселя потребуется 32 * 32 = 2 5 * 2 5 = 2 10 байт информации, т. е. 1 Кб. Ответ : 1.

54 Хранение, поиск и сортировка информации в базах данных Основными операциями, встречающимися в заданиях этой темы, являются отбор ( поиск ) записей по некоторым условиям и их сортировка

55 Пример : Далее в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся ( используется стобальная шкала ): Сколько записей в данном фрагменте удовлетворяют условию « Пол =' м ' ИЛИ Химия > Биология »? 1) 52) 23) 34) 4

56 Решение : Решая данную задачу, надо последовательно применять условие к каждой строке таблицы. Условию удовлетворяют учащиеся : Воронин, Григорчук, Сергеенко и Черепанова. У Аганян и Родниной не соответствует условию ни пол, ни соотношение баллов по химии и биологии. 1) 52) 23) 34) 4 Ответ : 4.