Алгоритмы и структуры данных

Курс лекций
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Курс лекций

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


Алгоритм - это точное предписание, определяющее вычислитель­ный процесс, ведущий от варьируемых начальных данных к искомому результату.
ЭВМ в настоящее время приходится не только считывать и выпол­нять определенные алгоритмы, но и хранить значительные объемы ин­формации, к которой нужно быстро обращаться. Эта информация в не­котором смысле представляет собой абстракцию тогог или иного фраг­мента реального мира и состоит из определенного множества данных, относящихся к какой-либо проблеме.
Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассмат­риваемые в виде последовательности битов, имеют очень простую органи­зацию или, другими словами, слабо структурированы. Для человека опи­сывать и исследовать сколько-нибудь сложные данные в терминах после­довательностей битов весьма неудобно. Более крупные и содержательные, чем бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».
Под структурой данных в общем случае понимают множество эле­ментов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каж­дой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, которая со­ответствует различным аспектам их рассмотрения. Прежде чем присту­пать к изучению конкретных структур данных, дадим их общую клас­сификацию по нескольким признакам (рис. 1).
Понятие «физическая структура данных» отражает способ физичес­кого представления данных в памяти машины и называется еще струк­турой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета ее представления в ма­шинной памяти называется абстрактной или логической структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим струк­турам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физи­ческой структуре данных. Кроме того, в зависимости от размещения физических структур, а соответственно, и доступа к ним, различают внутренние (находятся в оперативной памяти) и внешние (на вне­шних устройствах) структуры данных.
Различаются элементарные (простые, базовые, примитивные) структуры данных и составные (интегрированные, композитные, сложные). Элементарными называются такие структуры дан­ных, которые не могут быть расчленены на составные части, боль­шие, чем биты. С точки зрения физической структуры важным явля­ется то обстоятельство, что в конкретной машинной архитектуре, в конкретной системе программирования всегда можно заранее ска­зать, каков будет размер элементарного данного и каково его разме­щение в памяти. С логической точки зрения элементарные данные являются неделимыми единицами.
Составными называются такие структуры данных, составными частями которых являются другие структуры данных - элементарные или в свою очередь составные. Составные структуры данных конструи­руются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
Важный признак составной структуры данных - характер упорядо­ченности ее частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.
Весьма важный признак структуры данных - ее изменчивость, т. е. изменение числа элементов и/или связей между составными час­тями структуры. В определении изменчивости структуры не отра­жен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По

признаку изменчивости различают структуры статические и дина­мические.
В языках программирования понятие «структуры данных» тесно свя­зано с понятием «типы данных». Любые данные, т. е. константы, пере­менные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет:

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

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


В процессе решения прикладных задач выбор подходящего алгорит­ма вызывает определенные трудности. Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям:
1) быть простым для понимания, перевода в программный код и отладки;
2) эффективно использовать вычислительные ресурсы и выполнять-
ся по возможности быстро.
Если разрабатываемая программа, реализующая некоторый алгоритм, должна выполняться только несколько раз, то первое требование наи­более важно. В этом случае стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если решение за­дачи требует значительных вычислительных затрат, то стоимость вы­полнения программы может превысить стоимость написания програм­мы, особенно если программа выполняется многократно. Поэтому бо­лее предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее). Таким образом, прежде чем принимать решение об использо­вании того или иного алгоритма, необходимо оценить сложность и эф­фективность этого алгоритма.
^ Сложность алгоритма - это величина, отражающая порядок вели­чины требуемого ресурса (времени или дополнительной памяти) в за­висимости от размерности задачи.
Таким образом, будем различать временную T(n) и пространствен­ную V(n) сложности алгоритма. При рассмотрении оценок сложности будем использовать только временную сложность. Пространственная сложность оценивается аналогично.
Самый простой способ оценки - экспериментальный, т. е. запрограм­мировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программы. Однако этот способ име­ет ряд недостатков. Во-первых, экспериментальное программирование -это, возможно, дорогостоящий процесс. Во-вторых, необходимо учитывать, что на время выполнения программ влияют следующие факторы:

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

  2. качество скомпилированного кода исполняемой программы;

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

Наличие второго и третьего факторов не позволяют применять ти­повые единицы измерения временной сложности алгоритма (секунды, миллисекунды и т.п.), так как можно получить самые различные оцен­ки для одного и того же алгоритма, если использовать разных програм­мистов (которые программируют алгоритм каждый по-своему), разные компиляторы и разные вычислительные машины.
Существует метод, позволяющий теоретически оценить время вы­полнения алгоритма, который и рассмотрим далее.
Часто, временная сложность алгоритма зависит от количества входных данных. Обычно говорят, что временная сложность алгоритма имеет поря­док T(n) от входных данных размера n. Точно определить величину T(n) на практике представляется довольно трудно. Поэтому прибегают к асимпто­тическим отношениям с использованием O-символики.
Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 11n2 + 19n-log n + 3n + 4, то это алгоритм, для которого T(n) имеет порядок O(n2). Фактически, из всех слагаемых оставляется только то, которое вносит наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь), и игнори­руется коэффициент перед ним.
Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до посто­янного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи рас­тет не быстрее, чем квадрат количества элементов.
Для примера приведем числа, иллюстрирующие скорость роста для нескольких функций, которые часто используются при оценке времен­ной сложности алгоритмов (см. табл. 1).

Если считать, что числа соответствуют микросекундам, то для зада­чи с 1048476 элементами алгоритму со временем работы T(log n) потре­буется 20 микросекунд, а алгоритму со временем работы T(n2) - более 12 дней.
Если операция выполняется за фиксированное число шагов, не за­висящее от количества данных, то принято писать O(1).
Следует обратить внимание, что основание логарифма здесь не пи­шется. Причина этого весьма проста. Пусть есть O(log

2

n). Но l0g

2

n = = l0g

3

n/l0g

3

2, а l0g

3

2, как и любую константу, символ О() не учитывает. Таким образом, O(l0g

2

n) = O(l0g

3

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

Теоретическая оценка временной сложности алгоритма осуществля­ется с использованием следующих базовых принципов:
1) время выполнения операций присваивания, чтения, записи обычно имеют порядок O(1). Исключением являются операторы присваивания, в которых операнды представляют собой массивы или вызовы функций;

  1. время выполнения последовательности операций совпадает с наи­большим временем выполнения операции в данной последовательнос­ти (правило сумм: если T

    j

    (n) имеет порядок O(fn)), а T

    2

    (n) - порядок O(g(n)), то T

    j

    (n) + T2(n) имеет порядок O(max(f(n), g(n)) );

  2. время выполнения конструкции ветвления (if-then-else) со­стоит из времени вычисления логического выражения (обычно имеет порядок O(1) ) и наибольшего из времени, необходимого для выполне­ния операций, исполняемых при истинном значении логического выра­жения и при ложном значении логического выражения;

  3. время выполнения цикла состоит из времени вычисления условия прекращения цикла (обычно имеет порядок O(1) ) и произведения ко­личества выполненных итераций цикла на наибольшее возможное вре­мя выполнения операций тела цикла.

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

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

1. ^ СТРУКТУРЫ ДАННЫХ


1.1. Элементарные данные


Данные элементарных типов представляют собой единое и неде­лимое целое. В каждый момент времени они могут принимать толь­ко одно значение. Набор элементарных типов в разных языках про­граммирования несколько различаются, однако есть типы, которые поддерживаются практически везде. Рассмотрим их на примере язы­ка Паскаль:
var
i, j: integer; x: real; s: char; b: boolean; p: pointer;
Здесь объявлены переменные i, j целочисленного типа, x - веще­ственного, s - символьного, b - логического типа и p - указатель.
К данным элементарных типов можно обращаться по их именам: i := 46; x := 3.14; s := 'А'; b := true;

^ 1.1.1. Данные числовых типов


1.1.1.1. Данные целочисленного типа
С помощью целых чисел может быть представлено количество объек­тов, являющихся дискретными по своей природе (т. е. счетное число объектов).
Диапазон возможных значений целых типов зависит от их внутрен­него представления, которое может занимать 1, 2 или 4 байта. В табл. 2 приводится перечень целых типов, размер памяти для их внутреннего представления в битах, диапазон возможных значений.

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

1.1.1.3. Операции над данными числовых типов
Над числовыми типами, как и над всеми другими возможны прежде всего, четыре основных операции: создание, уничтожение, выбор, об­новление. Специфическими операциями над числовыми типами явля­ются арифметические операции: сложение, вычитание, умножение, де­ление. Операция возведения в степень в некоторых языках также явля­ется базовой и обозначается специальным символом или комбинацией символов, в других - выполняется встроенными функциями.
Следует обратить внимание на то, что операция деления по-разному выполняется для целых и вещественных чисел. При делении целых чисел дробная часть результата отбрасывается, как бы близка к 1 она ни была. В связи с этим в языке Паскаль имеются даже разные обозначения для деле­ния вещественных и целых чисел - операции «/» и «div» соответственно. В других языках оба вида деления обозначаются одинаково, а тип деления определяется типом операндов. Для целых операндов возможна еще одна операция - остаток от деления (в языке Паскаль операция «mod»).
Еще одна группа операций над числовыми типами - операции срав­нения > <, =, . Существенно, что хотя операндами этих опера­ций являются данные числовых типов, результат их имеет логический тип - «истина» или «ложь». Говоря об операциях сравнения, следует обратить внимание на особенность выполнения сравнений на равен­ство/неравенство вещественных чисел. Поскольку эти числа представ­ляются в памяти с некоторой (не абсолютной) точностью, сравнения их не всегда могут быть абсолютно достоверны.
Поскольку одни и те же операции допустимы для разных числовых типов, возникает проблема арифметических выражений со смешением типов. В реальных задачах выражения со смешанными типами встреча­ются довольно часто. Поэтому большинство языков допускает выраже­ния, операнды которых имеют разные числовые типы, но обрабатыва­ются такие выражения в разных языках по-разному. В одних языках все операнды выражения приводятся к одному типу, а именно к типу той переменной, в которую будет записан результат, а затем уже выражение вычисляется. В других (например, язык Си) преобразование типов вы­полняется в процессе вычисления выражения, при выполнении каждой отдельной операции, без учета других операций; каждая операция вы­числяется с точностью самого точного участвующего в ней операнда.

mezhdunarodnoe-chastnoe-pravo-stranica-3.html
mezhdunarodnoe-chastnoe-pravo-stranica-4.html
mezhdunarodnoe-chastnoe-pravo-stranica-6.html
mezhdunarodnoe-chastnoe-pravo-stranica-7.html
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат