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

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

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

2.

Понятие алгоритма
Способы описания алгоритмов
Структурные схемы алгоритмов
Методы разработки
алгоритмов

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

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

4.

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

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

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

6. Пример: алгоритм Евклида

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

7. Семь независимых параметров алгоритма Евклида

1.
2.
3.
4.
5.
6.
7.
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)

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

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

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

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

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

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

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

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

12. Блок-схема — это ориентированный граф, вершины которого могут быть одним из трех типов:

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

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

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

14.

Важной особенностью всех приведенных
структур является то, что они имеют один
вход и один выход
S1
T
B
S1
T
F
B
F
Итерация
(повторение)

15. Структурные блок - схемы алгоритмов

Линейные
Ветвящиеся
Циклические

16. Линейные

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

17.

Пример: Вычисление арифметического
выражения у = (b2 - ас) : (а + с)
Алгоритм:
Начало
Ввод a, b, c
p = b2 - ac
q=a+c
y= p / q
Вывод y
Конец

18. Ветвящийся

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

19.

Пример: Вычислить выражение
a + b, если X<=0
у=
Алгоритм:
c / b, если X>0
Начало
Ввод a, b, c, х
х>0
Да
y= с / b
y=a+b
Вывод y
Конец
Нет

20. Циклические

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

21. Примеры циклических алгоритмов

А)
В)
И
И
Да
Т
У
Нет
М
Т
Нет
У
М
Да
П
П

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

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

23. Основные методы разработки

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

24. Методы перебора вариантов

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