Лекции по информатике

Основные понятия теории алгоритмов

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

Термин «алгоритм» – транскрипция имени великого узбекского математика Мухаммеда аль-Хорезми, который в IX веке разработал правила выполнения четырех действий арифметики. Однако не следует считать алгоритм чисто математическим понятием. Например, при разговоре по телефону мы действуем по определенному алгоритму, и никому не приходит в голову побеседовать с абонентом, не набрав его номер.

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

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

- массовостью, позволяющей получать результат при различных исходных данных;

- результативностью, обеспечивающей получение результата через конечное число шагов.

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

Элементарной структурной единицей любого алгоритма является простая команда, обозначающая один элементарный шаг переработки или отображения информации, в процессе выполнения которого происходит изменение некоторых величин. Например, присвоить переменной X значение 528 (X=528) или вычислить Y=(A³+5)/C. Объектами действий в алгоритмах являются числа (45; 0,03189; -8.675), простые переменные (A; y; betta; d5s) и переменные с индексами (X₂₃; p₁₂).

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

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

Графическое представление хода решения задачи является самым наглядным способом записи алгоритма.

В качестве примера рассмотрим схему упрощенного алгоритма для решения квадратного уравнения.

Задание: составить алгоритм вычисления действительных корней уравнения ax² + bx + c = 0.

Исходные данные: a > 0, b > 0, c > 0.

Схема алгоритма показана на рисунке 1.

Вначале по заданным значениям a, b и с вычисляется дискриминант D. Потом значение D проверяется: если оно меньше нуля, выдается сообщение «решения нет»; если оно больше или равно нулю, вычисляется квадратный корень из дискриминанта, а затем значения двух корней уравнения x₁ и x₂.

Запись алгоритма на алгоритмическом языке, ориентированном на человека (псевдокоды), выполняется с помощью служебных слов и команд, которые записываются в сокращенном виде. Запись начинается со служебного слова алгоритм (АЛГ), за которым записывается его краткое название и определяются типы используемых величин. Далее перечисляются аргументы (АРГ) и результаты (РЕЗ). Команды, определяющие действия, записываются между служебными словами начало (НАЧ) и конец (КОН). Команды управления ходом вычислений начинаются служебными словами: ЕСЛИ, ТО, ИНАЧЕ, ЦК (цикл), КЦ (конец цикла), ПОКА. Команды друг от друга отделяются точкой с запятой.

Алгоритм решения квадратного уравнения, записанный в псевдокодах, имеет следующий вид:

АЛГ Решение квадратного уравнения

АРГ a,b,c,D,d; РЕЗ x₁,x₂;

НАЧ;

Вычислить D=b²–4•a•c;

ЕСЛИ D>=0;

ТО Вычислить d =; Вычислить x₁=(–b+d)/2•a; Вычислить x₂=(–b-d)/2•a;

КОН;

ИНАЧЕ Вывести сообщение: РЕШЕНИЯ НЕТ;

КОН

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

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

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

Согласно этой блок-схеме в зависимости от результата проверки условия выполняются только действия ветви «да» (действия 1 и 2) или только ветви «нет» (действия 3 и 4). В алгоритме решения квадратного уравнения на рис.1 происходит разветвление после проверки условия D>=0. В общем случае число ветвей может быть больше двух.

3. Алгоритм циклической структуры (повторение) – алгоритм, содержащий многократно выполняемые участки вычислительного процесса, называемые циклами. Внутри одного цикла могут размещаться один или несколько других.

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

Предположим, что рассмотренный выше (рис.1) алгоритм решения квадратного уравнения используется в качестве стандартной подпрограммы. Тогда достаточно присвоить ей имя и записать его в блок обращения к подпрограмме.

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

Содержание