Билет № 6

1. Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов; блок-схемы.
2. Вычислить информационный объем сообщения.

Рассмотрим 1 вопрос:

Слово "алгоритм" происходит от "algorithmi" - латинской формы написания
имени выдающегося математика IX века аль-Хорезми, который сформулировал правила
выполнения арифметических операций.

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

Алгоритм выполняется за определенное количество шагов. Шаг(команда) – отдельное
законченное действие.

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

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

Характеристики исполнителя:
Среда исполнителя – обстановка, в которой функционирует исполнитель.
Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять (mp3-player может выполнить команды: проигрывать, пауза, перемотать вперед, перемотать назад и т.п.).
Каждый исполнитель может выполнять команды только из некотоpого стpого заданного
списка — системы команд исполнителя.

Любой алгоритм должен удовлетворять четырем свойствам:

1. Конечность
2. Понятность
3. Дискретность
4. Точность

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

Так чтобы найти корни квадратного уравнения необходимо выполнить следующий алгоритм:

1) Определить постоянные a, b, c ;

2) Найти дискриминант D;

3) Посчитать значения х1 и х2.

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

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

Пример: переход дороги по пешеходному переходу без светофора:

1) подойти к зебре;

2) посмотреть налево и направо;

3) если нет машин, то дойти до середины дороги;

4) посмотреть направо и налево;

5) перейти по переходу до другой стороны улицы;

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

Рассмотрим следующий набор команд:

1) Идти прямо

2) Сесть на автобус

3) Проехать до остановки

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

Способы записи (формы представления) алгоритмов:

• словесная (записи на естественном языке);
• графическая (изображения из графических символов: блок-схемы);
• программная (тексты на языках программирования).

Графический способ записи алгоритмов

(блок-схема)

Графический способ представления алгоритмов является более компактным и
наглядным по сравнению со словесным.

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

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

Основные алгоритмические блоки: