Правила анализа программ

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

· Трудоемкость конструкции "Следование" есть сумма трудоемкостей блоков, следующих друг за другом: f=f1+f2+...+fn.

· Трудоемкость конструкции "Ветвление" определяется через вероятность перехода к каждой из инструкций, определяемой условием. При этом проверка условия также имеет определенную трудоемкость. Для вычисления трудоемкости худшего случая может быть выбран тот блок ветвления, который имеет большую трудоемкость, для лучшего случая – блок с меньшей трудоемкостью. fif=f1+f_then*p_then+f_else*(1-p_then)

· Трудоемкость конструкции "Цикл" зависит от вида цикла. Для цикла с параметрами будет справедливой формула: f_for=1+3n+nf, где n – количество повторений тела цикла, f – трудоемкость тела цикла.

Реализация цикла с предусловием и с постусловием не меняет методики оценки его трудоемкости. На каждом проходе выполняется оценка трудоемкости условия, изменения параметров (при наличии) и тела цикла. Общие рекомендации для оценки циклов с условиями затруднительны. Так как в значительной степени зависят от исходных данных.

В случае использования вложенных циклов их трудоемкости перемножаются.

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

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

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

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

Примеры:

Пример 1 Задача суммирования элементов квадратной матрицы

SumM (A, n; Sum)

Sum 0

For i 1 to n

For j 1 to n

Sum Sum + A[i,j]

end for

Return (Sum)

End

Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и следовательно является количественно-зависимым. Применение методики анализа конструкции «Цикл» дает:

F_A(n)=1+1+ n *(3+1+ n *(3+4))=7 n ²+4* n +2 = Q(n ²), заметим, что под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n ² значений.

Пример 2 Задача поиска максимума в массиве

MaxS (S,n; Max)

Max S[1]

For i 2 to n

if Max < S[i]

then Max S[i]

end for

return Max

End

Данный алгоритм является количественно-параметрическим, поэтому для фиксированной размерности исходных данных необходимо проводить анализ для худшего, лучшего и среднего случая.

А). Худший случай

Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна:

F_A^{^}(n)=1+1+1+ (n-1) (3+2+2)=7 n - 4 = Q(n).

Б) Лучший случай

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

F_A^Ú(n)=1+1+1+ (n-1) (3+2)=5 n - 2 = Q(n).

В) Средний случай

Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается к-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых к элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из к элементов расположен в определенной (последней) позиции равна 1/к. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как:

Величина Hn называется n-ым гармоническим числом. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из n элементов определяется величиной Hn (на бесконечности количества испытаний), тогда:

`F_A(n)=1 + (n-1) (3+2) + 2 (Ln(n) + g)=5 n +2 Ln(n) - 4 +2 g = Q(n).

Особенностью оценки ресурсной эффективности рекурсивных алгоритмов является необходимость учета дополнительных затрат памяти и механизма организации рекурсии. Поэтому трудоемкость рекурсивных реализаций алгоритмов связана с количеством операций, выполняемых при одном рекурсивном вызове, а также с количеством таких вызовов. Учитываются также затраты на возвращения значений и передачу управления в точку вызова. Для анализа трудоемкости механизма рекурсивного вызова-возврата будем учитывать следующие параметры: p – количество передаваемых фактических параметров, r – количество сохраняемых в стеке регистров, k – количество возвращаемых по адресной ссылке значений, l – количество локальных ячеек функции. Тогда функция трудоемкости на один вызов-возврат примет вид:

f=2(p+k+r+l+1), где дополнительная единица учитывает операции с адресом возврата.

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

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

В настоящее время исследования в области теории алгоритмов развиваются в следующих направлениях:

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

2. исследование механизмов вычисления (теория конечных автоматов как модели вычислительного механизма, растущие автоматы – самовоспроизводящиеся машины, машины с оракулом – развитие понятия алгоритма);

3. изучение понятия сложности алгоритма (разработка методов оценки сложности алгоритмов и вычисления).

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

· Цели и задачи теории алгоритмов

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

формализация понятия «алгоритм» и исследование формальных алгоритмических систем;

формальное доказательство алгоритмической неразрешимости ряда задач;

классификация задач, определение и исследование сложностных классов;

асимптотический анализ сложности алгоритмов;

исследование и анализ рекурсивных алгоритмов;

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

разработка критериев сравнительной оценки качества алгоритмов.

· Практическое применение результатов теории алгоритмов

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

Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос – является ли эта задача в принципе алгоритмически разрешимой – для алгоритмически неразрешимых задач возможно их сведение к задаче останова машины Тьюринга. В случае алгоритмической разрешимости задачи – следующий важный теоретический вопрос – это вопрос о принадлежности этой задачи к классу NP–полных задач, при утвердительном ответе на который, можно говорить о существенных временных затратах для получения точного решения для больших размерностей исходных данных.

Практический аспект: методы и методики теории алгоритмов (в основ-ном разделов асимптотического и практического анализа) позволяют осуществить:

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

получение временных оценок решения сложных задач;

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

разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.

Учебная практика по разработке и анализу алгоритмов

Алгоритмы внутренней сортировки.

Сортировки, не использующие сравнения

Сортировка подсчётом О(n)

Поразрядная сортировка О(n)

Сортировки, использующие сравнения

Сортировка выбором(SelectSort) О(n²)

Сортировка пузырьком(BubbleSort) О(n²)

Сортировка простыми вставками(InsertSort)О(n²)

Cортировка Шелла (ShellSort)О(n²)

Сортировка слиянием O(n * log₂ n) в среднем

Пирамидальная сортировка (n * log₂ n)

Быстрая сортировка (n * log₂ n) в среднем

Сравнение времени сортировок

Сравнить алгоритмы сортировки, испытав их на массивах, содержащих 500, 1000, 5000, 10000 и 15000 целых чисел, соответственно. Время выполнения измерить в тиках (1/60 доля секунды).

Применить к решению конкретных задач.

Списки. Решить задачу используя стек, очередь, двусвязный список.

Построение бинарного дерева поиска и сбалансированного дерева. Решение практических задач с использованием данных структур.

Алгоритмы на графах. Жадные алгоритмы. Задача минимального остова Алгоритм Прима. Алгоритм Краскала.

Поиск кратчайших путей. Свойства и применение. Алгоритм Дейкстры. Алгоритм Флойда. (Описание сложности алгоритмов).

Строковые алгоритмы. Префикс-функция, Z-функция и их использование в алгоритме Кнута — Морриса — Пратта.