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

1.

Вишнева Елена Владимировна

2.

Алгоритм — строго определенная последовательность
действий для некоторого исполнителя, приводящая к
поставленной цели или заданному результату за конечное
число шагов.
Любой алгоритм составляется в расчете на конкретного
исполнителя с учетом его возможностей.
Исполнитель — субъект, способный исполнять некоторый
набор команд.
Совокупность команд, которые исполнитель может понять и
выполнить, называется системой команд исполнителя
(СКИ).

3.

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

4.

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

5.

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

6.

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

7.

Произвольное изложение этапов алгоритма на естественном
языке имеет свои недостатки. Словесные описания строго не
формализуемы, поэтому может быть нарушено свойство
определенности алгоритма: исполнитель может неточно понять
описание этапа алгоритма. Словесная запись достаточно
многословна. Сложные задачи трудно представить в словесной
форме.
Программы на языке произвольного формального исполнителя
могут состоять только из элементарных команд, которые входят в
его систему (которые исполнитель «понимает»).
Исполнитель может иметь свою среду (например, систему
координат, клеточное поле и др.).
Среда исполнителя — это совокупность объектов, над которыми
он может выполнять определенные действия (команды), и связей
между этими объектами. Алгоритмы в этой среде выполняются
исполнителем по шагам.

8.

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

9.

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

10.

Внешний вид блока
ДА
НЕТ
Назначение блока
Альтернативный блок (условный блок, условие). Служит для
указания выбора одного из двух возможных действий. Внутри
ромба размещается условие выбора (например, вопрос или
сравнение).
Условием может быть выражение, для которого возможно
только одно из двух значений – либо «истина», либо «ложь».
В ромб входит одна направленная линия. Из ромба выходят
две направленные линии, каждая из которых подписана «Да»
или «Нет». Если условие, записанное внутри ромба, будет
верным (значение «истина», «да»), то управление передается
по стрелке «Да», в противном случае – по стрелке «Нет».
Блок цикла.
Предназначен для организации циклического процесса с
параметром. Количество повторений (итераций) цикла и шаг
изменения параметра должны быть известны. Внутри блока
указываются начальное значение параметра цикла, конечное
значение и шаг его изменения.

11.

начало
…
(блоки алгоритма)
конец

12.

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

13.

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

14.

Образуется последовательностью действий, следующих одно
за другим.
Действие 1
Действие 2
Действие 3

15.

• Написать алгоритм нахождения суммы двух чисел.
начало
Ввод a, b
S=a+b
Вывод S
конец

16.

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

17.

если—то
Да
если—то—иначе
Да
Условие
Действие
выбор
Действие 1
Действие 2
Действие 1
Нет
Да
Нет
Условие
выбор—иначе
Условие 1
Да
Действие 1
Условие 1
Нет
Нет
Да
Условие 2
Действие 2
…
Да
Действие N
Да
Условие 2
Действие 2
Нет
Условие N
Нет
…
Да
Действие N
Нет
Условие N
Нет
Действие N+1

18.

Написать алгоритм решения квадратного уравнения
ax2+bx+c=0
начало
Ввод a, b, c
D=b2-4ac
Корней
нет
Да
D<0
Нет
X1=(−