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

ВВЕДЕНИЕ

Практически в каждой минуте жизни любого человека, встречаются алгоритмы, которые часто повторяются. Например, заварить чай, завести автомобиль и поехать на прогулку, выйти погулять с собакой и ещё огромное количество подобного. При правильном подходе и взгляде многие алгоритмы можно заменить или сократить, что даст пару лишних секунд свободного времени. А время - самый ценный ресурс из всех существующих, возобновить который не представляется возможным даже для высшего истеблишмента нашего мира.
На данный момент в мире существует огромнейшее количество языков программирования, но большинство из них крайне схожи, и имеют различия только в синтаксисах команд и методе компиляции.
При помощи различных языков программирования присутствует возможность сокращения и упрощения алгоритмов, их автоматизации и улучшения.
Актуальность исследования обусловлена постоянным внедрением новых алгоритмов во все отрасли жизни, так же алгоритмы являются основными составляющими всех программ и одной из самых важных частей подготовки работников it-сферы.
Целью своей работы считаю изучить и понять типы, виды, свойства алгоритмов и возможности взаимодействия с их помощью. Выбирая источники я руководствовался авторитетностью издания, распространённостью и «наполненностью». Стараясь свести к минимум статьи-выдержки, я стараюсь использовать только объёмные и специализированные издания, в том числе учебники.
Языком программирования, который я буду использовать в практической части работы я выбрал C++, так как это самый распространённый и один из основных языков программирования.
Так же в данной работе я постараюсь раскрыть историю появления и развития понятия алгоритм, объяснить многие аспекты.




 

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

1.1 Понятие алгоритма
 

Алгоритм – набор предписаний, однозначно определяющий содержание и последовательность выполнения действий для систематического решения задачи. Для алгоритма можно выделить семь характеризующих его параметров: совокупность возможных исходных данных, совокупность возможных результатов, совокупность возможных промежуточных результатов, правило начала процесса обработки данных, правило непосредственно.[^[1]]

Понятие алгоритма относится к фундаментальным понятиям информатики, но ещё до существования информатики оно возникло в математике, став одним из основных её понятий.[^[2]]

Слово «алгоритм» происходит от имени узбекского Математика Мухаммеда аль-Хорезми (783–ок. 850 гг., рис. 1).[^[3]] В латинских переводах с арабского его арифметического трактата «ALgoritmi de numero Indorum» («Алгоритми о счете индийском»), где он излагал правила действия над числами в десятичной системе счисления, имя аль-Хорезми транскрибировалось как algorismi. В 1684 году Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…» впервые использовал слово «алгоритм» («algorithmo») в широком смысле: как систематический способ решения проблем дифференциального исчисления.
Рис.1. Портрет Мугаммад аль-Хорезми

Мугаммад аль-Хорезми является одним из крупнейших ученых средневековья, родина которого - Хорезм. Знания аль-Хорезми совершенствовались в ”Доме мудрости” в Багдаде. Исследователи установили, что аль-Хорезми был автором целых 9 сочинений:
Книга об индийской арифметике;

1. Краткая книга об исчислении алгебры и алмукабалы;
2. Астрономические таблицы (зидж);
3. Книга картины Земли;
4. Книга о построении астролябии;
5. Книга о действиях с помощью астролябии;
6. Книга о солнечных часах;
7. Трактат об определении эры евреев и их праздниках;

9. Книга истории.
Сочинение аль-Хорезми об арифметике сыграло очень важную роль в истории математики и хоть его арабский подлинный текст со временем был утерян, содержание ныне известно по латинскому переводу XII в. В этом сочинении впервые дано систематическое изложение арифметики, основанной на десятичной позиционной системе счисления с применением нуля, т.е. та арифметика, которая в наши дни представляется столь естественной и обычной. Она возникла в индии, и поэтому аль-Хорезми, а вслед за ним и другие средневековые математики называли её индийской. Долгое время она не выходила за пределы Индии, и только благодаря книге аль-Хорезми эта арифметика получила широкое распространение в странах Ближнего и Среднего Востока, а затем и в европе. [^[4]]
Алгебраическая книга аль-Хорезми (Китаб мухтасаб ал-джабр и ва-л-мукабала) состоит из двух частей – теоретической (теория решения линейных и квадратных уравнений, некоторые вопросы геометрии) и практической (применение алгебраических методов в решении хозяйственно-бытовых, торговых и юридических задач – дележ наследства, составление завещаний, раздел имущества, различные сделки, измерение земель, строительство каналов). Благодаря арабскому слову «ал-джабр» возник такой научный термин как «алгебра». Унаследованное от восточных математиков

учение о линейных и квадратных уравнениях стало основой развития алгебры в Европе. [^[5]]

Algorithmi – латинское транскрипция его фамилии, это слово применялось для обозначения правил по таким арифметическим действиям:

– деление;

– умножение;

– вычитание;

– сложение. [^[6]]

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

Так же аль-Хорезми сделал очень весомый вклад в астрономию написав трактат “Зидж аль-Синдх”, в котором содержались таблицы движения Солнца, луны, и пяти известных планет. Так же, его латинизированное имя вошло в историю как термин “алгоритм”.[^[7]] Так же
 Аль-Хорезми усовершенствовал часы и изобрел квадрант, используемый для измерения углов

Алгоритм – фундаментальное понятие программирования. Специалисты обычно выделяют 3 основных класса алгоритмов:

– информационные;

–управляющие
–вычислительные.
[^[8]]
Общая Теория алгоритмов занимается проблемой эффективной вычислимости. Разработано несколько формальных определений алгоритма, в которых эффективность и конечность вычислений может быть определена количественно – числом элементарных шагов и объемом требуемой памяти. Подобными моделями алгоритмических преобразований символьной информации являются:
-конечные автоматы;
-машина Тьюринга;
-машина Поста;
- ассоциативное исчисление или нормальные алгоритмы Маркова; - рекурсивные функции. Некоторые из этих моделей лежат в основе методов программирования и используются в алгоритмических языках. В современной программной инженерии алгоритмы, как методы решения задач, занимают ведущее место по сравнению с традиционной математикой. Причем не важно, существует или нет чистое алгоритмическое решение в абстрактных моделях алгоритмов. Если решение задачи необходимо, широко используется эвристика, а “доказательством” работоспособности алгоритма является успешное его тестирование.[^[9]]

 

1.2 Свойства алгоритмов

Любые алгоритмы вне зависимости от их типа обладают такими свойствами:
1)Дискретность: алгоритм должен представлять пpоцесс pешения задачи как последовательное выполнение элементарных шагов; для выполнения каждого шага требуется конечный отрезок времени.
2)Детерминированность (Однозначность). Каждое действие (шаг, этап) должно быть четким, однозначным, исключающим произвольное толкование и не оставляющим места для двусмысленности. Выполнение алгоритма носит, по сути, механический характер и не требует никаких дополнительных указаний[^[10]]
3) Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов.
4) Конечность. Каждое отдельное действие, как и весь алгоритм должны иметь возможность реального исполнения. Поэтому алгоритм имеет предел, т. е. конечен.
5) Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма[^[11]].
6) Ясность – это понимание исполнителя алгоритма о том, что нужно сделать для выполнения поставленного алгоритма.
7)Формальность– это когда результат выполнения алгоритмов не должен зависеть от любого рода факторов, что не являются частью рассматриваемого алгоритма.
Все исполнители, способные воспринимать и выполнять некоторые указания алгоритма (даже при этом не понимая их), действуя по нему, могут выполнить поставленную ранее задачу.
Абсолютно все шаги алгоритма должны быть четко и понятно описан и определен. Также он не должен допускать собственной и произвольной трактовки конечным исполнителем.

























2.Базовые структуры алгоритмов

2.1.Методы описания алгоритмов

Для доведения сути алгоритма к конечному пользователю, алгоритм обязан быть формализованным по принятым ныне правилам конкретных изобразительных или же графических средств.
Выбор способа записи зависит от характера задачи. Алгоритм вычислительного характера можно записать формулой, последовательностью формул. Алгоритм заваривания чая удобно записать словами в пронумерованных пунктах. Алгоритм решения квадратного уравнения будет наиболее понятен при записи словами и формулами.
Из формальных способов записи алгоритмов чаще других будем использовать язык блок-схем и алгоритмический язык. Заметим, что программа так же является записью алгоритма на языке программирования. [^[12]]
Блок-схема представляет собой графический документ, дающий представление о порядке работы алгоритма. Здесь предписания изображаются с помощью различных геометрических фигур, а последовательность выполнения шагов указывается с помощью линий, соединяющих эти фигуры. Направления линий связи слева направа и сверху вниз считаются стандартными, и линии связи изображаются без стрелок, в противоположном случае - со стрелками.[^[13]] Псевдокод же представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками.
С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. [^[14]]
Блок схемы записываются подобным образом:

Рис. 2 Блок ввода-вывода данных

Блок ввода-вывода данных. Надпись в блоке: слово «ввод» («вывод» или «печать») и список вводимых (выводимых) переменных.

Рис. 3 Блок ввода-вывода данных
Блок ввода-вывода данных(Рис. 3). Надпись в блоке: слово «ввод» («вывод»или «печать») и список вводимых (выводимых) переменных.[^[15]]

Рис. 4 Предопределенный процесс

Символ "Предопределенный процесс" (рис. 4) отображает алгоритм, схема которого раскрыта отдельно. Этот тип символа позволяет описывать схемы алгоритмов иерархически и, таким образом, снизить сложность каждой отдельной схемы, повысив ее наглядность


Так же для использования блок-схем для более сложных и точных алгоритмов используется еще большее количество блоков, описанное в ГОСТ 19.701-90

Псевдокод же изображается подобным образом:

Выбираем первый элемент( i=1)

IF A> xi или хi > B THEN

печать сообщения и переход на конец

ELSE

переход к следующему элементу( i = i +1 )

IF массив не кончился ( i <= n ) THEN

переход на проверку интервала

ELSE

печать сообщения, что все элементы входят в интервал

Конец [^[16]]

Самым популярным методом изображения алгоритмов являются языки программирования.

Языки программирования — искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов). Совокупность подобных требований образует синтаксис языка программирования, а смысл каждой команды и других конструкций языка — его семантику.[^[17]]

В самом общем смысле языком программирования называется фиксированная система обозначений и правил для описания алгоритмов и структур данных. Все языки программирования делятся на языки низкого, высокого и сверхвысокого уровня.[^[18]]

С некоторыми из них умеют пользоваться лишь пара десятков разработчиков, которые используют эти языки программирования в штучных вариантах промышленных машин, вычислительных устройств, специфических механизмах и других схожих вещах. Другие же языки программирования – известны многим миллионам людей. Высококлассные и опытные разработчики программ иногда применяют больше десятка самых различных языков программирования.
На более “глубоких” уровнях, называемых в простонародье - “железе”, т.е. в процессоре, используется машинный язык. Язык программирования превращается в машинный язык при помощи компиллятора. Компилятор — это такой транслятор, который переводит программу на некотором языке программирования в машинный код
Машинный язык (machine language) — язык, который определяется структурой аппаратных средств компьютера и может быть непосредственно воспринят ими. Программа на машинном языке записывается в двоичных кодах.[^[19]] Машинный вид команды для программы, состоящий из обозначений «0» и «1», указывает на то, именно какое действие должен выполнить центральный процессор в своей работе.
Парадигмами программирования в форме языков и систем программирования представлено знание о потенциале ИТ. В момент создания язык программирования отражает некий прогноз относительно области приложения ИТ. Практика разработки и применения систем программирования конкретизирует и уточняет такое знание в форме отлаженных программ с комплектами данных для них и прецедентами успешного их применения[^[20]]

Рассмотрим классификацию языков программирования по парадигме программирования. Абсолютно все языки делятся на следующие категории: