Курсовая теория на тему Методы анализа и оценки алгоритмов

Содержание:

Введение……………………………………………………………………………………. 3

1 Алгоритмы и их свойства…………………………………………………………. 4

1.1 Цели и задачи теории алгоритмов………………………………………. 5

1.2 Формализация понятия алгоритма……………………………………… 7

1.3 Свойства алгоритма…………………………………………………………. 10

1.4 Принципы построения алгоритма……………………………………… 12

1.5 Способы и формы представления алгоритмов……………………. 13

2 Анализ сложности алгоритмов……………………………………………….. 17

2.1 Модель RAM (Random Access
Machine)…………………………….. 17

2.2 Подсчет операций. Классы входных данных……………………… 18

2.3 Асимптотические обозначения………………………………………….. 19

2.4 Нотация «тэта»………………………………………………………….. 20

2.5 Нотация «большое О»……………………………………………………… 21

2.6  — (омега)-нотация………………………………………………………….. 24

2.7 Сравнение сложности алгоритмов…………………………………….. 25

Заключение………………………………………………………………………………. 26

Список использованных источников………………………………………….. 26

Введение:

Заключение:

Фрагмент текста работы:

1 Алгоритмы и их свойства

Слово "алгоритм" происходит от имени ученого IX
век Муххамеда бен Аль-Хорезми ("аль-Хорезми" ->
"алгоритм"), который описал правила выполнения арифметических
действий в десятичной системе исчисления.

Первый алгоритм — предложенный Евклидом в III веке до н. э.
алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида).
К началу XX века слово "алгоритм" употреблялось в сочетании "алгоритм
Эвклида". Для описания пошагового решения других заданий использовалось
слово "метод".

Пример — алгоритм Аль-каши вычисления значения xn,
где n — положительное число. Этот метод был разработан в XV веке и широко
использовался на практике.

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

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

К основным заданиям теории алгоритмов относятся:

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

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

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

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

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

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

o разработка критериев сравнительной оценки
качества алгоритмов. Практическое применение результатов теории алгоритмов
имеет два аспекта:

есть нужная
информация, с помощью поисковых машин.

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

2. Распределение
ограниченных ресурсов в производстве и коммерции — решается методами линейного
программирования.

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

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

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

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

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

Пусть D — область (огромное количество) выходных данных
задания, R

же раз выдать один и тот же результат.

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

Компьютерная программа — запись алгоритма решения задачи в
виде последовательности команд или операторов языком, который понимает
компьютер. 1.3 Свойства алгоритма

Пример.
На плоскости задан прямоугольник, разбитый на одинаковые клетки со стороной
единичной длины. Заштрихованные клетки — стены, другие клетки — коридоры. Вход
в лабиринт — в правой нижней клетке, а выход (*) — в левой верхней. Загодя
известно, что в таком лабиринте существует как минимум один путь по коридорам,
начиная от входа и до выхода. Необходимо запрограммировать поиск выхода из
лабиринта для робота, который находится в начальной клетке.

1. из
некоторой, как правило, бесконечного количества.

В примере один и
тот же алгоритм годится для поиска выхода из будь- какого лабиринта
прямоугольной формы, а не только для того лабиринта 8 × 8, который изображен на
рисунке.

2. Детерминированность (или конечная
недетерминированность) — вычисления продвигаются вперед детерминировано, то
есть вычислитель однозначно представляет, какие инструкции необходимо выполнить
в текущий момент.

В примере действия
детерминированные, но этот алгоритм можно переделать и в недетерминированный,
если предоставить свободу самостоятельного выбора клетки в пункте (3). При
этом, поскольку этот выбор конечен (соседних клеток всего четыре), можно
представить дальнейшие действия в виде распределенных (параллельных)
вычислений: в момент выбора робот создает несколько своих клонов, и каждые
клоны идут своим путем, руководствуясь теми же пунктами (0) — (5). Если хотя бы
один из клонов находит выход, то задание считается решенным.

Алгоритмизация —
процесс создания алгоритма. Основное задание алгоритмизации — проследить
превращение информации по цепочке: задание → алгоритм → программа → компьютер →
результат решения.

Этапы алгоритмизации :

1. Этап
анализа результатов. Результат — кажется компьютером в заданном программой виде
и анализируется пользователем. 1.4 Принципы построения алгоритма

Чтобы построить алгоритм, необходимо
придерживаться определенных условий:

–
входные и исходные данные задать в виде последовательности
слов;

– процесс решения задания — это процесс
превращения входных данных в выходные. Процесс превращения состоит из
совокупности элементарных допустимых операций формального характера.

1.
Формирование основной идеи, выбор методов
решения задачи.

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

I. Практическое решение

3. Применение
избранных методов и средств для решения задания.

4. Анализ
полученных результатов. 1.5 Способы и формы представления алгоритмов

1. Словесное описание — словесно сформулированная
последовательность правил выполнения задания. Это самая старая форма
представления алгоритма. В нем формальные правила превращения информации
формулируются, нумеруются и указывается последовательность их выполнения.

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

Пример — алгоритм с лабиринтом.

Не имеет широкого распространения по
следующим причинам:

2.
Программная запись алгоритмов

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

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

Язык программирования
— это формализованный язык, который являет собой совокупность алфавита, правил
написания конструкций (синтаксис) и правил толкования конструкций (семантика). 2 Анализ сложности алгоритмов

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

2.1 Модель RAM (Random Access Machine)

Каждое
вычислительное устройство имеет свои особенности, которые могут влиять на
длительность вычисления. Обычно при разработке алгоритма не берутся во внимание
такие детали, как размер кэша процессора или тип многозадачности, реализуемый
операционной системой. Анализ алгоритмов проводят на модели абстрактного
вычислителя, называемого машиной с произвольным доступом к памяти
(RAM).

Модель
состоит из памяти и процессора, которые работают следующим образом:

Несмотря
на то, что такая модель далека от реального компьютера, она замечательно
подходит для анализа алгоритмов. После того, как алгоритм будет реализован для
конкретной ЭВМ, вы можете заняться профилированием и низкоуровневой
оптимизацией, но это будет уже оптимизация кода, а не алгоритма.

2.2 Подсчет операций. Классы входных данных

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

2.3 Асимптотические обозначения

Подсчет
количества операций позволяет сравнить эффективность алгоритмов. Однако,
аналогичный результат можно получить более простым путем. Анализ проводят с
расчетом на достаточно большой объем обрабатываемых данных (n→∞), поэтому
ключевое значение имеет скорость роста функции сложности, а не точное
количество операций.

При
анализе скорости роста игнорируются постоянные члены и множители в выражении,
т.е. функции fx=10×2+20 и gx=x2 эквивалентны с точки
зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая
затрудняет анализ.

Также
при асимптотическом анализе сложности можно считать, что любая программа, не содержащая
циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число
инструкций (конечно, при отсутствии

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

· O(g) — функции, растущие медленнее чем g;

· Ω(g) — функции, растущие быстрее чем g;

· Θ(g) — функции, растущие с той же скоростью, что и g.

2.4 Нотация «тэта»

Когда
мы выясняем точную асимптотику f, мы говорим, что наша программа — Θ( f( n ) ).
Например, в нашей программе получаем Θ( n ) (произносится как «тета от n»).
Иногда мы говорим, что f( n ) (оригинальная функция подсчёта инструкций,
включая константы) есть Θ( что-то ).

имеет
сложность n. Также существуют специальные названия для Θ( 1 ), Θ( n ), Θ( n2
) и Θ( log( n ) ), потому что они встречаются очень часто. Говорят, что Θ( 1 )
— алгоритм с константным временем, Θ( n ) — линейный, Θ( n2
) — квадратичный, а Θ( log( n ) ) — логарифмический.