Лекция Алгоритмы и способы их описания, свойства алгоритмов

АЛГОРИТМЫ И СПОСОБЫ ИХ ОПИСАНИЯ, СВОЙСТВА АЛГОРИТМОВ

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

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

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

Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло в Европе после перевода на латынь книги этого среднеазиатского математика, в которой его имя писалось как «Алгоритми».

(Аль-Хорезми [имя] + Аритмос [число] → алгоритм)

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

Каждый шофер должен знать правила дорожного движения.

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

2. Разнообразие исполнителей

Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.

Исполнители бывают неформальными и формальными.

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

Таким образом:

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

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

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

2. Дискретность (прерывность, раздельность) — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов. Каждый шаг должен приносить определенный результат.

3. Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат. (Точность – конкретность команды не цвет а цвет 12 и т.п. ;значение переменной д.б. известно заранее до выполнения команды Порядок написания команды)

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

5. Результативность — каждый алгоритм должен приводить к обязательному решению в поставленной конкретной задаче (приводить к результату).

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

4. Способы записи алгоритма

Существует несколько способов записи Алгоритмов:

1. — Словесный - на естественном языке;

2. — Псевдокодами – на условном алгоритмическом языке;

3. — Графический – из специальных блоков – геометрических фигур в виде блок-схем;

4. — Программный - в виде программы на каком-либо языке программирования.

5. Основные алгоритмические структуры

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

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

1.САМОЙ ПРОСТОЙ СТРУКТУРОЙ ЯВЛЯЕТСЯ «СЛЕДОВАНИЕ».

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

Алгоритм, основанный на конструкции «следование» называется линейным алгоритмом.

Примером такого алгоритма может служить алгоритм вычисления дискриминанта квадратного уравнения, блок-схема которого приведена на рисунке 1.

Рис. 1

Пример 1

Пример 2

2.СЛЕДУЮЩЕЙ КОНСТРУКЦИЕЙ ЯВЛЯЕТСЯ «ВЕТВЛЕНИЕ».

Она встречается, если действия алгоритма зависят от некоторого условия.

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

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

Существуют полная и неполная формы ветвления.

В полной форме если условие выполняется, то алгоритм переходит к выполнению первой серии команд, а если не выполняется — то ко второй.

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

Алгоритм, основанный на конструкции «ветвление» называется разветвляющимся алгоритмом.

Примером алгоритма с неполным ветвлением может служить алгоритм нахождения корней квадратного уравнения, блок-схема которого приведена на рисунке 2.

Рис. 2

3. И, НАКОНЕЦ, ПОСЛЕДНЯЯ АЛГОРИТМИЧЕСКАЯ КОНСТРУКЦИЯ — «ПОВТОРЕНИЕ».

Повторение - Алгоритмическая конструкция, где некоторая последовательность действий выполняется много раз

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

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

Существует несколько разновидностей циклических алгоритмов.

Первый — цикл с заданным условием продолжения работы (цикл с предусловием или цикл-пока).

Второй — цикл с заданным условием окончания работы (цикл с постусловием или цикл-до).

И третий — цикл с заданным числом повторений (цикл с параметром или цикл - для).

Цикл с заданным условием продолжения работы (цикл - пока) (цикл с предусловием)

Пример:

Цикл с заданным условием окончания работы (цикл-до) (цикл с постусловием)

Цикл с заданным числом повторений (цикл - для) (цикл с параметром)

Пример:

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

ИТОГО:

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

Алгоритм, который состоит из нескольких алгоритмических структур, называется сложным.

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

Последовательным и вложенным

• При последовательном соединении одна алгоритмическая структура следует строго за другой

• При вложенном способе соединении одна алгоритмическая структура является частью другой

ПОДВЕДЕМ ИТОГИ

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

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

Исполнителем алгоритма может быть субъект или устройство, способное правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.

Один и тот же алгоритм может быть записан разными способами: на естественном языке, с помощью блок-схем, на языке программирования и т. д.

Выделяют три базовые алгоритмические структуры: следование, ветвление, повторение.

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

8