Алгоритмы и структуры данных в решении экономических задач

Учебное пособие для студентов бакалавриата

 

Иркутск Издательство БГУЭП 2013

УДК 004.421(075.8)

ББК 73я7

П31

 

Печатается по решению редакционно-издательского совета Байкальского государственного университета экономики и права

 

 

Рецензенты канд. экон. наук, доц. Т. И. Хитрова

канд. экон. наук, ст. преп. М. Ю. Неустроев

 

Работа выполнена при финансовой поддержке проекта ФБ-40

«Современные информационно-телекоммуникационные технологии в управлении социально-экономическими и технологическими процессами» (шифр заявки 8.8274.2013).

 

Пешкова О. В.

П31       Алгоритмы и структуры данных в решении экономических задач: учеб. пособие для студентов бакалавриата / О. В. Пешкова. – Иркутск: Изд-во БГУЭП, 2013. – 137 с.

 

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

 

ББК 73я7

 

© Пешкова О. В., 2013

© Издательство БГУЭП, 2013

ОГЛАВЛЕНИЕ

Введение........................................................................................................ 4

1. Основные понятия алгоритмизации..................................................... 6

1.1. Этапы решения задач на компьютере................................................. 6

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

1.3. Способы записи алгоритма............................................................... 14

1.4. Основные понятия, используемые при разработке алгоритма....... 16

1.5. Графический способ записи алгоритма............................................ 18

2. Структурная организация данных..................................................... 24

2.1. Основные понятия структур данных................................................ 24

2.2. Классификация структур данных по признаку изменчивости......... 26

2.3. Линейные и нелинейные структуры данных..................................... 27

3. Структурный подход к разработке алгоритмов............................... 33

3.1. Типы алгоритмических процессов.................................................... 33

3.2. Реализация алгоритмов линейных процессов.................................. 34

3.3. Алгоритмизация ветвящихся процессов........................................... 38

3.4. Реализация циклических процессов.................................................. 47

3.5. Циклы с известным числом повторений........................................... 53

3.6. Итерационные циклы......................................................................... 71

4. Алгоритмы обработки массивов......................................................... 77

4.1. Организация работы с массивами..................................................... 77

4.2. Преобразование одномерных массивов........................................... 78

4.3. Сложные циклы.................................................................................. 88

4.4. Алгоритмы сортировки..................................................................... 93

4.5. Алгоритмы преобразования двумерных массивов........................ 100

5. Декомпозиция задачи.......................................................................... 116

5.1. Механизм передачи данных............................................................ 117

5.2. Декомпозиция алгоритмов.............................................................. 122

Приложение. Элементы языка АЯРН..................................................... 133

Список рекомендуемой литературы..................................................... 136

ВВЕДЕНИЕ

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

Понятие алгоритма, относящееся к фундаментальным концепциям ин- форматики, возникло задолго до появления ПЭВМ. Алгоритмы с IX века и до настоящего времени используются в математике для обозначения правил вы- полнения четырех арифметических действий: сложения, вычитания, умножения и деления. На протяжении многих веков люди интуитивно пользовались алго- ритмами нахождения корней квадратного уравнения, расчета площади квадрата или круга, определения объема куба, цилиндра, конуса. В настоящее время сфера применения этого понятия существенно расширена. Об алгоритмах гово- рят при обсуждении процессов управления производством, проблем принятия решений или выполнения некоторых технологических операций.

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

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

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

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

- познакомиться со всем разнообразием имеющихся структур данных;

- рассмотреть основные операции, которые выполняются при решении экономических задач;

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

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

ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМИЗАЦИИ