На уроке рассмотрено решение 23 задания ЕГЭ по информатике: дается подробное объяснение и разбор задания 2017 года

23-е задание — «Преобразование логических выражений» — характеризуется, как задание высокого уровня сложности, время выполнения – примерно 10 минут, максимальный балл — 1

Элементы алгебры логики: преобразования логических выражений

Для выполнения 23 задания ЕГЭ необходимо повторить следующие темы и понятия:

• Рассмотрите тему .
• Рассмотрите тему .

Разные типы заданий 23 и их решение от простого к сложному:

1. Одно уравнение с непересекающимися операндами внешней операции и одним вариантом решения:

2. Одно уравнение с непересекающимися операндами внешней операции и несколькими вариантами решения

3. Одно уравнение с пересекающимися операндами внешней операции

Рассмотрим каждый случай отдельно и учтем его результаты для второго уравнения системы:

Поскольку для двух уравнений решения в трех случаях не могут «работать» одновременно, то результат — это сложение трех решений:

4. Несколько уравнений: метод отображения решений уравнения

Метод отображения можно использовать:

5. Несколько уравнений: использование битовых масок

Побитовая маска (битовая маска) - метод, который можно использовать:

Решение 23 заданий ЕГЭ по информатике

Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x6 , y1 , y2 , … y6

(¬(x1 ∨ y1)) ≡ (x2 ∨ y2)
(¬(x2 ∨ y2)) ≡ (x3 ∨ y3)
…
(¬(x5 ∨ y5)) ≡ (x6 ∨ y6)

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 7.

¬a ≡ b ¬b ≡ c ¬c ≡ d ¬d ≡ e ¬e ≡ f a ≠ b b ≠ c c ≠ d d ≠ e e ≠ f

Вспомним, как выглядит таблица истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

Рассмотрим, в каких случаях выражения будут возвращать ложь. Каждое из пяти выражений будет ложно, когда: либо оба операнда истинны, либо оба операнда ложны (операция равносильность = истине: при 00 или 11).

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

цеп.1 цеп.2 a 0 1 b 1 0 c 0 1 d 1 0 e 0 1 f 1 0

Теперь вспомним о заменах: каждая из переменных от a до f представляет собой скобку, внутри которой две переменные, связанные дизъюнкцией . Дизъюнкция двух переменных истинна в трех случаях (01, 10, 11), а ложна — в одном (00). Т.е., к примеру:

x1 ∨ y1 = 1 тогда, когда: либо 0 ∨ 1 , либо 1 ∨ 0 , либо 1 ∨ 1 x1 ∨ y1 = 0 тогда и только тогда, когда 0 ∨ 0

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

для первой цепочки: 3 3 * 1 3 = 27 наборов значений ,

и для второй: 3 3 * 1 3 = 27 наборов значений

Итого наборов:

27 * 2 = 54

Результат: 54

Подробное объяснение данного задания смотрите на видео:

23_2: Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x9 , y1 , y2 , … y9 , которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∧ y1)) ≡ (x2 ∧ y2)
(¬(x2 ∧ y2)) ≡ (x3 ∧ y3)
…
(¬(x8 ∧ y8)) ≡ (x9 ∧ y9)

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 9.

✍ Решение (использование метода побитовая маска):

• Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:

¬a ≡ b ¬b ≡ c ¬c ≡ d ¬d ≡ e ¬e ≡ f ¬f ≡ g ¬g ≡ h ¬h ≡ i

Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:

a ≠ b b ≠ c c ≠ d d ≠ e e ≠ f f ≠ g g ≠ h h ≠ i

Вспомним таблицу истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

Теперь рассмотрим, в каких случаях полученные условия будут возвращать ложь. Каждое из условий будет ложно, если либо оба операнда истинны, либо оба операнда ложны: например a ≠ b = 0 , если: a=0 и b=0 или a=1 и b=1

Это означает, что для одного условия не может быть такого случая, что a=0 и b=0 или a=1 и b=1 .

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

цеп.1 цеп.2 цеп. цеп. a 0 1 0 1 b 1 0 0 1 не может быть! c 0 1 ... ... d 1 0 e 0 1 f 1 0 g 0 1 h 1 0 i 0 1

a до i истинна в одном случае, а ложна — в трех . Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1 , либо 1 ∧ 0 , либо 0 ∧ 0 x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

0 в цепочке приходится три 1 - один . Т.о. получаем:

для первой цепочки: 3 5 * 1 4 = 243 набора значений ,

и для второй: 3 4 * 1 5 = 81 набор значений

Итого наборов:

243 + 81 = 324

Результат: 324

Предлагаем посмотреть видео с решением данного 23 задания:

23_3: Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x8 , y1 , y2 , … y8 , которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧ y1) ≡ (x3 ∧ y3)) → (x2 ∧ y2))
¬(((x2 ∧ y2) ≡ (x4 ∧ y4)) → ¬(x3 ∧ y3))
¬(((x3 ∧ y3) ≡ (x5 ∧ y5)) → (x4 ∧ y4))
¬(((x4 ∧ y4) ≡ (x6 ∧ y6)) → ¬(x5 ∧ y5))
¬(((x5 ∧ y5) ≡ (x7 ∧ y7)) → (x6 ∧ y6))
¬(((x6 ∧ y6) ≡ (x8 ∧ y8)) → ¬(x7 ∧ y7))

В качестве ответа Вам нужно указать количество таких наборов.

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019 года, вариант 11.

✍ Решение с использованием метода побитовая маска:

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

1-a 2-b 3-c 4-d 5-e 6-f 7-g 8-h

После замены получим следующие выражения:

¬((a ≡ c) → b) ¬((b ≡ d) → ¬c) ¬((c ≡ e) → d) ¬((d ≡ f) → ¬e) ¬((e ≡ g) → f) ¬((f ≡ h) → ¬g)

Используя законы алгебры логики, преобразуем одно из условий (первое). Потом по аналогии выполним преобразования для остальных условий:

1. Избавимся от импликации:
было: ¬((a ≡ c) → b) стало: ¬(¬(a ≡ c) ∨ b)
2. По закону Де Моргана избавимся от отрицания над общей внешней скобкой:
было: ¬(¬(a ≡ c) ∨ b) стало: (a ≡ c) ∧ ¬b

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

(a ≡ c) ∧ ¬b (b ≡ d) ∧ c (c ≡ e) ∧ ¬d (d ≡ f) ∧ e (e ≡ g) ∧ ¬f (f ≡ h) ∧ g

Рассмотрим, в каких случаях условия будут возвращать истину. Внешняя операция конъюнкция: каждое из условий будет истинно только в том случае, если оба операнда истинны : например: (a ≡ c) ∧ ¬b возвратит истину , если: (a ≡ c) = 1 и ¬b = 1

Это означает, что все операнды, стоящие после знака конъюнкции, должны быть истинны.

Составим битовую маску для наших уравнений с учетом указанного требования:

цеп.1 a ? b 0 c 1 d 0 e 1 f 0 g 1 h ?

Значение для переменной a найдем из условия (a ≡ c) ∧ b . В битовой маске с=1 , значит, чтобы условие a ≡ c было истинным, а должно тоже равняться 1

Значение для переменной h найдем из условия (f ≡ h) ∧ ¬g . В битовой маске f=0 , значит, чтобы условие f ≡ h было истинным, h должно тоже равняться 0 (таблица истинности эквивалентности).

Получим итоговую битовую маску:

цеп.1 a 1 b 0 c 1 d 0 e 1 f 0 g 1 h 0

Теперь вспомним, что каждая из переменных от a до h представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех . Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1 , либо 1 ∧ 0 , либо 0 ∧ 0 x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1 - один . Т.о., получаем:

3 4 * 1 4 = 81 набор значений

Результат: 81

23_4: Разбор 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

Сколько существует различных наборов значений логических переменных x1 , x2 , … x7 , y1 , y2 , … y7 , которые удовлетворяют всем перечисленным ниже условиям?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

✍ Решение, используется метод отображения:

• Внешняя операция в отдельно взятом уравнении — это импликация, результат которой должна быть истина. Импликация истинна если:

0 -> 0 0 -> 1 1 -> 1

т.е. ложна только, когда 1 -> 0

Если скобка (¬x1 ∨ y1) = 0 , то для скобки (¬x2 ∧ y2) возможны варианты 0 или 1 .

Если скобка (¬x1 ∨ y1) = 1 , то для скобки (¬x2 ∧ y2) возможен один вариант — 1 .

В скобках дизъюнкция (∨) истинна, когда: 0 ∨ 1, 1 ∨ 0, 1 ∨ 1; ложна, когда: 0 ∨ 0.

В скобках конъюнкция истинна, когда 1 ∧ 1 и ложна во всех остальных случаях.

Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Выделим в ней те строки, которые возвращают ложь: т.е. где первая скобка (¬x1 ∨ y1) возвратит 1 , а вторая (¬x2 ∧ y2) — 0 :

Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения. Для первого уравнения x1 и y1 будут обозначаться x i и y i , а x2 и y2 будут обозначаться x i+1 и y i+1 .

Теперь найдем общее количество решений, подставляя в отображении соответствующие x и y

В итоге получаем:

1 + 19 + 1 + 1 = 22

Результат: 22

Видеоразбор демоверсии 2018 23 задания смотрите здесь:

23_5: Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):

Сколько различных решений имеет уравнение:

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1

где a, b, c, d, e — логические переменные?

В качестве ответа указать количество таких наборов.

✍ Решение:

• Внешняя логическая операция — ∨ — дизъюнкция. Таблица истинности:

0 ∨ 0 = 0 0 ∨ 1 = 1 1 ∨ 0 = 1 1 ∨ 1 = 1

Поскольку дизъюнкция равна единице аж в трех случаях, то искать количество вариантов будет достаточно сложно. Значительно проще найти варианты, когда ∨ = 0 и вычесть их из общего количества вариантов .

Найдем общее количество строк в таблице истинности. Всего 5 переменных, поэтому:

количество строк в ТаблИстин = 2 5 = 32

Посчитаем, сколько вариантов имеют решение при значении уравнения = 0. Чтобы потом вычесть это значение из общего количества. Для операции дизъюнкция (∨) каждая скобка должна быть равна нулю:

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 0 0 0 0

Теперь рассмотрим каждую скобку отдельно:

1. (a → b) = 0, импликация ложна в одном случае (1 → 0) = 0 т.е. имеем a = 1 , b = 0 2. (c → ¬d) = 0, импликация ложна в одном случае (1 → 0) = 0 т.е. имеем c = 1 , d = 1 3. ¬(e ∨ a ∨ c) = 0

т.к. перед скобкой стоит отрицание, то для большей понятности раскроем скобки по закону Де Моргана:

¬e ∧ ¬a ∧ ¬c = 0 Конъюнкция равна 0, когда хоть один операнд = 0.

из п.1 и п.2 имеем a = 1 и c = 1 . Тогда для e имеем два варианта: e = 0 , e = 1 , т.е.:

¬0 ∧ ¬1 ∧ ¬1 = 0 ¬1 ∧ ¬1 ∧ ¬1 = 0

То есть всего имеем 2 цепочки «исключаемых» решений:

1. a = 1, b = 0, c = 1, d = 1, e = 0 2. a = 1, b = 0, c = 1, d = 1, e = 1

Эти два варианта исключаем (вычитаем) из общего количества:

32 - 2 = 30

Результат: 30

23_6: Разбор 23 задания демоверсии егэ по информатике 2019:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7 , которые удовлетворяют всем перечисленным ниже условиям?

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 (y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1 … (y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1 y7 → x7 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x7, y1, y2, … y7, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.

✍ Решение:

• Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
• Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:

1 -> 1 т.е.: (y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 1 1

Найдем случаи, когда равенство будет ложным (чтобы в дальнейшем исключить эти случаи):

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 0

Внутри первой «большой» скобки находится операция импликации. Которая ложна:

1 -> 0 = 0 т.е. случаи: y1=1 → (y2=0 ∧ x1=1) y1=1 → (y2=1 ∧ x1=0) y1=1 → (y2=0 ∧ x1=0)

Таким же образом проанализируем вторую скобку. В ней импликация вернет ложь:

(x1=1 → x2=0)

Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Поскольку переменных 4, то строк будет 2 4 = 16 . Выделим те строки, которые возвращают ложь:

Теперь переходим к методу отображения. Для первого уравнения x1 и y1 обозначим x i и y i , а x2 и y2 обозначим x i+1 и y i+1 . Стрелками обозначим значения только тех строк таблицы истинности, которые возвращают 1 .

Найдем общее количество решений, подставляя в таблицу из отображения соответствующие значения x и y , и, учитывая предыдущие значения:

Теперь вернемся к последнему равенству. По условию оно должно быть истинным. Равенство вернет ложь только в одном случае:

y7=1 → x7=0 = 0

Найдем соответствующие переменные в нашей таблице:

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

1 + 7 + 28 = 36

Результат: 36

Видео решения 23 задания демоверсии егэ 2019:

23_7: Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 16 (ФИПИ):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x6 , y1 , y2 , … y6 , которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧ y1)) ≡ (x2 ∧ y2)) → (x3 ∧ y3))
¬(((x2 ∧ y2)) ∨ ¬(x3 ∧ y3)) → (x4 ∧ y4))
¬(((x3 ∧ y3)) ≡ (x4 ∧ y4)) → (x5 ∧ y5))
¬(((x4 ∧ y4)) ∨ ¬(x5 ∧ y5)) → (x6 ∧ y6))

В качестве ответа Вам нужно указать количество таких наборов.

✍ Решение:

• Поскольку в малых скобках везде одна и та же операция (∧ ), и переменные в скобках не пересекаются, то можно выполнить замену:

¬((a ≡ b) → c) = 1 ¬((b ∨ ¬c) → d) = 1 ...

Избавимся от отрицания, указав, что каждое выражение при этом становится ложным:

(a ≡ b) → c = 0 (b ∨ ¬c) → d = 0 (c ≡ d) → e = 0 (d ∨ ¬e) → f = 0

Внешняя операция во всех выражениях — импликация (→ ). Вспомним таблицу истинности для операции импликация:

0 → 0 = 1 0 → 1 = 1 1 → 0 = 0 1 → 1 = 1

Импликация ложна только в одном случае: 1 → 0 = 0 . Все выражения в задании ложны. Учтем это.

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

цеп1 цеп2 a 0 1 b 0 1 c 0 0 d 0 0 e 0 0 f 0 0

Так как каждая переменная изначально заменяет скобку, в которой находится операция конъюнкция (∧), то, вспомнив таблицу истинности для этой операции, сопоставим для каждого нуля 3 решения (конъюнкция ложна в трех случаях), а для каждой единицы — 1 решение (конъюнкция истинна в одном случае).

Посчитаем значение для каждой побитовой цепочки:

цеп1 = 3*3*3*3*3*3 = 729 решений цеп2 = 1*1*3*3*3*3 = 81 решение

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

729 + 81 = 810 решений

Ответ: 810

Доступен видеоразбор задания 23:

23_8: Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 2 (ФИПИ):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x12 , которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) → (x3 ∧ x4) = 0
¬(x3 ≡ x4) → (x5 ∧ x6) = 0
¬(x5 ≡ x6) → (x7 ∧ x8) = 0
¬(x7 ≡ x8) → (x9 ∧ x10) = 0
¬(x9 ≡ x10) → (x11 ∧ x12) = 0
(x1 ≡ x4) ∨ (x5 ≡ x8) ∨ (x2 ≡ x12) = 1

В качестве ответа Вам нужно указать количество таких наборов.

✍ Решение:

x1 x2 x4 x5 x8 x12 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0

Так как в схеме отображений значения для пары x1 и x2 равные 00 и 11 не используются, то выделим их и не будем использовать в последующих вычислениях. Выпишем оставшиеся варианты:

x1 x2 x4 x5 x8 x12 0 1 1 0 1 0 y1 0 1 1 1 0 0 y2 1 0 0 0 1 1 y3 1 0 0 1 0 1 y4

Построим таблицу отображений отдельно для каждой получившейся строки, учитывая значения операндов (x n):

Посчитаем число решений для всех полученных строк: 4 + 4 + 2 + 2 = 12

Эти решения необходимо исключить, т.к. мы рассмотрели ложный случай уравнения 6 :

96 - 12 = 84

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

Изменений в КИМ ЕГЭ 2020 г. по информатике и ИКТ нет.

Направления, по которым будет проведена проверка знаний:

• Программирование;
• Алгоритмизация;
• Средства ИКТ;
• Информационная деятельность;
• Информационные процессы.

Необходимые действия при подготовке :

• Повторение теоретического курса;
• Решение тестов по информатике онлайн ;
• Знание языков программирования;
• Подтянуть математику и математическую логику;
• Использовать более широкий спектр литературы – школьной программы для успеха на ЕГЭ недостаточно.

Структура экзамена

Длительность экзамена – 3 часа 55 минут (255 минут), полтора часа из которых рекомендовано уделить выполнению заданий первой части КИМов.

Задания в билетах разделены на блоки:

• Часть 1 - 23 задания с кратким ответом.
• Часть 2 - 4 задачи с развернутым ответом.

Из предложенных 23 заданий первой части экзаменационной работы 12 относятся к базовому уровню проверки знаний, 10 – повышенной сложности, 1 – высокому уровню сложности. Три задачи второй части высокого уровня сложности, одна – повышенного.

При решении обязательна запись развернутого ответа (произвольная форма).
В некоторых заданиях текст условия подан сразу на пяти языках программирования – для удобства учеников.

Баллы за задания по информатике

1 балл - за 1-23 задания
2 балла - 25.
З балла - 24, 26.
4 балла - 27.
Всего: 35 баллов.

Для поступления в технический вуз среднего уровня, необходимо набрать не менее 62 баллов. Чтобы поступить в столичный университет, количество баллов должно соответствовать 85-95.

Для успешного написания экзаменационной работы необходимо четкое владение теорией и постоянная практика в решении задач.

Твоя формула успеха

Труд + работа над ошибками + внимательно читать вопрос от начала и до конца, чтобы избежать ошибок = максимальный балл на ЕГЭ по информатике.

"Решаем трудные задачи ЕГЭ по информатике"

Цель семинара: рассмотреть методические приёмы решения наиболее сложных задач ЕГЭ по информатике.

Ведущие: учителя информатики общеобразовательных организаций Костромской области

Внимание!!! Участникам семинара будут выданы сертификаты

Условия получения сертификата

• Выполнение предложенных в ходе мастер-классов заданий (по всем типам заданий)
• Обратная связь с учителями, ведущими мастер-класс (отправка выполненных заданий учителю на электронный адрес)

Ход семинара

1. Задание № 23 ЕГЭ. Решение логических уравнений зеркальным способом

Ведущая: Лебедева Елена Валерьевна, учитель информатики МБОУ города Костромы "Средняя общеобразовательная школа № 21"

• Посмотрите видео-материалы мастер-класса учителя и выполните тренировочные задания. Если видео-материалы просмотреть не удаётся, то скачайте презентацию и познакомьтесь с технологией выполнения задания № 23.
• [email protected]

Тренировочные задания к части 1 Метод отображения задание 1.docx

Тренировочные задания к части 2Метод отображения задание 2.docx

Презентация по материалам части 1 и части 2

Тренировочные задания к части 3. метод отображения задание 3.docx
Презентация по материалам части 3

2. Задание № 5 ЕГЭ. Кодирование и декодирование данных

Ведущая: Смирнова Елена Леонидовна, учитель информатики МОУ СОШ № 2 городского округа город Буй Костромской области

• Посмотрите видео-материалы мастер-класса учителя и выполните тренировочные задания. Если видео-материалы просмотреть не удаётся, то скачайте презентацию и познакомьтесь с технологией выполнения задания № 5.
• Выполненные тренировочные задания отправьте учителю на электронный адрес [email protected]
• Получите от учителя ответ о результатах выполненной вами работы.

Презентация по демонстрируемым материалам

Носкин Андрей Николаевич,
учитель информатики
высшей квалификационной категории,
кандидат военных наук, доцент
ГБОУ Лицей №1575 город Москва

Оптимизированный метод отображения для решения задачи 23 из КИМ ЕГЭ по информатике и ИКТ

Одной из самой трудной задачей в КИМ ЕГЭ является задача 23, в которой надо найти количество различных наборов значений логических переменных, которые удовлетворяют указанному условию.
Данная задача является едва ли не самым сложным заданием КИМ ЕГЭ по информатике и ИКТ. С ним, как правило, справляются не более 5% экзаменуемых {1}.
Такой маленький процент учеников, которые справились с данным заданием объясняется следующим:
- ученики могут путать (забыть) знаки логических операций;
- математические ошибки в процессе выполнения расчетов;
- ошибки в рассуждениях при поиске решения;
- ошибки в процессе упрощения логических выражений;
- учителя рекомендуют решать данную задачу, после выполнения всей работы, так как вероятность допущения
ошибок очень велика, а «вес» задачи составляет всего лишь один первичный балл.
Кроме того, некоторые учителя сами с трудом решают данный тип задач и поэтому стараются решать с детьми более простые задачи.
Также усложняет ситуацию, что в данном блоке существует большое количество разнообразных задач и невозможно подобрать какое-то шаблонное решение.
Для исправление данной ситуации педагогическим сообществом дорабатываются основные две методики решения задач данного типа: решение с помощью битовых цепочек {2} и метод отображений {3}.
Необходимость доработки (оптимизации) данных методик обусловлена тем, что задачи постоянно видоизменяются как по структуре, так и по количеству переменных (только один тип переменных Х, два типа переменных Х и Y, три типа: X, Y, Z).
Сложность освоения данными методиками решения задач подтверждается тем, что на сайте К.Ю. Полякова существует разборов данного типа задач в количестве 38 штук{4}. В некоторых разборах приведены более одного типа решения задачи.
Последнее время в КИМ ЕГЭ по информатике встречаются задачи с двумя типа переменных X и Y.
Я оптимизировал метод отображения и предлагаю своим ученикам пользоваться усовершенствованным методом.
Это дает результат. Процент моих учеников, которые справляются с данной задачей варьируется до 43% от сдающих. Как правило, ежегодно у меня сдает ЕГЭ по информатике от 25 до 33 человек из всех 11-х классов.
До появления задач с двумя типами переменными метод отображения ученики использовали очень успешно, но после появления в логическом выражении Y, я стал замечать, что у детей перестали совпадать ответы с тестами. Оказалось, они не совсем четко стали представлять, как составить таблицу отображений с новым типом переменной. Тогда мне пришла мысль, что для удобства надо все выражение привести к одному типу переменной, как удобно детям.
Приведу более подробно данную методику. Для удобства буду ее рассматривать на примере системы логических выражений, приведенных в {4}.
Сколько различных решений имеет система логических уравнений

(x 1 ^ y 1) = (¬x 2 V ¬ y 2 )
(x 2 ^ y 2) = (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5 ) = (¬ x 6 V ¬ y 6 )

где x 1 , …, x 6 , y 1 , …, y 6 , - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
1. Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У . Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z.
2. Теперь перепишем систему с новыми однотипными переменными. Сложность задачи будет заключаться во внимательной записи при замене переменных.

(z 1 ^ z 2) = (¬z 3 V ¬ z 4 )
(z 3 ^ z 4) = (¬ z 5 V ¬ z 6 )
...
(z 9 ^ z 10 ) = (¬ z 11 V ¬ z 12)

3. Построим таблицу, в которой переберем все варианты z 1 , z 2 , z 3 , z 4 , поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2 4); уберем из таблицы такие значения z 4 , при которых первое уравнение не имеет решения (зачеркнутые цифры).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Анализируя таблицу, строим правило отображения пар переменных (например, паре Z 1 Z 2 =00 соответствует пара Z 3 Z 4 = 11) .

5. Заполняем таблицу, вычисляя количество пар переменных, при котором система имеет решение.

6. Складываем все результаты: 9 + 9 + 9 + 27 = 54
7. Ответ: 54.
Приведенная выше оптимизированная методика решения задачи 23 из КИМ ЕГЭ позволила ученикам вновь обрести уверенность и решать успешно этот тип задачи.

Литература:

1. ФИПИ. Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ. Режим доступа: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. К.Ю. Поляков, М.А. Ройтберг. Системы логических уравнений: решение с помощью битовых цепочек. Журнал Информатика, № 12, 2014, с. 4-12. Издательский дом "Первое сентября", г.Москва.
3. Е.А. Мирончик, Метод отображения. Журнал Информатика, № 10, 2013, с. 18-26. Издательский дом "Первое сентября", г.Москва.

Решение систем логических уравнений методом замены переменных

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

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

				Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x9, y1, y2, ... y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 - два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Ответ: 1024

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x9 ∨ x10 = 1,

где x1, x2, … x10 - ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 (0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 (0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N i +1 = N i + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

Решение систем логических уравнений различного типа

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 , ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

				Кол-во наборов

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

Решение систем логических уравнений методом построения рекуррентных формул

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Наборы	Обозн .	Формула	Количество наборов
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255