Делая генератор заданий по математике, столкнулся с забавным фактом - в школьной программе есть «упрощение выражений». Есть задачи на это упрощение. Есть даже какой-то невнятный текст о том, что такое упрощение выражений.
Но вот измерения «сложности» выражения или другого формального способа определить, что «вот эта вот форма выражения проще вот этой формы» – в учебниках нет. Итак, давайте разбираться.
Небольшое введение
Да, есть очевидные варианты, когда из двух форм выражения можно однозначно указать более простую. Например, в примере ниже правая форма явно проще левой.
Впрочем, такие очевидные формулы прекрасно укладываются в метрики, которые кратко описаны далее в статье. Но стоит задать себе вопрос – а откуда вообще возникла задача упрощать выражения?
Оказывается, что упрощение выражений преследует две, зачастую противоречащие друг другу цели. Во-первых, необходимо упростить расчеты сделав их легче.
В эпоху, предшествующую массовому распространению компьютеров, трудозатраты человека по сокращения формулы выше оказывались бы значительно ниже трудозатрат на решение «в лоб». Кто-нибудь еще помнит вычисления с использованием таблиц Брадиса?
Во-вторых, простота связана с легкостью восприятия. Две формы одного и того же выражения ниже имеют одинаковую вычислительную сложность. Но вот читать намного проще правый вариант.
Ну и в-третьих, есть варианты, которые вычислять проще в одной форме, а читать – в другой. Один из простейших примеров приведен ниже (я его потом буду активно использовать).
Очевидно, что вычислительно проще левая форма – там одно умножение, а также сложение и вычитание. В тоже время правая форма содержит два возведения в квадрат (что обычно равносильно умножения) и одно вычитание.
При этом читается легче именно правая часть – та, что вычислительно сложнее. Какая из этих двух форм более «сложная»? Следует ли упрощать слева направо? Или же наоборот?
Метрика вычислительной сложности
Рассмотрим еще раз последний пример. Путь у каждой операции будет своя сложность:
- a – сложность сложения
- s – сложность вычитания
- m – сложность умножения
- q – сложность возведения в квадрат
Сделаем достаточно очевидное предположение о том, что вычислительная сложность не может быть отрицательной. Тогда мы можем записать сложности вычисления обеих форм (знак «?» означает неизвестное отношение):
a + s + m ? 2q + s
Так как сложность вычитания присутствует с обеих сторон по одному раз, то на него выражение можно сократить. В результате мы получаем:
a + m ? 2q
Итого, отношение с тремя неизвестными. Как знает любой преподаватель математики (ну я надеюсь, что знает) – решить такое отношение невозможно. Нужно знать конкретные значения сложностей. Это приводит к тому, что сокращение выражений выливается не в изучение математики, а в изучение вкусов конкретного учителя. Что конечно же бардак.
Методика описательной сложности
С другой стороны, можно считать не вычислительную сложность, а описательную. Грубо говоря вопрос заключается в том - сколько и каких символов используется. Детально в метод разбора я вдаваться не буду – существует масса литературы, посвященной данному вопросу.
Тут, так же как в методе вычислительной сложности, важно определить коэффициенты для каждого символа или конструкции. И точно так же использование разных коэффициентов приведет к разным решениям о том, какая форма выражения «проще», а какая сложнее.
В качестве заключения
Пока я остановился на создании двух генераторах. Один под вычислительную метрику, второй под описательную. Оба генератора работают так, что создают пары форм, для которых одна форма всегда «проще» другой – вне зависимости от конкретных коэффициентов.
Но это очевидное ограничение на допустимые формы. А как вы решаете проблему создания заданий на упрощение выражений? Конечно, если вы преподаете математику школьникам – неважно, как школьный учитель или репетитор.