Подготовка к единому государственному экзамену по информатике

Выберите тему для изучения
Изучение документов
Часть А
Часть В
Часть С
Переменка
Выход

А1 (базовый уровень, время – 1 мин)
Тема: Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы.
Что нужно знать:
все символы кодируются одинаковым числом бит (алфавитный подход)
чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные)
при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 кбайт) – 1024 байта, в мегабайте (1Мбайт) – 1024 кбайта
после знака препинания внутри (не в конце!) текста ставится пробел
чтобы найти информационный объем текста I, нужно умножить количество символов N на число бит на символ K: I = N * K
две строчки текста не могут занимать 100 кбайт в памяти
В самом деле, есть кодировки с переменным количеством бит на символ, например, кодировка UTF-8, но они не изучаются в школе.
Чаще всего килобайт обозначают «Кб», а мегабайт – «Мб», но в демо-тестах ЕГЭ разработчики привели именно такие обозначения.

Пример задания:
Определите информационный объем текста
Бамбарбия! Кергуду!
1) 38 бит 2) 144 бита 3) 152 бита 4) 19 бит
Решение:
в этом тексте 19 символов (обязательно считать пробелы и знаки препинания)
если не дополнительной информации, считаем, что используется 8-битная кодировка (чаще всего явно указано, что кодировка 8- или 16-битная)
поэтому в сообщении 19*8 = 152 бита информации (ответ 3).

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?
1) 30 2) 60 3) 120 4) 480
Решение:
обозначим количество символов через N
при 16-битной кодировке объем сообщения – 16*N бит
когда его перекодировали в 8-битный код, его объем стал равен– 8*N бит
таким образом, сообщение уменьшилось на 16*N – 8*N = 8*N = 480 бит
отсюда находим N = 480/8 = 60 символов (ответ 2).

Возможные ловушки:
указано правильное число, но другие единицы измерения (объем текста 19 байт, а один из неверных ответов – 19 бит)
расчет на то, что «забудут» пробел, в этом случае получается 18*8 = 144 бита (ответ 2, неверный)
в 16-битной кодировке объем текста – 38 байт, а один из неверных ответов – 38 бит.

Задачи для тренировки
Считая, что каждый символ кодируется одним байтом, определите, чему равен информационный объем следующего высказывания Жан-Жака Руссо:
Тысячи путей ведут к заблуждению, к истине – только один.
92 бита 2) 220 бит 3) 456 бит 4) 512 бит
Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 8-битном коде, в 16-битную кодировку Unicode. При этом информационное сообщение увеличилось на 2048 байт. Каков был информационный объем сообщения до перекодировки?
1) 1024 байт 2) 2048 бит 3) 2 кбайта 4) 2 Мбайта

A7 (повышенный уровень, время – 3 мин)
Тема: Основные понятия математической логики.
Про обозначения
К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (∨,∧, ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает ∧ и ∨. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (∨,∧, ¬), что еще раз подчеркивает проблему. Далее во всех решениях приводятся два варианта записи.

Что нужно знать:
условные обозначения логических операций
¬ A, не A (отрицание, инверсия)
A ∧ B, A и B (логическое умножение, конъюнкция)
A ∨ B, A или B (логическое сложение, дизъюнкция)
A → B импликация (следование)
таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)
операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A → B = ¬ A ∨ B или в других обозначениях A → B =
если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
иногда полезны формулы де Моргана:
¬ (A ∧ B) = ¬ A ∨ ¬ B
¬ (A ∨ B) = ¬ A ∧ ¬ B
Огастес (Август) де Морган – шотландский математик и логик.

Пример задания:
Для какого из указанных значений X истинно высказывание
¬((X > 2)→(X > 3))?
1) 1 2) 2 3) 3 4) 4
Решение (вариант 1, прямая подстановка):
определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках
выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:

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

значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):

таким образом, ответ – 3.

Решение (вариант 2, упрощение выражения):
обозначим простые высказывания буквами:
A = X > 2, B = X > 3
тогда можно записать все выражение в виде
¬(A → B) или
выразим импликацию через «ИЛИ» и «НЕ» (см. выше):
¬(A → B)= ¬(¬A ∨ B) или
раскрывая по формуле де Моргана операцию «НЕ» для всего выражения, получаем
¬(¬A ∨ B)= A ∧ ¬B или
таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ≤ 3), то есть для всех X, таких что 2 < X ≤ 3
из приведенных чисел только 3 удовлетворяет этому условию,
таким образом, ответ – 3.

Возможные проблемы:
нужно помнить законы логики (например, формулы де Моргана)
при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот
нужно не забыть, что инверсией (отрицанием) для выражения X > 3 является X ≤ 3, а не X < 3

B2 (базовый уровень, время – 1 мин)
Тема: Блок-схемы алгоритмов. Переменные, присваивание значений. Ветвления. Организация циклов с помощью блока «ветвление».
Что нужно знать:
переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы
оператор присваивания (в Паскале обозначается сочетанием символов «:=») служит для записи нового значения в переменную (для изменения ее значения)
если в переменную записывают новое значение, старое стирается
знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления
запись вида a := a + 2; – это не уравнение, а команда «прочитать текущее значение переменной a, добавить к нему 2 и записать результат обратно в переменную a»;
для наглядной записи небольших алгоритмов используют блок-схемы; они состоят из блоков разного назначения и соединительных линий со стрелками, которые показывают порядок выполнения блоков
в задачах ЕГЭ встречаются два блока: процесс (выполнение некоторых действий) и ветвление (условие, в зависимости от которого выполнение алгоритма продолжается по одной или другой «ветке» )

с помощью ветвления можно организовать цикл (многократное выполнение одинаковых действий), в этом случае в блок-схеме будет соединительная линия, идущая «в обратном направлении» (петля, замкнутый контур)
цикл на рисунке (выделен зеленым фоном) закончится только тогда, когда выполнится условие a = 256

Пример задания:
Запишите значение переменной b после выполнения фрагмента алгоритма:

знак вопроса означает, что после выполнения первого оператора значение b не определено
Решение (вариант 1, ручная прокрутка):
по схеме видим, что алгоритм содержит цикл (есть петля, контур)
ручную прокрутку удобнее всего выполнять в виде таблицы, в первом столбце будем записывать выполняемые команды, во втором и третьем – изменение значений переменных
a и b
после выполнения первого блока получаем

затем выполняется проверка условия; поскольку а не равно 256, ответ на вопрос «a = 256?» будет «нет»:

далее алгоритм уходит на выполнение тела цикла; здесь сначала меняется переменная a, а потом – b, причем нужно помнить, что для вычисления b используется новое значение a, равное 2, поэтому новое значение b равно 1 + 2 = 3:

после этого по стрелке переходим на проверку условия; поскольку a = 2, ответ на вопрос «a = 256?» снова будет «нет», и выполняется очередной шаг цикла:

аналогично можно выполнить вручную все шаги цикла, результаты последнего из них выглядят так:
как только значение a стало равно 256, цикл завершает работу таким образом, верный ответ – 511 .

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

C1 (повышенный уровень, время – 10 мин)
Тема: Исправление ошибок в простой программе с условными операторами.
Что нужно знать:
правила построения программы на Паскале, Бэйсике или Си
правила работы с переменными (объявление, ввод, вывод, оператор присваивания)
ветвление – это выбор одного из двух возможных вариантов действий в зависимости от того, выполняется ли некоторое условие;
на блок-схеме алгоритма ветвление изображается в виде блока-ромба с одним входом и двумя выходами:
Далее при разборе задачи используется язык Паскаль, который наиболее распространен в школах России.

если условие, записанное внутри ромба, истинно (ответ «да» на вопрос «a=b?»), выполняются все команды, входящие в блок-1 (ветка «да»), иначе (если условие ложно) выполняются все команды в блоке-2 (ветка «нет») в неполной форме условного оператора блок-2 пустой (отсутствует); теоретически можно сделать наоборот – так, чтобы блок-1 оказался пустой, но это очень неграмотное решение, поскольку оно осложняет понимание алгоритма, запутывает его одна команда ветвления может находиться внутри другой, например, так:

на этой схеме блок-10 выполняется, когда a=b; блок-11 – когда a=b=c, блок-21 – когда a=b, но a≠c и, наконец, блок-2 – когда a≠b
на этой схеме (Рисунок 3) одна команда ветвления (с условием «a=c») вложена в другую (с условием «a=b»), каждая из них – это ветвление в полной форме; если блок-12 будет пустой (отсутствует), внутреннее ветвление имеет неполную форму; аналогично, если блок-2 пустой, то внешнее ветвление имеет неполную форму
условный оператор if–else служит для организации ветвления в программе на языке Паскаль
условный оператор может иметь полную или неполную форму; вот фрагменты программы, реализующие ветвления, показанные на рисунках 1 и 2:

здесь вместо комментариев в фигурных скобках (они выделены синим цветом) могут стоять любые операторы языка программирования (в том числе операторы присваивания, другие условные операторы, циклы, вызовы процедур и т.п.)
обычно при записи программы операторы, находящиеся внутри обоих блоков, сдвигают вправо на 2-3 символа (запись «лесенкой»), это позволяет сразу видеть начало и конец блока (конечно, если «лесенка» сделана правильно)
после else не надо (нельзя!) ставить какое-то условие, эта часть выполняется тогда, когда условие после if неверно
в Паскале перед else не ставится точка с запятой, поскольку это ключевое слово обозначает не начало нового оператора, а вторую часть условного оператора if else слова begin и end (их называют также «операторные скобки») ограничивают блок-1 и блок-2; если внутри блока всего один оператор, эти «скобки» можно не писать, например, допустимы такие операторы

в условных операторах можно использовать сложные условия, которые строятся из простых отношений (<, <=, >, >=, =, <>) с помощью логических операций not («НЕ», отрицание), and («И», одновременное выполнение двух условий) и or («ИЛИ», выполнение хотя бы одного из двух условий)
в сложном условии сначала выполняются действия в скобках, потом – not, затем – and, затем – or и, наконец, отношения;
операции равного уровня (приоритета) выполняются последовательно слева направо
поскольку отношения в Паскале имеют низший приоритет, в сложном условии их приходится брать в скобки:
if (a = b) or (b < c) and (c <> d) then begin
...
end;
в приведенном выше примере сначала определяются результаты сравнения (выражения в скобках), затем выполняется операция and («И»), а затем – or («ИЛИ»)

Пример задания:
Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x, y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы. Программист торопился и написал программу неправильно. Вот она:
var x,y: real;
begin
readln(x,y);
if y <= 1 then
if x >= 0 then
if y >= sin(x) then
write('принадлежит')
else write('не принадлежит')
end.
Последовательно выполните следующее: 1) Приведите пример таких чисел x, y, при которых программа неверно решает поставленную задачу. 2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы) .