ЕГЭ Информатика и ИКТ. Тренировочный КИМ №3. Светлана Александровна Скопинцева

ирования. Доступ в Интернет запрещен.

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

      Баллы, полученные Вами за выполненные задания, суммируются.

      Постарайтесь выполнить как можно больше заданий и набрать наибольшее количество баллов.

      Желаем успеха!

      В заданиях используются следующие соглашения.

      1. Обозначения для логических связок (операций):

      a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

      b) конъюнкция (логическое умножение, логическое И) обозначается /\

      (например, А /\ В) либо & (например, А & В);

      c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/

      (например, А \/ В) либо | (например, А | В);

      d) следование (импликация) обозначается → (например, А → В);

      e) тождество обозначается ≡ (например, A ≡ B); выражение A ≡ B истинно

      тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

      f) символ 1 используется для обозначения истины (истинного высказывания);

      символ 0 – для обозначения лжи (ложного высказывания).

      2. Два логических выражения, содержащие переменные, называются

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

      при любых значениях переменных. Так, выражения А → В и (¬А) \/ В

      равносильны, а А \/ В и А /\ В неравносильны (значения выражений разные,

      например, при А = 1, В = 0).

      3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А /\ В \/ С /\ D означает то же, что

      и ((¬А) /\ В) \/ (С /\ D).

      Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится

      и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.

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

      1

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

      Ответ: ___________________________.

      2

      Логическая функция F задаётся выражением:

      Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.

      Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

      В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

      Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

      В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx

      Ответ: ___________________________.

      3

      Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании имеющихся данных найдите наибольшую разницу между годами рождения двоюродных сестер.

      Двоюродная сестра – дочь брата или сестры матери либо дочь брата или сестры отца

      Ответ: ___________________________.

      4

      По каналу связи передаются сообщения, содержащие только пять букв: Д, О, М, Н, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Д, О, М используются такие кодовые слова: Д – 0, О – 111; М – 1011. Укажите кратчайшее кодовое слово для буквы Н, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.