Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Алгоритм и его свойства. Способы записи алгоритма).pdf

ВВЕДЕНИЕ

В современном мире ни одно действие не обходится без алгоритмов. Так мы каждый день действуем по определенным алгоритмам в зависимости от той или иной ситуации.

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

Объект контрольной работы – это алгоритм и его виды. Предмет работы – возможность использования алгоритмов на практике.

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

1. Алгоритм и его свойства. Способы записи алгоритма

Термин «алгоритм» возник очень давно, первое упоминание о нем считается книга арабского математика IX века Аль-Хорезми «Algoritmic de numero Inndoru», что переводится как «Трактат Аль-Хорезми об арифметическом искусстве индусов»^[1]. Согласно данной книге алгоритм – это набор правил или действий, определяют процесс преобразования начальных данных задачи в искомый результат^[2].

К примеру, алгоритм для приготовления яичницы:

1. Взять сковородку.
2. Налить в него чайную ложку растительного масла.
3. Поставить на плиту.
4. Включить плиту на 50% мощности, подождать 5 минут.
5. Взять 4 яйца.
6. Разбить яйца в сковороду, скорлупу выкинуть в мусорное ведро.
7. Готовить пока яйца не прожарятся.
8. Яичница готова.

Даже из того простого алгоритма становится ясно, что алгоритм состоит из конечного числа действий, которые называются командами^[3]. Они выполняются строго последовательно, как указано в алгоритме. Все возможные команды, которые может сделать исполнитель, будем считать системой команд исполнителя.

Каждый алгоритм должен обладать рядом свойств, для того чтобы любой исполнитель мог, выполнив его получить результат^[4]. Перечислим свойства:

• Однозначность, под ней понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Для этого необходимо для записи алгоритма использовать систему команд исполнителя.
• Конечность, под ней понимается необходимость завершать каждый шаг алгоритма, и то, что алгоритм имеет конечное число шагов^[5].
• Результативность, под ней понимается, что выполнение всех шагов алгоритма обязательно приведет к определенному результату.
• Массовость, под ней понимается возможность использовать данный алгоритм для решения целого класса задач. Для этого необходимо использовать более общие фразы, и не использовать конкретные значения.
• Правильность, под ней понимается то, что выполнение алгоритма дает правильный результат^[6].
• Эффективность, под ней понимается, что для алгоритма необходимо использовать ограниченные ресурсы компьютера (место на жестком диске, в оперативной памяти, процессорное время, и т. д.).

Рассмотрим ранее приведенный пример и посмотрим удовлетворяет ли он всем свойствам алгоритмов (Таблица 1):

Таблица 1. Свойства алгоритма

Алгоритм можно задать различными способами:

• на естественном языке исполнителя, устно или письменно;
• в виде блок-схемы;
• на каком-либо языке программирования.

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

Иногда используют полуформальный язык с ограниченным словарём^[11] (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод^[12] удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования.

Псевдокод:

Алгоритм <название>

Начало

<последовательность действий>

Конец

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

В качестве базовых операций используются:

• операция присваивания вида

<переменная> := < выражение >

• операция ввода/вывода

ввод (список ввода)

вывод (список вывода).

Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах^[13] используют специальные графические символы^[14].

Составим алгоритм вычисления квадратного корня^[15] из произвольного положительного вещественного числа х в виде блок-схемы.

Блок-схема для решения данного рода задач будет выглядеть следующим образом:

Начало

Ввод вещественного числа х

Вычисление корня по формуле

Вывод результата

Конец

2. Классификация алгоритмов

Различают три типа базовых структур (рис. 1):

• Следование^[16]
• Развилка^[17]
• Цикл^[18]

Рис. 1. Классификация алгоритмов

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

Структура Развилка обеспечивает выбор одной из двух альтернатив: если < условие 1 > то

< действие 1 >

иначе

< действие 2 >

все

Существует сокращенная форма структуры Развилка, которая позволяет выполнить действие или пропустить его:

если < условие > то < действие >

все

Обобщением структуры Развилка является Множественный выбор:

если Var = Const1 то < действие 1 >

если Var = Const2 то < действие 2 >

если Var = ConstN то < действие N >

все

В зависимости от значения переменной Var^[19] выполняется одно из указанных действий, например, если Var = Const3, то выполняется < действие 3 >.

Третьей базовой структурой является Цикл, который предусматривает повторное выполнение определенных действий, необходимое для большинства программ. Различают следующие типы структур Цикл^[20]:

• цикл «от до»
• цикл «пока»
• цикл «до»

Цикл «от до» управляет повторением выполнения действия с помощью переменной цикла:

цикл от I:= N1 до N2

< действие >

кц

Здесь I - переменная цикла^[21], N1, N2 - начальное и конечное значения переменной цикла, вычисляются один раз при входе в цикл. Переменная цикла пробегает все следующие друг за другом в порядке возрастания значения от начального до конечного. Изменение значения переменной цикла происходит автоматически после каждого выполнения действия, указанного внутри цикла. В зависимости от соотношения N1 и N2 цикл может не выполниться ни разу (N1>N2) или выполниться (N2-N1+1) раз.

В цикле «пока»^[22] управление внутри цикла осуществляется с помощью логического условия:

цикл пока < условие>

< действие >

кц

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

Третий тип структуры цикл «до» имеет вид:

цикл

< действие > до < условие>

кц

Как только значение условия становится истинным^[23], цикл прекращается. Цикл “до“ независимо от значения условия выполнится по меньшей мере один раз, т.к. проверка условия производится после выполнения действия. Для завершения цикла необходимо внутри цикла изменить условие с ложного на истинное. Выбор структуры цикла^[24] определяется особенностями алгоритма решения конкретной задачи.

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

• линейные
• разветвляющиеся
• циклические.

2.1 Линейный алгоритм. Примеры

Линейным^[25] называется алгоритм, блоки которого расположены последовательно^[26] один за другим, нет условий и повторений. Покажем общую структуру линейного алгоритма в виде блок-схемы^[27] (Рис. 2.).

начало

Обработка данных

Ввод данных

Вывод результата

конец

Рис. 2. Блок-схема

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

Результат вычислений помещается в область S оперативной памяти^[28]. Чтобы вывести результат из памяти на экран монитора необходимо использовать оператор вывода.

2.2 Разветвляющийся алгоритм. Примеры

Алгоритм называется разветвляющимся^[29], если содержит хотя бы одно условие, в результате которого обеспечивается переход на один из двух возможных вариантов решения задачи. Ветвление может быть полным^[30] (действия и после да и после нет) и неполным (в случае если нет – ничего не происходит). Пример разветвляющегося алгоритма – алгоритм решения квадратного уравнения. Появление условия при решении этой задачи связано с отсутствием корней при отрицательном дискриминанте. Рассмотрим блок-схему этого алгоритма (Рис. 2):

начало

Ввод a,b,c