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

1. Теоретические основы алгоритмов

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

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

Понятие «алгоритма» появилось в Европе в средние века, когда у европейских ученых появилась книга средневекового математика Мухаммеда бен Муса Аль Хорезми [17, c. 9].

Его родина - древнее государство Хорезм, город Хивы. Хорезми занимал территорию, которая сейчас находится на территории современных Узбекистана (Хорезмская и Каракалпакская области) и Туркменистана (Ташаузская область).

Условно датами рождения и смерти Аль Хорезми считаются 783 и 850 годы. В некоторых книгах Аль Хорезми назван Аль Маджуси, то есть маг. Отсюда многие исследователи делают вывод, что предки Аль Хорезми были жрецами зороастрийской религии.

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

В первой половине XII века книга Аль Хорезми в латинском переводе проникла в Европу («Algoritmi de numero Indorum» («Индийское искусство счёта, сочинение Аль Хорезми»).

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

Конечно, слово «аль-хорезми» не очень похоже на слово «алгоритм», но это издержки греческого перевода. (Al - Gorethmi - так это примерно было написано по-гречески).

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

В учебнике «Информатика и информационные технологии» дано следующее определение алгоритма: «Алгоритм - понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату» [18, c. 32].

В современной информатике и математике этот термин имеет еще и такие определения:

---

- последовательность действий, в которой строго определены правила выполнения;

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

- точное описание какого-либо вычислительного процесса или любой другой последовательности действий;

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

Словарь Ожегова дает такое определение алгоритма: алгоритм – это «совокупность действий, правил для решения данной задачи» [11, c. 97].

В ГОСТ 33707-2016 (ISO/IEC 2382:2015) «Информационные технологии (ИТ). Словарь» понятие алгоритма расписывается так: алгоритм – это «конечное упорядоченное множество точно определенных правил для решения конкретной задачи» [1].

В ГОСТ 34.003-90 «Информационная технология (ИТ). Комплекс стандартов на автоматизированные системы. Автоматизированные системы» уточняется, что алгоритм – это «конечный набор предписаний для получения решения задачи посредством конечного количества операций» [2].

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

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

Цель же, в свою очередь, является достижением желаемого результата.

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

Перечень команд, воспринимаемых и выполняемых (по возможности) исполнителем, называют системой команд.

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

В качестве примера алгоритма можно вспомнить известный всем со школы арифметический способ сложения двух положительных чисел «столбиком». Алгоритм данной задачи представим в виде системы следующих действий [9, c. 13]:

- выделим в слагаемых разряды единиц и сложим единицы;

- при получении суммы меньшей 10 запишем ее в разряде единиц под нижним числом;

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

---

- сложим десятки и т. д.

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

Понятие алгоритма в теорию и практику обучения вошло в конце 50-х годов прошлого столетия в связи с развитием программированного обучения и применением обучающимися машин.

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

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

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

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

Существует ряд определенных требований к алгоритмам. Перечислим некоторые важные свойства, которыми должен обладать каждый алгоритм [5, c. 5].

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

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

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

4) Конечность означает, что решение задачи необходимо получить за конечное число шагов.

5) Определенность означает, что компьютеру понятны лишь определенные и однозначные инструкции.

---

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

Эффективность алгоритма определяют с учетом потребляемых ресурсов компьютера, к которым относят быстродействие (количество выполняемых операций и затраты трудоемкости на каждую из них) и общий объем оперативной памяти, которая выделяется под данные. Приведенные показатели могут иногда быть противоречивыми: так в результате повышения быстродействия могут потребоваться дополнительные расходы памяти и наоборот [6, c. 39].

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

Специалистами предлагается ряд мер для повышения эффективности.

1.2. Способы описания алгоритмов

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

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

При записи алгоритмов решения задач можно применять изобразительные способы, представленные в виде [14, c. 67]:

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

Запись алгоритмов осуществляется по общей методике [14, c. 68]:

1. Любому алгоритму присваивается имя, раскрывающее его смысл.

2. Обозначаются начало и конец алгоритма.

3. Описываются входные и выходные данные.

4. Указываются команды, позволяющие выполнять определенные действия над выделенными данными.

Таким образом, алгоритм имеет общий вид, состоящий из следующих разделов:

• названия;
• описания данных;
• начала;
• команд;
• конца.

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

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

---

у = 2а - (х + 6).

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

1.Ввести значения а и х.

2.Сложить х и 6.

3.Умножить а на 2.

4.Вычесть из 2а сумму (х+6).

5.Вывести у как результат вычисления выражения.

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

Все этапы вычислительного процесса представляются в виде геометрических фигур (блоков) [16, c. 110].

Между блоками начала и конца алгоритма размещаются остальные блоки алгоритма.

Операторный блок (блок действия) содержит команды обработки данных.

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

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

Порядок выполнения этапов указывают стрелками, которые соединяют блоки. Размещение геометрических фигур выполняется слева направо и сверху вниз. Нумеруют блоки в порядке их размещения в схеме.

Перечисленные выше блоки приведены в Приложении 1 [16, c. 96].

Рассмотрим пример. Алгоритм целочисленных преобразований представлен в виде фрагмента блок-схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1. Необходимо определить результат работы алгоритма для исходных данных Х = 7, Y = 12 (Приложение 2.) [16, c. 100]

Проведем решение.

1. Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).

2. В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».

3. Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».

4. Вычисляется результат выполнения алгоритма: X := 0, Y := 1.

Ответ: X := 0, Y := 1.

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

---