МЕТОДИКА ПРОВЕРКИ ХОДA РЕШЕНИЯ МАТЕМАТИЧЕСКИХ ЗАДАЧ

 

Шаповалов А.И., Зинченко Ю.Е.

Донецкий национальный технический университет

Доклад на первой Всеукраинской научно-технической конференции "Информационные процессы и технологии" г. Севастополь, 2007 г.

 

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

 

1. Принцип пошаговой проверки хода решения задачи.

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

 

Рис.  1 - ход решения квадратного уравнения

 

С точки зрения программирования нам необходимо иметь 3 множества переменных и модуль проверки эквивалентности формул.  Когда в систему поступает формула она проверяет правильность записи формулы, есть ли эта формула у неё в базе данных и есть ли для её вычисления все необходимые исходные и промежуточные данные, т.е. установлены ли биты в соответствующих множествах. При соблюдении всех этих условий система получает промежуточные данные или результат, т.е. устанавливает бит в необходимом множестве.

Наибольшим интересом и  наибольшей трудностью в данной системе являются методы проверки эквивалентности формул.

 

2. Численный метод проверки эквивалентности выражений.

Метод заключается в следующем:

1.      Разделение формулы на два выражения (до знака равно и после).

2.      Построение таблицы значений переменных, значения в таблице генерируются случайным образом.

3.      Подстановка значений из таблицы в выражения.

4.      Вычисление значений выражений.

5.      Проверка равенства значения выражения 1 и выражения 2.

Для шагов 2-5 выполняется необходимое количество итераций. Данный метод всегда даст правильный результат, если выражения равны. Если выражения не равны, то есть вероятность того, что метод даст неверный результат. Эта вероятность тем меньше, чем больше количество итераций. Оценим такую вероятность для формулы b=a и максимальным значением переменной в таблице равным 22. Отметим, что в реализации метода используется значение 100. Очевидно, что для одной итерации эта вероятность равна 1/22 или 4,5%, что слишком много. При количестве итераций n вероятность будет составлять . Таким образом уже при 5 итерациях вероятность ошибки будет составлять 1,9*10^-7. Такой вероятностью мы вполне можем пренебречь. Недостатком данного метода является то, что он не позволяет определить степени переменных и, в связи с этим, не подходит для задач типа «упростить выражение».

 

3. Аналитический метод проверки эквивалентности выражений.

Метод основан на синтаксическом разборе выражений, определении количества вхождений переменных в выражения и степеней переменных. Метод допускает множество вариаций, самой простой из которых является построение таблиц количества вхождений переменных в выражение. Затем эти таблицы сравниваются и делается вывод о том, эквиваленты ли эти выражения. Отличительной особенностью и преимуществом данного метода является то, что он всегда выполняется за одну итерацию, и в связи с тем, что определяются степени переменных данный метод идеально подходит для задач типа «упростить выражение». Недостатком данного метода является высокая вероятность ошибки и сложность алгоритма хорошего синтаксического анализатора. Так практически невозможно построить синтаксический анализатор, который бы определил эквивалентность выражений sin²(x)+cos²(x) и 1. Поэтому применение данного метода самого по себе нецелесообразно.

 

4. Комплексный метод проверки эквивалентности выражений.

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

Практическая реализация предусматривает использование комплексного метода проверки, в котором аналитический метод применяется только при необходимости, а количество итераций численного метода равно 20. Время выполнения одной проверки  на Pentium 4 2.8 GHz составляет менее 1 мс.