12.Понятие алгоритма. Свойства. Основные характеристики.

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

Перед решением любой задачи с помощью персонального компьютера (ПК) выполняются следующие этапы: постановка этой задачи, построение сценария и алгоритмизация.

Алгоритмизация задачи - процесс разработки (проектирования) алгоритма решения задачи с помощью ПК на основе ее условия и требований к конечно­му результату.

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

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

• последовательную декомпозицию задачи, выделение автономных этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;

• формальную запись содержания каждого этапа и/или шага;

• определение общего порядка выполнения этапов и/или шагов;

• проверку правильности алгоритма.

Алгоритмы обладают целым рядом свойств:

Понятность для исполнителя - содержание предписания о выполнениитолько таких действий, которые входят в систему команд исполнителя.

Дискретность (прерывность, раздельность) - выполнение команд алго­ритма последовательно, с точной фиксацией моментов окончания выполнения одной команды и начала выполнения следующей.

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

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

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

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

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

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

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

Объем текста алгоритма (программы) определяется количеством операторов, использованных для записи алгоритма.

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