Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf

Пятым правилом является сходимость или результативность. После конечного числа шагов алгоритм должен завершать работу. При этом необходимо указать, что считать результатом работы алгоритма. [13, с. 7]

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

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

Полное понимание алгоритма происходит благодаря его свойствам или по-другому правила построения алгоритма.

1.2 Виды алгоритмов и способы их описания

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

- механические алгоритмы, или детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);

- гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические. [3, с. 6]

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

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

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

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

---

Эвристика – это наука, изучающая продуктивное творческое мышление. Благодаря этому выявляет способы построения оптимальных направлений поиска решения задач, точные методы решения которых не известны.

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

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

Эквивалентными будут являться такие алгоритмы, результаты которых для одних и тех же исходных данных будут одинаковыми. [3, с. 7]

Эквивалентными алгоритмы будут считаться при условии, что

- множество допустимых исходных данных одного из них является множеством допустимых исходных данных и другого; из применимости одного алгоритма к каким-либо исходным данным следует применимость и другого алгоритма к этим данным;

- применение этих алгоритмов к одним и тем же исходным данным дает одинаковые результаты.

Пример таких алгоритмов. Допустим надо подсчитать общую сумму чисел, приведенных в табл. 1. Эквивалентными будут алгоритмы подсчета общей суммы по строкам: 5 + 1 + 3 + 8 + 10 + 9 + 6 + 1 + 5 + 10 + 1 + 1 = 60, и по столбцам: 5 + 10 + 5 + 1 + 9 + 10 + 3 + 6 + 1 + 8 + 1 + 1 = 60. Заметим, что для данной таблицы считать проще по столбцам. [14, с. 17]

Таблица 1. Целые числа

5	1	3	8
10	9	6	1
5	10	1	1

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

Также выделяют такие виды алгоритмов как:

- линейный, представленный набором команд (указаний), которые выполняются последовательно во времени друг за другом;

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

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

- цикл программы представлен последовательностью команд (серия, тело цикла), выполняемых многократно (для новых исходных данных) до того момента, как будут удовлетворены некоторые условия;

- вспомогательный или подчиненный. Под ним понимается алгоритм, который был ранее разработан и целиком используется при алгоритмизации конкретной задачи. Иногда при наличии одинаковых последовательных указаний для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. [1, c. 5]

---

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

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

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

Модель третьего типа состоит в преобразовании слов в произвольных алфавитах. Элементарными операциями в них являются подстановки, замена части слова (под словом понимается последовательность символов алфавита) другим словом. Такой тип обладает преимуществом в максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (необязательно числовой) природы. Примерами моделей данного типа служат канонические системы американского математика Эмиля Л. Поста и нормальные алгоритмы, которые были введены советским математиком А.А. Марковым.

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

Характер языка описания определятся тем, для какого исполнителя предназначен алгоритм. Возможности исполнителя алгоритмов определяют уровень используемых языковых средств, т. е. степень детализации и формализации предписаний в алгоритмической записи. [14, с. 17]

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

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

---

Часто встречаются такие формы представления алгоритмов как:

- словесная – записывается на естественном языке;

- графическая – с помощью блок-схемы;

- псевдокоды – полуформализованные описания алгоритмов на некотором условном алгоритмическом языке, которые включают в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др. [6, с. 6]

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

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

Однако словесная форма имеет ряд недостатков:

- строго не формализуема;

- страдает многословностью записей;

- допускает неоднозначность толкования отдельных предписаний.

Эта форма обычно используется на начальных стадиях разработки алгоритма. [9, с. 7]

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

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

Рассмотрим пример алгоритма на естественном языке:

1. Ввести в компьютер числовые значения переменных а, b и с.

2. Вычислить дискриминант по формуле d = b² - 4ас.

3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к п. 4. Иначе вычислить ????₁ = (−????+√D) / 2???? , ????₂ = (−????−√D) / 2???? и напечатать значения x₁ и x₂.

4. Прекратить вычисления. [6, с. 7]

Еще примером данного способа описания алгоритма является алгоритм нахождения максимального из двух значений:

- определим форматы переменных X, Y, M, где X и Y – значения для сравнения, M – переменная для хранения максимального значения;

- получим два значения чисел X и Y для сравнения;

- сравним X и Y.

- если X меньше Y, значит большее число Y.

- Поместим в переменную M значение Y.

- Если X не меньше (больше) Y, значит большее число X.

- Поместим в переменную M значение X. [13, с. 9]

Общепринятый способ записи алгоритма является графическая запись с помощью схем (блок-схем) и символьная запись с помощью какого-либо алгоритмического языка.

---

С помощью схем алгоритм описывается в виде последовательности геометрических фигур. Фигура определяет выполнение конкретного действия алгоритма. А порядок выполнения действий указывается стрелками.

Типы графических обозначений, элементы блок-схем изображаются следующим образом:

- начало (конец) алгоритма

- блок ввода-вывода данных

- блок вычислений. Процесс (действия или серия действий)

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

- процесс пользователя (подпрограмма)

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

- соединитель, используется для указания связи между потоками информации в пределах одного листа

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

Начало и конец алгоритма обозначают с помощью одноименных символов (рис. 1.1). Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом «процесс». Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом «решение» [11, с. 12]

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

Часто программистам требуется создать описание алгоритма, которое будет предназначаться только для человека. Такие описания не являются программами, но имеют более четкую структуру в отличии от обычного текса. Сочетание естественного языка и структур языка программирования делает описанный алгоритм доступным и также информативным. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. [2, с. 12]

Например, алгоритм умножения двух чисел можно записать с помощью псевдокода:

1. Ввод a, b.
2. P=a b.
3. Вывод Р.
4. Конец.

Примером псевдокода является школьный алгоритмический язык (АЯ).

Основные служебные слова этого языка представлены в табл. 2. [9, с. 7 – 8]

Таблица 2. Служебные слова школьного алгоритмического языка

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

---