- •1.7. Алгоритмы. Основные понятия
- •1.7.1. Определение алгоритма. Запись алгоритма. Свойства алгоритмов
- •1.7.3. Примеры алгоритмов. Способы, используемые при записи алгоритмов: рекурсия, итерация, разбор случаев, иерархическое построение
- •1.7.5. Объекты, типы объектов
- •1.7.7. Псевдокод для записи алгоритмов
- •1.7.9. Неструктурированная форма записи алгоритмов
- •1.7.11. Структурированная форма записи алгоритмов
- •1.7.13. Последовательный оператор
- •1.7.15. Условный оператор
- •1.7.17. Оператор цикла
-
1.7. Алгоритмы. Основные понятия
-
1.7.1. Определение алгоритма. Запись алгоритма. Свойства алгоритмов
Обработка информации предполагает выполнение какого-то правила (алгоритма), исходные данные для которого отождествляются с состоянием того или иного носителя.
Почти во всех сферах жизни нам приходится иметь дело с инструкциями (предписаниями, рецептами, правилами), в соответствии с которыми можно или нужно что-то сделать. Например, инструкции по пользованию телефоном-автоматом или инструкции по эксплуатации пылесосов. Когда такие инструкции удовлетворяют определенным минимальным требованиям, говорят об алгоритме - совокупности правил, определяющих эффективную процедуру решения любой задачи из некоторого класса задач.
Алгоритм является одним из основных начальных понятий математики. Так же, как и другие начальные понятия, такие как число, точка, множество, оно не имеет строгого определения, а может быть только пояснено.
Говорят, что алгоритм - это точное предписание, которое задает дискретный пошаговый процесс, начинающийся с некоторых произвольных исходных объектов и направленный на получение полностью определяемого этими исходными объектами результата.
В приведенном поясняющем определении неявно подразумевается наличие некоторого исполнителя, который способен выполнить предписанные алгоритмом действия и тем самым осуществить некоторый дискретный процесс получения нужного результата. Исполнитель может быть как специализированным исполнителем, способным выполнять один конкретный, как говорят, "зашитый" в него алгоритм, так и достаточно универсальным исполнителем, т.е. способным выполнять не один какой-то конкретный алгоритм, а любой из алгоритмов в некотором достаточно обширном классе алгоритмов.
Каждый универсальный исполнитель обладает некоторым языком для записи алгоритмов. Универсальным исполнителем алгоритма может быть как человек, так и некоторое автоматическое устройство, например, компьютер. Язык записи алгоритмов компьютера называется языком программирования. Запись любого алгоритма на языке программирования называется программой.
Подчеркнем, что алгоритмы не зависят от исполнителей и предоставляемых ими языков записи алгоритмов. Так, один и тот же алгоритм может быть записан множеством различных способов, в зависимости от того, на какой исполнитель ориентируется исполнение и какой при этом язык используется.
Алгоритмы характеризуются следующими основными свойствами:
· дискретностью,
· определенностью,
· результативностью,
· массовостью.
Дискретность. Любой исполнитель умеет выполнять только ограниченный конечный набор действий (приказов, команд). Следовательно, для выполнения сколь-либо сложного действия, оно должно быть разбито на совокупность более мелких действий, каждое из которых уже может быть непосредственно выполнено исполнителем. Отсюда следует, что запись алгоритма на заданном языке должна представлять собой совокупность из некоторого числа единиц этого языка, именуемых операторами, задающих действия исполнителя, которые он способен выполнить за один раз, не прибегая при этом к делению на более мелкие действия.
Элементарные такты обработки чаще всего выполняются один за другим (последовательно), но иногда и одновременно (параллельно).
Определенность. Набор операторов, составляющих запись алгоритма, должен быть не только понятен исполнителю, но и точен и не должен допускать двусмысленностей при выполнении. Описание должно быть составлено настолько точно, чтобы было возможно его однозначное понимание. Один и тот же алгоритм может быть записан на разных языках: русском, английском, на каком-либо искусственном языке или даже на языке пиктограмм. Для автоматических исполнителей предполагается использование формализованных строгих языков записи алгоритмов. Тем самым обеспечивается однозначность получаемых результатов. Описание должно быть конечным, иначе его передача исполнителю (человеку или компьютеру) длилась бы бесконечно долго.
Результативность. Для всех случаев, для которых алгоритм предназначен, он должен приводить к результату после конечного числа шагов выполнения. Требуется, чтобы он обязательно заканчивался, т.е. содержал конечное число элементарных тактов.
Массовость. Алгоритм должен быть применим к решению не какой-то одной единственной задачи, а к решению любой задачи из некоторого класса задач.