Пример. Исходные трехзначные числа: 835, 196

Исходные трехзначные числа: 835, 196. Поразрядные суммы: 9, 12, 11. Результат: 12119

Определите, какое из следующих чисел может быть результатом работы автомата.

1) 151303 2) 161410 3) 191615 4) 121613

Решение:

1) итак, число строится из трех чисел, каждое из которых может быть однозначным (от 0 до 9) или двузначным (от 10 до 9 + 9 = 18)

2) если в числе 6 цифр, значит соединены три двузначных числа; в первом числе одно из них записывается как «03», что недопустимо (в этом случае правильное число было бы записано как 15133)

3) в третьем числе тоже 6 цифр: три двузначных числа, первое из которых равно 19, чего не может быть (никакие два однозначных числа не могут дать такую сумму)

4) в четвертом числе тоже 6 цифр: три числа 12, 16 и 13 расположены НЕ в порядке убывания, поэтому этот вариант неверен

5) во втором варианте никаких противоречий с условием нет

6) таким образом, ответ: 2.

Еще пример задания:

Предлагается некоторая операция над двумя произвольными трехзначными десятичными числами:

1) Записывается результат сложения старших разрядов этих чисел.

2) К нему дописывается результат сложения средних разрядов по такому правилу: если он меньше первой суммы, то полученное число приписывается к первому слева, иначе – справа.

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

Какое из перечисленных чисел могло быть построено по этому правилу?

1) 141819 2) 171418 3) 141802 4) 171814

Решение:

1) заметим, что сумма двух однозначных чисел – это число от 0 до 18 включительно

2) все предложенные числа шестизначные, поэтому все суммы, из которых составлены числа, должны быть двузначными

1) 141819 2) 171418 3) 141802 4) 171814

3) поскольку числа 19 быть не может (его не получить суммой двух однозначных чисел), этот вариант не подходит

4) из условия (2) следует, что первые два двузначных числа должны быть расположены по возрастанию (неубыванию), поэтому вариант 2 не подходит

5) при записи числа 2 ноль впереди не добавляется (в условии про это ничего не сказано), поэтому третий вариант тоже не подходит

6) вариант 4 удовлетворяет всем условиям.

7) таким образом, ответ: 4.

A6 (базовый уровень, время – 3 мин)

Тема: Поиск и сортировка информации в базах данных.

Что нужно знать:

· при составлении условия отбора можно использовать знаки отношений <, <= (меньше или равно), >, >= (больше или равно), = (равно), <> (не равно)

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

· для изменения порядка выполнения операции используют скобки

Пример задания:

Таблица 1 ID Фамилия_И.О. Пол   Иванов Т.М. М   Петренко И.Т. М   Черных И.А. Ж   Петренко А.И. Ж   Иванова А.И. Ж   Петренко Н.Н. Ж   Черных А.Н. M   Цейс Т.Н. Ж   Цейс Н.А. М   ...

Таблица 2 ID_Родителя ID_Ребенка                                 ... ...

В фрагменте базы данных представлены сведения о родственных отношениях. Опреде-лите на основании приведенных данных фамилию и инициалы бабушки Ивановой А.И.

1) Иванов Т.М. 2) Черных И.А. 3) Цейс Т.Н. 4) Петренко Н.Н.

Ещё пример задания:

Результаты тестирования представлены в таблице:

Фамилия	Пол	Математика	Русский язык	Химия	Информатика	Биология
Аганян	ж
Воронин	м
Григорчук	м
Роднина	ж
Сергеенко	ж
Черепанова	ж

Сколько записей в ней удовлетворяют условию « Пол =’ж’ ИЛИ Химия > Биология »?

1) 5 2) 2 3) 3 4) 4

Решение:

1) заданное сложное условие отбора состоит из двух простых

У1: Пол =’ж’

У2: Химия > Биология

которые связаны с помощью логической операции «ИЛИ»

2) заметим, что столбцы «Фамилия», «Математика», «Русский язык» и «Информатика» никак не влияют на результат; уберем их из таблицы и добавим два новых столбца, в которых будем отмечать, выполняются ли условия У1 и У2 для каждой строчки

Пол	Химия	Биология	Пол =’ж’	Химия > Биология
ж			+
м				+
м
ж			+
ж			+	+
ж			+	+

3) логическая операция «ИЛИ» означает выполнение хотя бы одного из двух условия (или обоих одновременно), поэтому заданному сложному условию удовлетворяют все строки, где есть хотя бы один плюс; таких строк пять, они выделены зеленым фоном:

Пол	Химия	Биология	Пол =’ж’	Химия > Биология
ж			+
м				+
м
ж			+
ж			+	+
ж			+	+

4) таким образом, правильный ответ – 1.

Еще пример задания:

База данных о торговых операциях дистрибутора состоит из трех связанных таблиц. Ниже даны фрагменты этих таблиц.

Таблица зарегистрированных дилеров

Наименование организации	ID дилера	Регион	Адрес
ООО «Вектор»	D01	Башкортостан	г. Уфа, ул. Школьная, 15
АО «Луч»	D02	Татарстан	г. Казань, ул. Прямая, 17
АОЗТ «Прямая»	D03	Адыгея	г. Майкоп, просп. Мира, 8
ООО «Окружность»	D04	Дагестан	г. Дербент, ул. Замковая, 6
ИЧП Скаляр	D05	Дагестан	г. Махачкала, ул. Широкая, 28
АО «Ромб»	D06	Татарстан	г. Набережные Челны, ул. Заводская, 4

Таблица отгрузки товара

Номер накладной	Отгружено дилеру	Артикул товара	Отгружено упаковок	Дата отгрузки
001	D01	01002	300	5/01/2009 г.
002	D02	01002	100	5/01/2009 г.
003	D06	01002	200	5/01/2009 г.
004	D01	02002	20	5/01/2009 г.
005	D02	02002	30	5/01/2009 г.
006	D02	01003	20	6/01/2009 г.

Таблица товаров

Наименование товара	Артикул	Отдел	Количество единиц в упаковке	Брутто вес упаковки
Фломастеры, пачка 24 шт.		Канцтовары
Бумага А4, пачка 500 лист.		Канцтовары
Скрепки металлические, 1000 шт.		Канцтовары
Розетки трехфазные		Электротовары
Лампа накаливания, 60 Вт		Электротовары
Выключатель 2-клавишн.		Электротовары

Сколько пачек бумаги было отгружено в Татарстан 5 января 2009 года?

1) 100 2) 200 3) 300 4) 1500

Решение:

1) уберем из таблиц всю лишнюю информацию; во-первых, нас интересует только бумага и только количество пачек, поэтому таблица товаров сводится к одной строчке

Наименование товара	Артикул	Количество единиц в упаковке
Бумага А4,пачка 500 листов

2) во-вторых, нас интересуют только дилеры из Татарстана, причем их названия и адреса не дают полезной информации, нужен только код; вот что остается от таблицы дилеров:

ID дилера	Регион
D02	Татарстан
D06	Татарстан

3) из таблицы отгрузки товара выбираем только информацию о поставках этим дилерам:

Отгружено дилеру	Артикул товара	Отгружено упаковок	Дата отгрузки
D02	01002	100	5/01/2009 г.
D06	01002	200	5/01/2009 г.
D02	02002	30	5/01/2009 г.
D02	01003	20	6/01/2009 г.

4) в последней таблице отмечаем строчки, которые относятся к бумаге (артикул 01002) и дате 5/01/2009:

Отгружено дилеру	Артикул товара	Отгружено упаковок	Дата отгрузки
D02	01002	100	5/01/2009 г.
D06	01002	200	5/01/2009 г.

5) таким образом, в 5/01/2009 в Татарстан было отгружено 300 упаковок бумаги

6) теперь вспоминаем, что в таблице товаров сказано, что в каждой упаковке 5 пачек, поэтому всего отгружено 1500 пачек

7) таким образом, правильный ответ – 4.

Возможные ловушки и проблемы: · обратите внимание, что спрашивается количество пачек, а не количество упаковок; среди ответов есть «отвлекающий» вариант 300 – после выполнения шага 5 появляется соблазн выбрать именно его

A7 (базовый уровень, время – 3 мин)

Тема: Электронные таблицы.

Что нужно знать:

· адрес ячейки в электронных таблицах состоит из имени столбца и следующего за ним номера строки, например, C15

· формулы в электронных таблицах начинаются знаком = («равно»)

· знаки +, –, *, / и ^ в формулах означают соответственно сложение, вычитание, умножение, деление и возведение в степень

· запись B2:C4 означает диапазон, то есть, все ячейки внутри прямоугольника, ограниченного ячейками B2 и C4

· например, по формуле =СУММ(B2:C4) вычисляется сумма значений ячеек B2, B3, B4, C2, C3 и C4

· в заданиях ЕГЭ могут использоваться стандартные функции СЧЕТ (количество непустых ячеек), СУММ (сумма), СРЗНАЧ (среднее значение), МИН (минимальное значение), МАКС (максимальное значение)

· функция СРЗНАЧ при вычислении среднего арифметического не учитывает пустые ячейки и ячейки, заполненные текстом; например, после ввода формулы в C2 появится значение 2 (ячейка А2 – пустая) функция СЧЕТ(A1:B2) в этом случае выдаст значение 3 (а не 4).

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

Пример задания:

Дан фрагмент электронной таблицы:

	А	В	С
			= A1+B$1

Чему станет равным значение ячейки С2, если в нее скопировать формулу из ячейки С1? Знак $ обозначает абсолютную адресацию.

1) 40 2) 50 3)60 4) 70

Решение:

1) при копировании из C1 в C2 столбец не изменяется, а номер строки увеличивается на 1, поэтому в C2 получим формулу =A2+B$1

2) сумма ячеек A2 и B1 равна 30 + 20 = 50

Возможные ловушки и проблемы: · расчет на то, что ученик забудет, что абсолютная ссылка не меняется (тогда получится формула =A2+B$2, на этот случай дан неверный ответ 70)

 

Еще пример задания:

Дан фрагмент электронной таблицы:

	А	В	С
			=СЧЁТ(A1:B2)
			=СРЗНАЧ(A1:C2)

Как изменится значение ячейки С3, если после ввода формул переместить содержимое ячейки В2 в В3?(«+1» означает увеличение на 1, а «–1» – уменьшение на 1)

1) –2 2) –1 3) 0 4) +1

Решение:

1) это задача на знание особенностей функций СЧЕТ и СРЗНАЧ, которые не учитывают пустые ячейки

2) после ввода формул в С2 окажется количество непустых ячеек диапазона А1:В2, равное 4

3) в С3 будет выведено среднее значение диапазона А1:С2 равное

(1+2+2+6+4)/5 = 3

4) после перемещения (не копирования!) содержимого ячейки В2 в В3 ячейка В2 окажется пустой, поэтому в С2 выводится число 3 – количество непустых ячеек диапазона А1:В2

5) в С3 будет выведено среднее значение диапазона А1:С2 равное

(1+2+2+3)/4 = 2, то есть значение С3 уменьшится на 1

6) таким образом, правильный ответ – 2.

Возможные ловушки и проблемы: · нужно помнить, что при перемещении содержимого ячейки в другое место она становится пустой · нужно помнить, что функции СЧЕТ и СРЗНАЧ не учитывают пустые ячейки

A8 (базовый уровень, время – 3 мин)

Тема: Кодирование звука.

Что нужно знать:

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

· частота дискретизации определяет количество отсчетов, запоминаемых за 1 секунду; 1 Гц (один герц) – это один отсчет в секунду, а 8 кГц – это 8000 отсчетов в секунду

· глубина кодирования – это количество бит, которые выделяются на один отсчет

· для хранения информации о звуке длительностью секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется бит памяти; например, при кГц, глубине кодирования 16 бит на отсчёт и длительности звука 128 секунд требуется

бит

байт

Кбайт

Мбайт

· при двухканальной записи (стерео) объем памяти, необходимый для хранения данных одного канала, умножается на 2

Пример задания:

Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и глубиной кодирования 24 бита. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

1) 0,2 2) 2 3) 3 4) 4

Решение:

3) так как частота дискретизации 16 кГц, за одну секунду запоминается 16000 значений сигнала

4) так как глубина кодирования – 24 бита = 3 байта, для хранения 1 секунды записи требуется

16000 ´ 3 байта = 48 000 байт

(для стерео записи – в 2 раза больше)

5) на 1 минуту = 60 секунд записи потребуется

60 ´ 48000 байта = 2 880 000 байт,

то есть около 3 Мбайт

6) таким образом, правильный ответ – 3.

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

Еще пример задания:

Производится одноканальная (моно) звукозапись с частотой дискретизации 64Гц. При записи использовались 32 уровня дискретизации. Запись длится 4 минуты 16 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?

1) 10 2) 64 3) 80 4) 512

Решение:

1) так как частота дискретизации 64 Гц, за одну секунду запоминается 64 значения сигнала

2) глубина кодирования не задана!

3) используется 32 = 2⁵ уровня дискретизации значения сигнала, поэтому на один отсчет приходится 5 бит

4) время записи 4 мин 16 с = 4 ´ 60 + 16 = 256 с

5) за это время нужно сохранить

256 ´ 5 ´ 64 бит = 256 ´ 5 ´ 8 байт = 5 ´ 2 Кбайт = 10 Кбайт

6) таким образом, правильный ответ – 1.

Возможные ловушки и проблемы: · если указано, что выполняется двухканальная (стерео) запись, нужно не забыть в конце умножить результат на 2 · если «по инерции» считать, что 32 – это глубина кодирования звука в битах, то получим неверный ответ 64 Кбайта

А9 (базовый уровень, время – 2 мин)

Тема: Кодирование и декодирование информации.

Что нужно знать:

· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;

· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Пример задания:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 01 2) это невозможно

3) для буквы В – 01 4) для буквы Г – 01

 

Решение (1 способ, проверка условий Фано):

4) для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;

5) проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);

6) проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111.

«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);

«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;

7) проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111.

«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);

«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;

8) проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111.

«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;

9) правильный ответ – 4.

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

1)

А

Б

В

Г

Д

корень

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

 

2) здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);

3) теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом

4) видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано

5)

А

Б

В

Г

Д

корень

хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):

видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв

6) в заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится

7) правильный ответ – 4.

Ещё пример задания:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3)11 4) 010

Решение:

8) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова

9) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит

10) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит

11) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит

12) для четвертого варианта, Д = 010, условие Фано не нарушено;

13) правильный ответ – 4.

 

Возможные ловушки: · условие Фано – это достаточное, но не необходимое условие однозначного декодирования, поэтому для уверенности полезно найти для всех «неправильных» вариантов контрпримеры: цепочки, для которых однозначное декодирование невозможно

Еще пример задания:

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится

1) 4B₁₆ 2) 411₁₆ 3)BACD₁₆ 4) 1023₁₆

Решение:

14) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный

15) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011

16) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

1001011 = 0100 1011₂ = 4B₁₆

17) правильный ответ – 1.

 

Возможные ловушки: · расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116) · может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B416 · в ответах дана последовательность, напоминающая исходную (неверный ответ BACD16), чтобы сбить случайное угадывание

A10 (повышенный уровень, время – 2 мин)

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

Что нужно знать:

· условные обозначения логических операций

· таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация»

· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = A Ú B или в других обозначениях A → B =

· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

· иногда полезны формулы де Моргана[*]:

(A Ù B) = A Ú B

(A Ú B) = A Ù B

· основные сведения о логических операциях:

Логическая операция / соответствие в русском языке	Обозна-чение	Диаграмма Эйлера-Венна
инверсия (отрицание, логическое "НЕ")
конъюнкция (логическое "И")	∧, &
дизъюнкция (логическое "ИЛИ")	∨, |

 

Логическая операция / соответствие в русском языке	Обозна-чение	Диаграмма Эйлера-Венна	Таблица ист-ти
импликация (следование) «Житейский» смысл имплика­ции. Для более лёгкого понимания смысла прямой импликации и за­поминания ее таблицы истинности может пригодиться житейская модель: А — начальник. Он может приказать «работай» (1) или ска­зать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация — не что иное, как послушание подчиненного начальнику. По таблице истинности легко проверить, что послушания нет только тогда, когда начальник приказывает работать, а подчи­ненный бездельничает.	→		A	B	A→B
эквивалентность (тождество)	↔, ≡		A	B	A↔B

 

· порядок выполнения логических операций:

1. B

2. (B)∧C

3. A∨ ((B)∧C)

4. (A∨((B)∧C))→D

5. ((A∨((B)∧C))→D)↔E

Пример задания:

Какое из приведённых имен удовлетворяет логическому условию:
(первая буква согласная → вторая буква согласная) /\ (предпоследняя буква гласная → последняя буква гласная)?

1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

Решение:

7) два условия связаны с помощью операции /\ («И»), поэтому должны выполняться одновременно

8) импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна

9) первое условие «первая буква согласная → вторая буква согласная» ложно тогда, когда первая буква согласная, а вторая – гласная, то есть для ответов 2 и 4

10) второе условие «предпоследняя буква гласная → последняя буква гласная» ложно тогда, когда предпоследняя буква гласная, а последняя – согласная, то есть, для ответа 3

11) таким образом, для варианта 1 (КРИСТИНА) оба промежуточных условия и исходное условие в целом истинны

12) ответ: 1.

Ещё пример задания:

Для какого из указанных значений X истинно высказывание ((X > 2)→(X > 3))?

1) 1 2) 2 3) 3 4) 4

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

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

14) выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:

X	X > 2	X > 3	(X > 2)→(X > 3)	((X > 2)→(X > 3))

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

X	X > 2	X > 3	(X > 2)→(X > 3)	((X > 2)→(X > 3))

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

X	X > 2	X > 3	(X > 2)→(X > 3)	((X > 2)→(X > 3))

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

Возможные ловушки и проблемы: · можно «забыть» отрицание (помните, что правильный ответ – всего один!) · можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация») · нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов[†]

А11 (повышенный уровень, время – 3 мин)

Тема: Вычисление информационного объема сообщения.

Что нужно знать:

· с помощью K бит можно закодировать различных вариантов (чисел)

· таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

K, бит
Q, вариантов

· при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта[‡]

· чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K:

· две строчки текста не могут занимать 100 Кбайт в памяти

· мощность алфавита M – это количество символов в этом алфавите

· если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно ; для двоичного кодирования (мощность алфавита M – 2 символа) получаем известную формулу:

Пример задания:

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!).

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

Определите объём памяти, который занимает хранение 60 паролей.

1) 540 байт 2) 600 байт 3) 660 байт 4) 720 байт

Решение:

10) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа

11) для кодирования 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 2⁵ = 32 варианта)

12) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит

13) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт

14) тогда 60 паролей занимают 9 × 60 = 540 байт

15) ответ: 1.

Возможные ловушки: · часто забывают, что пароль должен занимать ЦЕЛОЕ число байт

Ещё пример задания:

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

1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт

Решение:

16) велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов

17) по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно зак