1.1. Базовые алгоритмические конструкции

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

Совокупность всех исходных данных, к которым алгоритм применим, называется областью применимости алгоритма. Каждый алгоритмзадает функцию, относящую каждому элементу области применимости соответствующий результат, т. е. область применимости совпадает с областью определения этой функции. Говорят тогда, что алгоритм вычисляет эту функцию. Функция, которая вычисляется некоторым алгоритмом, называется вычислимой. Множество значений вычислимой функции, определенной на N (натуральный ряд), образует перечислимое множество (значения функции перечисляются алгоритмом). Область применимости и область результатов любого алгоритма – перечислимые множества.

Не всякая математическая задача может быть решена с помощью алгоритма. Это связано с невычислимостью (неперечислимостью) некоторых областей, на которых определены решения этих задач. Например, существуют перечислимые подмножества натурального ряда с неперечислимым дополнением. Задачи, не решаемые с помощью алгоритма, называют алгоритмически неразрешимыми. К числу таких задач относятся, например, проблема распознавания эквивалентности (равенства) слов (существуют конечный алфавит, конечный набор правил составления и преобразования слов в этом алфавите, но нельзя построить алгоритм, который по двум произвольным словам этого алфавита всегда определит, преобразуются они или нет к одному и тому же слову). Другая известная задача – проблема остановки – не существует алгоритма, отвечающего на вопрос: остановится или нет некоторая программа, запущенная на некотором наборе начальных данных (не распознается наличие в программах бесконечных циклов). Проблема самоприменимости также неразрешима (нельзя с помощью алгоритма распознать для машины, преобразующей слова, распознает она или нет шифр самой себя). Задачи, решаемые алгоритмами, относятся к области исследований конструктивной математики.

1. 1. Базовые алгоритмические конструкции

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

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

12 3 4 5 6 7 8 9 Следующая ⇒