Системы уравнений
<<  Методы решения уравнений, содержащих модуль Решение систем логических уравнений  >>
Системы логических уравнений в задачах ЕГЭ по информатике
Системы логических уравнений в задачах ЕГЭ по информатике
Постановка задачи (ЕГЭ-2011)
Постановка задачи (ЕГЭ-2011)
Методы решения
Методы решения
Аналогии с алгеброй
Аналогии с алгеброй
Формулы логики – I
Формулы логики – I
Формулы логики – II
Формулы логики – II
Формулы логики – III
Формулы логики – III
Основные идеи
Основные идеи
Типичные ограничения
Типичные ограничения
Типичные ограничения
Типичные ограничения
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Ещё пример
Ещё пример
И снова – рекуррентные уравнения
И снова – рекуррентные уравнения
Последний пример
Последний пример
Демо-вариант ЕГЭ-2015
Демо-вариант ЕГЭ-2015
01011111
01011111
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
Основные шаги решения
Основные шаги решения
Конец фильма
Конец фильма

Презентация: «Системы логических уравнений в задачах ЕГЭ по информатике». Автор: kp. Файл: «Системы логических уравнений в задачах ЕГЭ по информатике.ppt». Размер zip-архива: 330 КБ.

Системы логических уравнений в задачах ЕГЭ по информатике

содержание презентации «Системы логических уравнений в задачах ЕГЭ по информатике.ppt»
СлайдТекст
1 Системы логических уравнений в задачах ЕГЭ по информатике

Системы логических уравнений в задачах ЕГЭ по информатике

К.Ю. Поляков, М.А. Ройтберг

2 Постановка задачи (ЕГЭ-2011)

Постановка задачи (ЕГЭ-2011)

2011: Решаемость 3,2%

Сколько решений имеет система уравнений:

2

3 Методы решения

Методы решения

замена переменных последовательное подключение уравнений метод отображения (Е.А. Мирончик)

«Информатика. Первое сентября» 1. Е. А. Мирончик, Метод отображения // Информатика, № 10, 2013, с. 18-26. 2. Е.А. Мирончик, Люблю ЕГЭ за В15, или Еще раз про метод отображения // Информатика, № 7-8, 2014, с. 26-32.

Трудоёмко длинная запись решения

2012: Решаемость 13,2%

3

4 Аналогии с алгеброй

Аналогии с алгеброй

Алгебра

Логика

Обычно уравнение имеет одно или несколько решений.

Уравнение может иметь большое, но конечное число решений.

Элементарные уравнения: линейные, квадратные.

Элементарные уравнения не выделяются.

Методы преобразования: законы сложения и умножения, формулы сокращенного умножения, свойства степеней.

Методы преобразования: законы логики (см. далее).

4

5 Формулы логики – I

Формулы логики – I

A. Свойства 0, 1 и отрицания

Свойства 0 и 1

Свойства отрицания

5

6 Формулы логики – II

Формулы логики – II

Б. Дизъюнкция и конъюнкция

Сочетательный закон

Переместительный закон

Закон поглощения

Распределительный закон

Правила де Моргана

6

7 Формулы логики – III

Формулы логики – III

В. Импликация и эквивалентность

Определение импликации

Свойства импликации

Эквивалентность

7

8 Основные идеи

Основные идеи

Решение системы уравнений – это битовая цепочка (битовый вектор) Битовый вектор рассматривается как единый объект. Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов). Нужно выделить элементарные уравнения и записать ограничения «на русском языке». Количество решений находится по правилам комбинаторики.

8

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

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

Задача 1.

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

Решения: 00000, 11111

Задача 2.

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

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

Решения: 01010, 10101

9

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

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

Задача 3.

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

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

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

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

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

10

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

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

Задача 4.

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

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

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

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

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

11

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

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

Задача 5.

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

12

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

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

Нет 00!

1

0

0

Непересекающиеся множества!

1

13

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

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

1, 1, 2, 3, 5, 8, 13, 21, 34, …

14

15 Ещё пример

Ещё пример

Задача 6.

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

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

15

16 И снова – рекуррентные уравнения

И снова – рекуррентные уравнения

Структура решения:

«Голова»

«Хвост»

0

1

1

?

1

Нет комбинации 11 последний бит – 0

16

17 Последний пример

Последний пример

Задача 7.

Последовательность выполнения:

Запрещена комбинация 1?0 на последнем шаге

Начальное значение:

17

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

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

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

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

«Голова»

«Хвост»

1

1

?

1

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

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

18

19 01011111

01011111

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

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

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

1 решение

2 решения

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

19

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

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

20

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

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

10 + 10 = 20

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

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

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

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

0000000000 0000000001 0000000010 0000000101 … 0101010101

1111111111 1111111110 1111111101 1111111010 … 1010101010

21

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

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

22

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

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

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

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

Связь X и Y:

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

23

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

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

X: 0000 0001 0011 0111 1111

Y: 0000 0001 0011 0111 1111

5 4 3 2 1

5 + 4 + 3 + 2 + 1 = 15

24

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

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

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

25

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

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

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

Решения:

26

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

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

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

5 бит

5 бит

27

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

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

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

28

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

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

Решение:

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

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

8 решений:

0000000 1000000 1100000 1110000 1111000 1111100 1111110 1111111

29

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

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

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

255

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

30

31 Основные шаги решения

Основные шаги решения

Упрощение уравнений с помощью эквивалентных преобразований замена переменных (если возможно) исследование структуры всех решений подсчёт количества решений по формулам комбинаторики

31

32 Конец фильма

Конец фильма

ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru РОЙТБЕРГ Михаил Абрамович д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ, зам. руководителя Федеральной комиссии по разработке КИМ ЕГЭ по информатике и ИКТ mroytberg@lpm.org.ru

32

«Системы логических уравнений в задачах ЕГЭ по информатике»
http://900igr.net/prezentacija/algebra/sistemy-logicheskikh-uravnenij-v-zadachakh-ege-po-informatike-105668.html
cсылка на страницу

Системы уравнений

17 презентаций о системах уравнений
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Системы уравнений > Системы логических уравнений в задачах ЕГЭ по информатике