Оглавление

Структуры данных и эффективность алгоритмов. 3

Построение модели задачи. Процедурная абстракция и абстракция данных. 8

1.1. Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.] 24

Наихудшее и среднее время работы. 25

Пример 4. Рассмотрим вычисление полинома 29

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

1) для n=1, 29

2) для п=2, 29

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

1) все переменные принимают значения 0 или 1, т. е. это биты, 30

2) используются логические операции вместо арифметических (and обозначается через &, or — через . exclusive or — через , not — через —). 30

Можно было бы не ограничивать значения переменных символами 0 и 1, а разрешить переменным принимать в качестве значения любой вектор из 0 и 1. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАМ, т. е., когда это удобно, просто разрешаются регистры неограниченного размера. 30

Асимптотические обозначения. 30

Сложность задач и нижние оценки. 34

Труднорешаемые задачи и NP-полнота. [8, 4 гл.34.] 43

1.1. Типы данных и структуры данных. 54

2. Абстрактные типы данных. 55

2.1. Последовательность (Sequence). [13 гл.4,5,11.1; 7 п.2.1-4; 3 гл.3-4; 4 п.10.1-3.] 57

2.2. Множество (Set). [7 гл.4.1-4; 13 п.10.2; 2 гл.4.] 58

2.3. Словарь (Dictionary, Map), другое название – ассоциативный массив [7 п.4.5-8; 3 гл.12; 2 п.4.10; 13 гл.8.]. 60

2.4. Очередь с приоритетом (Priority queue). [7 п.4.10-11, п.5.6; 3 гл.9; 4 п.6.5; 2 п.4.10-13; 13 гл.7.] 60

2.5. Непересекающиеся множества (Disjoint Sets, Partitions, Разбиения) [7 п.5.5; 4 гл.21; 2 п.4.6-8.]. 61

2.6. Деревья, графы и отношения общего вида. [13 гл.6,12; 7 гл.3, п.4.12, гл.6-7; 3 гл.17.] 61

3. Структуры данных как способы представления АТД. 63

3.1. Линейные структуры данных. 64

3.2. Графы 71

3.3. Деревья. 72

Поисковые деревья (search tree). [13 гл.9] 78

Splay-дерево [19 п.4.3; 3 п.13.2] 82

Деревья цифрового (позиционного) поиска (Digital Search Trees, Trie Trees). [7 п.5.3; 3 гл.15.; 13 п.11.3] 84

Пирамиды (heap), другое название – сортирующее (или частично упорядоченное) дерево. [4 гл.6,19-20] 84

Структуры данных для непересекающихся множеств (отношения эквивалентности). [4 гл.21] 87

3.4. Рандомизированные структуры данных. 87

Хеш-таблицы. [4 гл.11; 3 гл.14; 7 п.4.7-8] 87

Случайная балансировка бинарных поисковых деревьев. [3 п.13.1] 88

Списки пропусков (Skip Lists). [13 п.8.6; 3 п.13.5] 88

Декартово дерево (Treap). [4 гл.13 Задачи 13-4; 20] 89

Введение.

Как, столкнувшись с некоторой задачей, построить хороший алгоритм для нее? Имеется ли «исчисление структур данных», с помощью которого можно выбрать подходящее представление данных и метод для решения данной задачи? Что делает одну структуру данных лучшей по сравнению с другой для некоторого приложения?

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

Тарьян Роберт Эндре. Сложность комбинаторных алгоритмов. [1]

Вопросы построения хороших алгоритмов для задач являются одними из центральных в программировании. В этом месте уместным является вопрос: а что понимается под словом хороший? Известно, что для любой задачи существует множество программных реализаций, которые отличаются временем выполнения, объемом используемой памяти, длиной программного кода и т.д. При этом эти показатели, очень часто коррелируют друг с другом и выбор оптимального варианта решения является достаточно сложной задачей. К примеру, наиболее быстрое вычисление функции связано с простым выбором значения этой функции по значению аргумента в заданной таблице значений. Однако табличный способ задания связан с большим зачастую неоправданным расходом памяти. Алгоритмический вариант решения задачи может значительно сократить объем памяти одновременно с увеличением времени решения. Кроме того эмпирическое сравнение на различных тестах не дает ясного ответа на вопрос какой из алгоритмов лучше. Показатели работы могут вести себя различным образом на различных тестовых примерах. Если нужно сделать обоснованный выбор между двумя алгоритмами для решения одной задачи, то необходима более систематическая информация о сложности этих алгоритмов[1]. Эта информация должна не зависеть от языка реализации, от компьютера на котором выполняются программы. Хорошие алгоритмы имеют тенденцию оставаться хорошими даже если они написаны на различных языках программирования и выполняются на различных машинах. Кроме того вводимые меры сложности должны поддаваться теоретическому изучению.

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