Лекция 10. Основы алгоритмизации
Алгоритм — ключевое понятие информатики, это то, без чего се просто не может быть. Русские слова «метод», «способ», «рецепт», «план действий» можно, правда, с некоторой долей условности, считать близкими словами.
Итак, алгоритм — это последовательность команд (предписаний инструкций) некоторому исполнителю, выполнение которых приводит к получению конечного результата (достижению цели). Пример, робот-манипулятор.
Попробуем выразить последовательность алгоритма графически. Графическое отображение алгоритма с помощью блок-схемы называется его структурной схемой.
Будем использовать фигуры (блоки):
начало или конец процесса;
какое-либо действие или процесс;
проверка условия для принятия решения;
ввод (вывод) данных.
Тогда структурная схема алгоритма будет выглядеть так:
Алгоритм должен иметь точку входа — «начало» и точку окончания выполнения команд «конец», и так как любой алгоритм пишется для исполнителя, то этому исполни гелю нужно сообщить (ввести) значения чисел тип, позволяющих начать работу исполнителя корректно. На структурных схемах ввод или вывод информации указывается в фигуре «параллелограмм».
Формальное выполнение алгоритма. Алгоритм позволяет формализовать выполнение информационного процесса. Если исполнителем является человек, то он может выполнять алгоритм формально, не вникая в содержание поставленной задачи, а только строго выполняя последовательность действий, предусмотренную алгоритмом.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Рассмотрим свойства алгоритмов.
1. Конечность. Алгоритм должен всегда заканчиваться после конечного, пусть даже большого числа шагов. Это очень важное свойство алгоритмов. Именно оно отличает собственно алгоритм от вычислительного (математического) метода.
2. Определенность или детерминированность. Каждый шаг алгоритма должен быть точно определен. Действия, которые предписывается произвести исполнителю алгоритма, должны быть строго и однозначно описаны для каждого возможного случая. Определенность алгоритма обусловлена определенностью действий для каждого из его шагов, которые должны быть максимально формализованы в математическом смысле. Для реализации алгоритмов компьютером были созданы специальные алгоритмические языки. Записанный на таком языке алгоритм уже является компьютерной программой, вернее ее исходным текстом.
3. Доступность. У каждого исполнителя, будь то человек, управляющий каким-то механизмом или выполняющий действия на конвейере, техническое устройство (станок с программным управлением, робот-манипулятор, автомат), компьютер, есть своя «система команд», в области которой все понимается и интерпретируется им однозначно. Все, что выходит за эти рамки, даже будучи идеальным алгоритмом по каким-то другим свойствам, не может быть выполнено исполнителем или приведет к серьезным ошибкам.
4. Массовость. Алгоритмы должны быть широко применимыми.
5. Структура данных. Алгоритм всегда имеет входные и выходные данные. Способ их описания представляет собой структуру данных. Это могут быть цепочки, списки, деревья, таблицы. Важной составной частью системы команд при описании алгоритма являются алгоритмические возможности описания структур данных.
6. Дискретность. Это означает, что все операции, предусмотренные алгоритмом, должны быть представлены простыми шагами, что каждый шаг можно было выполнить однозначно и за конечный отрезок времени.
Задание: ответить на вопросы: учебник Цв., стр.102, вопр. 1,2,4.