23. Файлы. В-деревья. Представление файлов в-деревьями.

B-дерево представляет собой дерево поиска степени m, характеризующееся следующими свойствами:

1) корень либо является листом, либо имеет не менее двух потомков;

2) каждый узел, кроме корня и листьев, имеет от (m/2) до m потомков;

3) все пути от корня до любого листа имеют одинаковую длину. (рис)

24. Файлы. В-деревья. Основные операции.

Основные операции, производимые с B-деревьями:

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

– добавление элемента; В общем виде алгоритм добавления элемента Item в B-дерево можно описать следующей последовательностью действий:

1. Поиск среди листьев вершины Node, в которую следует произвести добавление элемента Item.

2. Добавление элемента Item в вершину Node.

3. Если Node содержит больше, чем NumberOfItems элементов (произошло переполнение), то:

– делим Node на две вершины, не включая в них средний элемент;

– Item := средний элемент Node;

– Node := Node.PreviousNode;

– переходим к пункту 2.

– удаление элемента; Удаление элемента из B-дерева предполагает успешный предварительный поиск вершины, содержащей искомый элемент. Если такая вершина не найдена, то удаление не производится.

25. Файлы. В-деревья. Общая оценка в-деревьев.

B-деревья являются хорошим средством программно ускорить доступ к данным.

Ярким примером практического применения B-деревьев является файловая система NTFS, где B-деревья применяются для ускорения поиска имен в каталогах.

B-деревья обладают прекрасным качеством: во всех трех операциях над данными (поиск/удаление/добавление) они обеспечивают сложность порядка O(h), где h – глубина дерева. Это значит, что чем больше узлов в дереве и чем сильнее дерево ветвится, тем меньшую часть узлов надо будет просмотреть, чтобы найти нужный элемент.

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

Одно из усовершенствований было предложено Р. Бэйером и Э. Мак-Крэйтом и заключалось в следующем. Если вершина дерева переполнена, то прежде чем расщеплять эту вершину, следует посмотреть, нельзя ли «перелить» часть элементов соседям слева и справа. При использовании такой методики уменьшается общее количество расщеплений и увеличивается коэффициент использования памяти.

26. NP-сложные и труднорешаемые задачи.

Для оценки сложности алгоритма используется О-символика.

На основе этой оценки можно привести следующую классификацию алгоритмов, при размере входных данных, равном n:

– постоянные – сложность не зависит от n: O(1);

– линейные – сложность О(n);

– полиномиальные – сложность O(nm), где m – константа;

– экспоненциальные – сложность O(tf(n)), где t – константа, которая больше 1, а f(n) – полиномиальная функция;

– суперполиномиальные – сложность O(сf(n)), где с – константа, а f(n) – функция возрастающая быстрее постоянной, но медленнее линейной;

Простые задачи (решаемые) – это задачи, решаемые за полиномиальное время.

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

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

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

1) класс P – класс задач, которые можно решить за полиномиальное время;

2) класс NP – класс задач, которые можно решить за полиномиальное время только на недетерминированной Машине Тьюринга, которая в отличие от обычной Машины Тьюринга может делать предположения. Это задачи, у которых есть ответ, найти который трудно, но проверить можно за полиномиальное время;

3) класс NP-полных задач – класс задач, не менее сложных, чем любая NP-задача;

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

5) класс EXPTIME-полных задач – класс задач, которые не решаются за детерминированное полиномиальное время. Известно, что P <> EXPTIME.