0

Министерство образования Российской Федерации

Московский государственный университет
приборостроения и информатики

Структуры и алгоритмы обработки данных

(Анализ эффективности алгоритмов)

Учебное пособие

Москва 2009

УДК 681.3

Филатов В.В.

Структуры и алгоритмы обработки данных (Анализ эффективности алгоритмов) – М.:МГУПИ, 2009. – 36 с.

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

Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Методы программирования» студентами различных форм обучения, проходящих подготовку по специальностям 230105 и 090105.

Рецензенты:

Утверждено:

Содержание

Структуры и алгоритмы обработки данных 1

Введение 4

1 Основные сведения 5

1.1 Понятия алгоритма и структуры данных 5

1.2 Понятия сложности и эффективности алгоритмов и структур данных 9

1.3 Асимптотические обозначения 12

1.3.1 Асимптотически точная оценка функции роста 12

1.3.2 - и - обозначения 14

1.3.3 и обозначения 15

1.3.4 Свойства асимптотических функций 17

1.3.5 Сложение и умножение в O-символике 21

1.3.6 Ограниченность показателя функции роста 22

1.3.7 Основные классы эффективности 23

1.3.8 Принципы анализа эффективности нерекурсивных алгоритмов 25

1.3.9 Примеры анализа алогритмов 28

1.3.10 Формулы, использующиеся анализе алгоритмов 32

Литература 35

Русскоязычные ресурсы InterNet 36

Введение

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

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

Во втором разделе приводятся описания различных структур данных и основных операций над ними. Рассмотрены простые и сложные (составные) типы данных, линейные и нелинейные структуры, а также файлы.

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

Материал учебного пособия базируется на следующих дисциплинах: «Информатика», «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика»

.

1Основные сведения

1.1Понятия алгоритма и структуры данных

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

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

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

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

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

3. набор допустимых операций, которые применимы к объекту описываемого типа.

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

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

Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов или операций определенных в рамках данной модели. Операции АТД реализуют функциональное назначения математической модели.

Абстрактному типу данных соответствует понятие класса в объектно-ориентированном программирование (ООП). Как известно, класс состоит свойств и методов класса. Свойства представляют собой совокупность переменных для описания объекта предметной области, а методы – набор допустимых операций над ним, реализованных в рамках данного класса.

К АТД применимы понятия инкапсуляции, абстрагирования (обобщение) и наследования парадигмы ООП:

1. Абстракция или обобщение в том смысле, что АТД можно рассматривать как обобщение понятия типа данных.

2. Наследование применимо в том смысле, что одни абстрактные типы данных могут быть описаны на основе АТД, реализация которых уже осуществлена в базовых АТД.

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

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

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

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

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

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

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

Важный признак составной структуры данных – характер упорядоченности ее составных частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.

Классификация структур данных по вышеназванным признакам приведена ниже (см. Рисунок 1).

Весьма важный признак структуры данных – ее изменчивость, то есть изменение числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические.

Рисунок 1. Классификация структур данных

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

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

1.2Понятия сложности и эффективности алгоритмов и структур данных

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

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

2. эффективно использовать вычислительные ресурсы и выполняться по возможности быстро.

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

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