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

Принципы построения алгоритмов и алгоритмические конструкции.

Тема 1.1. Сущность алгоритмизации

План:

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

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

3. Формы записи алгоритмов

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

Одним из фундаментальных понятий в информатике является понятие алгоритм. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которго европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первые алгоритмы в математике.

В наше время понятие алгоритма трактуется шире.

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

С алгоритмами мы имеем дело постоянно. И рецепты приготовления блюд, и нотные записи музыкальных произведений, и описание того, как вычислить корни квадратного уравнения по его коэффициентам, – всё это алгоритмы.

Пример 1. Алгоритм «Заварка чая»:

1. Вскипятить воду в чайнике.

2. Положить в пустую чайную чашку пакетик чая.

3. Залить чашку горячей водой.

4. Подождать 1 минуту.

5. Вытащить пакетик.

6. Положить в чашку 2 чайных ложки сахара.

7. Размешать сахар.

Пример 2. Алгоритм «Приготовь яичницу»:

1. Достать яйцо и масло.

2. Включить плиту.

3. Поставить сковороду на плиту.

4. Растопить на сковородке масло.

5. Взять нож.

6. Разбить ножом яйцо над сковородкой.

7. Выбросить скорлупу в мусорное ведро.

8. Жарить яичницу 5 минут.

9. Выключить плиту.

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

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

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

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

Пример 3. Исполнители алгоритмов:

§ Компьютер

§ Солдат

§ Автомобиль

§ Дрессированный лев

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

Поэтому исполнителя, выполняющего команды определённого алгоритма без анализа действий и ситуаций, называют формальным исполнителем.

Исполнителя алгоритма характеризует среда его «обитания» и система команд исполнителя (СКИ).

Среда исполнителя – обстановка, в которой функционирует исполнитель.

Система команд исполнителя (СКИ) – это вся совокупность команд, которую может выполнить исполнитель.

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

Пример 4. Некоторые команды из СКИ исполнителя «DVD-плеер»:

§ начать воспроизведение

§ пауза

§ остановить воспроизведение

§ увеличить громкость

§ уменьшить громкость

§ ускоренное воспроизведение назад

§ ускоренное воспроизведение вперёд

§ покадровое воспроизведение

§ выбор языка