Тема 3.1. Основы алгоритмизации

 

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

    Алгоритм (algorithm) – строго установленный порядок выполнения каких-то действий, необходимых для получения конечного результата.

Алгоритм (algorithm) – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к исходному результату (по ГОСТ 19.004-80).

Алгоритм является одним из фундаментальных понятий в математике и программировании. Он означает точное описание некоторого процесса, точную инструкцию по его выполнению, то есть понятие «алгоритм» требует точного определения, как самих действий, так и порядка их выполнения.

Вычислительный процесс (f) в компьютере является детерминированным (однозначность, определенность) преобразованием данных (Д) с одного алфавита в тот или иной конечный алфавит (Е): Д→ f → E

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

Программа (program) – данные, их описание и алгоритм, записанный на языке программирования.

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

Действия над данными, предписываемые программой, называются операциями, а элементарное предписание, предусматривающее выполнение определенной операции, - командой.

Назначение программы определяется, как правило, реализуемой ею задачей (управляющие, ввода/вывода, диагностические и пр.). Обычно программы хранятся во внешней памяти компьютера. Для выполнения они загружаются в оперативную память. Программа, постоянно находится в ОЗУ во время работы компьютера, называется резидентной программой.

Алгоритмизация (algorithmization) – совокупность взаимосвязанных действий, выполняемых в процессе разработки и обоснования алгоритма. Алгоритмизация включает: Расчленение вычислительного процесса на автономные шаги, Формальную запись содержания каждого шага вычислительного процесса, Определение очередности (порядка) выполнения выделенных шагов, Проверку правильности работы алгоритма при реализации заданного метода вычисления.

Запись алгоритма на алгоритмическом языке выполняется по строгим правилам и особенностям построения конструкций конкретного алгоритмического языка.

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

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

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

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

Массовость – пригодность алгоритма для решения определенного класса задач, то есть для каждого алгоритма существует свой класс объектов.

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

    По структуре выполнения алгоритмы и программы делятся на три вида:

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

    Разветвляющийся (ветвящийся) алгоритм – алгоритм, в котором предусматриваются варианты предписаний в зависимости от изменения назначенных условий.

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

    Все они образуют основные управляющие канонические структуры алгоритмических процессов.

Линейный вычислительный процесс (serial process) состоит из самостоятельных этапов вычислений, которые выполняются в естественном порядке их записи, то есть в строгой линейной последовательности независимо от значений первичных и промежуточных данных.

Ветвящиеся вычислительные процессы (branching process), ход которых зависит от первоначальных условий или полученных результатов. Они реализуются по одному из нескольких, предварительно предусмотренных направлений (по одной или другой ветви).

В алгоритмах любые логические условия могут быть выражены при помощи одного из четырех отношений числа к числу: a>b, a≥b, a<b, a≤b, a=b, a≠b., а также отношений числа к нулю: a=0,a≠0, a>0, a<0. Каноническая структура ветвящихся вычислительных процессов представлена на (Рис.4).

Условие

Оператор 1

Оператор 2

Оператор 3

Рис. 4. Каноническая структура ветвящихся вычислительных процессов

Ветвящиеся процессы описываются оператором If.

Структура оператора If полной формы можно показать так:

 

Then оператор 1 Else оператор 2

If (условие) →                                               →оператор 3

Формат оператора If неполной формы имеет вид:

If (условие) Then оператор1

Оператор 3

В операторе If оператор 1 и оператор 2 – это любая последовательность операторов внутри оператора If, а оператор 3 – следующий (внешний по отношению к If) оператор за оператором If.

Циклические вычислительные процессы. Для решения многих задач характерно многократное повторение соответствующих участков вычислительных процессов.

Многократно повторенные участки вычислительного процесса по одним и тем же математическим зависимостям при различных значениях первичных величин называется циклами.

Цикл (cycle loop)- последовательность команд, которая повторяется, пока не будет выполнено предписанное условие, например, до заполнения счетчика числа повторений.

По существу циклические вычислительные процессы можно задать n -м количеством линейных процессов. Циклическое описание многократно повторяемых вычислительных процессов уменьшает во много раз трудоемкость написания программы и увеличивает ее наглядность. Классическим примеров циклического вычислительного процесса является суммирование элементов вектора S=S+a(i). Этот пример, мы будем использовать для пояснения последовательности организации циклических процессов.

Автоматическое управление циклом осуществляет переменная, называемая параметром.

Параметр цикла (cycle parameter) – управляющая переменная. Задаются первоначальное значение (например, i≤100), и увеличение параметра на каждом шаге повторения (например: i=i+1).

Любой циклический процесс, включает в себя четыре обязательных шага:

1. подготовку к выполнению циклической части алгоритма

2. рабочую часть цикла

3. подготовку очередного шага цикла

4. проверку окончания цикла

Последовательность циклического вычислительного процесса предполагает два варианта:

Первый вариант очередности выполнения шагов цикла:

1. Подготовка цикла:

· гашение (очистка) рабочих полей памяти (Например, S=0),

· задание первичного значения параметра цикла (например, i=1)

2. Рабочая часть цикла (например, S=S+A(i)).

3. Подготовка очередного шага цикла (например, i=i+1)

4. Проверка окончание цикла (например,   i≤100)

Второй вариант выполнения очередности шагов цикла: Подготовка к выполнению цикла; Поверка окончания цикла; Рабочая часть цикла; Подготовка очередного шага цикла.

Каноническая структура циклического вычислительного процесса представлена на (Рис 5 и 6).

Условие

Тело цикла

Рис.5. Каноническая структура циклического вычислительного процесса

На рисунке тело цикла выполняется только при выполнении условия и на каждом шаге повторения управление передается на проверку условия (окончание цикла).

 

Тело цикла

Условие

Рис.6. Каноническая структура циклического вычислительного процесса

 

На рисунке тело цикла размещено перед условием и выполняется как минимум один раз. В зависимости от ограничения числа повторений тела цикла различают основных типа циклов: с известным числом повторений; с неизвестным числом повторений (итерационные).

Циклы с известным числом повторений. При их выполнении задаются: начальное и конечное значения параметров цикла S закономерность изменения параметра цикла на каждом шаге его повторения S необходимое число повторений цикла.

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

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

Общий вид алгоритма.

Алгоритм: Название алгоритма

Описание данных

Начало

Команды

Конец.

Например: Общий вид алгоритма вычисления площади круга (по формуле S=π*R^2) можно представить следующим образом:

Алгоритм: Вычисление площади круга

Описание величин S (результат), π (аргумент), R (аргумент)

Начало

S=π*R^2

Конец.

Способы записи алгоритма: СЛОВЕСТНЫЙ; ФОРМУЛЬНЫЙ; ТАБЛИЧНЫЙ; ГРАФИЧЕСКИЙ

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

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

Графический способ описания алгоритма (блок схема) получил самое широкое распространение.

Блок-схема – это графическое представление алгоритма с кратким дополнением в виде слов. Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками), которые закреплены ГОСТ.

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