2. Задание № 1. Разработка программы оценки средней трудоёмкости произвольного алгоритма методом марковских цепей

Цель выполнения задания  овладеть практическими навыками автоматизации расчётов при вычислении оценки средней трудоемкости произвольных алгоритмов методом марковских цепей.

Постановка задачи

1. Разработать математическую модель описания произвольного алгоритма, представленного в виде граф-схемы с указанием трудоёмкостей (Θ_i i=1, 2,…, k) всех вершин и вероятностей переходов (P_ij) между ними.

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

3. Провести вычислительный эксперимент для оценки средней трудоёмкости алгоритма, разработанного при выполнении лабораторной работы №1. В качестве тестового примера следует использовать результаты, полученные при выполнении лабораторной работы № 2.

4. Получить зависимость Θ₁(n)  средней трудоёмкости алгоритма от размеров экземпляра решаемой задачи.

5. Представить результаты в следующем виде:

• граф-схема алгоритма;

• обоснование выбора структуры данных для представления граф-схемы алгоритма;

• результаты вычислительного эксперимента по оценке средней трудоёмкости алгоритма Θ₁(n) в зависимости от размера экземпляра задачи n (построить график зависимости Θ₁(n)).

3. Задание № 2. Исследование эффективности равносильных алгоритмов

Цель выполнения задания  овладеть практическими навыками сравнительного анализа эффективности равносильных алгоритмов.

Постановка задачи

С использованием программы оценки средней трудоёмкости алгоритма, разработанной при выполнении задания №1 настоящей лабораторной работы, необходимо:

1. Провести вычислительный эксперимент с целью получения зависимости Θ₂(n)  средней трудоёмкости алгоритма (равносильного Вашему алгоритму, который исследовался в задании № 1) от размеров экземпляра решаемой задачи. Алгоритм, равносильный разработанному Вами алгоритму, следует взять у студента одной из параллельных групп с тем же вариантом, что и у Вас.

2. Представить результаты экспериментальной оценка средних трудоёмкостей равносильных алгоритмов в зависимости от размера экземпляра задачи. Провести анализ полученных результатов и сделать выводы.

3. Получить асимптотические оценки эффективности и определить классы эффективности исследуемых алгоритмов. Сделать выводы.

4. Представить результаты в следующем виде:

• граф-схема алгоритма, равносильного алгоритму из задания №1;

• исходные данные для представления граф-схемы равносильного алгоритма для проведения вычислительного эксперимента;

• результаты вычислительного эксперимента по оценке средней трудоёмкости алгоритма Θ₂(n) в зависимости от размера экземпляра задачи n (построить график зависимости Θ₂(n));

• асимптотические оценки эффективности для двух исследуемых алгоритмов (по нотациям О, , Θ). Результат представить графически;

• выводы.