1. Понятие алгоритма

1.1. Определение алгоритма

В Оксфордском словаре указано, что Algorithm – это ошибочное от algorism, который считается синонимом алгебры и арифметики и восходит к IX в.

Позднее этим символом обозначались в трудах Евклида правила нахождения общего делителя двух чисел – алгоритм Евклида.

История появления понятия «алгоритм» связана с именем выдающегося узбекского ученого Мухаммеда бен Муса ал-Хорезми (жил в IX в.), который был математиком, астрономом, географом. Он написал «Арифметический трактат», по которому европейцы впервые познакомились с десятичной позиционной системой счисления, пришедшей к арабам из Индии. После этого четыре арифметических действия долго называли ал-Хорезми (по латыни Algorithmi). В литературе встречалось «алгоритмус», «алгорифм», а в современном варианте произносится как «алгоритм». Этот термин расширил свое первоначальное значение.

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

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

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

К алгоритмам предъявляются ряд требований:

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

2. Массовость, т.е. чтобы его можно было применить к однотипным задачам.

3. Результативность, т.е. через определенное число шагов алгоритм должен закончиться.

4. Дискретность, т.е. возможность деления задачи на шаги, элементарные операции.

5. Понятность, т.е. ориентация на те команды, которые знает исполнитель.

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

7. Правильность.

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

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

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

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

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

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

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

К основным способам описания алгоритмов можно отнести следующее:

• словесно-формульный (на естественном языке);

• структурный или блок-схемный;

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

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

• с помощью сетей Петри.

Перед составлением программ чаще всего используются словесно-формульный и блок-схемный способы. Иногда перед составлением программ на низкоуровневых языках программирования типа языка Ассемблера алгоритм программы записывают, пользуясь конструкциями некоторого высокоуровнего языка программирования. Удобно использовать программное описание алгоритмов функционирования сложных программных систем. Так, для описания принципов функционирования ОС использовался Алголо-подобный высокоуровневый язык программирования.