Файл: Основные структуры алгоритмов сравнительный анализ и примеры их использования (ТЕОРЕТИЧЕСИКЕ АСПЕКТЫ ОСНОВНОЙ СТРУКТУРЫ АЛГОРИТМОВ).pdf

ВВЕДЕНИЕ

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

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

Актуальность исследования: проникновение понятия «алгоритм» в различные сферы жизни человека и примеры их использования.

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

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

Задачи исследования:

1. рассмотреть понятие и свойства алгоритмов

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

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

4. проектирование информационной системы подбора вакансий для выпускников технических вузов

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

Предмет исследования: разработка методов и алгоритмов подбора вакансий для выпускников ВУЗов.

Методы исследования: анализ литературных источников по проблеме исследования, сравнение, обобщение.

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

1. ТЕОРЕТИЧЕСИКЕ АСПЕКТЫ ОСНОВНОЙ СТРУКТУРЫ АЛГОРИТМОВ

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

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

Алгоритм — строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов[11].

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

Для выполнения алгоритма исполнителю недостаточно только самого алгоритма. Выполнить алгоритм — значит применить его к решению конкретной задачи, т. е. выполнить запланированные действия по отношению к определенным входным данным. Поэтому исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма.

Рис. 1.1 – Выполнение алгоритма [11]

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

Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов [4]:

• Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
• Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
• Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя [4].
• Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд [4].
• Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

Способы представления алгоритмов [7]:

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

1.2 Основные алгоритмические структуры

Большинство алгоритмических языков относится к так называемым процедурным языкам в которых основной единицей является оператор. Оператор представляет собой команду на выполнение некоторого действия. Язык таким образом состоит в основном из фраз в повелительном наклонении. Альтернативной операторамявляются описания, определяющие объекты или типы объектов и их взаимосвязи [15].

Всякий алгоритм предназначен исполнителю, который однозначно понимает команды алгоритма.

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

Строки алгоритма выполняются последовательно (считается, что исполнитель алгоритма способен не задумываясь выполнить каждую его команду) [2].

Большинство алгоритмов не сводится, однако, к последовательному выполнению команд, в них присутствуют ветвления и циклы. При ветвлении в зависимости от условия выполняется одна из ветвей программы; для этого используется оператор «если… то… иначе… конец если» [2].

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

Цикл пока — цикл с предусловием, поскольку условие продолжения цикла проверяется перед выполнением тела цикла, а не после него. Иногда используют циклы с постусловием (do … while), когда тело цикла всегда выполняется хотя бы 1 раз.

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

— Если условие

— то последовательность действий 1

— иначе последовательность действий 2

— конец если

Основные структуры алгоритмов — это ограниченный набор стандартных способов соединения отдельных блоков или структур для выполнения типичных последовательностей действий [9].

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

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

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

Если после проверки некоторого условия выбирается один из двух или более путей, вычислительного процесса и после выполнения любого из них вычислительный процесс опять сводится водно русло, то возникает разветвление [1].

Цикл до — применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия. Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, т.к. первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.

Тело цикла, — та последовательность действий, которая выполняется многократно, в цикле.

Цикл пока — отличается от цикла до тем, что проверка условия производится до выполнения тела цикла — такой цикл называется циклом по условию[5].

Обход — частный случай разветвления, когда одна ветвь не содержит никаких действий. Множественный выбор является обобщением разветвления, когда в зависимости от значения переменной выполняется ОДНО ИЗ нескольких действий.

Существует 3 типа основных алгоритмических структур [10]:

• следование;
• развилка;
• цикл.

Следование представляет собой последовательное выполнение операций и представляется алгоритмически последовательностью блоков «Процесс»:

Рис. 1.2 – Следование [10]

Развилка, в свою очередь, делится на [10]

• неполную развилку;
• полную развилку;
• ветвление.

 Развилка представляет собой блок выбора (проверка условия).
Неполная развилка выполняет последовательность операций только по одной из веток.

Рис. 1.3 – Неполная развилка [10]

Полная развилка выполняет последовательность операций по каждой из двух веток (при выполнении или невыполнении условия) [6]:

Рис. 1.4 – Полная развилка [10]

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

Рис. 1.5 – Ветвление [10]

Цикл [8]

Существует 3 основных вида циклов:

• цикл с предусловием;
• цикл с постусловием;
• параметрический цикл.

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

Рис. 1.6 - Цикл с предусловием [10]

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

Рис. 1.7 - Цикл с постусловием [10]

Параметрический цикл — это цикл с заданным числом повторений.

Рис. 1.8 - Параметрический цикл [10]

Таким образом, алгоритм — это последовательность команд управления каким-либо исполнителем.

Всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд.

Алгоритмы бывают [9]:

— линейные,

— разветвленные,

— циклические.

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

Разветвленный алгоритм содержит одно или несколько логических условий и имеет несколько ветвей обработки [3].

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