Программа. С++, Qt.

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

Что нужно сделать:

1. Написать программу, решающую предложенную задачу в одном потоке. Работа выполняется в среде Qt (консоль).

2. В случае необходимости написать программу генерации исходных данных. Проверить корректность алгоритма генерации на однопоточном алгоритме.

3. Написать программу, решающую предложенную задачу в нескольких потоках (для создания потоков рекомендуется использовать класс QThread библиотеки Qt).

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

5. Написать программу, решающую предложенную задачу средствами Qt Concurrent.

6. Выполнить сравнительные тесты производительности написанных программ (для тестирования необходимо использовать многоядерную или многопроцессорную вычислительную машину).

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

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

7.2) три (два) алгоритма решения задачи последовательный и параллельные(ый);

7.3) форматы входных и выходных данных и спецификации программ;

7.4) результаты проведённых тестов в виде таблиц

Объём отчёта 15-20 страниц + листинги.

Срок: 20 мая (обсуждаем).