Определение, свойства и виды алгоритмов

В мире информационных технологий понятие алгоритма занимает центральное место. Сам термин произошел от имени Аль-Хорезми, узбекского средневекового математика, который в 9 веке сумел четко описать правила выполнения простых арифметических действий – то есть составил первые алгоритмы.

Видео: Лекция 1: Понятие алгоритма и машина Тьюринга

Алгоритм – определение

В современной информатике и математике этот термин имеет такие определения:

- последовательность действий, в которой строго определены правила выполнения-

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

- точное описание какого-либо вычислительного процесса или любой другой последовательности действий-

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

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

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

Универсальным исполнителем алгоритма в информатике является компьютер.

Алгоритм и его свойства

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

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

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

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

Видео: Понятие алгоритма и исполнителя. Свойства алгоритмов.

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

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

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

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

4) Разветвляющиеся алгоритмы содержат как минимум одно условие, после проверки которого ЭВМ может перейти на один из нескольких возможных шагов.

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