Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Буянова И.В. 1 Замулин И.С. 1

---

1 ФГБОУ ВО «Хакасский государственный университет им. Н.Ф. Катанова»

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

Статья в формате PDF

450 KB

«О» большое

анализ алгоритмов

приближение с помощью кривых

вычислительная сложность

практикум по программированию

1. Буянова И.В. Требования к системе онлайн-обучения студентов программированию и обзор существующих решений // Инженерные технологии: традиции, инновации, векторы развития: сборник материалов VII Всероссийской научно-практической конференции с международным участием (Абакан, 10-12 ноября 2021 г.) / отв. ред. Д.Ю. Карандеев. Абакан: Издательство ФГБОУ ВО «Хакасский государственный университет им. Н.Ф. Катанова», 2021. С. 109-111.

2. Селиванова И.А., Блинов В.А. Построение и анализ алгоритмов обработки данных: учеб.-метод. пособие. Екатеринбург: Изд-во Урал. ун-та, 2015. 108 с.

3. Virtanen P., Gommers R., Oliphant T.E. et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nat. Methods. 2020. V. 17. Р. 261–272. DOI: 10.1038/s41592-019-0686-2.

4. Branch M.A., Coleman T.F., Li Y. A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems. SIAM Journal on Scientific Computing. 1999. V. 21(1). Р. 1–23. DOI: 10.1137/S1064827595289108.

5. Кормен Т.Х. Алгоритмы: вводный курс / Пер. с англ. М.: ООО «И.Д. Вильямс», 2014. 208 с.

К настоящему времени разработано множество электронных ресурсов [1], предназначенных для автоматизации проверки решений задач по программированию. В большинстве случаев они ориентированы на спортивное программирование, но также находят применение при обучении программированию в школах, колледжах и высших учебных заведениях. Зачастую такие ресурсы ограничиваются проверкой корректности решения и его способности выдать результат за заранее определённое время. Этого более чем достаточно для соревновательного программирования, но для облегчения работы преподавателя в ходе проведения практикумов по программированию для школьников и студентов мог бы оказаться полезным более подробный отчёт. Помимо других пунктов, характеризующих решение, такой отчёт должен включать информацию об эффективности алгоритма, предложенного обучающимся.

Чтобы судить об эффективности алгоритма, необходимо оценить его временную и пространственную сложность. Временная сложность определяется количеством элементарных операций, совершаемых алгоритмом для решения поставленной задачи. Пространственная сложность характеризуется объемом затраченной памяти. Для оценки обеих характеристик применятся нотация «О» большое [2, с. 12], ставшая популярной после того, как в 1976 году Дональд Кнут предложил её использование для анализа алгоритмов.

Таблица 1

Наиболее распространённые категории сложности алгоритмов по времени

Нотация «О» большое описывает сложность алгоритма в виде функции от объёма входных данных. Поскольку эта функция должна давать примерную оценку наихудшего возможного времени выполнения алгоритма, для неё берут только самый высокий порядок переменной и не берут константные коэффициенты. Например, если требуется выполнить поиск элемента в отсортированном массиве, то наихудшее время выполнения алгоритма бинарного поиска будет оцениваться как , где n – количество элементов в массиве.

Существует несколько наиболее распространённых категорий сложности алгоритмов по времени, каждая из которых характеризуется собственной О-нотацией. В учебных задачах чаще всего встречаются категории, приведённые в таблице 1.

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

Материалы и методы исследования

Программный код решений задач зачастую содержит блоки, ответственные за чтение входных данных и вывод результатов, что может исказить результаты анализа решения. Так, если от студента требуется реализовать алгоритм бинарного поиска, сложность которого определяется логарифмической функцией, то основные временные затраты придутся на чтение входных данных – процесс, описываемый линейной функцией. Чтобы корректно оценить решение задачи как имеющее временную сложность О(log2n), необходимо оценивать только фрагмент кода, осуществляющего основную обработку данных.

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

Одним из возможных способов определения категории сложности алгоритма является его трассировка, в ходе которой в реальном времени собирается статистика о выполняемых им действиях. В отличие от других методов, таких как статический анализ программного кода, трассировка легко осуществима, особенно в интерпретируемых языках. Например, язык программирования Python предоставляет функцию sys.settrace, позволяющую задать обработчик, который будет вызываться при переходе к каждой следующей строке программы. Анализ этих вызовов позволяет оценить количество выполненных в программе итераций циклов, а следовательно, и собрать статистику о временной сложности выполняющегося алгоритма.

Результаты исследования и их обсуждение

График на рисунке 1 показывает пример расчёта сложности сортировки массива методом «пузырька» и статистику, полученную путём подсчёта количества итераций во время трассировки. Как видно из графика, прогнозируемая и полученная кривые имеют схожую форму, отличие объясняется тем, что сортировка выполнялась на массиве, заполненном случайными данными, в то время как оценочная формула О(n2) даёт прогноз по наихудшему случаю. Для метода «пузырька» наихудшим случаем является массив, отсортированный в порядке, обратном требуемому. При тестировании на таком массиве различие между кривыми было бы менее заметным. Однако, для цели оценки, полученного результата достаточно, поскольку требуется определить категорию алгоритма, а не получить точную кривую.

Рис. 1. Прогноз и результаты замера вычислительной сложности алгоритма сортировки массива методом «пузырька»

Аналогично рассмотренному алгоритму были выполнены замеры для примеров алгоритмов №№ 3-8 из таблицы 1. Полученные результаты вместе с использованными исходными кодами разработанного программного обеспечения доступны в виде дополнительных материалов на GitHub (https://github.com/irinaby/bigO).

Следующим этапом после тестирования алгоритмов и сбора статистики о количестве итераций является выбор наиболее подходящей категории для каждого из них. Поскольку категории задаются функциями от количества обрабатываемых элементов, задачу подбора категории можно решить, выбрав кривую, наиболее точно аппроксимирующую полученные результаты измерений. Для этого была выбрана функция scipy.optimize.curve_fit из пакета SciPy [3], использующая алгоритм TRF (Trust Region Reflective) [4]. Такой подход даёт оптимальные результаты аппроксимации при малом количестве выполненных измерений, что позволит минимизировать необходимое количество циклов тестирования решения и повысить производительность тестирующей системы образовательного ресурса. Функции, для которых осуществлялся подбор коэффициентов, приведены в таблице 2. После подстановки коэффициентов в функции было выполнено вычисление выдаваемого ими прогноза для каждого из тестов. Данные, полученные для всех рассмотренных алгоритмов, доступны в дополнительных материалах к данной статье.

Таблица 2

Функции, применённые для аппроксимации результатов подсчёта количества итераций

Таблица 3

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

Для примера рассмотрим решение задачи коммивояжёра [5, с. 176] методом полного перебора. Имеются результаты десяти тестов, начиная с одного города и далее до десяти, с шагом один. Количество итераций, определённое при трассировке, а также прогнозы двух функций, давших наилучшую аппроксимацию, приведены в таблице 3.

На рисунке 2 приведена визуализация данных из таблицы 3.

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

Ромбами обозначены результаты замера количества выполненных итераций. Штрихами и штрих-пунктиром показаны графики двух функций, давших наилучшие результаты приближения. Заметно, что кривая, полученная для функции факториала (штрихи), дала наилучший результат, в то время как показательная функция (штрих-пунктир) заметно отклоняется при малых значениях n.

Для определения наиболее подходящих функций был применён метод RMSE (1), в силу квадратичной природы которого даже небольшие ошибки в предсказаниях аппроксимирующих функций оказывают существенное влияние на получаемые оценки. Это особенно важно при работе с такими функциями, как показательная или факториал, поскольку они дают значительный прирост значения при небольшом увеличении аргумента.

, (1)

где Е – среднеквадратичная ошибка, N – количество проведённых тестов, pi – предсказанные значения, ti – результаты трассировки.

После выполнения серии тестов для алгоритмов №№ 3-8 из таблицы 1 была предпринята попытка подбора коэффициентов для каждой из функций в таблице 3. Результаты вычисления оценки RMSE для всех пар алгоритм-функция приведены в таблице 4. Ячейки пар, давших наилучшие совпадения, выделены тёмным фоном. Выполнить подбор коэффициентов для показательной функции удалось только для алгоритмов, работающих с относительно небольшим количеством входных данных (n <= 32).

Таблица 4

Оценка методом RMSE прогнозов аппроксимирующих функций

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

Заключение

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

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

Библиографическая ссылка