Проектирование алгоритмов и основные их типы

Способ записи алгоритма должен соответствовать следующим требова­ниям:

· обеспечивать компактность и наглядность;

· быть понятным широкому кругу лиц;

· содержать строгие правила записи алгоритма;

· обеспечивать простой и формальный перевод на языки программирова­ния.

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

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

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

На рисунке изображены «функциональная » (a) вершина, имеющая один вход и один выход; «предикатная » (б) вершина, имеющая один вход и два выхода. В этом случае функция Р передает управление по одной из вет­вей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая » (в) вершина (вершина «слияния»), обеспе­чивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -). На прак­тике при составлении блок-схем оказывается удобным использовать и другие графические знаки, например:

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

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

Ветвящийся алгоритм - ход решения задачи определяется в зависи­мости от условия (переход и ветвление).

Да Проверка Нет

условия

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

IF <условие> THEN <оператор1>

ELSE <оператор2> - условный оператор;

GOTO <номер строки> - безусловный переход;

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

Циклический алгоритм – описывает повторяющиеся действия.

Проверка 100

условия

Да

Циклические процессы описываются следующим оператором:

FOR х = 1 ТО n STEP h <оператор>

NEXT x - циклическая конструкция.

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

Автоматическое управление циклом осуществляет переменная, назы­ваемая параметром. Параметр цикла - управляющая переменная. Задаются первоначальное значение параметра цикла (например, Х = 1), конечное зна­чение (например, Х =< 100), и увеличение параметра на каждом шаге повто­рения (например, Х = Х + 1).

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

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

· рабочую часть цикла;

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

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

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

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

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

Машина Тьюринга. В 1937-1938 гг. Э.Пост и А.Тьюринг независимо один от другого доказали, что алгоритмические процессы есть процессы, ко­торые может выполнять соответствующим образом построенная «машина» (на этой гипотетической машине оказалось возможным проверить, имити­ровать все алгоритмические процессы). Абстрактные (существующие лишь в воображении) машины Поста и Тьюринга, предназначены для доказательств различных утверждений о свойствах программ для них. Они представляют собой универсальных исполнителей, являющихся полностью детерминиро­ванными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат. Машина Поста менее популярна, хотя она зна­чительно проще машины Тьюринга.

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

1. Информационную ленту, представляющую собой бесконечную (неог­раниченную) внешнюю память машины. Это может быть магнитная лента, перфолента. Информационная лента поделена на отдельные ячейки. В одной ячейке может помещаться только один символ, в том числе и ноль.

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

3. Устройство управления, которое в каждый рассматриваемый момент находится в каком-то «состоянии». В общем устройство управления (предпо­лагаемое) может находиться в каком-то числе «состояний».

Схематично машина Тьюринга показывается так:

0 1 2 3 k r – 1 r

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