Цикл типа «пока» 2. Цикл типа «до»

Тема 2. Алгоритмы

Алгоритмы, их свойства и средства описания

Алгоритм - четкая система правил, которые задают последовательность действий над некоторыми объектами и после конечного числа шагов приводят к достижению поставленной цели. Всякий алгоритм рассчитан на определенного исполнителя (организация, человек, автомат, компьютер). Выполнимый алгоритм должен представлять собой последовательность предписаний для конкретного исполнителя.

Любой алгоритм должен обладать следующими свойствами:

- дискретность - пошаговый характер определяемого алгоритмом процесса.

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

- результативность - возможность получения результата через конечное число шагов.

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

Существуют следующие способы описания алгоритмов:

- запись на естественном языке;

- запись на алгоритмическом языке;

- изображение в виде блок-схем алгоритмов;

- запись на языке конкретной системы программирования.

Основные понятия теории алгоритмов. Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Понятие «алгоритма» сформировалось в математике в 20-х годах ХХ века. Началом систематической разработки теории алгоритмов можно считать 1936 г. (работа А. Черча).

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

Результатами теоретических исследований явились три основных класса арифметических моделей:

- первый класс – основан на арифметизации алгоритмов, предполагается, что любые данные можно закодировать числами, и как следствие - всякое их преобразование становится в этом случае арифметическим вычислением, алгоритмом в таких моделях есть вычисление значения некоторой числовой функции, а его элементарные шаги - арифметические операции. Последовательность шагов определяется двумя способами. Первый способ - суперпозиция, т.е. подстановка функции в функцию, а второй - рекурсия, т.е. определение значения функции через «ранее» вычисленные значения;

- второй класс – для того, чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина, к которой предъявляются требования простоты и универсальности. Одной из таких машин явилась абстрактная машина Тьюринга;

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

Базовые управляющие структуры алгоритмов

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

- следование (цепочка);

- разветвление (развилка);

- повторение (цикл).

Следование.

Указывает естественный порядок выполнения действий в той последовательности, в которой они записаны (рис.4). На содержание действий, входящих в цепочку, не накладывается каких либо ограничений, в частности, допускается обращение к внешнему фрагменту алгоритма при условии возвращения в ту же точку.

Простейшая форма разветвления - альтернатива (рис. 6, а), где есть два возможных пути, и выбор одного из них зависит от того, верно или неверно некоторое логическое условие. «Серия» представляет собой цепочку действий, причем серия 2 может не содержать никаких действий (рис. 6, б).

Часто приходится выбирать не из двух, а из нескольких возможностей, что приводит к задаче многозначного ветвления, которая может быть решена путем последовательного вложения структуры «если…то…иначе» в такую же структуру.

Циклический алгоритм (повторение). Используется для задания многократного повторения действий.Существует три разновидности циклов:

а) бесконечный цикл (рис. 8) используется в области процессов реального времени, операционных системах и т.д.

действия должны повторяться до тех пор, пока выполняется некоторое условие, зависящее от переменных программы. На практике используются два варианта такой управляющей структуры (рис.9):

Цикл типа «пока» 2. Цикл типа «до»