Понятие алгоритма и его характеристики

Тема 3. Алгоритмы и алгоритмизация. Визуализация алгоритмов

План конспекта лекции

1. Введение

2. Понятие алгоритма и его характеристики

3. Место алгоритма при решении задачи на компьютере

4. Проектирование алгоритмов

Введение

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

Понятие алгоритма и его характеристики

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

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

Свойства алгоритмов:

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

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

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

· правильность. Выполнение алгоритма должно давать правильные результаты;

· конечность. Полное выполнения алгоритма должно происходить за конечное число шагов;

· дискретность. Алгоритм должен состоять из отдельных операций, которые выполняются последовательно;

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

Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи.

Можно назвать две формы написания алгоритмов:

· на естественном языке (словесно-пошаговый);

· на языке блок-схем.

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

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

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

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

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

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

· ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения;

· ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения;

· ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические.

Данные документы регулируют способы построения схем и внешний вид их элементов.

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

Словесная форма представления алгоритма становится более доступной для составления программы, если она написана на псевдоязыке (псевдокоде). Это полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др. Такой язык не транслируется, но позволяет компактно задавать логику исходного описания, в отличие от языка блок- схем. Хотя псевдоязык похож на язык программирования, но в нем нет такой синтаксической строгости, как, собственно, у языка программирования. Поэтому, на псевдоязыке удобно демонстрировать или разрабатывать алгоритмы, но нельзя написать работающую программу. Он занимает промежуточное место между естественным и формальным языками.

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

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

Базовые структуры алгоритмов. Базовые алгоритмические конструкции - это способы управления обработкой информации. На сегодняшний день существует три базовых структуры: линейные алгоритмы; алгоритмы ветвления; циклические алгоритмы.

Структура – линейный алгоритм

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

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

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

Алгоритм предполагает выполнение Плечо 1, если записанное условие истинно (выполняется), и выполнение Плечо 2 (если условие ложно (не выполняется). Это полное ветвление.

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

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

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

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

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

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

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

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

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

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

Можно выделить три крупных класса алгоритмов:

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

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

· Управляющие — исходные данные поступают от процесса или объекта, которым управляют. Результат — воздействие на процесс. Алгоритмы должны выдавать результирующие сигналы, управляющие работой тех или иных устройств. Для этого класса алгоритмов очень существенную роль играет их быстродействие, т.к. управляющие сигналы всегда должны появляться в нужный момент времени.