Форум МОУ Орловской средней общеобразовательной школы №1

БЛОК «ИНФОРМАЦИЯ И ЕЕ КОДИРОВАНИЕ»
В соответствии с обобщенным планом экзаменационной работы по информатике на уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как:
- единицы измерения информации;
- понятие о кодировании различной информации;
- системы счисления.
Материал на проверку сформированности умений применять свои знания в стандартных ситуациях входит во все три части экзаменационной работы. По данному тематическому блоку это следующие умения:
- подсчитывать информационный объем сообщения;
- осуществлять перевод из одной системы счисления в другую;
- осуществлять арифметические действия в двоичной, восьмеричной и шестнадцатеричной системах счисления.
Задания занимают следующие позиции в вариантах КИМ: А1-А5, А13, В1, В5.
Причиной немногочисленных ошибок при выполнении за¬даний на оценку информационного объема фразы в различных кодировках обычно являются смешивание или не¬правильная интерпретация учащимися таких элементарных по¬нятий, как «бит» и «байт», а также неверные арифметические вычисления. Следует также обратить внимание на то, что в от¬ветах используются обе единицы измерения количества инфор¬мации.
При выполнении этого задания у учащихся иногда возникают вопросы: «Как точно узнать количество пробелов в фразе? Счи¬тать ли точку в конце частью задания или частью оцениваемой фразы?» В точном подсчете символов в данном случае нет необходимости, поскольку в задании требуется оценить информаци¬онные фразы, т.е. из предложенных вариантов ответа выбрать наиболее близкий к полученному учащимся. Если полученный результат существенно отличается от всех предложенных вари¬антов, то это означает либо арифметическую ошибку, либо то, что надо выразить полученное значение в битах через байты или наоборот.
Пример.
Каждый символ в Unicode закодирован двухбайтным словом. Оцените информационный объем следующего предложения в этой кодировке:
Без труда не вытащишь рыбку из пруда.
1) 37 бит 2) 592 бита 3) 37 байт 4) 592 байта
Решение:
Длина фразы составляет 37 символов (вместе с точкой). Следователь-но, ее объем можно оценить в 37 х 2 = 74 байт. Такого варианта ответа нет, попробуем перевести результат в би¬ты: 74 байт х 8 = 592 бит.
Ответ: 2.

При выполнении заданий следующего типа: «Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100%, которое записывается при помощи минимально воз¬можного количества бит. Станция сделала 80 измерений. Опреде¬лите информационный объем результатов наблюдений», следует пользо¬ваться формулой алфавитного подхода к измерению количества информации I = M-log2N, где N — количество символов (мощ¬ность) алфавита, в котором записано сообщение, М — количество символов в записи сообщения (длина сообщения), l — количество бит информации, содержащееся в сообщении. Если log N не яв-ляется целым числом, то l округляется в большую сторону.
Информационный объем сообщения, выраженный в битах и минимальное количество двоичных разрядов, требуемое для записи сообщения в двоичном алфавите совпадают.
Из приведенной формулы легко получить следующее след¬ствие: с помощью п двоичных разрядов (бит) можно закодировать двоичным кодом все элементы множества мощностью 2n (т.е. со¬стоящего из 2n элементов). Информационный объем одного сим¬вола алфавита, обозначающего элемент данного множества, будет равен n.
Решение
Способ 1
Воспользуемся приведенной выше формулой. Алфавитом в данном случае является множество целочисленных значений влажности от 0 до 100. Таких значений 101. Поэтому, информа¬ционный объем результатов одного измерения l=log2 101. Это зна¬чение не будет целочисленным. Не вычисляя его, сразу найдем округленное в большую сторону целое значение. Заметим, что ближайшая к 101 целая степень двойки, большая 101, есть чис¬ло 128 = 27. Поэтому принимаем l=log2128=7 бит. Учитывая, что станция сделала 80 измерений, общий информационный объем равен 80 х 7= 560 бит = 70 байт. Ответ: 70 байт.
Способ 2
Воспользуемся следствием из формулы. Заметим, что 26< 101 < 27, поэтому минимально необходимое количество двоичных разрядов (бит) равно 7. Далее аналогично получаем, что общий информационный объем равен 80 х 7=560 бит= 70 байт. Ответ: 70 байт.

При выполнении заданий, связанных с понятием скорости передачи данных, часто допускаются ошибки, связан¬ные с неверным использованием размерности единиц измерения. Следует следить за размерностью исходных данных и размерно¬стью, в которой требуется записать результат. Для успешного вы¬полнения заданий такого типа нужно потренироваться в переводе Кбит/мин в Кбайт/с и т.д.
Пример
Скорость передачи данных через ADSL-соединение равна 256000 бит/с. Передача файла через данное соединение заняла 3 мин. Определите размер файла в килобайтах.
Решение
Размер файла = скорость х время передачи. Выразим время в секундах, а скорость — в килобайтах в секунду.
Размер файла = 256 000/(8 • 1024) • 3 • 60 Кбайт.
Прежде чем выполнять действия, выделим в явном виде, там, где это очень просто, степени двойки.
Размер файла = 28 • 1000/(23 • 210) • 3 • 15 • 4 = 28 • 125 • 23/ (23 • 210) • • 45 • 22 = 213 • 125 • 45/213 = 125 • 45 = 5625 Кбайт. Ответ: 5625.

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

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

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

Для быстрого и правильного решения заданий ЕГЭ, уча¬щийся, помимо умения применять стандартные алгоритмы перевода чисел из одной системы счисления в другую, должен знать:
 наизусть значения целых степеней числа 2 от 2° до 210,
 представление чисел от 0 до 16 в системах счисления с основаниями 2, 8, 10, 16,
 свойства систем счисления с основаниями вида Р = Q" ( в этом случае одной цифре в записи числа в системе с основанием Р соответствует п цифр в системе с основанием Q).

n 0 1 2 3 4 5 6 7 8 9 10
2n 1 2 4 8 16 32 54 128 256 512 1024

Основание 10 2 8 16
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 А
11 1011 13 В
12 1100 14 С
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10

Пример
Количество значащих нулей в двоичной записи десятичного числа 126 равно:
1) 1 2) 2 3) 3 4) О
Решение
Способ 1
Преобразуем число 126 в двоичную систему с помощью из-вестного алгоритма деления «уголком» с выделением остатков:

126 2
0 63 2

1 31 2
1 15 2
1 7 2
1 3 2
1 1 2
1 0
Выписав остатки от деления, получим 12610=11111102. В дво¬ичной записи один значащий нуль. Ответ: 1.
Способ 2
Заметим, что 126=128-2 = 100000002-102=11111102
Ответ: 1.

Пример
Укажите через запятую в порядке возрастания все числа, не превосходящие 25, запись которых в двоичной системе счисле¬ния оканчивается на 101. Ответ запишите в десятичной системе счисления.
Решение
1012 = 58. Найдем числа, не превосходящие 25, запись которых в восьмеричной системе счисления оканчивается на 5. Посколь¬ку, 25<82, такие числа должны иметь представление х =qx8+5, где q — цифра восьмеричной системы. Так как х 25, q 2. Под¬ставив допустимые значения q, получим искомые значения х:
q x =q x 8+5
0 5
1 13
2 21

Выполним проверку:
510=1012;
1310=11012;
2110=101012.
Ответ: 5, 13, 21.

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

Проанализировав КИМ по информатике можно отметить, что знания и умения, связанные с использованием основных алгоритмических конструкций, выявлялись как заданием на исполнение и анализ отдельных алгоритмов, записанных в виде блок-схемы, на алгоритмическом языке или на языках программирования, так и заданиями на составление алгоритмов для конкретного исполнителя (задание с кратким ответом) и анализ дерева игры.
Приведем пример решения типичного задания на исполнение алгоритма, сформулированного на естественном языке.
Пример:
Цепочки символов (строки) создаются по следующему пра¬вилу.
Первая строка состоит из одного символа — цифры «1».
Каждая из последующих цепочек создается такими действия¬ми: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписы¬вается еще одно число — номер строки по порядку (на i-м шаге дописывается число «i»).
Вот первые 4 строки, созданные по этому правилу:
1)1 2)112 3)1121123 4)112112311211234
Какая цифра стоит в седьмой строке на 121-м месте (считая слева направо)?
Решение:
Найдем длину седьмой строки. По условию, длина каждой последующей строки увеличивается в 2 раза, по сравнению с предыдущей, плюс еще один символ — цифра, обозначающая порядковый номер самой строки.
Получается, что длина строк составит:
1) 1 элемент в строке;
2) 1x2 + 1 = 3 элемента в строке;
3) 3x2 + 1 = 7;
4) 7x2 + 1 = 15;
5) 15x2+1 = 31;
6) 31x2 + 1=63;
7) 63x2 + 1 = 127 элементов в строке.
Требуется найти 121-й элемент в строке длиной в 127 симво¬лов. Это означает, что нам нужен седьмой элемент с конца. По¬скольку в конец строки на каждом шаге добавляется его номер (совпадающий с номером формируемой строки), то последние семь символов 7-й строки будут 1234567. Таким образом, седьмой символ с конца — единица.
Ответ: 1.

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

Высоким уровнем сложности обладают задания, в которых требуется построить дерево игры по заданному алгоритму и обо-сновать выигрышную стратегию. При выполнении таких заданий надо не только верно ука¬зать выигрывающего игрока и его стратегию, но и дать ей стро¬гое обоснование, перебрав все варианты ходов обоих игроков, возможные при реализации одним из них своей выигрышной стратегии.
Пример:
Два игрока играют в следующую игру. Имеются три кучки камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь кучке, или добавить по два камня в каж¬дую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней. Выигрывает тот игрок, после чьего хода в какой-нибудь кучке становится не менее 15 камней или во всех трех кучках суммарно ста¬новится не менее 25 камней. Игроки ходят по очереди. Выясните, кто выигрывает при пра¬вильной игре, — первый или второй игрок.
Решение (развернутый ответ):
Для решения задачи составим таблицу (дерево развития игры при разных продолжениях).
В колонке 0 показано начальное со¬стояние игры (вершина дерева игры), в колонке 1 показаны 4 возможных состояния игры после 1-го хода 1-го игрока, в колонке 2 показано 16 возможных состояний игры после 1-го хода 2-го игрока, далее дерево игры не ведется, а проводится анализ уже рассчитанных состояний игры.
Если 1-й игрок сделает свой первый ход 2,3,4 —>4,3,4, то 2-й игрок при правильной игре сделает ход 4,3,4 —>4,6,4, что при¬водит к проигрышу 1-го игрока (т.к. из состояния (4,6,4) 1-й игрок может своим ходом перевести игру в одно из четырех со¬стояний — (8,6,4), (4,12,4), (4,6,8), (6,8,6), и для любого из этих состояний найдется ход 2-го игрока, дающий ему выигрыш, на¬пример, по критерию S>25 ).
Если 1-й игрок сделает свой первый ход 2,3,4 —>2,6,4, то 2-й игрок при правильной игре сделает ход 2,6,4 —> 4,6,4, что, как мы только что видели, приводит к выигрышу 2-го игрока.
Если 1-й игрок сделает свой первый ход 2,3,4 —>2,3,8, то его проигрыш очевиден, так как 2-й игрок, как указано в таблице, добьется выигрывающего состояния игры 2,3,16.
Наконец, если 1-й игрок сделает свой первый ход 2,3,4 —> 4,5,6, то он выигрывает игру, т.к. на любой из четырех возмож¬ных ответов 2-го игрока (см. табл.) есть выигрывающий ход 1-го игрока.
Таким образом, при правильной игре выигрывает 1-й игрок (при этом его первый ход должен быть 2,3,4 —>4,5,6)

Начальное состояние 1-й ход
первого игрока 1-й ход
второго игрока 2-й ход
первого игрока
2,3,4 4,3,4 4,6,4
Приводит к выигрышу второго игрока при любом втором ходе первого игрока
2,6,4 4,6,4
Приводит к выигрышу второго игрока при любом втором ходе первого игрока
2,3,8 2,3,16
Выигрыш второго игрока

4,5,6 8,5,6 16,5,6
Выигрыш первого игрока
4,10,6 4,20,6
Выигрыш первого игрока
4,5,12 4,5,24
Выигрыш первого игрока
6,7,8 6,7,16
Выигрыш первого игрока

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

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

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

Примечание: знаком :=обозначена операция присваивания.
1) 1 2) 2 3) 3 4) 33

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

N шага Значе-ние т Значе-
¬ние п т =п т>п
0 81 48
1 81 48 81 = 48 — нет (выполняем тело цикла)
2 81 48 81>48 - да
3 33 48
4 33 48 33= 48 — нет (выполняем тело цикла)
5 33 48 33>48-нет
6 33 15
7 33 15 33=15 — нет (выполняем тело цикла) i
8 33 15 33>15 - да
9 18 15 18=15 — нет (выполняем тело цикла)
10 18 15 18>15 - да
11 3 15
12 3 15 3 = 15 — нет (выполняем те¬ло цикла)
13 3 15 3 > 15 - нет
14 3 12
15 3 12 3 = 12 — нет (выполняем те¬ло цикла)
16 3 12 3>12 - нет
17 3 9
18 3 9 3 = 9 — нет (выполняем тело цикла)
19 3 9 3 > 9 - нет
20 3 6
21 3 6 3 = 6 — нет (выполняем тело цикла)
22 3 6 3 > 6 - нет
23 3 3
24 3 3 3 = 3 — да (выход из цикла и завершение алгоритма)

Ответ: 3.

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

Бейсик Паскаль Алгоритмический
а=2468 а:=2468; а:=2468
b= (a MOD 1000)*10 b:=(a mod 1000)ПО; b:=mod(a, 1000)*10
а=а\1000 + 6 а:=а div 1000 + 6; a:=div(a, 1000) +b
'\ и MOD — опера- {div и mod — опера- |div и mod — функ-
ции, вычисляющие ции, вычисляющие ции, вычисляющие
результат деления результат деления результат деления
нацело первого ар- нацело первого ар- нацело первого ар-
гумента на второй и гумента на второй и гумента на второй и
остаток от деления остаток от деления остаток от деления
соответственно соответственно} соответственно
1) a =22, b=20
2) a =4682, b=4680
3) a =8246, b=246
4) a =470, b=468

Решение:
Составим таблицу переменных:
N шага Значение a Значение b
0 2468 не определено
1 2468 468*10=4680
2 2 + 4680=4682 4680
Ответ: 2.

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

Пример:
В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные а, b, с имеют тип «строка», а переменные i,k — тип «целое». Используются следующие функ¬ции:
Длина (а) — возвращает количество символов в строке а. (Тип «целое».)
Извлечь (а, i) — возвращает i-тый (слева) символ в строке а. (Тип «строка».)
Склеить (а, b) — возвращает строку, в которой записаны сна¬чала все символы строки а, а затем все символы строки b. (Тип «строка».)
Значения строк записываются в одинарных кавычках.
(На¬пример, а :='дом'.)

Фрагмент алгоритма:
i := Длина (а)
k:=1
b:= ‘П’
пока i>0
нц
с := Извлечь (a, i)
b := Склеить (b, с)
i:=i - k
кц

Какое значение будет у переменной b после выполнения выше-приведенного фрагмента алгоритма, если значение переменной а было 'РОЗА'?
1) 'ПАЗ' 2) 'ПАЗОР' 3) 'ПОЗА' 4) 'ПРОЗА'

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

Выполняемый оператор Значение а Значение b Значение с Значение i Значение k
‘РОЗА’ не определено не определено не определено не определено
i := Длина (а) ‘РОЗА’ не определено не определено 4 не определено
k:=1 ‘РОЗА’ не определено не определено 4 1
b:=’П’ ‘РОЗА’ ‘П’ не определено 4 1
с := Извлечь (а, i) ‘РОЗА’ ‘П’ ‘А’ 4 1
b := Склеить (b, с) ‘РОЗА’ ‘ПА’ ‘А’ 4 1
i:=i — k ‘РОЗА’ ‘ПА’ ‘А’ 3 1
с := Извлечь (а, i) ‘РОЗА’ ‘ПА’ ‘З’ 3 1
b := Склеить (b, с) ‘РОЗА’ ‘ПАЗ’ ‘З’ 3 1
i:=i - k ‘РОЗА’ ‘ПАЗ’ ‘З’ 2 1
с := Извлечь (а, i) ‘РОЗА’ ‘ПАЗ’ ‘О’ 2 1
b := Склеить (b, с) ‘РОЗА’ ‘ПАЗО’ ‘О’ 2 1
i:= i - k ‘РОЗА’ ‘ПАЗО’ ‘О’ 1 1
с := Извлечь (а, i) ‘РОЗА’ ‘ПАЗО’ ‘Р’ 1 1
b := Склеить (b, с) ‘РОЗА’ ‘ПАЗОР’ ‘Р’ 1 1
i:= i - k ‘РОЗА’ ‘ПАЗОР’ ‘Р’ 0 1
Ответ: 2.

К теме «Алгоритмизация и программирование» относятся также задания на проверку умения написать корот¬кую (10—15 строк) простую программу обработки массива на языке программирования или записать алгоритм на естествен¬ном языке.
Подчеркнем, что в данном задании от ученика не обязательно требуется писать программу на языке программирования. Для получения высшего балла за задание достаточно сформулировать корректный алгоритм на естественном языке.
Для решения этой группы заданий полезно усвоить следующие элементарные алгоритмы:
1) Поиск минимального и максимального элементов в массиве с определением их номеров.
2) Поиск в массиве элемента, удовлетворяющего заданному условию с определением его номера.
3) Подсчет числа элементов массива, удовлетворяющих за данному условию:
4) Вычисление суммы элементов числового массива.
5) Вычисление суммы элементов числового массива, удовлетворяющих заданному условию.
6) Поиск в массиве подпоследовательности убывающих (возрастающих) элементов.
После того как алгоритм начерно написан, рекомендуется его протестировать на небольших (4—5 элементов) массивах исходных данных. Желательно проверить корректность работы алгоритма в следующих ситуациях:
1) элементы массива различны и не упорядочены;
2) элементы массива различны и упорядочены по возрастанию;
3) элементы массива различны и упорядочены по убыванию;
4) элементы массива равны между собой;
5) иные «экстремальные» случаи.

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

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

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

Кроме того, желательно знать следующие свойства конъюнк¬ции, дизъюнкции и импликации:

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

X Y Z F
0 1 0 0
0 1 1 1
1 1 0 0
Какое выражение соответствует F?
1)
2)
3)
4)
Решение
Способ 1
Последовательно подставим первую строку таблицы истин¬ности во все варианты ответов:
l) , а по условию F для этого набора значений равно 0. Первый ответ не подходит.
2) , по условию F = 0. Второй ответ пока под¬ходит.
3) , по условию F =0. Третий ответ пока под¬ходит.
4) , по условию F = 0. Четвертый ответ пока под¬ходит.
Отбросив первый вариант ответа, подставим теперь вторую строку во все оставшиеся:
2) , по условию F = 1. Второй ответ отпадает.
3) , по условию F =1. Третий ответ пока под¬ходит.
4) , по условию F = 1. Четвертый ответ пока под¬ходит.
Подставим теперь третью строку в оставшиеся два варианта ответов:
3) , по условию F = 0. Третий ответ подходит для всех строк.
4) , по условию F = 0. Четвертый ответ не под¬ходит.
Ответ: 3.

Способ 2
Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z:
X Y Z F

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

Рассмотрим приемы решения текстовой логической задачи.
Пример: Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на крас-ном «Рено», Джон сказал, что нарушитель уехал на синей «Тойо¬те», а Сэм показал, что машина была точно не красная и, по всей видимости, это был «Форд». Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля, а в другом ошибся. Какая и ка¬кого цвета была машина у нарушителя?
Ответ запишите в виде двух слов, разделенных пробелом: МАРКА ЦВЕТ. Например: ЖИГУЛИ БЕЛЫЙ.
Решение
Способ 1
Обозначим высказывания:
А = «машина красного цвета»;
В = «машина была «Рено»;
С = «машина синего цвета»;
D = «машина была «Тойота»;
Е = «машина была «Форд».
Согласно условию:
из показаний Боба следует, что А v В истинно;
из показаний Джона следует, что С v D истинно;
из показаний Сэма следует, что — А v E истинно.
Следовательно, истинна и конъюнкция (А vВ) (С v D) ( А v E) = l.
Раскрывая скобки, получаем:
(А v В) (С v D) ( А v E) = (А С v А D v В С v В D) ( A v E) = A C A v A D A v B C A v B D A v A C E v A D E v B C E v B D E =1.
Из полученных восьми слагаемых семь (согласно условию) являются ложными, остается единственное истинное слагаемое (подчеркнуто):
B C A = 1.
Значит, нарушитель скрылся на автомобиле «Рено» синего цвета.
Ответ: «РЕНО СИНИЙ».

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

БЛОК «МОДЕЛИРОВАНИЕ»
По теме «Моделирование» на экзамене в 2006 г. было только одно задание базового уровня с выбором ответа, которое учащие¬ся очень хорошо выполнили: средний процент выполнения выше 80%.
Рассмотрим пример решения типичных заданий по этой теме.
Пример:
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, озна¬чают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: «Мини¬мальная стоимость проезда из А в В не больше 6».
Стоимость проезда по маршруту складывается из стои¬мостей проезда между соответствующими соседними стан¬циями.

1)
А В С D E
A 3 1
B 4 2
C 3 4 2
D 1
E 2 2

2)
А В С D E
A 3 1 1
B 4
C 3 4 2
D 1 4
E 1 2

3)
А В С D E
A 3 1
B 4 1
C 3 4 2
D 1
E 1 2

4)
А В С D E
A 1
B 4 1
C 4 4 2
D 1 4 4
E 1 2

Решение
Построим схемы, соответствующие каждой таблице:

1)

2)

3)

4)

Видно, что минимальная стоимость проезда из А в В дости¬гается на схеме 3 на маршруте АСЕВ, и она равна 6, т.е. условие задания выполнено.
Ответ: 3.

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

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

Программные средства информационных и коммуникационных технологий
Для успешного выполнения заданий надо знать классифика¬цию программного обеспечения, свойства и функциональные воз¬можности основных видов программного обеспечения, структуру файловой системы, включая правила именования каталогов и файлов. Следует понимать разницу между именем файла, путем к нему, полным (абсолютным) и относительным именем.
Разберем типичное задание по этой теме:
Пример:
Перемещаясь из одного каталога в другой, пользователь последовательно посетил каталоги DOC, USER, SCHOOL, A:\, LETTER, INBOX. Каково полное имя каталога, в котором ока¬зался пользователь?
Примечание: при каждом перемещении пользователь либо спускался в каталог на уровень ниже, либо поднимался на уро¬вень выше.
1) INBOX
2) А:\ LETTER\INBOX
3) A:\SCHOOL\USER\DOC
4) LETTER\INBOX
Решение:
А:\ — имя корневого каталога, поэтому, последовательно дви¬гаясь из него, пользователь попал в каталог А:\ LETTER\MNBOX.
Ответ: 2.

Обработка графической информации
Основные проверяемые элементы этой темы — знание прин¬ципов векторной и растровой графики, в том числе способов ком¬пьютерного представления векторных и растровых изображений, умение оперировать с понятиями «глубина цвета», «простран¬ственное и цветовое разрешение изображений и графических устройств», «кодировка цвета», «графический объект», «графи¬ческий примитив», «пиксель».
Пример:
Для хранения растрового изображения размером 128x128 пикселей отвели 4 килобайта памяти. Каково максимально воз¬можное число цветов в палитре изображения?
1) 8 2) 2 3) 16 4) 4
Решение:
Подсчитаем количество пикселей в изображении:
128х128=27х27=214.
Вычислим объем памяти в битах: 4 Кб=4 х 210 байт=22х 210х23 = 215бит.
Таким образом, на один пиксель изображения приходится 215/214 = 2бита.
Как известно, двумя двоичными разрядами можно закодировать четыре разных состояния объекта, в данном случае четыре цвета пикселя.
Ответ: 4.

Еще раз обратить внимание на необходимость использовать свойства степенной функции вместо вычисления «в лоб». Приведем пример решения обратной задачи.
Пример:
Укажите минимальный объем памяти (в килобайтах), доста¬точный для хранения любого растрового изображения размером 32 х 32 пикселя, если известно, что в изображении используется палитра из 256 цветов. Саму палитру хранить не нужно.
1)1 2)2 3)64 4)1024
Решение:
Исходя из количества цветов в палитре определим минимальное количество двоичных разрядов, необходимое для хранения одного пикселя. Для представления 256 различных состояний требуется log2256 = 8 двоичных разрядов, т.е. 1 байт.
Поэтому для представления изображения размером 32x32 пикселя потребуется 32х32 = 25х25 = 210 байт информации, т.е. 1 Кб. Ответ: 1.
Обработка информации в электронных таблицах

Для решения заданий этой темы надо знать правила адресации ячеек в электронной таблице, знать различие между абсолютной и относительной адресацией и уметь использовать его на практике.
В электронных таблицах принято следующее правило: обычные адреса ячеек в формулах являются относительными. Это означает, что при копировании ячейки, содержащей формулу, в ячейку, отстоящую от исходной на некоторое число столбцов и строк, адреса ячеек в формуле изменяются на такое же число столбцов и строк. Пусть, например, ячейка В2 содержит формулу = С2 + 1. При копировании ячейки формула изменится следую¬щим образом:
А В С D
1 =B1 + 1
=D1 + 1
2 =C2 + 1
=E2 + 1
3 =B3 + 1

4 = D4 + 1

Чтобы адрес при копировании не менялся, он должен быть абсолютным. В абсолютном адресе перед обозначениями строки и столбца ставится знак $. Если знак $ стоит только перед именем столбца, то при копировании будет сохраняться имя столбца, если перед номером строки — номер строки.
Пусть ячейка В2 содержит формулу =$С$2+$СЗ+С$4. При копировании ячейки формула изменится следующим образом:
А В С D
1 =$C$2+$C3+B$4
=$C$2+$C2+D$4
2
=$C$2+$C3+C$4
=$C$2+$C3+E$4
3 =$C$2+$C4+B$4

4 = $C$2+$C5+D$4

Пример:
В ячейке А1 электронной таблицы записана формула = $А2+С1. Какой вид приобретет формула после того, как ячей¬ку А1 скопируют в ячейку В1?
1)=$B2+D1 2)=$A2+D1
3)=$A2+D2 4)=$В2 + С1
Решение:
Адрес В1 получен из адреса А1 сдвигом на 1 вправо. Также из-менятся все относительные адреса столбцов в адресах формулы, а именно С1 преобразуется в D1. Адреса строк не изменятся, так как формула копируется в пределах одной строки (первой). Адрес $А2 не изменится, так как здесь адрес столбца абсолютный, и формула приобретет вид =$A2+D1.
Ответ: 2.

Отдельную группу задания по этой теме образуют задачи на представление числовых данных в виде диаграмм. Для решения этих задач нужно уметь строить диаграммы столбчатого и кругового типа, выражающие как абсолютные величины, так и относительные зависимости между исходными данными. Также необходимо уметь анализировать и сопоставлять диаграммы.
Пример:
В цехе трудятся рабочие трех специальностей — токари (Т), слесари (С) и фрезеровщики (Ф). Каждый рабочий имеет разряд не меньший второго и не больший пятого. На диаграм¬ме I отражено распределение рабочих по специальностям, а на диаграмме II количество рабочих с различными разрядами. Каждый рабочий может иметь только одну специальность и один разряд.

1) 2)

Имеются четыре утверждения:
A) Среди слесарей найдется хотя бы один третьего разряда.
Б) Среди токарей найдется хотя бы один второго разряда.
B) Все токари могут иметь четвертый разряд.
Г) Все фрезеровщики могут иметь третий разряд.
Какое из этих утверждений следует из анализа обеих диа¬грамм?
1)А 2) Б 3) В 4) Г

Решение:
По правой диаграмме найдем общее количество рабочих 25+40+20+15 =100 чел.
Из левой диаграммы следует, что токарей половина от общего количества рабочих, т.е. 50 чел., слесарей и фрезеровщиков — по 25 чел.
Проверим утверждение А. Оно не следует из анализа диа¬граммы, так как слесарей меньше, чем суммарное количество работников второго, четвертого и пятого разрядов, следователь¬но, возможна ситуация, когда никто из слесарей не имеет третий разряд.
Проверим утверждение Б. Оно не следует из анализа диаграм¬мы по той же причине, что и А.
Утверждение В тоже ложно, т.к. токарей больше, чем рабочих четвертого разряда.
Утверждение Г — истинно, так как фрезеровщиков насчиты¬вается 25 человек, следовательно, все они могут входить в число 40 рабочих, имеющих трет