- •Алгоритмы и структуры данных
- •Введение
- •1.1. Практикум по теме
- •1.2. Требования к отчёту
- •1.3. Контрольные вопросы
- •1.4. Варианты индивидуальных заданий к темам «Хеш-таблицы» и «Деревья двоичного поиска»
- •2. Деревья двоичного поиска
- •2.3. Контрольные вопросы
- •2.1. Практикум по теме
- •2.2. Требования к отчёту
- •3. Поддержка произвольной последовательности в структуре данных для множеств
- •3.1. Практикум по теме
- •3.2. Индивидуальные задания к теме «Последовательности»
- •3.3. Требования к отчёту
- •3.4. Контрольные вопросы
- •4. Работа с иерархией объектов: наследование и изоморфизм
- •4.1. Учебная программа «Библиотека фигур»
- •4.2. Практикум по теме
- •4.3. Варианты индивидуальных заданий к теме «Наследование и изоморфизм»
- •4.4. Требования к отчёту
- •4.5. Контрольные вопросы
- •5. Поддержка обработки исключительных ситуаций
- •5.1. Практикум по теме
- •5.2. Требования к отчёту
- •5.3. Контрольные вопросы
- •6. Использование стандартной библиотеки шаблонов
- •6.1. Практикум по теме
- •6.2. Требования к отчёту
- •6.3. Контрольные вопросы
- •7. Курсовая работа. Измерение временной сложности алгоритма
- •7.1. Пример программы для эксперимента
- •7.2. Обработка результатов эксперимента
- •7.3. Оформление результатов эксперимента
- •7.4. Выводы
- •Список литературы
- •197376, С.-Петербург, ул. Проф. Попова, 5
7.2. Обработка результатов эксперимента
По результатам эксперимента выполняется регрессионный анализ: подбор уравнения регрессии, наиболее соответствующего полученным данным. Для этого можно использовать программу RG32. Входом программы является текстовый файл с результатами измерений. Первая строка текста содержит общее количество опытов. Каждая из последующих строк содержит результат одного опыта: размер входа и время, разделённые хотя бы одним пробелом. Упорядочивать данные по размеру входа не обязательно. Можно выполнить по несколько опытов для некоторых или для всех размеров входа. Если общее количество опытов окажется меньше указанного в первой строке, будет сделано предупреждение об этом, и программа использует фактически имеющееся количество. Если данных окажется больше – лишние игнорируются. Программа откажется работать, если опытов менее 10.
Программа RG32 выдаст на экран значения коэффициентов регрессии для набора функций, начиная от константы (отсутствие pегpесии) и кончая полиномом четвёртой степени. Общий вид уравнения регрессии выводится программой в первой строке. Далее выводятся результаты подбора с поочерёдным подключением коэффициентов слева направо. Не используемые в уравнении коэффициенты выводятся нулями. Кроме коэффициентов, даётся значение выборочной дисперсии (и среднеквадратичного отклонения). Результат работы программы следует включить в отчёт в виде таблицы.
Одновременно с выводом на экран программа RG32 создаёт текстовый файл OUT.txt, пригодный для импорта в электронную таблицу EXCEL.
Для упрощения обработки результатов следует получить у преподавателя заготовку электронной таблицы EXAMPLE.xls. В эту таблицу импортируются файлы с результатами измерений и с коэффициентами уравнений регрессии — ввод и вывод программы RG32. Данные из файлов переносятся на отведенные для них места.
Вся необходимая обработка данных уже заложена в таблицу EXAMPLE. Рядом с колонками результатов эксперимента находятся расчёты значений уравнений регрессии, по которым уже построены графики, а правее места расположения коэффициентов регрессии находится расчёт отношений каждой выборочной дисперсии ко всем остальным. По значениям отношений дисперсий можно сразу указать наиболее подходящее уравнение регрессии, самый старший коэффициент которого определит временную сложность алгоритма. Наиболее подходящим будет то уравнение, при дальнейшем усложнении которого уменьшение выборочной дисперсии прекращается или перестаёт быть значимым.
Поскольку выборочные дисперсии являются случайными величинами. значения дисперсий можно считать различными только в том случае, если их отношение превосходит значение квантиля распределения Фишера (см. таблицу).
Входом в таблицу является количество степеней свободы выборки, равное количеству опытов минус количество оцениваемых коэффициентов регрессии. Во второй строке дано значение отношения выборочных дисперсий, которое можно считать значимым с ошибкой не более 5%, в третьей — не более 1%.
Если с учётом уровня значимости из всех полученных уравнений регрессии невозможно однозначно указать наиболее подходящее, следует попробовать увеличить количество опытов.
