Раздел 8 (Лекция 14)

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

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

Алгоритмический процесс

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

Семь независимых параметров алгоритма

совокупность возможных исходных данных;

совокупность возможных промежуточных результатов;

совокупность результатов;

правило начала;

правило непосредственной переработки;

правило окончания;

правило извлечения результата.

Пример: параметры алгоритма Евклида

предназначен для нахождения наибольшего общего делителя пары натуральных чисел (m, n)

1 {Нахождение остатка} r:=m mod n.

2 {Замена} m:=n; n:=г.

3 {Остановка?} Если n<>0, то переход к п.1.

4 {Остановка процесса} m — искомое число.

Смена конструктивных объектов в алгоритме Евклида для пары чисел m=10, n=4:

(10, 4) ® (4, 2) ® (2, 0)

Способы описания алгоритмов

Словесно-формульный

Структурный (блок - схемный)

С помощью граф-схем Блок-схема — это ориентированный граф, вершины которого могут быть одним из трех типов: Функциональная вершина используется для представления функции f: X—>Y. Предикатная вершина используется для представления функции (или предиката) р: X —» ( T, F), т.е. логического выражения, передающего управление по одной из двух возможных ветвей. Объединяющая вершина представляет передачу управления от одной из двух входящих ветвей к одной выходящей.

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

Линейные

Ветвящиеся

Циклические

С помощью сети Петри

Словесно-формульный способ

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

Блок-схемный

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

Структурная блок-схема алгоритма

Структурная блок-схема — это блок-схема, которая может быть выражена как композиция из 4 элементарных блок-схем.

Линейные, ветвящиеся и циклические алгоритмы

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

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

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

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

Цикл – это многократно повторяемый участок программы.

В организации цикла можно выделить следующие этапы:

подготовка (инициализация) цикла (И);

выполнение вычислений цикла (Т);

модификация параметров (М);

проверка условий окончания цикла (У);

Методы разработки алгоритмов

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

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

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