Понятие алгоритма. Проектирование алгоритмов презентация

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

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

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

Пример: алгоритм Евклида
предназначен для нахождения наибольшего общего делителя пары натуральных чисел (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)

Семь независимых параметров алгоритма Евклида
I={(m,n)/ n>0, m>=n}.
P={(m, n)/ m>=n}.
R={(m/n) >0}.
Ввести пару чисел (m, n) таких, что m>=n
(m, n) → (n, m mod n)
Если в паре (m, n) n=0, то Останов.
Результатом является первое число пары (m, 0)

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

Словесно-формульный способ
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пример: Необходимо найти значение выражения.
у = 2а – (х+6)
Алгоритм:
Ввести значение а и х
Сложить х и 6
Умножить а на 2
Вычесть из 2а сумму (х+6)
Вывести у как результат вычисления выражения

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

Условные обозначения блоков

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

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

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

Структурные блок - схемы алгоритмов
Линейные
Ветвящиеся
Циклические

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

Пример: Вычисление арифметического выражения
у = (b2 - ас) : (а + с)
Конец
Алгоритм:

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

Пример: Вычислить выражение
y= с / b
Конец
Алгоритм:
Да
Нет

Циклические
Циклическими называются программы, содержащие циклы.
Цикл – это многократно повторяемый участок программы.
В организации цикла можно выделить следующие этапы:
подготовка (инициализация) цикла (И);
выполнение вычислений цикла (Т);
модификация параметров (М);
проверка условий окончания цикла (У);

Примеры циклических алгоритмов
А)
В)

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

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