Структуры данных и эффективность алгоритмов. 4
![]()
|
ОглавлениеСтруктуры данных и эффективность алгоритмов. 4 Построение модели задачи. Процедурная абстракция и абстракция данных. 9 1.1. Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.] 24 Наихудшее и среднее время работы. 25 Пример 4. Рассмотрим вычисление полинома 30 Входными переменными служат коэффициенты и неопределенная переменная х Выходной переменной будет значение полинома р. 30 1) для n=1, 30 2) для п=2, 30 Существует простая модификация модели неветвящихся программ, которая соответствует логарифмической весовой функции. Эта модель, называемая битовым вычислением, по существу, является той же неветвящейся программой, но только в ней 31 1) все переменные принимают значения 0 или 1, т. е. это биты, 31 2) используются логические операции вместо арифметических (and обозначается через &, or — через . exclusive or — через , not — через —). 31 Можно было бы не ограничивать значения переменных символами 0 и 1, а разрешить переменным принимать в качестве значения любой вектор из 0 и 1. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАМ, т. е., когда это удобно, просто разрешаются регистры неограниченного размера. 31 Асимптотические обозначения. 32 Сложность задач и нижние оценки. 35 Труднорешаемые задачи и NP-полнота. [8, 4 гл.34.] 45 1.1. Типы данных и структуры данных. 56 2. Абстрактные типы данных. 57 2.1. Последовательность (Sequence). [13 гл.4,5,11.1; 7 п.2.1-4; 3 гл.3-4; 4 п.10.1-3.] 59 2.2. Множество (Set). [7 гл.4.1-4; 13 п.10.2; 2 гл.4.] 61 2.3. Словарь (Dictionary, Map), другое название – ассоциативный массив [7 п.4.5-8; 3 гл.12; 2 п.4.10; 13 гл.8.]. 62 2.4. Очередь с приоритетом (Priority queue). [7 п.4.10-11, п.5.6; 3 гл.9; 4 п.6.5; 2 п.4.10-13; 13 гл.7.] 62 2.5. Непересекающиеся множества (Disjoint Sets, Partitions, Разбиения) [7 п.5.5; 4 гл.21; 2 п.4.6-8.]. 63 2.6. Деревья, графы и отношения общего вида. [13 гл.6,12; 7 гл.3, п.4.12, гл.6-7; 3 гл.17.] 63 3. Структуры данных как способы представления АТД. 65 3.1. Линейные структуры данных. 66 3.2. Графы 73 3.3. Деревья. 74 Поисковые деревья (search tree). [13 гл.9] 80 Splay-дерево [19 п.4.3; 3 п.13.2] 84 Деревья цифрового (позиционного) поиска (Digital Search Trees, Trie Trees). [7 п.5.3; 3 гл.15.; 13 п.11.3] 86 Пирамиды (heap), другое название – сортирующее (или частично упорядоченное) дерево. [4 гл.6,19-20] 87 Структуры данных для непересекающихся множеств (отношения эквивалентности). [4 гл.21] 89 3.4. Рандомизированные структуры данных. 89 Хеш-таблицы. [4 гл.11; 3 гл.14; 7 п.4.7-8] 90 Случайная балансировка бинарных поисковых деревьев. [3 п.13.1] 90 Списки пропусков (Skip Lists). [13 п.8.6; 3 п.13.5] 91 Декартово дерево (Treap). [4 гл.13 Задачи 13-4; 20] 91 Введение. Как, столкнувшись с некоторой задачей, построить хороший алгоритм для нее? Имеется ли «исчисление структур данных», с помощью которого можно выбрать подходящее представление данных и метод для решения данной задачи? Что делает одну структуру данных лучшей по сравнению с другой для некоторого приложения? Известные результаты призывают лежащую в их основе теорию объяснить их. Это, возможно, одна из проблем, требующих наибольшего внимания среди проблем, с которыми сталкиваются исследователи в алгоритмической сложности. Тарьян Роберт Эндре. Сложность комбинаторных алгоритмов. [1] Вопросы построения хороших алгоритмов для задач являются одними из центральных в программировании. В этом месте уместным является вопрос: а что понимается под словом хороший? Известно, что для любой задачи существует множество программных реализаций, которые отличаются временем выполнения, объемом используемой памяти, длиной программного кода и т.д. При этом эти показатели, очень часто коррелируют друг с другом и выбор оптимального варианта решения является достаточно сложной задачей. К примеру, наиболее быстрое вычисление функции ![]() Как выясняется, задача построения хорошего алгоритма (оптимального с точки зрения расходования ресурсов) напрямую связана с выбором подходящей структуры данных для хранения информации, представленной в задаче. |