|
|
Конспект лекций по информатике. Конспект лекций по информатике учебное пособие
2. Алгоритм и его основные свойства
Человеку в жизни приходится решать множество разнообразных задач. Простые задачи имеют простое решение, а для решения сложных задач используются различные приемы, способы, системы и т.п. Понятие "алгоритм" связано, как правило, с решением сложных задач, требующих привлечения вычислительной техники. Вместе с тем, это понятие можно использовать и при описании простых операций и решений.
Примеры простых решений, в которых используются алгоритмические подходы:
рецепты кулинарной книги;
порядок автоматической стирки;
кипячение воды в чайнике.
Понятие "алгоритм" связано, как правило, с решением сложных задач, требующих привлечения вычислительной техники.
Алгоритм – набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время8.
Алгоритм – это конечный набор правил, позволяющих чисто механически решать любую конкретную задачу из некоторого класса однотипных задач9.
Различают процессы создания и реализации алгоритмов.
Создание алгоритма – творческий процесс, выполняемый специалистом в области разработки алгоритмов.
Реализация – процесс выполнения предписанных команд формальным исполнителем, к которым, в первую очередь, относятся различные автоматические устройства, в том числе, вычислительная техника.
Формальный исполнитель не вникает в смысл того, что он делает, но получает при этом необходимый результат. Строгое выполнение последовательности операций с отвлечением исполнителя от содержания поставленной задачи выражается в особенности, которая называется формальностью алгоритма.
Алгоритм – искусственная конструкция, которая строится по определенным правилам и характеризуется конкретными свойствами.
Дискретность. Одно из свойств алгоритма, которое выражается в разбиении описываемого процесса на последовательность отдельных шагов или команд. Совокупность отдельных шагов образует дискретную структуру алгоритма.
Понятность. Для создания алгоритма могут быть использованы только те команды, которые исполнитель понимает и может выполнить. Другими словами, алгоритм должен состоять из команд, которые имеются в системе команд исполнителя.
Определённость или детерминированность. При разработке алгоритма не могут быть использованы команды, смысл которых воспринимается исполнителем неоднозначно. Иначе говоря, алгоритм не должен оставлять места для произвола исполнителя.
Результативность. Процесс, описываемый алгоритмом, должен прекратиться за конечное число шагов с получением определённого результата.
Массовость. Чаще всего алгоритмы обеспечивают решение не одной конкретной задачи, а некоторого класса задач данного типа. Это свойство позволяет выделять область применимости алгоритма.
Из перечисленных свойств вытекают правила построения алгоритма, которые выражаются в следующем.
Алгоритм приступает к работе с набором данных, которые называются входными, в результате работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.
Это правило позволяет сразу отделить алгоритмы от "методов" и "способов". Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Для работы алгоритма требуется дискретная память, в ячейках которой размещаются входные данные, а также промежуточные и выходные данные, которые являются результатом работы алгоритма.
Алгоритм строится из отдельных шагов, действий, операций или команд, при этом множество шагов алгоритма всегда конечно.
После каждого шага необходимо указывать, какой шаг в алгоритме выполняется следующим, либо давать команду на остановку.
Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указывать, что считать результатом работы алгоритма.
3. Типы алгоритмических процессов
Алгоритмы в зависимости от цели, начальных условий, путей решения задачи, последовательности действий исполнителя подразделяются следующим образом.
Механические или жесткие алгоритмы, например, алгоритм работы двигателя внутреннего сгорания.
Гибкие алгоритмы, например, вероятностные или эвристические:
Вероятностные (стохастические) алгоритмы определяют программу решения задачи несколькими путями, каждый из которых дает достижение результата с некоторой вероятностью.
Эвристический алгоритм не имеет определенной последовательности действий, достижение конечного результата алгоритма однозначно не предопределено. В эвристических алгоритмах используют логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения задач.
Линейные алгоритмы состоят из набора команд, которые выполняют последовательно друг за другом.
Разветвляющиеся алгоритмы содержат условие, в результате проверки которого исполнитель переходит на один из двух возможных вариантов продолжения алгоритма.
Циклические алгоритмы связаны с многократным повторением одного и того же действия с обновляющимися исходными данными. Циклические алгоритмы используются, например, для выполнения приближенных вычислений.
Вспомогательные алгоритмы относятся к уже созданным алгоритмам, которые можно использовать в готов виде при алгоритмизации новой задачи.
|
|
|
Скачать 0.97 Mb.