Лекция 10. Основы алгоритмизации

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

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

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

Будем использовать фигуры (блоки):

начало или конец процесса;

какое-либо действие или процесс;

проверка условия для принятия решения;

ввод (вывод) данных.

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

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

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

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

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

1. Конечность. Алгоритм должен всегда заканчиваться после конеч­ного, пусть даже большого числа шагов. Это очень важное свой­ство алгоритмов. Именно оно отличает собственно алгоритм от вычислительного (математического) метода.

2. Определенность или детерминированность. Каждый шаг алгорит­ма должен быть точно определен. Действия, которые предписы­вается произвести исполнителю алгоритма, должны быть строго и однозначно описаны для каждого возможного случая. Опреде­ленность алгоритма обусловлена определенностью действий для каждого из его шагов, которые должны быть максимально фор­мализованы в математическом смысле. Для реализации алгорит­мов компьютером были созданы специальные алгоритмические языки. Записанный на таком языке алгоритм уже является ком­пьютерной программой, вернее ее исходным текстом.

3. Доступность. У каждого исполнителя, будь то человек, управ­ляющий каким-то механизмом или выполняющий действия на конвейере, техническое устройство (станок с программным управ­лением, робот-манипулятор, автомат), компьютер, есть своя «система команд», в области которой все понимается и интер­претируется им однозначно. Все, что выходит за эти рамки, даже будучи идеальным алгоритмом по каким-то другим свойствам, не может быть выполнено исполнителем или приведет к серьез­ным ошибкам.

4. Массовость. Алгоритмы должны быть широко применимыми.

5. Структура данных. Алгоритм всегда имеет входные и выходные данные. Способ их описания представляет собой структуру дан­ных. Это могут быть цепочки, списки, деревья, таблицы. Важной составной частью системы команд при описании алгоритма яв­ляются алгоритмические возможности описания структур дан­ных.

6. Дискретность. Это означает, что все операции, предусмотренные алгоритмом, должны быть представлены простыми шагами, что каждый шаг можно было выполнить однозначно и за конечный отрезок времени.

Задание: ответить на вопросы: учебник Цв., стр.102, вопр. 1,2,4.