Теория алгоритмов

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

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

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

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

Циклический алгоритм – это конечная последовательность указаний (команд), позволяющая конечное количество повторений определённого действия (операции) над новыми исходными данными до осуществления некоторого условия.

Основные свойства алгоритма:

· дискретность, то есть алгоритм должен состоять из отдельных действий исполнителя,

· упорядоченность, то есть действия должны иметь определённый порядок исполнения,

· детерминированность, то есть выполнение алгоритма должно обеспечивать неизменный результат при его применении к одинаковому набору исходных данных,

· формальность, то есть алгоритм должен обеспечивать однозначность понимания исполнителем действий и содержать только те команды, которые исполнитель может исполнить,

· конечность, то есть работа алгоритма должна завершаться за конечное время и за конечное число шагов,

· результативность, то есть выполнение алгоритма должно обеспечивать решение поставленной задачи и обеспечивать получение определённого результата,

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

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

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

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

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

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

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

Ветвление – это алгоритмическая структура, которая осуществляет вычисление и проверку определённого условия и, в зависимости от результата проверки (условие выполняется или нет), обеспечивает выбор одного из альтернативных путей работы алгоритма. Обозначение ветвления выполняется с помощью структурного блока в форме ромба, внутри которого помещается описание проверяемого условия. Структурный блок имеет один вход, как правило, в верхней вершине ромба, и один или несколько выходов из оставшихся вершин. Выходов может быть больше трёх, тогда они отображаются одной линией, которая выходит из нижней вершины структурного блока и затем разветвляется. Альтернативные пути работы, обеспечиваемые ветвлением, называются ветви алгоритмической структуры. Выбор ветви зависит от результата проверки условия на входе ветвления (ветвь ДА означает, что условие выполняется, а ветвь НЕТ, означает, что условие не выполняется) и исходных данных. Все ветви имеют общий выход из ветвления. Алгоритмическая структура ветвление имеет разновидности: неполная развилка, полная развилка, выбор, полное ветвление.

Неполная развилка – это разновидность алгоритмической структуры ветвление, которая имеет один вход и два выхода. Ветвь, которая соответствует выполнению условия (ДА), обеспечивает выполнение определённого действия или конечной последовательности действий, а другая ветвь (НЕТ), обеспечивает продолжение выполнения основного алгоритма без выполнения каких-либо действий. Иначе неполная развилка называется ветвление если-то или if.

Полная развилка – это разновидность алгоритмической структуры ветвление, которая имеет один вход и два выхода. Ветвь, которая соответствует выполнению условия (ДА), обеспечивает выполнение определённого действия или конечной последовательности действий, а другая ветвь (НЕТ), обеспечивает выполнение альтернативного определённого действия или альтернативной конечной последовательности действий. После выполнения действий или конечной последовательности действий по одной из ветвей, полная развилка обеспечивает продолжение выполнения основного алгоритма. Иначе полная развилка называется ветвление если-то-иначе или if-else.

Выбор – это разновидность алгоритмической структуры ветвление, которая имеет один общий вход, позволяющий последовательно осуществлять проверку определённых условий, причём проверка каждого последующего условия выполняется в случае невыполнения предыдущего условия (следование по ветви НЕТ предыдущего структурного блока). Как только проверка выявляет выполнение условия какого–либо структурного блока, то ветвь, которая соответствует выполнению данного условия (ДА), обеспечивает выполнение определённого действия или конечной последовательности действий, после чего обеспечивается продолжение выполнения основного алгоритма без проверки выполнения всех последующих условий. В случае если ни одно из условий не выполняется (следование по ветвям НЕТ всех структурных блоков), то выполняется действие или конечная последовательность действий по умолчанию, после чего обеспечивается продолжение выполнения основного алгоритма. Алгоритмическая структура выбор допускает отсутствие действий по умолчанию, в этом случае, если ни одно из условий не выполняется (следование по ветвям НЕТ всех структурных блоков), то обеспечивается продолжение выполнения основного алгоритма без выполнения каких-либо действий. Иначе выбор называется ветвление выбор или switch.

Цикл – это алгоритмическая структура, которая обеспечивает возможность многократного выполнения определённого действия или конечной последовательности действий до выполнения некоторого условия, заданного циклом. Многократно повторяемое действие или конечная последовательность действий называются тело цикла. Тело цикла повторяется каждый раз для новых исходных данных. Количество повторений тела цикла зависит от условия цикла. Обозначение цикла выполняется с помощью структурных блоков в форме прямоугольников с обрезанными углами в верхней (начало цикла) или нижней части (конец цикла), внутри одного их которых помещается условия цикла (начала, изменения данных, завершения цикла). Цикл имеет один вход и один выход из цикла, который обеспечивает продолжение выполнения основного алгоритма после выполнения некоторого условия, заданного циклом. Алгоритмическая структура цикл имеет разновидности: цикл с предусловием, цикл с постусловием, параметрический цикл.

Цикл с предусловием – это разновидность алгоритмической структуры цикл, которая осуществляет проверку условия цикла перед началом выполнения тела цикла. Тело цикла каждый раз выполняется с изменёнными исходными данными, пока выполняется условие, записанное в начале цикла. Условие цикла проверяется перед каждым повторением цикла, как только оно перестаёт выполняться, то повторение определённого действия или конечной последовательности действий прекращается, цикл завершается, и обеспечивается продолжение выполнения основного алгоритма. Цикл с предусловием может не выполниться ни одного раза, если условие начала цикла не прошло первоначальную проверку. Иначе цикл с предусловием называется цикл пока  или while.

Цикл с постусловием – это разновидность алгоритмической структуры цикл, которая осуществляет проверку условия цикла после выполнения тела цикла в первый раз. Тело цикла каждый раз выполняется с изменёнными исходными данными, пока выполняется условие, записанное в конце цикла. Условие цикла проверяется после каждого повторения цикла, как только оно перестаёт выполняться, то повторение определённого действия или конечной последовательности действий прекращается, цикл завершается, и обеспечивается продолжение выполнения основного алгоритма. Цикл с постусловием выполниться хотя бы один раз, до прохождения первоначальной проверки. Иначе цикл с постусловием называется цикл до  или do.

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