Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: СРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ (АЛГОРИТМЫ).pdf

отдельное научное направление, изучающее информацию и информационные процессы, реализующее разработку и создание новых средств для работы с информацией;
практическая область деятельности людей, непосредственно связанная с использованием компьютеров при обработке информации [17].

Одним из направлений информатики как науки является программирование – наука, которая изучает теорию и методы разработки, производства и эксплуатации программного обеспечения ЭВМ [5].

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

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

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

Предметом исследования данной работы являются алгоритмы.

Объект исследования – основные структуры алгоритмов.

Целью работы является описание структур алгоритмов, а также их сравнение.

Для достижения поставленной цели предстоит решить ряд задач:

проанализировать литературу по заданной теме;
дать определения основным терминам;
раскрыть понятие алгоритма;
привести примеры различных структур алгоритмов и сравнить их друг с другом.

В качестве опорных источников при написании работы были использованы следующие: И.Г. Попова – «Программирование и алгоритмизация» и Н.М. Третьякова – «Turbo Pascal. Решение инженерных задач».

1. АЛГОРИТМЫ

1.1. История становления теории алгоритмов

Еще в конце XIX в. известный немецкий математик Д. Гильберт заметил, что математика представляет собой искусство называть разные вещи одинаковыми именами. Уже тогда понятие алгоритма было ключевым в этой науке. Алгоритмом всегда назывался некоторый единый общий метод решения бесконечного числа однотипных задач, представляющих собой массовую проблему. Другими словами, алгоритм – это решение конкретной задачи из класса подобных задач «в общем виде». К первым алгоритмам относятся алгоритмы арифметических действий. Затем они получили свое развитие не только в математике, но и в других науках. Однако было целое множество задач, решение которых не подчинялось алгоритмам. Лишь к 1930 г. была создана специальная наука – теория алгоритмов, объектом исследования которой стало понятие и свойства алгоритма. Первое формализованное определение алгоритма было предложено Э. Постом и А. Тьюрингом. Они описали точными математическими терминами некие идеализированные вычислительные машины, получившие впоследствии название «машины Тьюринга».

С развитием вычислительных устройств поднялся вопрос о практической выполнимости алгоритмов на реально существующих вычислительных устройствах в реально допустимое время. Данный факт явился предпосылкой создания теории вычислительной сложности алгоритмов, появившейся в 60-е годы прошлого века. Эта теория была призвана классифицировать алгоритмы в зависимости от их сложности. В дальнейшем теория сложности вычислений стала одной из центральных в теории алгоритмов [7].

1.2. Основные понятия

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

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

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

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

Характерные черты исполнителя алгоритма (см. рисунок 1):

Рисунок 1 – Характерные черты исполнителя алгоритма

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

Важно отметить, что исполнитель не вникает в смысл выполняемых им действий – его действия формальны, отвлечены от содержания поставленной цели и строго соответствуют алгоритму [4].

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

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

1.3. Формы представления

В настоящее время существует несколько форм записи алгоритмов (см. рисунок 2):

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

Рисунок 2 – Формы представления алгоритмов

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

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

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

Приведем пример записи алгоритма вычисления НОД двух чисел в построчной записи:

Ввод A, B
Если A = B, переход к шагу 8
Если A > B, переход к шагу 6
B = B – A
Переход к шагу 2
A = A – B
Переход к шагу 2
НОД = А
Вывод НОД
Конец

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

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

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

На территории нашей страны действует единая система программной документации (ЕСПД), сформировавшаяся в 1981 г. Данная система описывает условные графические изображения, которые применяются в алгоритмах (ГОСТ 19.003-80 «Схемы алгоритмов и программ. Обозначения условные графические»), а также набор правил, которые следуют соблюдать при записи блок-схем (ГОСТ 19.002-80 «Схемы алгоритмов и программ. Правила выполнения»).

На сегодняшний день существует целое множество программных продуктов, облегчающих построение блок-схем. К ним относятся такие программы, как Microsoft Visio, Dia, OpenOffice.org Draw и т.п.

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

Рисунок 3 – Блок ввода/вывода

Рисунок 4 – Вычислительный блок (блок обработки данных)

Рисунок 5 – Блок принятия решения (проверки условия)

Рисунок 6 – Блок начала/конца программы

Рисунок 7 – Блок начала цикла

Рисунок 8 – Блок конца цикла

Рисунок 9 – Ссылка

Рисунок 10 – Блок вызова подпрограммы

Рисунок 11 – Блок комментария

Существует ряд правил при работе с блок-схемами:

выполнение алгоритма всегда начинается с блока начала и заканчивается при попаданием на блок конца. Порядок вычислений при этом определяется стрелками между блоками;
блок обработки данных содержит описание только тех действий, которые должны быть выполнены над объектами при попадании на этот блок по входящей в него стрелке. В данном блоке принято вычислять значения каких-либо выражений и присваивать новые значения переменным;
блок принятия решения содержит запись логического условия. Результатом проверки является выбор одной из двух стрелок, которые соответствуют возможным дальнейшим направлениям вычислений;
блок ввода содержит переменные, значения которых вводятся в данном месте схемы;
блок вывода содержит переменные, значения которых выводятся в данном месте схемы;
комментарии применяются с целью пояснений, которые не могут быть помещены внутри блока;
очень часто в состав одних алгоритмов входят другие, уже известные алгоритмы. Для этого они помещаются в блок «переопределенный процесс» (блок вызова подпрограммы);
в случае больших размеров схем разрешается прерывать стрелки и использовать соединители [14].