Требования к алгоритмическим процедурам

Характерные черты алгоритма и основные

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

АЛГОРИТМЫ И ИХ ПРИМЕНЕНИЕ

Лабораторная работа № 10

ЦЕЛЬ РАБОТЫ – изучение элементов теории алгоритмов и приобретение практических навыков по их применению

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

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

Сам термин «алгоритм» (или «алгорифм») происходит от имени великого среднеазиатского ученого Абу Абдалла Мухаммед ибн Мусса аль Хорезми аль Меджуси (787 – ок. 850 гг.). В своем трактате, написанном на арабском языке, латинская версия которого относится к ХII в. и начинается словами «Dixit algorism», то есть буквально «Сказал аль-Хорезми», им была также описана индийская позиционная система чисел и сформулированы правила выполнения четырех арифметических действий над числами в десятичной записи.

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

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

Можно дать еще одно интуитивное определение алгоритма.

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

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

Алгоритм имеет общие типичные черты и особенности.

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

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

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

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

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

4. Элементарность алгоритма. Закон получения последующей системы величин из предшествующей должен быть простым.

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

Например, задача нахождения наибольшего общего делителя чисел 12 и 18 есть единичная проблема (ее можно решить и без применения алгоритма Евклида – методом подбора), но задача нахождения наибольшего общего делителя произвольных натуральных чисел и - уже проблема массовая. Основное содержание алгоритма Евклида состоит в том, что он приводит к желаемому результату вне зависимости от выбора конкретной пары натуральных чисел, в то время как при решении приведенной единичной задачи можно предложить метод подбора или такой способ, который окажется неприменим для другой пары натуральных чисел.

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

Такое свойство алгоритма говорит о том, что выполнение алгоритмов можно передать машине.

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

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

Дата добавления: 2017-02-01; Просмотров: 76; Нарушение авторских прав?; Мы поможем в написании вашей работы!