Понятие алгоритма относится к основным понятиям информатики.
Когда речь идет об алгоритме, всегда подразумевается существование некоторого исполнителя, для которого предназначен алгоритм.
· Исполнитель – человек или автомат (например, компьютер), который умеет выполнять определенный конечный набор действий.
· Предписание – приказ на выполнение действий из указанного конечного набора.
· Система предписаний – совокупность допустимых приказов.
· Программа – конечная последовательность предписаний с указанием порядка их выполнения.
В случае, когда исполнителем является компьютер, предписание называется командой, а система предписаний называется системой команд компьютера.
Программирование – составление последовательности команд, которая необходима для решения поставленной задачи.
Составлению программы предшествует разработка алгоритма.
Алгоритм – это точное и понятное указание исполнителю совершить конечную последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.
Любой алгоритм обладает следующими свойствами:
· Дискретность. Выполнение алгоритма разбивается на последовательность элементарных действий – шагов. Каждое действие должно быть закончено исполнителем прежде, чем он перейдет к выполнению следующего действия. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
· Точность или детерминированность. Запись алгоритма должна быть такой, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей.
· Понятность. Каждый алгоритм строится в расчете на конкретного исполнителя, который должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением.
· Результативность. При точном исполнении всех предписаний алгоритма процесс должен завершится за конечное число шагов и при этом должен быть получен какой-либо ответ на поставленную задачу. В качестве одного из возможных решений может быть установление того факта, что задача не имеет решения
· Массовость. помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно. Свойство массовости значительно увеличивает практическую ценность алгоритмов.
Каждый алгоритм предполагает наличие некоторых исходных данных. Например, для медицинского рецепта (алгоритма) исходными данными являются медикаменты, а результатом – флакон с готовым лекарством. Для алгоритма сложения исходными данными являются пара слагаемых, а результатом – их сумма. Для каждого алгоритма существует класс объектов, допустимых в качестве исходных данных. Иногда исходными данными являются материальные объекты, а иногда – числа.
Алгоритм – это правило, следовательно, оно должно быть сформулировано на некотором языке. Исходные данные и искомые результаты также должны быть описаны на некотором языке, возможно отличном от языка, на котором описан алгоритм.
Таким образом, каждый алгоритм связан с двумя языками: на одном он сформулирован сам, предложения другого являются для него допустимыми вариантами исходных данных.
Разработка алгоритма решения задачи называется алгоритмизацией. В процессе алгоритмизации задача сводится к построению последовательности шагов, расположенных в определенном порядке.
Между алгоритмами и программами нет четкого разграничения. Программой обычно называют алгоритм решения задачи, рассчитанный на исполнение его компьютером и записанный с помощью предложений используемого языка программирования.
Алгоритмической структурой называется стандартный способ соединения отдельных шагов алгоритма для выполнения типичной последовательности действий.
В теории алгоритмов доказывается, что любой алгоритм может быть представлен в виде комбинации трех алгоритмических структур: следования, развилки и цикла.
Следование. Представляет собой последовательное выполнение действий (рис. 12).
Рис. 12. Следование.
Развилка. Применяется в случае, когда в зависимости от истинности некоторого логического условия необходимо выполнить то или иное действие (рис. 13).
Рис. 13. Развилка.
Действия 1 и 2 могут, в свою очередь, включать в себя другие алгоритмические структуры.
Цикл. Применяется, когда некоторые действия необходимо выполнить несколько раз. Существуют две разновидности цикла.
Цикл До. Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет ложным (рис. 14).
Рис. 14. Цикл До.
Под начальными присвоениями подразумеваются операции присвоения исходных значений переменным, используемым в цикле. Многократно повторяемая последовательность действий называется телом цикла.
Цикл Пока. Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет истинным (рис. 15).
Рис. 15. Цикл Пока.
4.2. Понятие языка
Естественный язык – социальное средство хранения и передачи информации, одно из самых эффективных средств управления поведением человека. Он неразрывно связан с мышлением и существует в виде речи.
Кроме естественного языка существуют искусственные языки, целенаправленно сконструированные для:
международного общения (эсперанто, интерлингва);
автоматической обработки данных с помощью ЭВМ (языки программирования);
записи информации из определенной области науки и техники (информационные языки).
Основой любого естественного или искусственного языка является алфавит, состоящий из некоторого множества символов или букв. Последовательности букв образуют слова. Однако не любая последовательность букв образует правильное слово с точки зрения данного языка. Совокупность правил, позволяющих строить правильные слова, называется грамматикой.
Слова могут объединяться в более сложные конструкции – предложения. Предложения строятся из слов и более простых предложений по определенным правилам. Совокупность правил, с помощью которых строятся правильные предложения, называется синтаксисом.
Каждому правильному предложению языка приписывается некоторый смысл. Совокупность правил, с помощью которых предложениям ставится в соответствие смысл, называется семантикой.
Естественный язык является универсальным в том смысле, что с его помощью может быть представлена любая информация. Однако он обладает особенностями, делающими его неудобным для записи алгоритмов. Эти особенности следующие:
зависимость синтаксиса от семантики;
многозначность смысла предложений;
расплывчатость смысла предложений и возможность парадоксальных предложений.
Зависимость синтаксиса от семантики заключается в том, что способ построения предложения зависит от его смысла. Например, правильность предложения
Кравченко пришел домой
зависит от того, является ли Кравченко мужчиной или женщиной.
Зависимость синтаксиса от семантики означает, что для распознавания правильности предложения нужно знать его смысл.
Приведем пример многозначности естественного языка:
Я вижу косу.
Здесь слово «коса» может означать сельскохозяйственное орудие, сплетение волос на голове или длинную узкую отмель, идущую вдоль берега.
Пример парадоксального предложения:
Если у состава отцепить последний вагон, то у состава не будет последнего вагона.
