Понятие алгоритма
Понятие алгоритма является центральным понятием информатики. Слово «алгоритм» произошло от имени узбекского математика аль-Хорезми, который еще в IX веке сформулировал правила выполнения арифметических действий. В современной математике и информатике термин алгоритм имеет следующие определения:
- — последовательность действий со строго определенными правилами выполнения;
- — предписание, определяющее содержание и последовательность операций, переводящих исходные данные в искомый результат;
- — точное описание некоторого вычислительного процесса или любой иной последовательности действий;
- — точное и полное предписание о последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством — формальным исполнителем. Задача исполнителя — точная реализация уже имеющегося алгоритма. Формальный исполнитель не обязан вникать в сущность алгоритма, а возможно, и неспособен его понять.
Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете па конкретного исполнителя.
Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие.
В информатике универсальным исполнителем алгоритмов является компьютер.
Виды алгоритмов
Алгоритм применительно к вычислительной машине — точное предписание, т. е. набор операций н правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа.
Алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
- Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
- Эвристический алгоритм (от греческого слова «эврика») — это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
- Линейный алгоритм — набор команд (указаний), выполняемых последовательно друг за другом.
- Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
- Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) Над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторому условию.
- Вспомогательный (подчиненный) алгоритм (процедура) — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.
Алгоритм можно задать несколькими способами:
- — словесным, то есть записью последовательности действий на естественном языке;
- — графическим, с помощью специальных графических символов;
- — формульным, то есть с помощью математических формул, которые определяют порядок вычислений;
- — табличным, и виде таблицы, в которой фиксируются этапы исполнения алгоритма и результаты исполнения.
Блок-схема алгоритма
Задание алгоритмов с помощью блок-схем оказалось очень удобным средством изображения алгоритмов и получило широкое распространение.
Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.
В таблице приведены наиболее часто употребляемые символы.
| Символы блок-схемы | ||
| Название символа | Обозначение и пример заполнения | Пояснение |
| Процесс | 
| Вычислительное действие или последовательность действий |
| Решение | 
| Проверка условий |
| Модификация | 
| Начало цикла |
| Предопределенный процесс | 
| Вычисления по подпрограмме, стандартной подпрограмме |
| Ввод-вывод | 
| Ввод-вывод в общем виде |
| Пуск-остановка | 
| Начало, конец алгоритма, вход и выход в подпрограмму |
| Документ | 
| Вывод результатов |
Блок «процесс » применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.
Блок «решение » используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.
Блок «модификация » используется для организации циклических конструкций. (Слово «модификация» означает «видоизменение, преобразование»). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.
Блок «предопределенный процесс » используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам.
Для примера приведем блок-схемы алгоритма нахождения максимального из двух значений:
Правила построения алгоритма
Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить все же не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.
Первое правило — при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результата своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило — для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т. е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Точнее — из множества шагов.
Четвертое правило — детерминированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
Пятое правило — сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Запись опубликована в рубрике Информатика с метками алгоритм, правила, программирование. Добавьте в закладки постоянную ссылку.
Свойства алгоритма
Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Определенность — каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость — алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.