8. ЛАБОРАТОРНЫЕ ЗАДАНИЯ 8.1. Сортировка В заданиях этой части требуется: 1. Разработать одну или две (в зависимости от варианта) программу сортировки по одному (или двум соответственно) из известных ме- тодов и исследовать ее (их) характеристики. Ссылки ( типа п. 1.1) даны на пункты этого методического пособия. 2. Испытать программу на заданных файлах разной длины и степени упо- рядоченности. Имена файлов в наборе исходных данных сформированы из трех чисел. Первые два числа составляют имя файла : 4-знач- ное, задающее длину N файла в байтах и идущее за ним через символ подчеркивания "_" 3-значное, задающее процент I инверсий. Процент инверсий вычисляется от максимально возможного числа инвер- сий N*(N-1)/2 и принимает значения от 0 до 100. Расширение файла может принимать значения 1,2,3 и определяет случайный вариант файла с одними и теми же параметрами N и I. Например файл 0256_075.2 со- ответствует последовательности из N=256 чисел с количеством инверсий I=75%=24384 от максимального, вариант 2. Таким образом программу нужно испытать на примерно 80 различных файлах, что приводит к не- обходимости сводить времена работы программы в 5 таблиц следующего вида по числу различных значений I= 0%, 25%, 50%, 75%, 100%. Для значений I=0% и I=100% очевидно существует только по одному варианту файла данных. I=... ┌──────┬──────┬────┬─────┬─────┬────┬────┬────┬─────┐ │ N │ 128 │256 │ 512 │1024 │2048│4096│8192│16384│ ╞══════╪══════╪════╪═════╪═════╪════╪════╪════╪═════╡ │Вар.1 │ │ │ │ │ │ │ │ │ ├──────┼──────┼────┼─────┼─────┼────┼────┼────┼─────┤ │Вар.2 │ │ │ │ │ │ │ │ │ ├──────┼──────┼────┼─────┼─────┼────┼────┼────┼─────┤ │Вар.3 │ │ │ │ │ │ │ │ │ └──────┴──────┴────┴─────┴─────┴────┴────┴────┴─────┘ Максимальное значение N может быть меньше 16384. Оно выбирается исходя из наличия машинного времени для счета. Число вариантов про- счетов также может быть уменьшено по согласованию с преподавателем. Для измерения малых временных интервалов при небольших значениях N можно зациклить просчет, вводя количество повторений в диалоге. 3. По полученным числовым данным строятся аппроксимирующие графики зависимостей. Эти же данные являются исходными и для вычисления ана- литических зависимостей времени от длины в форме, приведенной в опи- сании каждого алгоритма. Неизвестные коэффициенты находятся как ре- шение системы уравнений, составленной по критерию наименьших квад- ратов. 4. Сделать выводы. Если заданы несколько алгоритмов, то сравнить их и определить предпочтительные области применения. В отчет включить: - задание; - описание алгоритма; - текст програмы с комментариями; - таблицы полученных зависимостей; - описание решения задачи аппроксимации по критерию наименьших квад- ратов; - графики найденных аналитических зависимостей, для каждой из 5 таб- лиц результатов с нанесенными точками экспериментальных данных. - выводы. 8.2. Поиск Исходные файлы содержат данные для различных значений нескольких параметров. Эти значения определяют имена файлов. 1.Первый символ имени файла - буква y или n - задает последователь- ность запросов на удачный или неудачный поиск. То есть файлы с y со- держат только запросы, которые есть среди значений ключей K[1] ... K[N], а файлы с n содержат только запросы, которых нет среди значе- ний ключей. 2. Число ключей в файле поиска: 64, 128, 256, 512, 1024, 2048, 4096, которое следует за буквой n или y. 3. Число 0 или 1 - параметр Х в формуле распределения вероятностей запросов: P[i]=c/i**Х. Здесь c - нормирующая константа. При Х=0 мы имеем равномерное распределение, при Х=1 - т.н. за- кон Зипфа, при котором вероятности P[1] ... P[N] убывают обратно пропорционально индексу. Это значение определяется последней бук- вой имени файла: е или z. e соответствует Х=0 (равномерное), z соответствует Х=1 (по закону Зипфа). 4.i=1,2,3 - номер варианта при одних и тех же значениях N и Х. Для каждой пары значений {N,Х} нужно просчитывать три варианта данных, поскольку и величины ключей, и запросы на поиск задаются как случай- ные последовательности. Номер варианта задан в расширении файлов. Пример имени файла: y0256e.2 Это файл запросов на удачный поиск (первая буква - y), число ключей, среди которых должен проводиться поиск, равно 256 (0256 в имени), вероятности появления ключей в запросах на поиск равны (последняя буква имени e), вариант данных 2 (расширение). Любой файл с данными представляет собой текстовый файл, который на- чинается со значения N, затем следует N чисел - список значений клю- чей K[i] в порядке возрастания индекса i, затем следует 1500 чисел - сами запросы на поиск. Значение 1500 постоянно для всех файлов ис- ходных данных. Перечисление всех вариантов файлов данных в исследуемых програм- мах можно делать автоматически, так как имена образуются по извест- ным правилам. Рекомендуется величину N все же задавать вручную в ди- алоге, так как время расчета может оказаться неожиданно большим. Та- ким образом, один запуск разработанной программы соответствует пере- числению значений {e,z},{1,2,3},{y,n} в имени файла. Максимальное значение N может быть меньше 16384. Оно выбирается исходя из наличия машинного времени для счета. Число вариантов про- счетов также может быть уменьшено по согласованию с преподавателем. Для измерения малых временных интервалов при небольших значениях N можно зациклить просчет, вводя количество повторений в диалоге. Для каждого варианта выполнить и включить в отчет следующие пункты задания. а. Разработать программы по двум алгоритмам поиска, указанным в варианте задания. Если алгоритм требует специальной структуры дан ных, (например, упорядоченного файла или дерева поиска), то первым этапом разрабатываемого алгоритма и программы будет построение нуж ной структуры данных. Время построения структуры данных не нужно включать в исследуемое время поиска, если это специально не огово рено в задании. б. Сделать просчеты каждой программы на всех необходимых вариан- тах данных удачного и неудачного поиска. Результаты просчетов занес- ти в таблицы следующего вида: Удачный(неудачный) поиск. Равномерное (Зипфа) распределение. ┌──────┬──────┬────┬─────┬─────┬────┬────┬────┬─────┐ │ N │ 128 │256 │ 512 │1024 │2048│4096│8192│16384│ ╞══════╪══════╪════╪═════╪═════╪════╪════╪════╪═════╡ │Вар.1 │ │ │ │ │ │ │ │ │ ├──────┼──────┼────┼─────┼─────┼────┼────┼────┼─────┤ │Вар.2 │ │ │ │ │ │ │ │ │ ├──────┼──────┼────┼─────┼─────┼────┼────┼────┼─────┤ │Вар.3 │ │ │ │ │ │ │ │ │ └──────┴──────┴────┴─────┴─────┴────┴────┴────┴─────┘ в. Построить графики зависимостей времени от N для тех режимов и программ, для которых выполнялись просчеты в предыдущем пункте. г. Определить параметры теоретических зависимостей времени от N для различных алгоритмов по критерию наименьших квадратов. Для этого составить и решить системы нормальных уравнений. д. Сделать выводы об областях применения заданных алгоритмов.