Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Основные алгоритмические структуры

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

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

Слово «алгоритм», «algorithm» происходит от имени выдающегося ученого IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского Мухаммед, сын Мусы из Хорезма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней арифметических действий.

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

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

Варианты словесного определения алгоритма, принадлежащие российским ученым-математикам А. Н. Колмогорову и А. А. Маркову:

Определение 2 (Колмогоров). Алгоритм — это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

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

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

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

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

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

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

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

Автоматическое исполнение алгоритма

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

Примером исполнителя, автоматически выполняющего различные алгоритмы, является компьютер. Рассмотрим запись на жесткий диск компьютера телевизионной передачи с помощью ТВ-тюнера. Указав в расписании время начала и окончания записи, поставив «флажок» возле позиции «Выключить компьютер после записи», пользователь может быть уверен, что передача будет записана и компьютер будет выключен. Всю заданную работу выполнит компьютер по разработанному ранее алгоритму, не внося никаких изменений (другая передача, другое время, невыключение компьютера).

Способы описания алгоритмов

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

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

Описание в графической форме в виде блок-схемы. В схеме алгоритма каждому типу действий (ввод исходных данных, вычисление, проверка условия, управление циклом, вывод результатов, окончание) соответствует своя геометрическая фигура — блок. Блоки соединяются линиями со стрелками, указывающими последовательность действий. Форма блоков установлена ГОСТом. Внутри блока записывается содержание соответствующего действия. Совокупность блоков образует блок-схему алгоритма. (В Microsoft Office можно использовать готовые шаблоны блоков.)

Основные блоки, используемые при графической форме записи алгоритмов:

 

Описание в виде программы для компьютера на языке программирования (например, Паскаль, Бейсик, Си).

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

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

Алгоритм линейной структуры — алгоритм, в котором предписываемые действия выполняются последовательно: Оператор1 — Оператор2 —... — Оператор N. Такой порядок выполнения действий называется естественным.

Алгоритм разветвленной структуры — алгоритм, в котором предусмотрено разветвление выполняемой последовательности действий в зависимости от результата проверки какого-то условия. Условие — это некоторое логическое выражение. Если условие (логическое выражение) принимает значение «истина», то выполняется Оператор1, в противном случае — значение «ложь» — выполняется Оператор2. Oпeратор1 и Оператор2 могут представлять собой группу операторов, а также могут быть условными операторами. В случае отсутствия Оператора2 получаем конструкцию с неполным ветвлением.

Алгоритм циклической структуры (цикл с повторением) — алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. Эту последовательность действий называют телом цикла.

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

Циклическую структуру реализуют операторы трех типов.

Оператор FOR...DO действует следующим образом. Тело цикла выполняется для каждого значения параметра цикла I от его начального M1 до конечного значения М2 включительно. I, Ml, M2 — чаще всего переменные целого типа. Шаг изменения переменной цикла I равен +1 или -1.

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

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

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