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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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].

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

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

2.ПРИМЕР ИСПОЛЬЗОВАНИЯ АЛГОРИТМОВНА ПРИМЕРЕ ПОДБОРА ВАКАНСИЙ ДЛЯ ВЫПУСКНИКОВ ВУЗОВ

2.1 Требования к алгоритмам подбора вакансий

Исходя из анализа потребностей заинтересованных сторон для обеспечения функций поиска и подбора актуальных вакансий для выпускников и студентов ВУЗов необходимо разработать следующие алгоритмы:

1. Алгоритм расчета значимости дисциплины в формировании конкретной компетенции.
2. Алгоритм расчета освоения компетенций в соответствии с оценками в дипломе (зачетной книжке).
3. Алгоритм семантического представления матрицы компетенций выпускника (студентов).
4. Алгоритм семантического представления описания требований работодателя к кандидатам на вакансию.

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

2.2Разработка метода расчета значимости дисциплины в формировании компетенции

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

Для примера рассмотрим ПК-3: «Способность разрабатывать технические задания по проектам на основе профессиональной подготовки и системно-аналитических исследований сложных объектов управления различной природы», в нее входят 5 дисциплин: Интеллектуальные технологии и представление знаний, Управление научно-исследовательскими и опытно-конструкторскими работами, Основы изобретательства и технической инноватики, Методология и практика институционального управления, Управление проектами. На основе экспертных оценок автор выставил оценки и составил матрицу:

Таблица 2.1 - Матрица анализа иерархий для ПК-3

В качестве экспертов выступили преподаватели, студенты и работодатели.

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

_ij (1)

(2)

После нормировки представим результаты в процентах и возьмем общую сумму за 100%.

Таблица 2.2 - 2я матрица анализа иерархий для ПК-3

Теперь, допустим, что после аттестации студент набрал следующие баллы по каждой дисциплине. (табл.2.3)

Таблица 2.3 - Аттестация студента по дисциплинам, входящим в ПК-3

Интеллектуальные технологии и представление знаний	4
Управление научно-исследовательскими и опытно-конструкторскими работами	3
Основы изобретательства и технической инноватики	5
Методология и практика институционального управления	5
Управление проектами	5

Вычислим процент ОТ ДО освоения респондентом компетенции ПК-3 по следующей формуле:

, (3)

Где А_n- вес дисциплины n, Х_n- баллы по дисциплине n, Q- процент освоения компетенции n. Тогда получим следующие результаты освоения компетенции ПК-3(табл.2.4)

Таблица 2.4 - Расчет освоения ПК-3

15.97%	4	12.78%
41.70%	3	25.02%
9.17%	5	9.17%
12.10%	5	12.10%
21.07%	5	21.07%
100%		80%

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

Рис.2.1 - Результат освоения ПК-3

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

Рис.2.2 – Результат освоения всех компетенций

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

2.3 Разработка алгоритма семантического представления матрицы компетенций выпускника

На рисунке 2.3 представлена концепция алгоритма семантического представления матрицы компетенций выпускника.

Рис. 2.3 – Алгоритм семантического представления матрицы компетенций выпускника.

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

Составление таблицы соответствия дисциплин компетенциям без учета весов.
Комментарий. Как сказано во введении работы у нормативных актов ВУЗов, а конкретно в РУП каждой дисциплины указанно в формировании каких компетенций она учувствует. Но если речь идет об оценки знаниевой составляющей каждой компетенции необходимо провести обратное соответствие, а именно для каждой компетенции составить список участвующих в ее формировании дисциплин.

Таблица соответствия без учета весов является входной информацией для шага 2.

Расчет матрицы для компетенций на основании экспертных оценок.

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

2.4Разработка алгоритма семантического представления описания требований работодателя к кандидатам на вакансию

На рисунке 2.4 представлена концепция алгоритма выделения семантического образа вакансии.

Рис.2.4 -Алгоритм выделения семантического образа вакансии

2.5Алгоритм поиска наиболее подходящей вакансии на основании компетенций

На рисунке 2.5 представлена концепция алгоритмапоиска вакансий.

Рис. 2.5 -Алгоритм поиска вакансий

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

3.ПРОЕКТИРОВАНИЕ ИНФОРМАЦИОННОЙ СИСТЕМЫ ПОДБОРА ВАКАНСИЙ ДЛЯ ВЫПУСКНИКОВ ТЕХНИЧЕСКИХ ВУЗОВ

3.1Анализ требований стейкхоледеров к проектируемой системе

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

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

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

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

3.2Проектирование архитектуры системы

Концептуальная архитектура взаимодействия модулей системы представлена на рисунке 3.1. RESTfulAPI позволит максимально удобно использовать паттерн асинхронности и использованию http-статусов для описания всевозможных прецедентов использования и поведения системы. Так же это удобно для управления разработкой и дальнейшего развития системы.

GatewayAPI позволяет описать систему, как набор микросервисов, что также удобно для масштабируемости, более того позволяет в рамках развития функционала развивать паттерн повторного использования, что значительно сокращает трудоемкость доработок. Интеграционный слой на уровне БД снимает нагрузку с сервера приложений.

Рис.3.1 – Концептуальная архитектура ИС

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

Рис.3.2 - Общая архитектура проектного решения

Где

- XML файлы для пополнения базы данных

- Базы данных

- Логика, исполняемая на серверной стороне

- Аттестация студента

- Оценка релевантности

- Список наиболее подходящих кандидатов на вакансию

Взаимодействие модулей системы также отражено на диаграмме взаимодействия рисунок 3.3.

Рис. 3.3 - Диаграмма взаимодействия модуля систем

3.3 Разработка прототипов графического интерфейса системы

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

Рис. 3.4 - Карта сайта

Макет стартовой страницы с возможными переходами на информационные страницы, представлен на рисунке 3.5.

Рис. 3.6- Концепция стартовой страницы

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

— линейные,

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

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

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

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

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

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

Исходя из анализа потребностей заинтересованных сторон для обеспечения функций поиска и подбора актуальных вакансий для выпускников и студентов ВУЗов были разработаны следующие алгоритмы:

1. Алгоритм расчета значимости дисциплины в формировании конкретной компетенции.
2. Алгоритм расчета освоения компетенций в соответствии с оценками в дипломе (зачетной книжке).
3. Алгоритм семантического представления матрицы компетенций выпускника (студентов).
4. Алгоритм семантического представления описания требований работодателя к кандидатам на вакансию.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Ахо Альфред В. Структуры данных и алгоритмы: Вильямс / пер. с английского и ред. Минько А. А., Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. — М. и др.: Вильямс, 2011. – 382 с.
2. Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Бином. Лаб. знаний, 2016. – 319 с.
3. Апанасевич С.А. Структуры и алгоритмы обработки данных. Линейные структуры: учебное пособие - Издательство «Лань» - 2019 
4. Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2019. - 240 с
5. Воробьева, А. П. Основы информатики: учеб. пособие / А. П. Воробьева, Л. А. Литвинов; под ред. Л. А. Литвинова; Новосиб. гос. архитектур.-строит. ун-т (Сибстрин). – Новосибирск: НГАСУ (Сибстрин), 2019. – 136 с.
6. Вирт Н. Алгоритмы и структуры данных с примерами на Паскале. – СПб.: Невский диалект, 2015. – 410с.
7. Вирт Никлаус. Алгоритмы и структуры данных: Нев. Диалект / Вирт Никлаус, [перевод с английского Д. Б. Подшивалова] — 2-е изд., испр. — СПб.: Нев. Диалект, 2011. — 351с.
8. Гагарина Л.Г. Алгоритмы и структуры данных: учеб. Пособие / Л.Г. Гагарина, В.Д. Колдаев. – М.: Финансы и статистика; ИНФРА-М, 2019. – 304 с.
9. Красиков, И.В. Алгоритмы. Просто как дважды два / И.В.Красиков, И.Е. Красико-ва,- 2-е изд.- М.: Эксмо, 2017 — 256 с.
10. Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Издательский дом «Вильямс», 2016. – 576 с.
11. Макконнелл Дж. Основы современных алгоритмов. 2-е изд., доп. – М.: Техносфера, 2014. – 368 с.
12. Макконелл, Дж. Анализ алгоритмов. Вводный курс / Дж. Макконелл,- М.: Техно-сфера, 2012,- 304 с.
13. Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд. – СПб.: БХВ-Петербург, 2011. – 720 с.
14. Столяр С.Е., Владыкин А.А. Информатика: Представление данных и алгоритмы. – СПб.: Невский Диалект; М.: БИНОМ. Лаборатория знаний, 2011. – 382 с.
15. Хусаинов, Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си / Б.С. Хусаинов — М.: Финансы и статистика, 2014 — 464 с.