Теоретико-отчетная часть




Программная часть

2. Реализовать указанные алгоритмы в виде компьютерной программы на одном из языков программирования высокого уровня (Pascal, Delphi, C, C++, C#, Java, Python). Рекомендуемый формат входных и выходных данных указан в задании (изменения возможны при согласовании с преподавателем). Проверок на корректность входных данных не требуется (считать, что все входные данные корректны). Все алгоритмы должны быть реализованы в одном проекте, но отдельные алгоритмы должны быть структурно выделены (в виде отдельных модулей, подпрограмм, классов и т.п.).

3. Дополнить программу автоматическим генератором тестов. Входные данные должны генерироваться с помощью генератора случайных чисел с учетом ограничений задачи. Также оставить возможность ввода входных данных вручную (с клавиатуры или из файла).

4. Протестировать и отладить программу.

Экспериментальная часть

5. Экспериментально определить предельные значения объема входных данных Vmax, при которых все алгоритмы работают за приемлемое время (не более 2–3 минут на один тест).

6. На интервале (0; Vmax ] выбрать несколько значений V 1, V 2, …, Vn. Для каждого значения Vi запустить серию тестов на автоматически сгенерированных входных данных объема Vi. В каждой серии тестов определять следующие характеристики:

a. для каждого алгоритма – среднее время работы (в мс);

b. для каждого приближенного алгоритма – процент тестов, в которых его решение совпало с точным решением;

c. для каждого приближенного алгоритма – среднее относительное отклонение приближенного решения от точного, то есть среднее значение выражения , где f – характеристика приближенного решения, f * – точного.

7. Для нескольких значений Vi вручную или автоматизировано составить такие входные данные, которые соответствуют «худшему случаю» (когда количество выполняемых операций должно быть максимальным), а также входные данные, которые соответствуют «лучшему случаю» (когда количество операций должно быть минимальным). Провести тесты с полученными данными, определив время работы алгоритма.

8. Экспериментально определить приблизительное время выполнения одной элементарной условной операции (ЭУО) на используемом компьютере.

Примечание. Данный шаг можно выполнить после выполнения шага 9, сравнивая теоретическое значение функции сложности (в количестве ЭУО) с экспериментальными данными (в мс). Если на шаге 9 определен только порядок роста функции сложности, то данный шаг можно совместить с подбором констант, выполняемым в шаге 9.

Математическая часть

9. Для каждого из реализованных алгоритмов построить функцию сложности (при необходимости – максимальную, минимальную и среднюю оценки сложности). В случае затруднения с нахождением точных функций необходимо определить порядок роста функции сложности, а затем, считая, что если , то , экспериментальным путём подобрать приближенное значение соответствующей константы C.

10. Для тех приближенных алгоритмов, которые имеют фиксированную погрешность — проверить, во всех ли проведенных тестах показатель 6.c не превышает её.

Теоретико-отчетная часть

11. Составить отчет, содержащий следующую информацию:

a. титульный лист с указанием имён и фамилий всех членов группы;

b. название и описание решаемой задачи;

c. в случае если формат входных данных отличается от рекомендованного – описание формата;

d. краткое описание фактически реализованных алгоритмов;

e. ссылка на созданную программу (исходный код программы прикладывается к отчету в электронном виде);

f. теоретические оценки сложности реализованных алгоритмов (результат выполнения пункта 9);

g. использованный язык программирования и среда разработки;

h. характеристики оборудования, использованного для тестирования (процессор, тактовая частота, объем памяти)

i. значение Vmax (пункт 5);

j. на основе значений, полученных в пунктах 6 и 7, а также оценок, полученных в пункте 9, построить графики зависимости времени работы программы от объема входных данных;

k. вывод о соответствии экспериментальных данных и теоретических оценок (на основе построенных графиков); в случае существенных отклонений или других аномальных результатов – возможные объяснения наблюдаемых эффектов;

l. на основе данных, полученных в пункте 6, построить таблицу: для каждой серии тестов указать количество тестов в серии, а также для каждого алгоритма указать значения характеристик 6.a. – 6.c;

m. результат проверки на не превышение фиксированной погрешности (пункт 10);

n. заключение: вывод о проделанной работе, вывод о применимости реализованных алгоритмов.

Презентационная часть

12. Составить презентацию по материалам отчета, подготовить выступление на 10–15 минут.

13. Выступить с презентацией на паре.

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

 

Варианты задач. (+распределение по группам)

1. Задача коммивояжера для евклидовых графов. (3 чел)

Дано: число вершин в графе (n) и сам граф в виде матрицы расстояний (все расстояния положительные).

Указание. Чтобы выполнить условие «евклидовости» (неравенство треугольника) можно генерировать не длины ребер графа, а координаты вершин на плоскости или в пространстве, а затем вычислить расстояние между всеми парами по формуле расстояния между точками.

Получить: длину найденного кратчайшего гамильтонова цикла, а также сам цикл в виде последовательности вершин.

Алгоритмы:

a. полный перебор (перебрать все (n -1)! гамильтоновых циклов);

b. «жадный» (известен, например, из курса дискретной математики)

c. приближенный алгоритм Кристофидеса (самый простой, рассмотренный на лекции, либо модифицированный)

2. Задача коммивояжера для произвольных графов. (3 чел)

Дано: число вершин в графе (n) и сам граф в виде матрицы расстояний (все расстояния положительные).

Получить: длину найденного кратчайшего гамильтонова цикла, а также сам цикл в виде последовательности вершин.

Алгоритмы:

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

b. «жадный» (известен, например, из курса дискретной математики)

c. МВГ

3. Задача о правильной раскраске графа в минимальное количество цветов. (3 чел)

Дано: число вершин в графе (n) и сам граф в виде матрицы смежности.

Получить: правильная раскраска графа с использованием минимального количества цветов (вывести количество использованных цветов, а также список пар «номер вершины – номер цвета»).

Алгоритмы:

a. полный перебор (для каждой вершины перебирать все возможные цвета либо перебирать все возможные n! перестановок вершин, к каждой применяя жадный алгоритм);

b. тривиальный «жадный» (известен, например, из курса дискретной математики);

c. «жадный» с оптимизацией (красить в первую очередь вершины с максимальной степенью).

4. Задача о вершинном покрытии минимальной мощности. (3 чел)

Дано: число вершин в графе (n) и сам граф в виде матрицы смежности.

Получить: количество вершин в найденном вершинном покрытии, а также сам список вершин.

Алгоритмы:

a. переборный (перебрать все 2n наборов вершин);

b. приближенный (рассмотрен на парах)

c. «жадный» (рассмотрен на парах)

5. Задача об оптимальной одномерной упаковке («об упаковке в контейнеры»). (3 чел)

Дано: число предметов (n), вместимость одного контейнера (M), а также n чисел – массы предметов (mi). Все числа положительные. Каждое mi£ M.

Получить: количество использованных контейнеров, а также распределение предметов по контейнерам (для каждого контейнера нужно перечислить номера предметов, сложенных в него).

Алгоритмы:

a. переборный (например, перебрать все возможные n! перестановок предметов, к каждой применяя алгоритм FF «первый подходящий»);

b. FFS (или любой другой приближенный с фиксированной погрешностью)

c. BF (или любой другой приближенный)

6. Задача «о рюкзаке». (3 чел)

Дано: в первой строке записано число предметов (n) и вместимость рюкзака (M), во второй записаны n чисел – массы предметов (mi), в третьей строке записаны n чисел – стоимости предметов (ci). Все числа положительные. Каждое mi £ M.

Получить: максимальную суммарную стоимость предметов, которые можно положить в рюкзак, а также список предметов в виде последовательности их номеров.

Алгоритмы:

a. рекурсивный полный перебор;

b. итерационный полный перебор (перебрать все возможные 2n масок);

c. «жадный» (предметы сортируются по ценности (ci / mi) и на каждом шаге выбирается самый ценный из оставшихся, помещающийся по массе).

7. Задача перемножения матриц. (2 чел)

Дано: в первой строке записана размерность матриц (n), далее в следующих n строках располагаются по n чисел – значения элементов 1й матрицы ai,j, далее еще n строк по n чисел – значения элементов 2й матрицы bi,j.

Получить: матрицу C = A×B.

Алгоритмы:

a. тривиальный (по определению);

b. оптимизированный рекурсивный (на консультации).

8. Поиск подстроки в строке. (2 чел)

Дано: в первой строке записана строка t – исходный текст, во второй строке записана строка s – искомый текст (шаблон). Длина s £ длины t.

Получить: первое вхождение шаблона s в текст t (первую позицию в строке t, начиная с которой там присутствует шаблон s), либо значение «–1», если шаблона s в тексте t нет.

Алгоритмы:

a. тривиальный (перебор всех позиций в тексте t);

b. алгоритм Рабина – Карпа.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-22 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: