Алгоритмы

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

Слово «алгоритм» происходит от имени среднеазиатского математика IX века аль-Хорезми, который установил правила четырех арифметических действий над числами в десятичной системе счисления. В Европе эти правила получили название «алгоризм». Затем это слово постепенно преобразовалось в слово «алгоритм» и стало собирательным названием правил, которые применялись не только для выполнения арифметического счета.

В течении длительного времени термин «алгоритм» употребляли преимущественно математики, описывая правила решения различных задач. При этом они пользовались так называемым интуитивным понятием алгоритма как способа описания порядка решения той или иной задачи при помощи конечного набора однозначных математических действий. На этом пути были получены ставшие теперь известными правила поиска корней квадратных и кубических уравнений, решения систем линейных и нелинейных уравнений, дифференцирования и интегрирования функций и многие другие правила вычислений. Более того, известна попытка Г. Лейбница найти общий алгоритм решения любых математических задач [24].

Вместе с тем, решая различные задачи, математики столкнулись с рядом неразрешимых проблем, т.е. задач, для которых не удавалось построить решающий их алгоритм. Широко известной из них стала проблема П. Ферма. Существуют ли натуральные числа х, у, 1, для которых при целом п >2 справедливо равенство х" + у" = г”? Были известны и другие задачи, в частности, из области геометрии: о квадратуре круга, удвоении куба и др. [25]. Это побудило математиков более глубоко подойти к обоснованию сущности алгоритмов и прежде всего формальным, т.е. математическим путем.

Основные результаты теории алгоритмов были получены в 30—50-х годах XX века Э. Черчем, А. Тьюрингом, А. Постом, А. Колмогоровым, А. Марковым. Введенные в рассмотренные модели алгоритмов (алгоритмические модели) машины А. Тьюринга, А. Поста дали возможность устанавливать алгоритмическую разрешимость проблемы путем построения соответствующих машин логического действия, т. е. более конструктивно подходить к поиску решения неразрешенных проблем, часто акцентируя внимание на их частных случаях.

Широкое употребление слова «алгоритм» обязано буму кибернетики — науки об управлении и связи в живом и машине, который пришелся на 50-е годы XX века. Слово «алгоритм» стало настолько популярным, что его начали применять в различных случаях, весьма далеких от вычислений. Например, алгоритмами стали называть рецепты приготовления и приема лекарств, переход пешеходом улицы с интенсивным движением транспорта, завязывание шнурков на ботинках и т. п. Дело дошло до абсурда. Появились дикие словосочетания типа «алгоритм изобретения», что означает не что иное, как конец изобретательства (творческой деятельности).

Оставляя в стороне подобного рода алгоритмы, сосредоточим внимание лишь на тех из них, которые описывают решение задач обработки информации на ЭВМ. Построение таких алгоритмов должно удовлетворять ряду принципов. Первое, что следует отметить, — алгоритм применяется к исходным данным и выдает результаты. Иными словами, он имеет информационный вход и выход. Кроме того, в ходе выполнения алгоритма получаются промежуточные результаты, которые могут использоваться в дальнейшем. Таким образом, каждый алгоритм выполняет операции с данными — входными, промежуточными и выходными.

Данные должны быть четко определены и отделены от «не данных». Примерами данных, с которыми работают алгоритмы, предназначенные для ЭВМ, являются числа, формулы, векторы, матрицы смежности графов, чертежи, рисунки, фотографии. Не данными являются, например, «хорошая книга» или «логическое утверждение». С этими «не данными» алгоритм работать не будет до тех пор, пока они не будут представлены в форме подходящих данных.

Для универсальности представления данных в алгоритмах используются специальные алфавиты — конечные наборы символов, из которых конструируются слова и предложения. Поэтому считается, что вход алгоритмов — это слова разной длины, определенные в конечном алфавите. Каждый символ алфавита имеет стандартный код определенной длины, занимающий не более восьми двоичных разрядов. В современных ЭВМ символы кодируются при вводе их в ЭВМ с клавиатуры или со сканера.

Введенные в компьютер данные размещаются в памяти. Память является дискретной, состоящей из отдельных ячеек. Каждая ячейка может вмещать один символ. Так, что например, слово АЬРА для своего размещения потребует 4 ячейки. Таким образом, физической единицей памяти является ячейка. На логическом уровне единица памяти называется байтом.

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

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

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

Суммируя все перечисленные требования, которым должны удовлетворять алгоритмы обработки информации на ЭВМ, введем следующее

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

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

С точки зрения современной практики алгоритм существует только тогда, когда по нему может быть составлена программа для ЭВМ, правильно решающая задачу. Поэтому критерием алгорит-мичности некоторой задачи, является возможность ее запрограммировать.

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

Определение 5.2. Орграф, вершины которого отображают шаги алгоритма, а дуги — переходы между шагами, называется блок-схемой алгоритма.

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

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

По существу, блок-схемы — это средства описания детерминизма алгоритма.

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

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

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

Для иллюстрации описанных методов представления алгоритмов рассмотрим следующую задачу. Необходимо составить алгоритм приближенного вычисления квадратного корня х - 4а с заданной точностью е методом Ньютона. Этот метод состоит в том, что очередное значение корня хп вычисляется по рекку- рентному соотношению хп = х„_, + -

а

л-1

4*«-1

, п - 1,2,... при

/

условии, что задано начальное значение корня х0. Тогда первое значение корня будет равно х, = х0 +—

а

о

  • - х
  • 4*0

о

второе —

1 х2 = X, + —

ґ

а

- х

и т. д. Корень будем считать вычисленным

4*1

ня

1

(

1

а

- х„

2

1 х„

п

)

приведена на рис. 5.1.

с заданной точностью е, если модуль очередного уточнения кор-

< е. Блок-схема алгоритма решения этой задачи

Блок-схема алгоритма вычисления квадратного корня методом Ньютона

Рис. 5.1. Блок-схема алгоритма вычисления квадратного корня методом Ньютона

Текстовая форма алгоритма дана ниже.

Шаг 1. Ввести о, х0,?и перейти к шагу 2.

Шаг 2. Положить и - х0 и перейти к шагу 3.

Шаг 3. Вычислить v = —

'a

- - и у и

и перейти к шагу 4.

Шаг 4. Вычислить х - и + у и перейти к шагу 5.

Шаг 5. Если |у| > е, положить и - х и вернуться к шагу 3; если иначе, перейти к шагу 6.

Шаг 6. Вывести значение корня х и перейти к шагу 7.

Шаг 7. Остановиться.

В связи с тем, что естественная последовательность выполнения 1—4 шагов алгоритма не нарушается, согласно оговоренному ранее соглашению, он может быть записан так:

Шаг 1. Ввести а, х0, е.

Шаг 2. Положить и - х

Шаг 3. Вычислить v = — о-

/ а

и

уп

X - U + V.

Шаг 4. Если |v| > е, положить и = х и вернуться к шагу 3; если иначе, перейти к шагу 5.

Шаг 5. Вывести значение корня х и остановиться.

Алгоритм в программной форме представлен полностью на языке BASIC:

INPUT “Введите а, х0, е”; а, х0, Eps и — Х0

Ml:

v = 0.5*((а/и - и): х - и + v IF ABS(v) >= Eps THEN и = х: GOTO М PRINT “Корень квадратный из а равен”; х END

 
< Пред   СОДЕРЖАНИЕ     След >