Теоретическое введение
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

24.08.2017 Поздравляем учителей, преподавателей, учащихся и их родителей с началом нового учебного года! Пусть он окажется успешным и даст много полезных и нужных знаний.

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


Теоретическое введение: построение и анализ дерева игры


Найти репетитора

Теоретическое введение: построение и анализ дерева игры

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

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

Остановимся на контекстных определениях тактики и стратегии.

  • Контекстные

    • Тактика — алгоритм осуществления одного действия, учитывающий различные возможные начальные условия.

      Стратегия — методология последовательного выбора тактик для достижения поставленной цели.

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

      Тактика тоже имеет цель (как и любой алгоритм, ведь он обладает свойством конечности), но эта цель — промежуточная, достижение которой как минимум не препятствует достижению стратегической цели.

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

    • Тактика на дереве игры представляется всеми переходами между узлами двух соседних уровней (рёбрами графа, ходами), не противоречащими стратегии.

      Стратегия игры видна из дерева благодаря выделению всех удовлетворяющих ей тактик.

    • Дерево игры определяет понятие возможного хода игрока как совокупность всех переходов между узлами двух соседних уровней, конкретный же ход игрока — один переход, выбранный из всех возможных.

Решение задачи в общем случае производится по следующему плану.

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

2. Анализ дерева "снизу вверх", включающий:

2а: первоначальную постановку гипотезы о достижении цели игры одним из её участников;

2б: доказательство или опровержение гипотезы п. 2а путём выделения узлов дерева особыми условными обозначениями по определённым правилам;

2в: если гипотеза п. 2а опровергнута, то п. 2б выполняется для другого участника игры.

3. Запись ответа на основе выполненного в п. 2 анализа.

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

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

В задаче предлагается простая модель игры с двумя участниками, в которой верный первый ход выигрывающего "по определению" игрока при условии дальнейшего следования им беспроигрышной стратегии (проще говоря, — "не подставляться") определяет исход игры в его пользу; второй и последующие его ходы в игре фактически не имеют значения (важно только "не подставляться"). Поэтому соблюдение выигрышной стратегии означает лишь следующее: 1) осуществление верного первого хода выигрывающим "по определению" игроком, 2) несовершение никаким игроком хода, которым он проигрывает или после которого другой игрок выигрывает следующим ходом (при наличии к тому возможностей), и 3) осуществление выигрышного хода игроком в случае, если для такого хода есть возможность. Как видно, вопрос соблюдения выигрышной стратегии на определённом этапе игры ограничивается анализом двух ходов: предстоящего и всех вариантов следующего за ним со стороны соперника.

    • Если игрок на определённой стадии игры не может осуществить другой ход, кроме как означающий его проигрыш, то ошибка этого игрока будет считаться вынужденной.

В связи с этим договоримся об особенностях построения дерева игры для двух основных типов задачи.

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

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

    • Из сказанного выше напрашиваются важные выводы, касающиеся использования условных обозначений.

      Решение задачи заключается не только в построении дерева игры, но и в его "комментариях" с использованием условных обозначений. Каждый учащийся формирует условные обозначения самостоятельно. Для расшифровки условных обозначений необходимо записать легенду.

      Часть условных обозначений появляется на этапе построения дерева: они касаются выделения узлов дерева (результатов ходов), противоречащих условию задачи (выигрышной стратегии). Маркированные такими условными обозначениями узлы не требуют рассмотрения своих следствий (т. е. ходов, следующих из них). Применительно к разным участникам игры эти условные обозначения не отличаются.

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

    • Кроме того, использование условных обозначений гарантирует выполняющему задание, что эксперт ими воспользуется при проверке: эксперт не обязан (и не должен) додумывать за участника экзамена, что тот имел в виду и о чём он думал! Здесь будущим участникам ЕГЭ (кстати, по любому предмету) нужно напомнить, что черновики не рассматриваются в принципе.

В последнем Примечании был упомянут ещё один контекстный термин — производящая комбинация. Покажем, что имеется в виду под этим понятием, и что такое в нашем контексте комбинация вообще.

  • Контекстные

    • Комбинация — набор данных.

      Производящая комбинация — комбинация, из которой можно получить другую комбинацию или несколько таких комбинаций.

      Следственная комбинация — комбинация, полученная из производящей комбинации по некоторому правилу.

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

      Комбинацию можно толковать как пару. При построении дерева важно выяснить, является ли конкретная комбинация упорядоченной или неупорядоченной парой (см. соответствующие определения в §2 раздела "Дискретная математика"/"Элементы теории множеств").

Укажем ещё на один важный вопрос, возникающий при построении дерева игры, о чём сделан "намёк" в последнем Примечании: отличаются ли друг от друга две комбинации, данные которых переставлены местами? Ответить на этот вопрос помогут два нижеследующих правила.

Если с данными, составляющими производящую комбинацию, можно осуществить одинаковые действия, то все её следственные комбинации являются неупорядоченными парами (хотя это утверждение ещё зависит от условия окончания игры, см. Пример 1 в §2 раздела "Дискретная математика"/"Элементы теории множеств").

Если с разными данными, составляющими производящую комбинацию, выполняются отличающиеся действия, то все её следственные комбинации являются упорядоченными парами (см. Пример 2 в §2 раздела "Дискретная математика"/"Элементы теории множеств").

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

  • Контекстные

    • Локальный проигрыш — факт наличия узла дерева (производящей комбинации), все подчинённые (следственные) узлы которого (следственные комбинации) удовлетворяют условию проигрыша.

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

    • Локальные и, тем более, тактический проигрыши могут рассматриваться в качестве основания для выдвижения гипотезы о выигрывающем игроке. Отметим, что из дерева можно увидеть лишь один тактический проигрыш, на нём, собственно, построение дерева и заканчивается.

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

Когда дерево игры построено, выполняется поиск решения для определения выигрывающего игрока и его выигрышной стратегии. Первое, что нужно сделать, согласно Плану решения задачи, — выдвинуть гипотезу о выигрывающем игроке. В первую очередь имеет смысл считать выигравшим НЕ того игрока, для которого имеется ситуация тактического проигрыша, видимая из дерева, но, соответственно, его соперника.

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

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

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

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

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

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

Как только гипотеза о выигрывающем игроке доказана, становится возможной запись ответа (п. 3 Плана).

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



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика