Scientific journal
International Journal of Experimental Education
ISSN 2618–7159
ИФ РИНЦ = 0,425

1 1
1

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

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

На примере задачи: «Моделирование одной антагонистической позиционной игры на взвешенном ориентированном графе» рассмотрим применение метапредметных связей в курсе информатики. Для решения данной задачи необходимы знания следующих дисциплин: алгоритмы на графах, теории игр, основ алгоритмизации и программирования, моделирования и формализации, основ объектно-ориентированного программирования.

Цель работы - проанализировать и смоделировать одну антагонистическую позиционную игру на взвешенном ориентированном графе.

Основной предмет нашего исследования — комбинаторная игра.

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

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

Работа проводилась в несколько этапов.

1. Постановказадачи.

Имеется взвешенный ориентированный прямоугольный граф-решетка размером stark1.wmf (где stark2.wmf – количество вершин графа по горизонтали, stark3.wmf – количество вершин графа по вертикали, stark4.wmf) с весами дуг stark5.wmf и stark6.wmf (где stark7.wmf) - веса соответственно вертикальных и горизонтальных ребер

stark8.wmf.

Из вершины stark9.wmf возможен переход либо в вершину stark10.wmf, либо в вершину stark11.wmf (где

stark12.wmf).

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

2. Определены правила хода для каждого игрока: игроки по очереди рисуют ребра маршрута из s в t, выигрывает тот, у которого сумма его ребер в маршруте больше.

3. Для моделирования игровой ситуации построим игровую математическую модель.

Взвешенный ориентированный прямоугольный граф-решетка размером stark13.wmf - это поле игры для двух игроков. В данном графе stark2.wmf вершин и stark13.wmf ребро по вертикали, stark14.wmf вершин и stark15.wmf ребро по горизонтали.

Пусть, для определенности, в начальной вершине s ход первого игрока. Тогда, принимая за stark16.wmf - количество пройденных ребер, с помощью формулы (stark17.wmf(где stark18.wmf – операция вычисления остатка от целочисленного деления числа stark16.wmf на 2) можно легко узнать, ход какого игрока в текущей вершине. Если при подстановке значения stark16.wmfполучаем 1, то ход первого игрока, если 2– ход второго игрока. В суммарном маршруте игроков stark19.wmf ребра. Поэтому в заключительной позиции ход игрока с номером stark20.wmfВ заключительной позиции выиграл первый игрок, если сумма весов его ребер в маршруте больше, чем у второго, и второй, если сумма весов его ребер в маршруте оказалась больше, чем у первого.Пусть stark21.wmf - сумма весов ребер в маршруте первого игрока, stark22.wmf - сумма весов ребер в маршруте второго игрока.

Игра антагонистическая, а значит, интересы игроков противоположны.

Первый игрок стремится максимизировать разность сумм весов ребер первого и второго игрока, то есть stark23.wmf. Второй игрок, наоборот, стремится минимизировать разность сумм весов ребер первого и второго игрока, то есть stark24.wmf

Напомним, что stark5.wmf и stark6.wmf (где stark7.wmf) - веса соответственно вертикальных и горизонтальных ребер stark25.wmfРассмотрим, как рассчитывается функция stark26.wmf для текущего положения игрока.

Пусть в позиции stark9.wmf ход первого игрока. Напомним, что из вершины stark9.wmf возможен переход либо в вершину stark10.wmf либо в вершинуstark11.wmf (где

stark27.wmf.

Пусть stark28.wmf - максимальное значение функции stark26.wmf. Тогда для первого игрока значение функции stark28.wmf в вершине stark9.wmf равно максимальному значению суммы функций stark28.wmf для второго игрока в вершинах stark10.wmf и stark11.wmf и соответствующих значений весов ребер stark5.wmf или stark6.wmf. Получаем формулу

stark29.wmf.

Пусть в позиции stark9.wmf ход второго игрока. Тогда для второго игрока значение функции stark28.wmf в вершине stark9.wmf равно минимальному значению разности функций stark28.wmf для второго игрока в вершинах stark10.wmf и stark11.wmf и соответствующих значений весов ребер stark5.wmf или stark6.wmf. Получаем формулу:

stark30.wmf

4. Разработка алгоритма решения задачи нахождения значений функцииstark28.wmf в виде блок-схемы (рис. 1). Алгоритм был разработан на основе идей теории Шпрага-Гранди и методов динамического программирования.

stark31.wmf

Рисунок 1. Блок-схема алгоритма

Чтобы заполнить матрицу выигрышных позиций, воспользуемся формулой (1):

stark32.wmf (1)

Получаем, что stark33.wmf, если переход в вершину stark9.wmf выигрышен для первого игрока, и stark34.wmf, если переход в вершину stark9.wmf выигрышен для второго игрока, stark35.wmf в ничейной ситуации.

5. Этот алгоритм был протестирован на нескольких примерах в системе Maple 15.

6. Реализован на языке С++ в среде C++ Builder 6 в консольном приложении и в форме игрового приложения с графическим интерфейсом пользователя.

Согласно проведенным исследованиям, данную задачу можно использовать в процессе изучения дисциплины информатика, используя знания дисциплин математического цикла.