, ̆мурович
Ярославский Государственный Университет им. , Ярославль
Аннотация
Обучение информатиков анализу сложности алгоритмов направлено не только на эффективный выбор при построении алгоритмов информационных технологий, но и дает путь в создании программ прогнозирования времени выполнения аолгоритмов. Но использование математического анализа требует индивидуальных методов обучения, и при этом создание компьютерной системы обучения могло бы помочь решить эту проблему. Доклад посвящен созданию математического и методического обеспечения для проектирования такой системы обучения.
Рассматривается методика обучения анализу сложности алгоритмов [1, 2]. В основе методики получения оценок лежит составление символьной таблицы прокрутки алгоритма и анализ циклов. В этой таблице каждой переменной алгоритма соответствует свой столбец, а также в ней есть некоторые специальные столбцы:
- для каждого цикла столбец с номером выполнения цикла и символьным обозначением этого номера при последнем выполнении цикла;
столбец Условие цикла, в котором записывается символьное условие выполнения цикла для последнего его выполнения с комментарием посл. вып. и условие выхода из цикла с комментарием выход.
В эти условия входит символьное значение параметра номера последнего выполнения цикла. Использование этих условий даёт 2 оценки количества выполнения цикла, определённого символом: снизу и сверху. Анализ этих оценок позволяет определить временную сложность цикла, если выражения условий не являются сложными. Чаще всего оценки снизу и сверху разнятся только константным множителем, что приводит к - нотации 
скорости роста времени выполнения цикла по параметру алгоритма 
.
Если циклы не являются вложенными и не являются зависимыми (параметр, определяемый первым циклом, не участвует во втором), то, определив временную сложность каждого из циклов, для временной сложности алгоритма берём наибольшую из них.
Если циклы вложены, но независимы (количество выполнения внутреннего цикла не зависит от номера выполнения внешнего цикла), то для определения общей сложности таких циклов их сложности перемножаются. Так, если внешний цикл 
имеет сложность 
, а внутренний цикл 
имеет сложность 
, то их общая сложность
Если циклы вложены и зависимы, то для вложенного цикла нужно определять суммарное количество его выполнения для всех выполнений внешнего цикла. Однако, если сложность вложенного цикла при любом выполнении внешнего цикла оценивается одной и той же функцией, то такую зависимость циклов назовём слабой зависимостью. При слабой зависимости циклов справедлива для сложности алгоритма та же формула перемножения сложностей циклов.
Условия последнего выполнения цикла и выхода из цикла обычно связаны с изменением параметров цикла или некоторого выражения, входящего в эти условия. Назовём его определяющим выражением. В тех случаях, когда изменения значения определяющего выражения монотонны важным для анализа количества выполнений цикла является получение оценок сверху и снизу на определяющее выражение. Часто такое изменение на каждой итерации цикла определяется рекуррентным образом: если начальное значение определяющего выражения 
где 
— параметр алгоритма, а изменение его значения в цикле даётся функцией итерации 
, то после первой итерации 
а после выполнения цикла 
раз значением будет 
.
Теорема 1. Пусть функция итерации задана формулой
где 
– определяющее выражение цикла на его - ой итерации, 
. Тогда для 
справедливы неравенства
В качестве примера использования теоремы 1 возьмём следующий пример:
int f (int m) {
int i, j, k = 0;
for (k = 0; m > 2∗k + 1; k = (m+k)/3.0, k++)
for (j = m; k < j; j−−) i++;
return i;
}
Обозначим 
Тогда оператор изменения параметра 
во внешнем цикле выглядит как 
.
Из условий последнего выполнения и выхода внешнего цикла после использования нижней и верхней оценок 
теоремы 1 получаются оценки
, откуда сложность внешнего цикла 
.
Внутренний цикл имеет сложность 
для любого выполнения внешнего цикла, то есть имеет место слабая зависимость циклов, а потому сложность алгоритма можно определить как произведение сложностей циклов 
, что даёт окончательный результат:
Теорема 2. Пусть для неотрицательной монотонно возрастающей функции 
рост её значений ограничен условием 
где константа 
. Тогда справедлива следующая формула:
Условие теоремы 2 является существенным, так как при его нарушении интеграл не является элементарной функцией. Однако, и в этом случае удаётся получить оценку сложности функции суммирования как 
нотацию для функции со значением аргумента, равным верхнему пределу суммирования, что утверждает следующая теорема 3.
Теорема 3. Пусть для положительной монотонно возрастающей функции 
функция 
определённая отношением
, является монотонно возраста-ющей неограниченной сверху функцией. Тогда справедлива следующая формула:
Описанные исследования по анализу сложности алгоритмов являются математической основой для построения обучающей системы Анализ сложности алгоритмов. В этой системе весь учебный материал разделяется на секции (небольшие порции), изучение которых контролируется тестами (начальные секции, где приводятся определения) и упражнениями (основные секции, связанные с построением и анализом символьных выражений). При этом решение проблемы контроля символьных преобразований достигается введением ограниченной системы нормальных преобразований, которая позволяет проконтролировать каждый шаг преобразований.
Литература
и др. Алгоритмы: построение и анализ // М. : «Вильямс», 2013. — 1328 с. , Юсуфов система для обучения анализу вычислительной сложности алгоритмов // Международный научный журнал «Современные информационные технологии и ИТ - образование». — 2016. — Т. 12, No 1. — С. 135–145 (ISBN 2411-1473)