Данная статья является дополнением ранее опубликованного видео второго урока, поэтому перед прочтением рекомендуется его посмотреть.
Трассировка алгоритма - пошаговое выполнение действий, входящих в алгоритм.
Ниже рассмотрим пример анализа и трассировки алгоритма, но сначала приведём пример разных вариантов решения задачи поиска наименьшего из трёх чисел (в виде блок-схем).
Вариант 1.
Вариант 2.
Для выполнения трассировки на основе имеющихся блок-схем для каждого варианта построим управляющий граф.
Управляющий граф – граф G(V,A), где V(V1,… Vm) – множество вершин (действий/операторов), A(A1,… An) – множество дуг (управлений), соединяющих операторы-вершины.
На построенном графе выделим пути и ветви.
Путь – последовательность вершин и дуг управляющего графа, в которой любая дуга выходит из вершины Vi и приходит в вершину Vj. Количество вершин определяет мощность пути.
Ветвь – путь (V1, V2, … Vk), где V1 - либо первый блок, либо блок решений, Vk - либо блок решений, либо блок терминатор, а все остальные операторы – безусловные.
Так же, следует отметить, что существуют реализуемые и нереализуемые пути в программе, в нереализуемые пути в обычных условиях попасть нельзя.
Для первого варианта блок-схемы управляющий граф будет выглядеть следующим образом:
Возможными путями на приведенном графе являются:
{1, 2, 3, 4, 9} {1, 2, 3, 5, 9} {1, 2, 6, 7, 9} {1, 2, 6, 8, 9}
В качестве примеров ветвей на графе можно привести следующие:
{1, 2} {2, 3} {3, 4, 9}
Далее, пошагово выполним первый вариант алгоритма и построим пути на управляющем графе (пожалуйста, самостоятельно пошагово выполните данный алгоритм и запишите полученные пути) для каждого элемента из набора
{1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1} {3, 3, 3}
По результатам трассировки нужно отметить, что все полученные пути реализуемы.
Для второго варианта алгоритма управляющий граф будет иметь вид:
Возможными путями на приведенном графе являются:
{1, 2, 3, 4, 5, 7} {1, 2, 3, 5, 6, 7} {1, 2, 3, 4, 5, 6, 7}
По аналогии с трассировкой первого варианта алгоритма выполните трассировку второго варианта.
Итак, получив набор путей для первого и второго варианта можно определить в каком из вариантов содержится путь с наибольшим количеством вершин (наибольшей мощностью) и исходя из этого можно сделать вывод о количестве операций, которые необходимо выполнить алгоритму для достижения результата. Из первого урока мы помним, что сложность алгоритма, в том числе, определяется количеством шагов его выполнения (временная сложность) и количеством инструкций операторов (сложность описания), а значит чем больше мощность пути на управляющем графе, тем сложнее алгоритм. Таким образом мы можем сделать выбор менее сложного алгоритма (какой из приведённых алгоритмов обладает меньшей сложностью? Пожалуйста, напишите в комментарии).