Алгоритм и его

свойства

Алгоритм

-

конечный набор правил, который определяет

последовательность операций для решения конкретного

множества задач и обладает пятью свойствами:

-

конечность;

-

определенность;

-

ввод;

-

вывод;

-

эффективность.

Свойства алгоритма

1.

Результативность

(конечность). Если исходные данные определены

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

получим ответ, либо установим, что его нет.

2.

Детерминированность

(определенность) алгоритма – свойство алгоритма

всякий раз с одинаковыми исходными данными формировать одинаковый

результат.

3.

Понятность и дискретность

(ввод и вывод). Оговоренным образом

алгоритм получает исходные данные и сообщает о результатах работы, а

каждый последующий шаг алгоритма определяется предыдущим шагом.

4.

Эффективность

алгоритма определяется количеством действий,

совершаемых исполнителем алгоритма для решения задачи, и объемом

памяти, который требуется ему для выполнения этих действий.

5.

Массовость

. Алгоритм решает типовую для данного класса задачу, т.е.

может работать с разными наборами исходных данных.

Машина

Тьюринга

Английский математик, логик, криптограф, оказавший существенное

влияние на развитие информатики. Кавалер Ордена Британской

империи, член Лондонского королевского общества. Предложенная

им в 1936 году абстрактная вычислительная «Машина Тьюринга»,

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

позволила формализовать понятие алгоритма и до сих пор

используется во множестве теоретических и практических

исследований.

Тьюринг Алан Матисон (1912-1954)

Машина Тьюринга

Машина Тьюринга – формальная логическая конструкция,

позволяющая описать преобразование цепочек символов по

некоторым правилам

Критерии сравнения алгоритмов

1.

Количество действий.

а) минимальная оценка, т.е. минимум действий, которые алгоритм совершит в

самом удачном случае его исполнения;

б) средняя оценка, т.е. количество действий, которые будут совершаться в

средней по сложности ситуации;

в) максимальная оценка – это наибольшее возможное время работы.

Использование такой оценки позволяет определить время, за которое

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

«плохие» данные поступили для обработки;

2.

Объем требуемой оперативной памяти.

Сложность алгоритма -

примерная оценка количества ресурсов (шагов

исполнения и/или памяти), которые необходимо

затратить на решение задачи с помощью этого

алгоритма.

Классы

сложности

О(1) – количество действий постоянно и не зависит от количества входных

данных.

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

время их использования хорошо предсказываются;

L – O(log(n)) – количество действий сравнимо с логарифмом n.

Это быстрые

алгоритмы, в которых при увеличении объёма данных время исполнения растет

медленно.

Р – О(Р(n)) – количество действий не превосходит некоторого многочлена от n.

Такие алгоритмы тоже считаются быстрыми. Скорость их решения сравнительно

мало зависит от входных данных

.

NP – задачи, сложность решения которых существенно зависит от количества

данных.

Но если есть некоторые дополнительные сведения, то задача становится

задачей из предыдущего класса.

EXPTIME – О(2

p(n)

) – количество действий возрастает по некоторой экспоненте.

Это алгоритмы вычислительно – сложные, поскольку с ростом количества данных их

затраты растут очень быстро.

Задание

Уменьшить число, записанное в двоичной системе счисления, на 1 .

Каретка стоит над числом.