Понятие алгоритма (исторические сведения)

1. АЛГОРИТМ

2. План

– Понятие алгоритма (исторические
сведения).
– Исполнитель алгоритма.
– Свойства алгоритмов.
– Виды алгоритмов.

3.

Название "алгоритм" произошло от
латинской формы имени величайшего
среднеазиатского математика Мухаммеда
ибн Муса ал-Хорезми (Alhorithmi), жившего в
783—850 г.
В своей книге "Об индийском счете" он
изложил правила записи натуральных чисел с
помощью арабских цифр и правила действий
над ними "столбиком", знакомые теперь
каждому школьнику. В XII веке эта книга была
переведена на латынь и получила широкое
распространение в Европе.

4.

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

5. Исполнитель алгоритма

Исполнитель алгоритма — это некоторая
абстрактная или реальная (техническая,
биологическая или биотехническая) система,
способная выполнить действия,
предписываемые алгоритмом.
Исполнителя хаpактеpизуют:
• среда;
• элементарные действия;
• система команд;
• отказы.

6.

• Среда (или обстановка) — это "место
обитания" исполнителя.
Напpимеp, для исполнителя Робота из
школьного учебника среда — это
бесконечное клеточное поле. Стены и
закрашенные клетки тоже часть среды.
А их расположение и положение самого
Pобота задают конкретное состояние
среды.

7.

• Система команд. Каждый исполнитель может
выполнять команды только из некоторого
строго заданного списка — системы команд
исполнителя. Для каждой команды должны
быть заданы условия применимости (в
каких состояниях среды может быть
выполнена команда) и описаны результаты
выполнения команды. Напpимеp, команда
Робота "ввеpх" может быть выполнена, если
выше Робота нет стены. Ее результат —
смещение Робота на одну клетку вверх

8.

• После вызова команды исполнитель
совершает соответствующее
элементарное действие.
• Отказы исполнителя возникают, если
команда вызывается при недопустимом
для нее состоянии среды.

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

• Дискретность – алгоритм состоит из
отдельных инструкций (шагов);
• Однозначность – каждый шаг понимается
исполнителем единственным образом;
• Массовость – алгоритм работает при
меняющихся в некоторых пределах входных
данных;
• Результативность – за конечное число
шагов достигается некоторый результат;
• Конечность – каждое действие в
отдельности и весь алгоритм в целом должны
иметь возможность завершения .

10. Виды алгоритмов

• Механические алгоритмы, или иначе
детерминированные, жесткие (например алгоритм
работы машины, двигателя и т.п.).
• Гибкие алгоритмы - вероятностные (алгоритм дает
программу решения задачи несколькими путями или
способами, приводящими к вероятному достижению
результата.
• Эвристический алгоритм (от греческого слова
“эврика”) – это такой алгоритм, в котором достижение
конечного результата программы действий
однозначно не предопределено

11. Виды алгоритмов

• Линейный алгоритм – набор команд, выполняемых
последовательно во времени, друг за другом.
• Разветвляющийся алгоритм – алгоритм,
содержащий хотя бы одно условие, в результате
которого обеспечивается переход на один из двух
возможных шагов.
• Циклический алгоритм – алгоритм,
предусматривающий многократное повторение
одного и того же действия над новыми данными.
• Вспомогательный алгоритм – алгоритм, который
можно использовать в других алгоритмах, указав
только его имя.

12. Алгоритмическая система

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

13.

Алгоритмическая система определяется наличием
четырех составляющих ее частей:
1) множеством входных объектов или исходных данных,
подлежащих обработке алгоритмами данной
системы;
2) множеством выходных объектов или результатов
выполнения алгоритмов данной системы;
3) системой команд исполнителя, т. е. набором тех
действий, которые может выполнять исполнитель и
которое мы можем описывать в алгоритмах;
4) языком описания алгоритмов — языком исполнителя;