СИСТЕМА ПОДГОТОВКИ К ЕГЭ ПО ИНФОРМАТИКЕ (НА ПРИМЕРЕ ЗАДАНИЯ №26)
методическая разработка по информатике и икт

Слайд 1

МАСТЕР-КЛАСС СИСТЕМА ПОДГОТОВКИ К ЕГЭ ПО ИНФОРМАТИКЕ (НА ПРИМЕРЕ ЗАДАНИЯ №26) у читель информатики высшей квалификационной категории, Петрова Татьяна Валентиновна, у читель информатики первой к валификационной категории Андреева Оксана Евгеньевна Сургут, 2020г . МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №44 ГОРОДА СУРГУТА

Слайд 2

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

Слайд 3

Теперь нужно определиться с критериями, по которым мы будем оценивать эффективность подготовки. Самый главный критерий – это балл на ЕГЭ и поступление в вуз. Немаловажным мы считаем начальный уровень подготовки, то есть тот уровень, с которого УЧЕНИК НАЧИНАЕТ ПОДГОТОВКУ . Третий критерий – это скорость усвоения материала, то есть способности ребёнка, который решил сдать ЕГЭ. У каждого свой темп, свои пробелы в знаниях и нужно реалистично их оценивать. КРИТЕРИИ ЭФФЕКТИВНОСТИ ПОДГОТОВКИ КОНЕЧНЫЙ РЕЗУЛЬТАТ СТАРТОВЫЕ ПОЗИЦИИ СКОРОСТЬ

Слайд 4

Система подготовки к ЕГЭ ЕГЭ 2020 ИНФОРМАТИКА СЕКРЕТЫ УСПЕШНОЙ ПОДГОТОВКИ ДОПОЛНИТЕЛЬНЫЕ ШКОЛЬНЫЕ ЗАНЯТИЯ САМОСТОЯТЕЛЬНАЯ ПОДГОТОВКА ДИСТАНЦИОННАЯ ПОДГОТОВКА ЗАНЯТИЯ С КВАЛИФИЦИРОВАННЫМ РЕПЕТИТОРОМ Я УЧИТЕЛЬ СТУПЕНЬКИ ИНТЕЛЛЕКТА ТРЕНИРОВКА ПРИСТАЛЬНОГО ВЗГЛЯДА Виды подготовки ОПЫТ УЧИТЕЛЕЙ, НАКОПЛЕННЫЙ НА ПРАКТИКЕ Приемы и методы

Слайд 5

Задание 26. Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию

Слайд 6

Спецификация КИМ для проведения в 2020 году ЕГЭ по информатике и ИКТ Элементы содержания, проверяемые на ЕГЭ Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности Проверяемые умения или способы действий Строить информационные модели объектов, систем и процессов в виде алгоритмов Уровень сложности задания В (ВЫСОКИЙ) Макс. балл за выполнение задания 3 Макс. балл за выполнение задания 30 мин (НО, МОЖНО ГОРАЗДО МЕНЬШЕ)

Слайд 7

Указания по оцениванию В задаче требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий. Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу – например, арифметическая ошибка при вычислении количества камней в заключительной позиции – при оценке решения не учитывается.

Слайд 8

Содержание 1. Формализация игровой ситуации; 2. Определение выигрышной стратегии для игры двух игроков; 3. Определение выигрышной стратегии для произвольной ситуации

Слайд 9

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

Слайд 10

И гра с полной информацией ( «крестики-нолики», шахматы) S 0 - начальная ситуация; D ={ a , b , …} - множество альтернатив на каждом шаге постоянное; Si – новая ситуация (после сделанных ходов всеми игроками); Sn - конечная ситуация; S 0 Sn - траектория игрока или его стратегией.

Слайд 11

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

Слайд 12

В ыигрышная позиция Если у игрока имеется четкая стратегия, которая однозначно приводит его из некоторой позиции ( Si ) к выигрышу, то говорят, что игрок «имеет выигрышную позицию » в позиции ( Si ).

Слайд 13

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

Слайд 14

Вариант графа, отражающий все ситуации в простой игре двух игроков

Слайд 15

Граф отображающий все множество стратегий в игре Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.

Слайд 16

Вариант таблицы , отражающий все ситуации в простой игре двух игроков

Слайд 17

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

Слайд 18

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза . Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10,7) . Тогда за один ход можно получить любую из четырёх позиций: Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не 68 менее. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 68 или больше камней. (10,7) (11,7) – 10+1 (30,7) – 10*3 (10,8) – 7+1 (10,21) – 7*3

Слайд 19

Запишем условие: +1 *3 S ≥ 68 В первой куче 6 камней. Во второй – S ( 1 ≤ S ≤ 61) Петя ходит первый. Задание 1 а) Укажите все такие значения числа S , при которых Петя может выиграть за один ход. То есть, надо найти все возможные варианты (количества камней во второй куче), при которых Петя выиграет за один ход. Очевидно, что выгоднее использовать команду – *3. Имеем: 6 + 3 S ≥ 68 S = 21 → выигрышная позиция будет (6, 21) ПРОВЕРЯМ:

Слайд 20

(6,21) (7, 21) (18,21) (6, 22) (6, 63) – 21*3 К = 6 + 63 = 69 / условие выполнено, игра завершена Если S < 21, то К max = 66 / (6,20) → (6, 20*3) → S = 66 Если S > 21 , то К max = 72, при позиции (6, 22); К max = 75, при позиции (2, 23) и т.д. То есть, при 21 ≤ S ≤ 61 , Петя однозначно выиграет за один ход. Записать надо так: Задание 1 а) Петя может выиграть при 21 ≤ S ≤ 61 . ЛИШНЕГО НИЧЕГО ПИСАТЬ НЕ НАДО!

Слайд 21

Задание 1 b ) Известно , что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S , когда такая ситуация возможна. То есть, S < 21, так как, исходя из п.а), если 21 ≤ S ≤ 61 , то Петя выиграет первым. Надо найти такое S min , при котором, Петей будет создана выигрышная позиция ( 6, 21). Следовательно S min = 7. ПРОВЕРИМ: ( 6, 7) → первый возможный неудачный ход Пети, который даст возможность Ване выиграть своим первым ходом: (6, 7*3) → (6, 21) , а это выигрышная позиция (см. п.а). Если S < 7, например 6, то максимальное значение K = 24 : (6,6) → (6, 6*3) → (6, 18). Записать надо так: Задание 1 b ) S = 7. ЛИШНЕГО НИЧЕГО ПИСАТЬ НЕ НАДО!

Слайд 22

Задание 2 Укажите такое значение S , при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один ход . Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня . Для указанного значения S опишите выигрышную стратегию Пети. То есть, надо найти такое значение S (количество камней во второй куче), при котором Петя не выиграет с первого хода, но и не даст возможность Ване выиграть его первым ходом. Причем, любой ход Вани для второго Петиного хода, создаст выигрышную ситуацию. S max = 20 ( это число легко увидеть из решения первого задания ) . (6,20) П1: (6+1,20) (7,20) В1: (8,20) (21,20) (7,21) (7,60) П2: количество камней во второй куче умножает на 3 (8,60) → К = 68 (21,60) → К = 81 (7,63) → К = 70 (7,180) → К = 187 Как бы Ваня не сыграл, любая его позиция выигрышная для Пети. Возможно, вы найдете еще значение S , которое создаст для Пети выигрышную стратегию со второго хода. Его надо описать аналогично.

Слайд 23

Записать надо так: Задание 2 Возможное значение S = 20. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (7,20). После хода Вани может возникнуть одна из 4-х позиций: (8,20), (21,20), (7,21), (7,60). В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче. ВАЖНО! Достаточно указать одно значение S и описать для него выигрышную стратегию. Можно нарисовать дерево всех возможных при выбранной стратегии Пети партий (и только их).

Слайд 24

Задание 3 Укажите значение S , при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

Слайд 25

Еще раз: надо найти S, причем обязательно учитывать условия: у Вани есть выигрышная стратегия (первым или вторым ходом) при любой игре Пети; первый ход не гарантированно выигрышный. То есть, первая стратегия может быть выигрышная, может, нет, но вторая – однозначно должна быть выигрышная! S min , при котором однозначен выигрыш со второго хода – 20, позиция (6,20) (см. задание 2). Следовательно рассмотрим S = 19.

Слайд 26

(6 ,19) П1 : (6 ,20) → К = 26 (6 ,57) → К = 63 ( 7,19) → К = 26 ( 18,19) → К = 37 ( 7,20) → К = 27 В1: ( 7,20) → К = 27 В1: ( 18,57) → К = 75 выигрывает В1: ( 6,171) → К = 177 выигрывает В1: П2 : ( 8,20) → К = 28 ( 7,21) → К = 28 ( 21,20) → К = 41 ( 7,60) → К = 67 ( 8,60) → К = 68 выигрывает В2 : ( 7,63) → К = 70 выигрывает В2: ( 7,180) → К = 187 выигрывает В2: ( 21,60) → К = 81 выигрывает В2: П2 : такая же партия Возможные партии описанной стратегии Вани: с первого хода Ваня возможно выиграет, а после второго хода Пети, Ваня выиграет гарантированно.

Слайд 27

Записать надо так: Задание 3 Возможное значение S = 19. После первого хода Пети возможны позиции: (7,19), (18,19), (6,20), (6,57). В позициях (18,19) и (6,57) Ваня может выиграть первым ходом, утроив количество камней во второй куче. Из позиций (7,19) и (6,20) Ваня может получить позицию (7,20). Эта позиция разобрана в п.2. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом. Кроме того, надо нарисовать дерево или представить ситуации в виде таблицы.

Слайд 28

Литература и источники: 1. Станкевич А. Игры на графах - https://ejudge.lksh.ru/archive/2014/08/A/games.pdf 2. Построение графической схемы алгоритма - https://megapredmet.ru/1-3657.html 3. Основные комбинаторные ситуации https://cyberpedia.su/16x3e61 4 . https://4ege.ru/informatika/57717-zadacha-26-ege-po-informatike.html 5. https://rosuchebnik.ru/material/razbor-zadaniya-26-ege-2019-po-informatike-i-ikt/