2инф. Понятие алгоритма. Свойства алгоритма. Способы представления алгоритмов. Виды алгоритмов. Временная и емкостная сложность алгоритмов.

Алгоритм – точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Исполнитель алгоритма – некоторая объективная или субъективная система, способная выполнить действия предписываемые алгоритмом. Такой объект или субъект принято называть формальным исполнителем. Каждый алг-м создается на конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность этих действий образует систему команд исполнителя (СКИ).

Свойства алг-мов:1)Дискретность. Алгоритм должен представлять решение задачи как последовательное выполнение простых шагов. Только выполнив очередной шаг, можно перейти к выполнению следующего. 2)Определенность (однозначность). Каждое действие должно быть четким и однозначным 3)Результативность. Выполнение алг-ма должно завершиться, получив определенный рез-т за конечное число шагов. 4)Массовость. Алг-тм разрабатывается в общем виде для решения определенного класса задач. 5)Понятность. Все команды должны быть записаны на языке понятном исполнителю.

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

 Блок-схема – система связанных между собой блоков, изображаемых в виде плоских геометрических фигур. Внутри блоков записываются различные указания, блоки соединяются между собой стрелками, изображающие порядок выполнения действий.

По структуре алгоритмы разделяют на линейные, разветвляющиеся и циклические. Линейными называют алгоритмы, в которых операции выполняются последовательно, одна за другой, в естественном и единственном порядке следования. Линейные алгоритмы, как правило, являются составной частью любого алгоритмического процесса.

При составлении алгоритмов часто возникает необходимость проведения анализа исходных данных или промежуточных результатов вычислений и определение дальнейшего порядка выполнения вычислительного процесса в зависимости от рез-тов этого анализа. Алгоритмы, в которых в зависимости от выполнения некоторого логического условия происходит разветвление вычислений по одному из нескольких возможных направлений, называют разветвляющимися. Подобные алгоритмы предусматривают выбор одного из альтернативных путей продолжения вычислений. Каждое возможное выполнение вычислений называется ветвью. Логическое условие называют простым, если разветвляющий процесс имеет две ветви, и сложным, - если процесс разветвляется на три и более ветви.

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

Наличие у одной задачи нескольких решений привело к появлению хар-ки алг-ма – сложность: временная и емкостная. n – размерность, тогда временная сложность функции одной переменной, Емкостная – функция одной переменной, которая каждой входной длине слова n ставит в соответствие объем памяти, используемой в процессе работы алгоритма.