Article describes problems of designing automated teaching system for “Computational complexity of algorithms” course of study. This system should provide its students with means to familiarize themselves with complex mathematical apparatus and improve their mathematical thinking in respective area. Then article introduces the technique of algorithms symbol scroll table that allows estimating lower and upper bounds of computational complexity. Further, we introduce a set of theorems that facilitate analysis in cases when integer rounding of algorithm’s parameters is involved and when analyzing complexity of a sum. At the end, article introduces a normal system of symbol transformations that both allows one to perform any symbol transformations and simplifies automated validation of such transformations.
Automated learning; algorithm complexity analysis; estimating algorithms’ computational complexity; algorithm’s symbol scroll table; theorems on analysis of computational complexity; normal system of symbol transformations. Исследование подходов к построению автоматизированной обучающей системы алгоритма, вычислительнои сложности и асимптотическим оценкам трудоёмкости. Основная цель этих секции – развитие и тренировка памяти обучаемого с использованием навыков запоминания. Контроль этих секции, чаще всего, производится с помощью тестирования.
Однако, в программу курса также входит обучение неформальному использованию математического аппарата, и в этом месте возникают дополнительные трудности. К ним относятся технические трудности, связанные с вводом формул и их преобразованием, и трудности, связанные с недостаточным уровнем логического мышления учащегося, которыи должен достигнуть цели, конструируя последовательность ведущих к неи преобразовании. Таким образом, определяется вторая категория секции, связанных с математическими методами оценки сложности алгоритма и направленных на развитие логико-математического мышления.
Выделяются следующие черты, отличающие вторую категорию секции от первои. Вопервых, контроль материала секции второи категории не может быть основан только на тестировании, потому что необходимо проверять умение учащегося использовать различные математические приёмы. Во-вторых, при изучении материала требуется научить обучаемого связывать отдельные приёмы в целенаправленныи процесс путём конструирования последовательности изученных приёмов. В-третьих, нужно проконтролировать умение связывать несколько процессов при решении итоговои задачи по оценке вычислительнои сложности алгоритма. Одним из инструментов, используемых в контроле материала секции второи категории, является алгоритм проверки символьных преобразовании.
Материал и контроль взаимодеиствуют с помощью третьего компонента системы, ответственного за определение объёма материала за один сеанс, набор задании и их количество, а также другие параметры системы. Именно этот компонент придаёт системе гибкость и отличает АОС от приложения, которое умеет только выдавать текст и набор тестов по нему. Далее следует описание предлагаемого сценария взаимодеиствия системы и пользователя.
При входе в систему пользователь видит список секции курса, которые делятся на доступные и недоступные в соответствии с планом прохождения курса. Каждая секция должна быть проидена одна за другои по порядку (принцип линеиного обучения). При входе в секцию студенту предоставляется для изучения её материал. После изучения материала он переходит к контролю полученных знании, для прохождения которого он должен выполнить определённое в секции начальное количество задании (тестов, упражнении, задач). На каждыи вопрос теста предлагается несколько вариантов ответов (обычно 6), случаино выбранных из заранее определённого для каждого задания множества ответов. Среди предлагаемых ответов может быть несколько правильных, или все правильные, или ни одного правильного. Студент должен отметить все правильные ответы. Но если, по его мнению, правильных ответов нет, то он должен выбрать именно такои ответ. Система считает задание выполненным, если студент отметил все правильные ответы и ни одного неправильного. В противном случае она выводит на экран или один из текстов: «Не все правильные ответы отмечены», «Некоторые из отмеченных ответов не верны», или их комбинацию и предоставляет фрагмент текста материала секции, связанныи с совершеннои ошибкои. После изучения этого фрагмента или повторного изучения всего материала секции студент имеет возможность повторно ответить на вопрос задания. Если же он опять не выполнит задание, то оно будет заменено на два дополнительных задания. Таким образом, число задании для прохождения секции может расти. Сеанс работы со студентом будет прекращён при достижении некоторого предельного количества задании секции, и он сможет вернуться к обучению только после определённого перерыва. Если студент добивается прерывания сеанса несколько раз подряд, то его учётная запись в системе временно блокируется, а сам он вызывается к преподавателю. В случае, когда сначала студент заработал много дополнительных задании, а затем начал отвечать безошибочно, число контрольных задании начинает снижаться по некоторои прогрессии. Такои подход заставляет студента внимательно и вдумчиво относиться к материалу секции. Таким образом, организуется не только контроль знании секции, но и обучение. Только после выполнения всех задании студент сможет переити к изучению материала следующеи секции.
Однако, существуют секции, материал которых опирается на предыдущие секции и не может быть освоен без безусловного владения материалом этих предыдущих секции. В таких секциях проводится дополнительныи контроль знании предыдущих секции. При этом количество начальных задании для повторения секции снижается до одного. Вычислительная сложность алгоритмов и методика получения оценок сложности Переидём к описанию предметнои области, поскольку материал секции тесно связан с нею. Сначала напомним определение вычислительнои сложности алгоритма. Под вычислительнои сложностью алгоритма чаще всего понимают время (число шагов), требующееся для выполнения алгоритма в зависимости от некоторых входных параметров. И хотя в некоторых случаях интерес представляет не только рост времени с ростом параметров, но и рост памяти, используемои для работы алгоритма, мы будем использовать термин сложность алгоритма для обозначения его временнои сложности.
Для оценки быстроты роста числа шагов ( ), где − выделенныи параметр данных, используют -нотацию: ( ) = ( ( )), означающую оценку сверху быстроты роста ( ) скоростью изменения ( ), т. е.
∃ > 0, , ∀ ≥ : ( ) ≤ ⋅ ( ), а также используют Ω-нотацию: ( ) = Ω( ( )), означающую оценку снизу быстроты роста ( ) скоростью изменения ( ), т. е. } Составим таблицу символьнои прокрутки, включив в неё столбец с номером выполнения цикла, столбец со значением параметра цикла и столбец с условием выполнения цикла. При этом в столбце обозначает номер последнего выполнения цикла.
Анализ последнего выполнения цикла даёт неравенство ( / ) > 2, из которого следует log > 2 , откуда получаем неравенство < log log + 1. Из условия выхода из цикла ( / ) ≤ 2 следует неравенство ≥ log log , и так как определяет временную сложность алгоритма, то Таблица 1. Символьная прокрутка алгоритма 1 } while (z /= 2 > 1); } Составим таблицу символьнои прокрутки, включив в неё столбец ц с номерами циклов 1 и 2, столбцы , с номерами выполнения каждого цикла, столбцы , со значением этих переменных и столбец с условием выполнения цикла. При этом в столбце обозначает номер последнего выполнения цикла 1 (внешнего), а в столбце – номер последнего выполнения цикла 2 (внутреннего). В таблице мы будем записывать только изменение значении объектов каждого столбца.
Анализ цикла 1 такои же, как и в предыдущем примере 1, и приводит к оценкам снизу и сверху для количества выполнения этого цикла log log ≤ < log log + 1, из которого следует = log log . Это дает следующую временную сложность цикла 1: ( ) = (log log ). Таблица 2. Символьная прокрутка алгоритма 2 ц 1 2 1 2 … … условие цикла > 2 / > 2 Анализ условия последнего выполнения цикла 2: /2 > 1, учитывая значение приводит к неравенству 2 < = . Логарифмируя неравенство получаем − 1 < log , что дает < log + 1, а учитывая целочисленность получаем ≤ log . Анализ выхода из цикла 2: /2 ≤ 1 приводит, учитывая значение , к неравенству 2 ≥ = . Логарифмируя его, получаем ≥ log , что вместе с предыдущим неравенством даёт = log , и, следовательно, временная сложность цикла 2: ( ) = (log ). Выбирая максимальную оценку временнои сложности циклов окончательно получаем временную сложность алгоритма:
( ) = (log ).
Если циклы вложены и зависимы, то временная сложность алгоритма образуется из суммарного количества выполнения вложенного цикла по всем выполнениям внешнего. Рассмотрим пример 3 для этого случая.
void f3 (unsigned long n) { float x = n, y, z = n; while (x > 2) { x = sqrt(x); z = z * z; y = z; while (y /= 2 > 1); } Составим таблицу символьнои прокрутки (на следующеи странице), включив в неё столбец ц с номерами циклов 1 и 2, столбцы , с номерами выполнения каждого цикла, столбцы , , со значением этих переменных и столбец с условием выполнения цикла. При этом в столбце обозначает номер последнего выполнения цикла 1 (внешнего), а в столбце – номер последнего выполнения цикла 2 (внутреннего). В таблице мы будем записывать только изменение значении объектов каждого столбца.
Таблица 3. Символьная прокрутка алгоритма 3
1
2
…
(
… ( ) + 1 … 1 2 … ( ) 1 2 …
/ ( / ) условие цикла
> 2 /2 > 1 /2 > 1
… /2 ( ) > 1 /2 ( ) … ( / )
… ( / ) Подставляя обе оценки, получим log < ∑ ( ) < 2 log , откуда следует временная сложность алгоритма ( ) = (log ).
Заметим, что во всех примерах условия выхода из циклов задаётся неравенством, включающим параметр алгоритма и параметр номера последнего выполнения цикла. В общем случае условие выхода из цикла может быть сложнои булевои функциеи. Однако, любую булеву функцию можно преобразовать к дизъюнктивнои нормальнои форме (ДНФ), а затем исследовать для каждои элементарнои конъюнкции ДНФ все входящие в неё неравенства и равенства, из которых оценить снизу выражение значения номера последнего выполнения цикла, при котором все входящие в элементарную конъюнкцию условия становятся истинными. Взяв минимальную из оценок по всем элементарным конъюнкциям ДНФ, получим оценку снизу на значение номера последнего выполнения цикла. Аналогичным образом можно получить оценку сверху этого параметра из ДНФ последнего выполнения цикла. Рассмотрим пример алгоритма 4: void f4(unsigned long n) { float x, y; x = y = n; while (x > 1 || y > 2048) { x = x / 2; y = y - 128; } Составим таблицу символьнои прокрутки, включив в неё по одному столбцу для каждои элементарнои конъюнкции из записи условия цикла в ДНФ.
Таблица 4. Символьная прокрутка алгоритма 4 } 1 2 … … 2 … 2 … 2 2 Условие 2 − 128 > 2048 − 128 ⋅ 2 > 2048
… − 128 ⋅ > 2048
… − 128 ⋅ > 2048
посл. вып. − 128 ⋅ ( + 1) ≯ 2048 выход log 17 ≤
Анализ количества выполнении цикла с условием 1 приводит к оценкам сверху и снизу − 1 ≤ < log , что может дать оценку Θ(log ). Анализ условия 2 дает иные оценки – − <
− 16, что может дать оценку Θ( ). Из этого следует, что алгоритм может иметь разные оценки в разных диапазонах параметра . Чтобы уточнить эти диапазоны, приравняем верхние и нижние оценки для условии: − 16 = log , − 17 = log − 1; Уравнения получились эквивалентными, поэтому дальше рассматриваем только одно из них. Его корнями являются числа = 3558 и ≅ 0.00001.
Если внимательно взглянуть на условие цикла, то можно заметить, что цикл не выполнится ни разу при значениях параметра от 0 до 2048 включительно, поэтому второи корень нас не интересует. При значениях параметра от 2048 до 3558 включительно оценка будет линеинои, а при значениях параметра от 3559 и выше оценка будет логарифмическои. Таким образом, сложность алгоритма Θ(log ). Анализ условий циклов и его упрощение в некоторых случаях
Общим для всех рассмотренных примеров условии (выполнения цикла или выхода из цикла) является отношение, которое может быть приведено к виду:
f (p, n) <знак операции отношения> <выражение, не содержащее параметры p и n>, где n – натуральныи параметр алгоритма, а p − параметр номера выполнения цикла. В простых случаях функции f (p, n) сравнительно просто получить -нотацию роста количества выполнении цикла через рост n. Но в случае сложного вида этои функции достаточно получить скорость изменения функции f (p, n) при росте ее параметров в виде -нотации для более простои функции g (p, n), позволяющеи провести дальнеишии анализ отношения:
f (p, n) = ( g (p, n) ), означающую ∃ > 0, > 0, , ∀ > 0, ≥ : · ( , ) ≤ ( , ) ≤ · ( , ). Так, если алгоритм целочисленныи (параметры принимают только целые значения за счёт преобразования к целому), то анализ получаемых выражении может быть осложнён. Суммирование последовательностеи, отличающихся от арифметическои или геометрическои последовательностеи, также усложнит анализ. Следующие теоремы позволяют получить Θнотацию для многократных операции целых частеи линеиных выражении от параметра и Θнотацию через интегралы для целочисленных сумм.
Пусть ( · + ) = · + линеиная форма с натуральным параметром алгоритма и положительным . Обозначим через ( · + ) функцию ( · + ) = · ( · … ( · + ) + ⋯ + ) + , полученную -кратным применением формы , а через ([ · + ]) = [ · [ · … ⋅ [ · + ] + ⋯ + ] + ], где квадратные скобки означают целую часть выражения, функцию полученную кратным применением формы к целои части значения линеинои формы. В том случае, когда такая функция связана с количеством шагов цикла, нас интересует оценка скорости её изменения. Однако, при > 1 указанная функция возрастает с ростом и нас интересует Θ-нотация этого возрастания, а при < 1 она убывает с ростом и нас интересует Θ-нотация скорости её убывания. Следующая теорема позволяет при получении -нотации снять операцию взятия целои части.
Теорема 1. Пусть , вещественные коэффициенты линейной формы · + с > 0, ≠ 1 и натуральным . Тогда ([ · + ]) = ( ( · + )) = ( ). В качестве примера использования теоремы 1 приведём анализ алгоритма следующеи процедуры A: procedure A (unsigned long N) {
for (unsigned long k = N; k > 1; k = k/2); } Цикл будет выполняться раз и при последнем выполнении цикла переменная k примет значение получаем 1 ≤ ⋅ < 2, что при логарифмировании дает оценку log − 1 < ≤ log , а, следовательно, временная сложность процедуры оценивается как (log ).
Следующая теорема 2 устанавливает оценку вычислительнои сложности конечнои суммы через -нотацию интеграла.
Теорема 2. Пусть для неотрицательной монотонно возрастающей функции ( ) ( ≥ 0) рост ее значении ограничен условием ( ) ≤ · ( − 1), где константа ≥ 1. Тогда справедлива следующая формула procedure B (unsigned long n) { unsigned long m = 0; for (unsigned long i = 1, j = 2; i < n; i++, j <<= 1)
m += i * j; while (m--); В качестве примера использования теоремы 2 приведём анализ алгоритма следующеи процедуры B:
( ) неограниченной сверху функцией. Тогда справедлива следующая формула
}
Временная сложность первого цикла оценивается как Θ (n), а временную сложность второго цикла
определяет суммарное время выполнения второго цикла (∑ ⋅ 2 ) = ∫ ⋅ 2 = (
Условие теоремы 2 является существенным, так как при его нарушении интеграл не является элементарнои функциеи. Однако и в этом случае удаётся получить оценку сложности суммы как -нотацию верхнего предела суммирования, что утверждает следующая теорема 3.
Теорема 3. Пусть для положительной монотонно возрастающей функции ( ), ( ≥ 0), функция ( ), определённая отношением ( ) = ( ), ( ≥ 1), является монотонно возрастающей ( ) = ( ) , (∀ > > 0).
В качестве примера использования теоремы 3 приведём анализ алгоритма следующеи процедуры C: procedure C (unsigned long n) { unsigned long k = 0, m = 1; for (int i = 1; i <= n; i++) { m *= i; k += m; while (k--); } } Временная сложность первого цикла оценивается как ( ), а временную сложность второго ! цикла определяет суммарное количество его выполнении = ∑ !. Так как ( ) = ( )! = и ( ) > 2 при > = 2, то по теореме 3 получаем (∑ !) = ( !). Используя формулу Стирлинга, получаем, что временная сложность процедуры C оценивается как ( ). Нормальная система символьных преобразований
Приведённые теоремы позволяют ускорить анализ сложности алгоритмов определённого класса. Но, так как это возможно не во всех случаях, то для анализа приходится выполнять преобразования символьных выражении, а также равенств и неравенств с такими выражениями. Поэтому появляется проблема контроля правильности проведения преобразовании студентом. Подход с использованием сложных систем преобразования символьных выражении, например, Mathcad, является неверным, так как они не помогают научить студента выполнять эти преобразования. Воспользуемся следующим подходом: сначала выделим те части анализа, которые требуют таких преобразовании, а затем выделим некоторую ограниченную группу допустимых преобразовании, при помощи которых может быть выполнено любое преобразование, необходимое для анализа сложности алгоритма. Назовём эту группу нормальными преобразованиями.
Случаями использования символьных преобразовании являются следующие: символьная прокрутка алгоритма с преобразованием выражении, определяющих изменение данных алгоритма на этапе анализа значения переменных в таблице; конструирование неравенств для параметра отдельного цикла с помощью таблицы символьнои прокрутки. Эти неравенства и определяют вычислительную сложность этого цикла; символьное преобразование равенств и неравенств как для переменных, так и для количества итерации циклов; проведение оценки итоговои сложности алгоритма по сложности отдельных циклов или по суммарным оценкам изменения параметров сложности алгоритма.
В качестве первого допустимого преобразования возьмём изменение порядка двух рядом стоящих аддитивных членов или множителеи. Все остальные допустимые преобразования не будут изменять порядок преобразуемых членов. Контроль таких преобразовании упрощается, но через них все равно можно выразить любое необходимое преобразование.
Перечислим допустимые шаги символьного преобразования формулы равенства – систему нормальных преобразовании равенств: перестановка членов в формуле – замена местами двух членов только в одном месте формулы, где такая перестановка допустима; перестановка членов формулы из однои части равенства в другую со сменои знака; арифметические преобразования: сокращение только одного общего множителя; арифметические преобразования: вынесение только одного общего множителя; арифметические преобразования: разложение на множители, причём факторизация происходит атомарно (выносится только один из множителеи); арифметические преобразования: использование основных тождеств для функции/операции (множество функции, заранее определённых в интерфеисе системы); символьное раскрытие скобок – только в одном месте формулы может быть раскрыта одна пара скобок; символьное группирование – однократное заключение в скобки некоторои части формулы (вся часть находится в одном месте формулы) с вынесением за скобки общего члена в скобках; символьное разложение на множители выражения, если оно может быть записано в виде произведения сомножителеи; символьное разложение на множители степенеи выражения, если она может быть записана в виде произведения сомножителеи; символьное разложение на множители произведения сумм в выражении, если оно может быть записано в виде произведения сомножителеи; порядок членов не должен изменяться однократное символьное перемножение степенеи выражения, которое объединяет члены, содержащие одинаковые степени общего подвыражения; однократное символьное перемножение произведения сумм в выражении с соблюдением порядка записи каждого из полученных слагаемых (деиствие похоже на символьное раскрытие скобок).
Аналогично строится система нормальных преобразовании для неравенств. Но при получении неравенств для преобразования к верхним и нижним оценкам сложности циклов вводится дополнительные нормальные преобразования: перемещение ведущего аддитивного члена (максимальная скорость роста) на первое место в однои из частеи неравенства; усиление оценки сверху отбрасыванием аддитивных частеи со знаком минус; усиление оценки снизу отбрасыванием аддитивных частеи со знаком плюс; оценивание в оценке сверху неведущего аддитивного члена со знаком плюс через ведущии член; оценивание в оценке снизу неведущего аддитивного члена со знаком минус через ведущии член.
Указанная система нормальных преобразовании требует введения дополнительных секции АОС для обучения этому материалу. Поэтому предлагается следующии порядок секции АОС: 1. Характеристики сложности алгоритма; 2. Определение временной сложности алгоритма; 3. Система нормальных преобразований равенств; 4. Таблица символьной прокрутки алгоритма; 5. Система нормальных преобразований неравенств; 6. Оценивание временной сложности алгоритма с простым циклом; 7. Оценивание временной сложности алгоритма с вложенным независимым циклом; 8. Оценивание временной сложности алгоритма с невложенными зависимыми циклами; 9. Оценивание временной сложности алгоритма с вложенными зависимыми циклами; 10. Оценивание временной сложности алгоритма с целочисленными преобразованиями выражений; 11. Оценивание временной сложности алгоритма с суммированием последовательностей количества выполнения цикла; 12. Итоговое задание.
При необходимости сложную по обучению секцию можно разбить на подсекции (например, секции с системои нормальных преобразовании). Описанныи подход обучения анализу сложности алгоритмов позволяет переити к построению методического обеспечения, выделяющего для каждои секции и подсекции материал обучения и контрольные тесты, упражнения, задачи, необходимые для взаимодеиствия учащегося с материалом в процессе обучения и контроля усвоения материала; к построению программного обеспечения, позволяющего через интерфеис выполнять все этапы обучения.
Выразим надежду, что описанныи подход к построению автоматизированнои обучающеи системы анализу вычислительнои сложности алгоритмов будет реализован и покажет эффективность в обучении этому предмету и развитию логико-математического мышления студентов.
References