Задания по информатике
<<  «Каверзные» задания в ОГЭ по информатике Авторский курс информатики для основной школы: проблемы и возможности  >>
Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ
Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ
Структура КИМ ЕГЭ 2015(2016)
Структура КИМ ЕГЭ 2015(2016)
Изменения КИМ ЕГЭ 2015 (2016)
Изменения КИМ ЕГЭ 2015 (2016)
Итоги ЕГЭ по информатике и ИКТ 2015
Итоги ЕГЭ по информатике и ИКТ 2015
Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ
Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ
Распределение участников по группам
Распределение участников по группам
Группа 1
Группа 1
Группа 2
Группа 2
Группа 3
Группа 3
Группа 4
Группа 4
Задания с решаемостью выше нормативного значения №№ 3, 5, 15, 17, 19 –
Задания с решаемостью выше нормативного значения №№ 3, 5, 15, 17, 19 –
Задания с решаемостью ниже нормативного значения №№ 1, 6, 9, 10, 11,
Задания с решаемостью ниже нормативного значения №№ 1, 6, 9, 10, 11,
Задания с решаемостью по нормативам №№ 2, 4, 7, 8, 13, 20, 21, 24, 25,
Задания с решаемостью по нормативам №№ 2, 4, 7, 8, 13, 20, 21, 24, 25,
Задания с решаемостью по Марий Эл ниже, чем по России №№ 7, 8, 12, 15,
Задания с решаемостью по Марий Эл ниже, чем по России №№ 7, 8, 12, 15,
Блоки тем из курса информатики, проверяемые в ЕГЭ
Блоки тем из курса информатики, проверяемые в ЕГЭ
Раздел «Элементы математической логики» (раздел 1.5 «Перечня элементов
Раздел «Элементы математической логики» (раздел 1.5 «Перечня элементов
Общие свойства
Общие свойства
Дизъюнкция
Дизъюнкция
Конъюнкция
Конъюнкция
Простые дизъюнкции и конъюнкции
Простые дизъюнкции и конъюнкции
Дизъюнкция простых конъюнкций
Дизъюнкция простых конъюнкций
Импликация
Импликация
Задание 2 (базового уровня сложности)
Задание 2 (базового уровня сложности)
Решение
Решение
Задание 2.2
Задание 2.2
Решение
Решение
Задание 18 (повышенного уровня сложности)
Задание 18 (повышенного уровня сложности)
Решение
Решение
Задание №23 высокого уровня сложности
Задание №23 высокого уровня сложности
Примеры СЛУ:
Примеры СЛУ:
Примеры СЛУ:
Примеры СЛУ:
Решить систему логических уравнений – это значит найти такие значения
Решить систему логических уравнений – это значит найти такие значения
Способы решения СЛУ:
Способы решения СЛУ:
Пример 1
Пример 1
Выбор метода решения СЛУ
Выбор метода решения СЛУ
Выбранные методы решения СЛУ
Выбранные методы решения СЛУ
Анализ СЛУ
Анализ СЛУ
Метод отображения
Метод отображения
Метод отображения для уравнений первого типа
Метод отображения для уравнений первого типа
Метод отображения для уравнений первого типа
Метод отображения для уравнений первого типа
Метод отображения для уравнений второго типа
Метод отображения для уравнений второго типа
Метод отображения для уравнений 2-го типа
Метод отображения для уравнений 2-го типа
Метод динамического программирования при заполнении таблицы
Метод динамического программирования при заполнении таблицы
Пример 2. Метод отображения
Пример 2. Метод отображения
00
00
00
00
1
1
Пример 3. Дополнительные условия
Пример 3. Дополнительные условия
Пример 4. Дополнительные условия
Пример 4. Дополнительные условия
Пример 5. Дополнительные условия
Пример 5. Дополнительные условия
Пример 6. Дополнительные условия
Пример 6. Дополнительные условия
Пример 7. Дополнительные условия
Пример 7. Дополнительные условия
Пример 8. Метод построения бинарного дерева
Пример 8. Метод построения бинарного дерева
Преобразование системы
Преобразование системы
Дерево решений
Дерево решений
Решение с помощью анализа битовых цепочек
Решение с помощью анализа битовых цепочек
Типичные ограничения
Типичные ограничения
Типичные ограничения
Типичные ограничения
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Ещё пример
Ещё пример
Демо-вариант ЕГЭ-2015
Демо-вариант ЕГЭ-2015
01011111
01011111
10 + 10 = 20
10 + 10 = 20
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
X: 0000 0001 0011 0111 1111
X: 0000 0001 0011 0111 1111
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
Сколько существует различных наборов значений логических переменных x1
Сколько существует различных наборов значений логических переменных x1
к ЕГЭ 2016
к ЕГЭ 2016
Этап 1. Как устроено множество решений
Этап 1. Как устроено множество решений
Уравнения полученной системы имеют вид (k=1, 2, 3, 4): Это означает,
Уравнения полученной системы имеют вид (k=1, 2, 3, 4): Это означает,
Б. Анализ системы
Б. Анализ системы
Этап 2. Подсчет числа решений
Этап 2. Подсчет числа решений
Пример 10
Пример 10
Этап 1. Как устроено множество решений
Этап 1. Как устроено множество решений
Далее, ¬a /\ ¬b = 0 означает, что, если ¬a истинно, то ¬b истинным
Далее, ¬a /\ ¬b = 0 означает, что, если ¬a истинно, то ¬b истинным
Б. Анализ системы
Б. Анализ системы
Этап 2. Подсчет числа решений
Этап 2. Подсчет числа решений
Полезные преобразования
Полезные преобразования
Рекомендации
Рекомендации
Если не получается решить задачу в общем виде, можно попробовать
Если не получается решить задачу в общем виде, можно попробовать
Ким егэ 2016
Ким егэ 2016
Заключение
Заключение
Библиографический список
Библиографический список
Благодарю за внимание
Благодарю за внимание

Презентация: «Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ». Автор: User. Файл: «Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ.pptx». Размер zip-архива: 1079 КБ.

Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ

содержание презентации «Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ.pptx»
СлайдТекст
1 Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ

Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ

Ледак Л.П., заместитель председателя предметной комиссии по информатике и ИКТ РМЭ

2 Структура КИМ ЕГЭ 2015(2016)

Структура КИМ ЕГЭ 2015(2016)

3 Изменения КИМ ЕГЭ 2015 (2016)

Изменения КИМ ЕГЭ 2015 (2016)

Деление работы на части; общее количество заданий (с 32 до 27); максимальное количество первичных баллов (с 40 до 35); необходимый минимум первичных баллов (с 8 до 6); алгоритм перевода первичных баллов в тестовые; относительный вес баллов за задания с развернутым ответом; укрупненные позиции в спецификации; сокращение количества простых заданий;

4 Итоги ЕГЭ по информатике и ИКТ 2015

Итоги ЕГЭ по информатике и ИКТ 2015

50394 чел.

89 чел .

7,2%

2, 6 %

16,15%, (в 2014г. – 10,36%)

19,1% (в 2014г. – 12,6%)

105 чел. – 0,21%, (в 2014г. – 35 чел. – 0,07%)

0 чел. (В 2014г. – 0 чел.)

8,21% (в 2014г. – 7,15% )

11,2% (в 2014г. – 4,2% )

53,99 (в 2014г. – 57,79 )

55,6 (в 2014г. – 57,2)

Показатели

по России

по Марий Эл

Количество участников

Доля участников экзамена среди всех выпускников

Доля выпускников, не набравших минимального количества баллов

Количество стобалльников

Доля высокобалльников (81-100 тестовых баллов)

Средний балл:

5 Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ
6 Распределение участников по группам

Распределение участников по группам

Группа 1 – участники экзамена, получившие балл ниже минимального (менее 6 первичных баллов) Группа 2 – участники, набравшие больше минимального, но менее половины первичных баллов (от 6 до 17) Группа 3 – участники, набравшие более половины первичных баллов, но не входящие в группу 4 Группа 4 – участники, получившие максимальные баллы

7 Группа 1

Группа 1

По России - 16,53% ; по Марий Эл - 19,1% (17 чел.) Из части 2 только задание 26 покорилось 5% участников этой группы с минимальным результатом в 1 балл (из 3-х возможных). Рекомендация: для оценки своих возможностей им необходимо хотя бы знакомство с демоверсией КИМ ЕГЭ.

8 Группа 2

Группа 2

По России - 32,3% Не справляются с заданиями 11, 18, 21, 22 23, 25 и 27. Рекомендации: использовать при подготовке к экзамену тематические сборники заданий в формате ЕГЭ.

9 Группа 3

Группа 3

По России – 46 % Уверенное выполнение заданий 1, 6, 9, 10, 12, 13, 20, 21, 24, 25 и 26. Вызывают затруднения задания 11, 14, 16 и 22 (40%). Задания 18, 23 и 27 выполняются неудовлетворительно (ниже 15%). Рекомендация: тренировка по решению заданий с нестандартными формулировками, заданий, требующих применения знаний в новой ситуации.

10 Группа 4

Группа 4

В России – менее 5% участников Затруднения у участников из этой группы вызывают лишь задания 18, 23 и 27. Рекомендация: тренировка по созданию оригинальных программ для решения практических задач; тренировка по решению систем логических уравнений разных типов.

11 Задания с решаемостью выше нормативного значения №№ 3, 5, 15, 17, 19 –

Задания с решаемостью выше нормативного значения №№ 3, 5, 15, 17, 19 –

легкие задания

по России по Марий Эл

12 Задания с решаемостью ниже нормативного значения №№ 1, 6, 9, 10, 11,

Задания с решаемостью ниже нормативного значения №№ 1, 6, 9, 10, 11,

12, 14, 16, 18, 22, 23, 27 по России по Марий Эл

1(5н)

43,5

44

6

42,3

48

9

38,5

53

10

36,5

40

11

25,7

36

12

40,2

37

14

27,5

36

16

30,9

40

18

11,3

19

22

25,6

16

23

9,4

6

27

9,8

14

Умение кодировать и декодировать информацию

1

Формальное исполнение алгоритма, записанного на естественном языке

1

Умение определять скорость передачи информации, объем памяти для хранения звук. и граф. информации

1

Знания о методах измерения количества информации

1

Умение исполнить рекурсивный алгоритм

1

Знание базовых принципов адресации в сети

1

Умение исполнить алгоритм для конкретного исполнителя

1

Знание позиционных систем счисления

1

Знание основных понятий и законов математической логики

1

Умение анализировать результат исполнения алгоритма

1

Умение строить и преобразовывать логические выражения

1

Умения создавать собственные программы (30–50 строк) для решения задач средней сложности

4

Б 60–90

Б 60–90

Б 60–90

Б 60–90

Б 60–90

Б 60–90

П 40–60

П 40–60

П 40–60

П 40–60

В < 40

В < 40

13 Задания с решаемостью по нормативам №№ 2, 4, 7, 8, 13, 20, 21, 24, 25,

Задания с решаемостью по нормативам №№ 2, 4, 7, 8, 13, 20, 21, 24, 25,

26

по России по Марий Эл

14 Задания с решаемостью по Марий Эл ниже, чем по России №№ 7, 8, 12, 15,

Задания с решаемостью по Марий Эл ниже, чем по России №№ 7, 8, 12, 15,

22, 23 по России по Марий Эл

15 Блоки тем из курса информатики, проверяемые в ЕГЭ

Блоки тем из курса информатики, проверяемые в ЕГЭ

Математические основы информатики (кодирование и передача данных, системы счисления, элементы математической логики, дискретные математические объекты). Алгоритмы и программирование. Теоретические основы информационно-коммуникационных технологий.

16 Раздел «Элементы математической логики» (раздел 1.5 «Перечня элементов

Раздел «Элементы математической логики» (раздел 1.5 «Перечня элементов

содержания, проверяемых на ЕГЭ» Кодификатора).

Логические операции: Отрицание (инверсия, логическое НЕ); конъюнкция (логическое умножение, логическое И); дизъюнкция (логическое сложение, логическое ИЛИ); следование (импликация); тождество (эквивалентность). Логические константы – ИСТИНА (1) и ЛОЖЬ (0). Логическое выражение – выражение, составленное из символов логических переменных и констант с помощью знаков логических операций и скобок. Приоритеты логических операций. Значение логического выражения при заданных значениях переменных. Таблица истинности.

17 Общие свойства

Общие свойства

Для набора из n логических переменных существует ровно 2n различных набора значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2n строк.

18 Дизъюнкция

Дизъюнкция

1. Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений. 2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна. 3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна. 4. Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

19 Конъюнкция

Конъюнкция

1. Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений. 2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна. 3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна. 4. Значение конъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

20 Простые дизъюнкции и конъюнкции

Простые дизъюнкции и конъюнкции

Назовем (для удобства) конъюнкцию простой, если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой, если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания. Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных. Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.

21 Дизъюнкция простых конъюнкций

Дизъюнкция простых конъюнкций

На рисунке приведены все строки таблицы истинности функции F(x, y, z), при которых F(x, y, z) истинно. x y z F 0 1 1 1 1 0 1 1 1 1 0 1 Тогда функция F может быть задана таким выражением: (¬x/\y/\z) \/ (x/\¬y/\z) \/ (x/\y/\¬z).

22 Импликация

Импликация

Импликация A ?B равносильна дизъюнкции (¬А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В. 2. Импликация A ?B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A ?B истинна при любом значении B.

23 Задание 2 (базового уровня сложности)

Задание 2 (базового уровня сложности)

Задание 2.1 Логическая функция F задаётся выражением (¬z) /\ x \/ x /\ y Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Перем. 1 Перем. 2 Перем. 3 Функция ??? ??? ??? F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

24 Решение

Решение

Заметим, что при x=0 значение F(x, y, z)=0 независимо от значений аргументов y и z. В таблице этому свойству удовлетворяет 3-я переменная. Значит, это x. Чтобы понять, какой столбец таблицы соответствует переменной y, а какой – переменной z, рассмотрим строку, в которой x=1 (то есть в третьем столбце стоит 1), а F(x, y, z) = 0 . Это происходит, если y=0, а z=1. В нужной строке (это 3-я строка снизу) 1 стоит в 1-м столбце, а 0 – во втором. Значит, 1-й столбец соответствует z, а второй соответствует y. Ответ: zyx

25 Задание 2.2

Задание 2.2

Логическая функция F задается выражением (x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z). На рисунке приведен фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Перем. 1 Перем. 2 Перем. 3 Функция ??? ??? ??? F 0 1 0 1 1 1 0 1 1 1 1 1 В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.

26 Решение

Решение

В этом случае также при x=0 значение F(x, y, z)=0 независимо от значений аргументов y и z. В таблице только второй столбец содержит только единицы. Значит, второй столбец соответствует x. Чтобы понять, какой столбец таблицы соответствует переменной y, а какой – переменной z, надо найти строку, в которой у переменных y и z разные значения. В этом случае x /\ y /\ z = 0 и x /\¬y /\¬z = 0. Значит, так как F(x, y, z) = 1, x /\ y /\¬z = 1. Это происходит, если y=1, а z=0. В нужной строке (это 3-я строка снизу) 1 стоит в 1-м столбце, а 0 – во втором. Значит, 1-й столбец соответствует y, а третий столбец соответствует z. Ответ: yxz

27 Задание 18 (повышенного уровня сложности)

Задание 18 (повышенного уровня сложности)

Пример задания 18. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула x&25 ? 0 ? (x&17 = 0 ? x&А ? 0) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

28 Решение

Решение

x&25 ? 0 ? (x&17 = 0 ? x&А ? 0) ? ? x&25 = 0 \/ (x&17 = 0 ? x&А ? 0) ? ? x&25 = 0 \/ (x&17 ? 0 \/ x&А ? 0) ? ? x&25 = 0 \/ x&17 ? 0 \/ x&А ? 0 Запишем числа 25 и 17 в двоичной системе: 2510 = 110012, 1710 = 100012. Различие между ними только в одном разряде – четвертом. Поэтому число A = 10002 =810 обеспечит тождественную истинность выражения x&25 = 0 \/ (x&17 ? 0 \/ x&8 ? 0) Ответ: 8.

29 Задание №23 высокого уровня сложности

Задание №23 высокого уровня сложности

Для того, чтобы выполнить задание № 23, ученик должен знать: таблицы истинности логических операций; законы алгебры логики должен уметь: преобразовывать логические выражения, включая выполнение замены переменных; переводить формальное описание в виде системы логических условий на нормальный, "человеческий" язык; подсчитать число двоичных наборов, удовлетворяющих заданным условиям. должен владеть: элементами комбинаторики.

30 Примеры СЛУ:

Примеры СЛУ:

31 Примеры СЛУ:

Примеры СЛУ:

32 Решить систему логических уравнений – это значит найти такие значения

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

логических переменных, которые обращают КАЖДОЕ уравнение системы в верное равенство. Логические переменные в двузначной логике могут принимать два значения: True («1») False («0»).

33 Способы решения СЛУ:

Способы решения СЛУ:

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

34 Пример 1

Пример 1

35 Выбор метода решения СЛУ

Выбор метода решения СЛУ

Данная СЛУ имеет 10 логических переменных. При решении методом составления таблицы истинности мы получим 2^10=1024 строки, поэтому этот способ затруднителен. Метод замены переменных также неэффективен, так как получится 12 новых переменных вместо 10. Построение полного бинарного дерева затруднительно в силу размерности задачи. Сведение к одному уравнению не упростит решение.

36 Выбранные методы решения СЛУ

Выбранные методы решения СЛУ

Динамическое программирование – способ решения сложных задач путём разбиения их на более простые подзадачи и их последовательного решения.

Метод отображений – нахождение правил (зависимостей) между элементами двух множеств и использование их при переходе от исходного множества к новому множеству.

37 Анализ СЛУ

Анализ СЛУ

Все уравнения, включенные в систему, являются чередующимися двух типов. В каждое уравнение включены три переменные. Зная x1 и x2, можем найти все возможные значения x3, удовлетворяющие первому уравнению. От пары (x1 , x2) переходим к паре (x2 , x3).

38 Метод отображения

Метод отображения

(0,1) (0, 0) (1,0) (1,1)

(0,1) (0, 0) (1,0) (1,1)

Исходное множество пар отображается само в себя.

Множество наборов Множество наборов исходных пар полученных пар

39 Метод отображения для уравнений первого типа

Метод отображения для уравнений первого типа

x?

x?

x?

0

0

0

0

0

0

0

1

1

1

0

1

1

1

1

1

0

0

0

1

1

1

0

1

По таблице строим правило отображения множества пар само в себя.

40 Метод отображения для уравнений первого типа

Метод отображения для уравнений первого типа

Правила отображения:

41 Метод отображения для уравнений второго типа

Метод отображения для уравнений второго типа

x?

x?

x?

0

0

0

0

1

0

1

0

1

По таблице строим правило отображения множества пар само в себя.

42 Метод отображения для уравнений 2-го типа

Метод отображения для уравнений 2-го типа

Правила отображения:

43 Метод динамического программирования при заполнении таблицы

Метод динамического программирования при заполнении таблицы

00

01

10

11

Ответ: 34 решения СЛУ

44 Пример 2. Метод отображения

Пример 2. Метод отображения

0

0

0

0

1

1

0

1

1

1

0

1

1

0

1

x1

x2

x3

45 00

00

00

01

01

10

10

11

11

0

0

0

0

0

0

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

x1x2

x2x3

x1

x2

x3

46 00

00

00

01

01

10

10

11

11

F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11)

x1x2

x2x3

47 1

1

1

1

1

232

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

48 Пример 3. Дополнительные условия

Пример 3. Дополнительные условия

1

1

0

0

143

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

49 Пример 4. Дополнительные условия

Пример 4. Дополнительные условия

1

1

1

1

124

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

50 Пример 5. Дополнительные условия

Пример 5. Дополнительные условия

1

1

1

1

56

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

51 Пример 6. Дополнительные условия

Пример 6. Дополнительные условия

1

1

0

0

52

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

52 Пример 7. Дополнительные условия

Пример 7. Дополнительные условия

52 решения

65 решений

Ответ: 117 решений

0

0

1

1

65

00

01

10

11

Пара

Пара

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

Количество пар

x1, x2

x2, x3

x3, x4

x4, x5

x5, x6

x6, x7

x7, x8

x8, x9

x9, x10

53 Пример 8. Метод построения бинарного дерева

Пример 8. Метод построения бинарного дерева

Сколько различных решений имеет система логических уравнений: (X1 ? X2 ? ¬X1 ? ¬X2) ?(X2 ? ¬X3 ? ¬X2 ? X3) = 1 (X2 ? X3 ? ¬X2 ? ¬X3) ?(X3 ? ¬X4 ? ¬X3 ? X4) = 1 (X3 ? X4 ? ¬X3 ? ¬X4) ?(X4 ? ¬X5 ? ¬X4 ? X5) = 1 …………………………………………………… (X8 ? X9 ? ¬X8 ? ¬X9) ?(X9 ? ¬X10 ? ¬X9 ? X10) = 1 X1 =0 X10= 0

54 Преобразование системы

Преобразование системы

(X1 ? X2) ?(X2 ? X3) = 1 (X2 ? X3) ?(X3 ? X4) = 1 (X3 ? X4) ?(X4 ? X5) = 1 ………………………………………………… (X8 ?X9) ?(X9 ? X10) = 1 X1 =0 X10= 0

55 Дерево решений

Дерево решений

Ответ: 5

56 Решение с помощью анализа битовых цепочек

Решение с помощью анализа битовых цепочек

57 Типичные ограничения

Типичные ограничения

Задача 1.

«Соседние биты одинаковы»

Решения: 00000, 11111

Задача 2.

«Соседние биты различны»

«Биты чередуются»

Решения: 01010, 10101

57

58 Типичные ограничения

Типичные ограничения

Задача 3.

«Запрещена комбинация 10»

«После первой единицы все следующие биты – 1»

«Все нули, потом все единицы»

Решения: 000000, 000001, 000011, 000111, 001111, 011111, 111111

Для уравнения с N переменными: N+1 решений.

58

59 Более сложный пример

Более сложный пример

Задача 4.

«Запрещена комбинация 1?0»

«Слева от каждого нулевого бита (начиная с 3-го) должны стоять два нуля»

«Все нули, потом все единицы»

Решения: 000000, 000001, 000011, 000111, 001111, 011111, 111111

Для уравнения с N переменными: N+2 решений.

59

60 Более сложный пример

Более сложный пример

Задача 5.

«Запрещена комбинация 00»

60

61 Ещё пример

Ещё пример

Задача 6.

«Запрещена комбинация 1?0»

«После двух единиц подряд следуют только единицы»

61

62 Демо-вариант ЕГЭ-2015

Демо-вариант ЕГЭ-2015

«Запрещено 00»

«После двух единиц идут только единицы»

«Голова»

«Хвост»

1

1

?

1

«Запрещено 00 и 11»

«Биты чередуются»

62

63 01011111

01011111

Варианты отличаются местом последнего нуля:

11111111, 01111111, 10111111, 01011111, 10101111, 01010111, 10101011, 01010101, 10101010

1 решение

2 решения

2 нулевых бита, 22 вариантов

Демо-вариант ЕГЭ-2015

63

64 10 + 10 = 20

10 + 10 = 20

Демо-вариант ЕГЭ-2014

«Очередной бит равен хотя бы одному из 2-х следующих»

«Запрещены комбинации 100 и 011»

«После 01 или 10 биты чередуются»

Сначала цепочка нулей, потом биты чередуются (1/0) сначала цепочка единиц, потом биты чередуются.

0000000000 0000000001 0000000010 0000000101 … 0101010101

1111111111 1111111110 1111111101 1111111010 … 1010101010

64

65 Демо-вариант ЕГЭ-2013

Демо-вариант ЕГЭ-2013

5 решений: X = 0000, 0001, 0011, 0111, 1111

5 решений: Y = 0000, 0001, 0011, 0111, 1111

Связь X и Y:

Без ограничений!

65

66 X: 0000 0001 0011 0111 1111

X: 0000 0001 0011 0111 1111

Y: 0000 0001 0011 0111 1111

5 4 3 2 1

5 + 4 + 3 + 2 + 1 = 15

Демо-вариант ЕГЭ-2013

66

67 Демо-вариант ЕГЭ-2012

Демо-вариант ЕГЭ-2012

Замена переменных:

67

68 Демо-вариант ЕГЭ-2012

Демо-вариант ЕГЭ-2012

К одному уравнению:

Решения:

68

69 Демо-вариант ЕГЭ-2012

Демо-вариант ЕГЭ-2012

Переход к исходным переменным:

5 бит

5 бит

69

70 Ещё одна задача (2015)

Ещё одна задача (2015)

Замена переменных:

70

71 Ещё одна задача (2015)

Ещё одна задача (2015)

Решение:

«Запрещена комбинация 01»

«Все единицы, потом – все нули»

8 решений:

0000000 1000000 1100000 1110000 1111000 1111100 1111110 1111111

71

72 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

255

Ещё одна задача (2015)

2 решения: (0;1) и (1;0)

1 решение: (1;1)

Z

X,Y

Z

X,Y

0000000 1000000 1100000 1110000

128 64 32 16

1111000 1111100 1111110 1111111

8 4 2 1

72

73 Сколько существует различных наборов значений логических переменных x1

Сколько существует различных наборов значений логических переменных x1

x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям? (¬ (x1 ? y1)) ? (x2 ? y2) (¬ (x2 ? y2)) ? (x3 ? y3) … (¬ (x8 ? y8)) ? (x9 ? y9)

74 к ЕГЭ 2016

к ЕГЭ 2016

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, x10, которые удовлетворяют всем перечисленным ниже условиям? Набросок решения: Решение состоит из двух этапов. Сначала попытаемся описать, как устроены все наборы значений переменных, удовлетворяющие данной системе. Далее подсчитаем число таких наборов.

75 Этап 1. Как устроено множество решений

Этап 1. Как устроено множество решений

А. Предварительный этап – упрощаем уравнения. В системе фигурируют логические функции от следующих выражений: (x1 ? x2), (x3 ? x4), (x5 ? x6), (x7 ? x8), (x9 ? x10). Подобно тому, как это делается при решении алгебраических уравнений, сделаем замену переменных: Общая формула замены (k=1, 2, 3, 4, 5): tk = (x2k-1 ? x2k)

76 Уравнения полученной системы имеют вид (k=1, 2, 3, 4): Это означает,

Уравнения полученной системы имеют вид (k=1, 2, 3, 4): Это означает,

что из каждых двух переменных tk и tk+1 ровно одна равна 1 и ровно одна равна нулю, т.е. эти переменные имеют разные значения.

77 Б. Анализ системы

Б. Анализ системы

В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: 01010 и 10101. Далее, так как tk = x2k-1 ? x2k (здесь k=1, 2, 3, 4, 5), то каждому значению tk соответствуют две пары значений переменных x2k-1 и x2k. Например, tk = 1 в двух случаях: { x2k-1 = x2k=1 } и { x2k-1 = x2k=0 }.

78 Этап 2. Подсчет числа решений

Этап 2. Подсчет числа решений

Каждому из двух решений системы для переменных t соответствует 25 = 32 решения исходной системы. Поэтому исходная система имеет 2?32 = 64 решения. Ответ: 64

79 Пример 10

Пример 10

Битовые цепочки

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

80 Этап 1. Как устроено множество решений

Этап 1. Как устроено множество решений

А. Предварительный этап – упрощаем уравнения. Заметим, что выражение (a \/ b) /\ (¬a \/ ¬b) равносильно тому, что ровно одна из переменных a и b равна 1, то есть равносильно выражению ¬(a ? b). Поэтому каждое выражение вида (xk \/ xk+2) /\ (¬xk \/ ¬xk+2), где k=1, …, 8, в наших уравнениях можно заменить выражением ¬(xk ? xk+2). Таким образом, наша система эквивалентна системе

81 Далее, ¬a /\ ¬b = 0 означает, что, если ¬a истинно, то ¬b истинным

Далее, ¬a /\ ¬b = 0 означает, что, если ¬a истинно, то ¬b истинным

быть не может. То есть ¬a /\ ¬b = 0 эквивалентно ¬a ? b = 1. Поэтому систему можно записать в виде

82 Б. Анализ системы

Б. Анализ системы

Каждое из уравнений полученной системы имеет вид (k = 1, …, 8): ¬(xk ? xk+1) ? (xk ? xk+2) =1 Пример решения: 1111010101 Здесь голова набора состоит из четырех единиц, а хвост – это последовательность 01010101. в данном примере длина головы равна 4. Важное наблюдение. Для каждой непустой головы есть ровно один хвост, образующий вместе с ней решение. Действительно, первая цифра такого хвоста – это цифра, противоположная цифрам головы. А дальше цифры в хвосте чередуются.

83 Этап 2. Подсчет числа решений

Этап 2. Подсчет числа решений

В соответствии с важным наблюдением, количество решений совпадает с количеством возможных голов. Очевидно, существует 10 голов, состоящих из единиц (1, 11, 111, …, 1111111111) и столько же голов, состоящих из нулей. Ответ: 20

84 Полезные преобразования

Полезные преобразования

¬A \/ b равносильно a ? b (a? b) /\ (a ? b) равносильно a ? b (¬a \/ b) /\ (a \/ ¬b) равносильно a ? b (a \/ b) /\ (¬a \/ ¬b) равносильно ¬(a ? b)

85 Рекомендации

Рекомендации

Первая цель при выполнении задания №23 - понять, что собой представляет множество решений системы. Для этого систему бывает полезно преобразовать (упростить) систему, используя тождественные преобразования и замены переменных. Затем подсчитать количество элементов во множестве решений. Во многих случаях система состоит из однотипных уравнений, каждое из которых связывает небольшое число переменных (две-три-четыре), при том, что в системе может быть 10 и более переменных. Обычно, количество переменных не является источником сложности, оно является параметром решения. .

86 Если не получается решить задачу в общем виде, можно попробовать

Если не получается решить задачу в общем виде, можно попробовать

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

87 Ким егэ 2016

Ким егэ 2016

Модель КИМ 2016 г. по сравнению с КИМ 2015 г. изменилась незначительно. В первой части больше совсем не будет заданий с выбором одного ответа из множества предложенных, все ответы будут представлять собой либо число, либо строку символов, формируемую по определенному алгоритму. В связи с этим была изменена последовательность предъявления заданий 1–5 Количество заданий и максимальный первичный балл остались без изменений.

88 Заключение

Заключение

ЕГЭ по информатике и ИКТ имеет профильный характер, является экзаменом по выбору, требует от участника целенаправленной подготовки. ЕГЭ - инструмент по отбору абитуриентов в ведущие ВУЗы страны. Конечно, педагогическое мастерство учителя в решении данной задачи играет не меньшую роль, чем уровень мотивации ученика. При подготовке ориентироваться не на тренировку решения конкретного типа заданий, приведенного в демоверсии КИМ ЕГЭ, а на полноценное усвоение изучаемого материала.

89 Библиографический список

Библиографический список

Поляков К.Ю. Логические уравнения // Информатика, № 14, 2011, с. 30-35. Мирончик, Ел. А. Системы логических уравнений. Метод отображений/ Ел. А. Мирончик, Ек. А. Мирончик// Преподавание информационных технологий в Российской Федерации: материалы Десятой открытой Всероссийской конференции. – М.: МГУ им. М.В. Ломоносова, 2012. – С. 232–234 К.Ю. Поляков, М.А. Ройтберг. Системы логических уравнений: решение с помощью битовых цепочек // Информатика, № 12, 2014, с. 4-12 К.Ю. Поляков, Множества и логика в задачах ЕГЭ // Информатика, № 10, 2015, с. 38-42.

90 Благодарю за внимание

Благодарю за внимание

«Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ»
http://900igr.net/prezentacija/informatika/reshenie-slozhnykh-zadanij-kim-ege-po-informatike-i-ikt-219079.html
cсылка на страницу

Задания по информатике

10 презентаций о заданиях по информатике
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Задания по информатике > Решение сложных заданий КИМ ЕГЭ по информатике и ИКТ