              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
        для различных алгоритмов по критерию наименьших квадратов. Для этого
        составить и решить системы нормальных уравнений.
           д. Сделать выводы об областях применения заданных алгоритмов.
