Основные признаки структуры данных (1-70)

1. Основные признаки структуры данных: 1. возможные множество допустимых значений; 2. характер отношений м/у данными; 3. операции над данными. Математически структуру данных можно определить S= (D,R), где D - множество данных, R –множество отношений. Типы отношений: -одного к одному; -отношения одного ко многому; -отношения многих ко многим. Основные операции: -поиск; -вставка; -удаление. Структуры данных - совокупность элементов данных, м/у которыми существуют определенные отношения, причем элементами данных может быть, как простые данные, так и структуры данных. Различают: - логические и физические. Логические - структуры данных без учета представления их в памяти. Физические – отражает способ физического представления данных машиной и осуществляется с помощью функции адресации. Дескриптор (заголовок) – существует для запоминания структуры и ее параметра. Алгоритм, необходимо: 21. знать с какой структурой работает алгоритм; 2. качество. Сложность алгоритма: временная и емкостная; n – количество данных; Типы сложности алгоритма: 1. логарифмическая O(log (n)); 2. линейная O(n); 3. полиномиальная O( a n ) a=const; 4. экспоненциальная O( n a ). Классификация структур данных: 1) – оперативные (для оперативной памяти); – внешние (для внешней памяти); 2) В зависимости от наличия заданных связей: - несвязанные (векторы, массивы, строки); - связанные (связанные списки); 3) изменчивость структуры в процессе выполнения программ: - статические (размеры и взаимоотношения структуры не меняются); - полустатические (меняются только размеры); - динамические (меняются и размеры и связи м/у элементами); 4) По характеру упорядоченности: - линейные; - нелинейные (связыв. различные куски памяти с помощью указателя).
2. Абстрактный тип данных - это множество абстрактных объектов, представляющих элементы данных, и определенные на нем наборы операций, которые могут быть выполнены над элементами этого множества. Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Конечно, это весьма удобно и позволяет добиться большей модульности программы. Пример. Для автоматизированного управления температурой в различных комнатах большого здания полезным АТД был бы ТЕРМОСТАТ. В программе может быть много переменных типа ТЕРМОСТАТ, соответствующих реальным термостатам в различных помещениях здания. АТД может быть описан своим именем, множеством значений и допустимыми операциями так же, как и любой другой тип данных. АТД — это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями. В языке программирования такое определение оформляется как специальная синтаксическая конструкция, называемая в разных языках капсулой, модулем, кластером, классом, пакетом, формой и т.д. Эта конструкция в самой развитой форме содержит: спецификацию типа данных, включающую описание интерфейса (имя определяемого типа, имена операций с указанием их профилей) и абстрактное описание операций и объектов, с которыми они работают, некоторыми средствами спецификации; реализацию типа данных, включающую конкретное описание тех же операций и объектов. Реализация АТД включает конкретное описание объектов определяемого типа и реализацию операций этого типа.
3. Статические структуры включают: векторы, массивы, записи, таблицы. Вектор, одномерный массив – конечное упорядоченное множество структур данных одного и того же типа. Физическая структура вектора представляется в машинной памяти последовательностью одинаковых по длине участков памяти, называемых полями или слотами, каждый из которых предназначен для хранения одного элемента вектора. Слот может иметь размер минимальной адресуемой ячейки памяти или соответствовать целой группе последовательных ячеек памяти. Операции над структурами: - доступ к элементу; - определение размера структур; - описание типов элемента. Массив – вектор, каждый элемент которого вектор. В свою очередь элементы вектора тоже могут быть векторами (многомерные массивы). Преобразование логической структуры массива в физическую структуру может быть выполнено многими способами. Однако, на практике, обычно используют только два способа: отображение строками и отображение столбцами. Частный случай массива – разреженный массив, большинство элементов – 0. В этом случае - хранить только ненулевые элементы в виде связного списка. Запись - конечное упорядоченное множество элементов с различным типом данных, т.е. обобщение вектора (не требуется однотипность или однородность). Запись: - простая; - многоуровневая. Элементы записи - поля. Доступ к любому элементу записи осуществляется с помощью имени, которое должно задаваться для каждого элемента на этапе описания логической структуры записи. Дескриптор записи может содержать имя записи, число входящих элементов, имена и типы элементов, длины соответствующих полей, указатели значений элементов. Таблица - конечное множество записей, имеющих одну и ту же организацию. Запись, входящая в таблицу – элемент таблицы. Таблица представляет собой такое обобщение понятия двухмерного массива, в котором свойство однотипности элементов массива требуется лишь для элементов, расположенных в одном и том же столбце. Доступ к каждому элементу таблицы осуществляется не с помощью индексов, а с помощью ключа, причем целью служит не отдельное данное, а целая запись. Операции: включение данных о новом элементе, поиск заданного элемента и исключение заданного элемента из таблицы. Св-ва статических структур: 1. постоянство структуры в течении всего времени ее существования; 2. смежность элементов и непрерывность области памяти, отводимой сразу для всех элементов структуры; 3. простота и постоянство отношений между элементами структуры, позволяющие исключить информацию об этих отношениях и хранить ее в компактной форме в дескрипторах.
4. Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняется только с одной стороны списка по принципу “последним пришел, первым ушел”. Очередь- это такой последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение с другой стороны списка. Дек - это последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Списком называется линейно-упорядоченная последовательность элементов данных E(1), E(2), ..., E(n), где n>0, причем каждый элемент характеризуется одним и тем же набором полей. Такой список называют линейным вследствие линейной упорядоченности его элементов.
5. Связный список - это такая структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей хранящихся в самих элементах. Простейшими связными являются линейные односвязные и двусвязные списки. В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля и поля указателя. Линейный двусвязный список отличается от односвязного списка тем, что его элемент содержит два указателя, один из которых (прямой указатель) адресует, как в односвязном списке, следующий элемент, а другой указатель ( обратный ) адресует предыдущий элемент списка. В структуру двусвязного списка добавлен указатель конца списка. Наличие двух указателей в каждом элементе заметно усложняет список и приводит к дополнительным затратам памяти, но обеспечивает более эффективное выполнение операций над списком.
6. Деревом наз-ся граф к-рый: - связен; - не содержит ни одного цикла. Св-ва: 1. сущ-ет единственный элемент/узел, на к-рый не ссылается никакой др элемент(корень); 2. начиная с корня и следуя по определенной цепочке указателей, содерж. в элем-ах, можно осуществить доступ к люб. Элементу стр-ры; 3. на кажд. элем, кроме корня, имеется единственная ссылка(адресуется единственным указателем). Формы представления: 1.графическая; 2.символьная; 3.представление с помощью массива и списка (ломанная последовательность, линейная: десятичная, код Прюфера). Линейная форма дерева - это последовательность узлов дерева, перечисленная в прямом порядке, с указанием для каждого узла номера уровня. Одной из разновидностей линейной формы представления дерева является десятичная система обозначений Дьюи, в которой для каждого узла через разделитель-точку указываются все номера уровней узлов, расположенных на пути от корня к заданному узлу. Представление деревьев с использованием списка сыновей: А->Б->В. Инверсная форма представления дерева: отношение между узлами обратно обычным отношениям, т.е. каждый узел ссылается на своего предшественника.
7. Наиболее общий вид многосвязной структуры - многосвязная структура, которая характеризуется след. свойствами:
1. каждый элемент структуры содержит произвольное число направленных связей с другими элементами(или ссылок на другие элементы); 2. с каждым элементом может связываться произвольное число других элементов (т.е. каждый элемент может быть объектом ссылки произвольного числа других элементов); 3. каждая связь в структуре имеет не только направление, но и вес. Такую многосвязную структуру называют сетевой структурой или сетью. Логически сеть эквивалентна взвешенному ориентированному графу, и поэтому вместо термина "сеть" часто употребляются термин "графовая структура", или просто "граф".
8. Под обходом дерева понимают просмотр в некотором регулярном порядке каждого его узла. Существует несколько принципиально разных способов обхода дерева:





1. Обход в прямом порядке (КЛП) ABECFGDHIJ. Каждый узел посещается до того, как посещены его потомки(посетить узел; обойти левое поддерево; обойти правое поддерево). Пример использования – сортировка Фон Неймана, быстрая сортировка, умножение длинных чисел.
2. Симметричный обход (ЛКП) EBAFCGHDIJ Алгоритм: левое поддерево; узел; правое поддерево.
3. Обратный обход (ЛПК) EBFGCHIJDA. Узлы посещаются снизу вверх (обойти левое поддерево; обойти правое поддерево; посетить узел). Применение: динамическое программирование, анализ игр с полной инфой.
4. Обход в ширину ABCDEFGHIJ. При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо. Для реализации используется структура queue - очередь с методами: enqueue - поставить в очередь; dequeue - взять из очереди; empty - возвращает TRUE, если очередь пуста, иначе – FALSE.
Различные обходы бинарного дерева, дают следующие формы записи исходного выражения: 1) *+*аЬс - d/е f - префиксная форма (прямой порядок обхода); 2) (a*b+c)*(d-e/f) - инфиксная форма, в которой приоритет выполнения операций задается структурой дерева (симметричный порядок обхода); 3) a b*c+def/- * - постфиксная форма (обратный порядок обхода).
9. Корневые: 1. n-арные: а)случайные(Patricia), б)синтаксические, в)цифрового поиска, г)Trie(нагруженные); 2. бинарные: а)случайные, б)сбалансированные(красно-черные, идеальносбалансированные, АВЛ, ВВ); 3. деревья решений; 4. сильноветвящиеся: а)2-3, б)2-3-4, в)В(В, В*, В+, В++, SB, В с префиксом); 5. многомерные: R, K-D, приоритетного поиска, многомерные В.
10. Любое дерево может быть единственным образом представлено бинарным деревом. На первом этапе для каждой вершины уничтожаются все исходящие из нее ребра кроме самого левого ребра. Вместо них рисуются ребра, каждое из которых соединяет некоторую вершину с вершиной, расположенной справа от нее на том же ярусе, что и рассматриваемая. После этого для каждой вершины дерева осуществляется выбор ее левого и правого сыновей по следующему правилу. Левым сыном является вершина расположенная непосредственно ниже данной вершины, а правым сыном - вершина, расположенная непосредственно справа от данной и на одном ярусе с ней.
11. Усовершенствованный метод представления бин дерева поиска, содержащего n узлов, с помощью массива, размер которого равен n единицам памяти вместо 2n-1, .используется в методе пирам-ной сортировки. Для деревьев определены следующие основные операции: 1) операции доступа: доступ к произвольному узлу дерева, доступ к предшественнику (преемнику) определенного узла, просмотр всех узлов дерева в определенном порядке; 2) поиск заданного элемента (по ключу); 3) операции редактирования на уровне элемента модели (узла): включение, исключение произвольного узла дерева; 4) операции редактирования на уровне модели памяти (дерева): удаление поддерева, замена листа деревом.
12. Бинарное дерево называется сбалансированным, если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1. Полностью сбалансированные деревья являются частным случаем «сбалансированных деревьев» и среди сбалансированных деревьев они являются деревьями с минимальной высотой при заданном числе узлов. АВЛ-дерево высоты h есть дерево с наименьшим числом узлов n, высота которого почти равна log2n. (показатель сбалансированности узла) == (высота правого поддерева этого узла)—(высота левого поддерева этого узла). АВЛ-дерево представляет собой стр-py, для которой любая операция: поиск, вставка и удаление ключа имеет временную сложность O(log2n).
13. Упорядоченное дерево, каждый узел которого содержит 2 или 3 связи, а все листья расположены на одном уровне, называется (2—3)-деревом. Из определения следует, что узел (2—3)-дерева может содержать один или два ключа. Поскольку (2—3)-деревья имеют большую свободу узлов, чем АВЛ-деревья, изменение структуры затрагивают меньшую часть дерева и расщепления узлов выполняются проще, чем балансировка.
14. Обычно в узлах дерева поиска хранятся значения ключей, но в случае, когда ключами яв-ся дост. короткие слова, можно рас-ть каждый ключ как список букв, а все списки вместе—как дерево поиска, структура которого несколько отличается от рассмотренных ранее. В этой структуре узлу (l+1)-го уровня ставится в соответствие 1-я буква слова, так что каждый узел содержит только один символ. Методы поиска по такому дереву часто весьма экономичны как по памяти, так и по времени.
15. При выборе способа машинного представления дерева используется понятие “прошивания” дерева. Этот способ обладает эффективностью как с точки зрения уменьшения объема памяти, так и с точки зрения увеличения быстродействия. Дерево “прошивается” с учетом определенного способа обхода. В этом случае легко разработать алгоритмы обработки дерева и обход осуществляется быстрее, т. к. вместо стека имеется прошивка. Однако включение новой вершины в прошитое дерево занимает больше времени, чем включение ее в непрошитое дерево. При представлении бинарного дерева в стандартной форме листья имеют нулевые значения в полях ссылок. Эти поля ссылок используются для хранения дополнительных связей, упрощающих обход дерева в модели памяти, получившей название прошитого дерева. В прошитом дереве для каждого узла, не имеющего левого преемника, в поле ссылки на левого преемника помещается указатель-нить на узел дерева, который является непосредственным предшественником этого узла при симметричном (прямом, обратном) обходе дерева. Аналогично, в поле ссылки на правого преемника записывается указатель на узел дерева, являющийся непосредственным преемником рассматриваемого узла при симметричном (прямом, обратном) обходе дерева. Для того чтобы различать обычные указатели и указатели-нити, в каждый узел дерева вводятся два дополнительных поля ltag и rtag, в которые записываются единица для обычных указателей и нуль для указателей нитей. Преимущество прошитых деревьев перед обычными бинарными деревьями заключается не только в более эффективном использовании памяти, но и в том , что алгоритмы обхода такого дерева не требуют стека для реализации возврата.
16. Они представляют попытку объединить выгоды от АВЛ-дерева с простым случайным двоичным деревом поиска. Дерево расширений не хранит значение высоты; вместо этого каждый раз, когда мы имеем доступ к узлу, мы перемещаем этот узел к корню, используя АВЛ-вращения. Практически это приводит к хорошо сбалансированным деревьям с быстрым временем доступа. Фактически средняя сложность алгоритма - O(lоg n). Редактирование: узлы, к которым часто обращаются, будут очень близко к корню. Алгоритм формирования и редактирования деревьев расширений состоит в том, что вначале выполняются операции над деревом как над обычным бинарным деревом, а затем рассматриваемый узел с помощью соответствующих последовательных вращений перемещается в корень дерева. Процедуры левого и правого вращений аналогичны вращениям, применяемым в АВЛ-деревьях и в красно-черных деревьях. Отличие состоит в том, как применяются эти вращения.
17. Алгоритм Хаффмана. 1) сортируем все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте; 2) последовательно объединяем 2 символа с наименьшими вероятностями появления; 3) Прослеживаем путь к каждому месту, помечаем направление (налево-«0», направо-«1»), получаем код Хаффмана. Альтернативы коду Хаффмана является коды Фано-Шеннона. Сообщение ABACCDA, коды: A - 0 (частота 3), B - 110 (частота 1), C - 10 (частота 2), D - 111 (частота 1). Тогда наше сообщение закодируется как 0110010101110 (13 бит).
18. Алгоритм Фано-Шеннона. 1) Сортируем символы в порядке возрастания появления их тексте; 2) Делим множество символов на 2 подмножества, так, чтобы сумма вероятностей появления символов одного подмножества = сумме вероятностей появления другого подмножества; 3) Для правого подмножества приписываем «1», для левого-«0»; 4) Разбиение продолжается до тех пор, пока подмножество не будет состоять из одного элемента.
19. К-Ч Д - это бинарное дерево со следующими свойствами: 1. каждый узел покрашен либо в черный, либо в красный цвет. 2. листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет. 3. Если узел красный, то оба его потомка черны. 4. На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково. Количество черных узлов на ветви от корня до листа наз-ся черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Вставка: Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL-узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево. Если предок нового узла красный возм. 2 случ.: 1) красный предок, красный дядя(перекрашиваем предка и дядю, дед-если черн.=> красный, корень - черн.); 2) красн. предок, черн. дядя(вращения для корректировки, в этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева окрашивается в черный цвет, если новый узел вначале был правым потомком, то первым примениться левое вращение, к-рое делает этот узел левым).
20. Упорядоченные деревья, имеющие степень не менее 3, называются сильно ветвящимися деревьями. Если считать, что степень некоторого узла равна n, то он должен содержать n-1 ключей и п указателей.

Св-ва: 1)Степень может меняться в зависимости от узла. Если все узлы имеют одинаковую степень n, структура называется n-арным деревом. 2) Ключ вышерасположенного узла может совпадать с ключом нижерасположенного узла (например, с наибольшим). Сложность (n+1)lognN. Сильно ветвящиеся деревья очень удобны для поиска во внешней памяти.
21. В-деревом порядка п называется сильно ветвящееся дерево степени 2n+1, обладающее след. св-ми: 1) каждый узел, за исключением корня, содержит не менее п и не более 2n ключей; 2) корень содержит не менее одного и не более 2п ключей; 3) все листья расположены на одном уровне. Те узлы, которые не ссылаются на другие узлы дерева, называются листьями; 4) каждый нелистовой узел содержит число указателей на единицу больше числа ключей; 5) каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответствующий ему список указателей (для листовых узлов список указателей отсутствует). Вставка: 1) убедиться в том, что аргумент поиска не совпадает ни с одним из уже имеющихся в дереве ключей(необходимо (начиная с корня) последовательно просматривать узлы дерева, пока не будет достигнут соответствующий лист (неудачный поиск всегда заканчивается в листовом узле)). 2) если лист заполнен не полностью, произвести вставку аргумента в соответствующее место списка ключей и на этом завершить операцию вставки. 3) если в этом листе свободного места нет, то в результате вставки число ключей станет равным 2n+1 и возникнет ситуация переполнения((n + 1)-й ключ/средний ключ удалить из узла; создать новый узел (лист) и переместить в него n ключей списка из узла, в котором возникло переполнение; удаленный ключ вставить в узел-корень переполненного узла, т.е. при переполнении происходит расщепление узла: образуются два новых вместо одного старого и ключ переноса.). 4) если в результате вставки ключа переноса внутренний узел окажется переполненным, он тоже расщепляется (при этом половина списка ключей и списка указателей помешается в новый узел). 5) если ключ переноса достигнет корня и корень после вставки также окажется переполненным, его тоже расщепляют, что приводит к увеличению высоты дерева на единицу и созданию нового корня, куда и помещается ключ переноса. Получившиеся в результате расщепления два узла становятся корнями поддеревьев нового корня.
22. В+ - В, в к-ром истинные значения ключей содержатся только в листьях (концевых узлах). Во внутренних узлах - ключи - разделители, задающие диапазон изменения ключей для поддеревьев. Во многих случаях они совпадают с истинными значениями ключей или их частью, но это вовсе не обязательно. Поскольку все ключи расположены на одном уровне - в листьях, если связать их указателями, то последовательный доступ станет особенно прост при высокой скорости доступа по дереву. При расщеплении листа в результате вставки ключ из листа не удаляется, а в качестве ключа переноса используется его копия. Операция удаления из В+ имеет то преимущество, что удаление всегда производится из листа. Необх-ть в Δ ключа-разделителя возникает только в случае нехватки, когда потребуются перестановка ключей и установление новых связей при балансировке. Все другие операции, помимо рассмотренных выше, выполняются аналогично операциям над В. Таким образом, В+ во многом превосходят В, ступают же они В в том, что требуют несколько больше памяти для представления.
В++ отлич. от В+ расщеплением, объединением. Все ключи в листьях объединяются, а затем почти поровну делятся между листьями.
В* для В - каждый узел должен быть заполнен ключами не < чем на 0.5 для В* - требуется, чтобы каждый узел был заполнен ключами не < чем на 2/3.
Использование: словари, б. д., виртуальная память.
23. Многомерный объект может представлять собой: – некоторую точку в пространстве; – сложный, сос-ий из тысяч полигонов / мн-ва атрибутов объект. Св-ва стр-р: комплексность, динамичность, адаптация к большим размерам, поддержка нестандартных операций, независимость стр-ры индекса от последоват. построения, расшир-ть, произв-ть, пространст. эффек-ть. Применение: ГИС, компьютерная графика, медицина.
24. Методы доступа: Точечные Методы Доступа –ТМД(Point Access Methods – PAM); Пространственные Методы Доступа – ПМД(Spatial Access Methods – SAM); Пространственно-Временных Методов Доступа – ПВМД(Spatio-Temporal Access Methods – STAM); Метрические Методы Доступа – ММД(Metric Access Methods – MAM). Виды запросов: поиск по точному совпадению (Exact Match Query); поиск объекта, содержащего точку (Point Query); поиск по области (Range Query); поиск покрывающих объектов (Overlap Query); поиск вмещающего объекта (Enclosure Query); поиск вхождений (Containment Query); поиск соседей (Adjacency Query); поиск ближайшего соседа (Nearest Neighbor Query); запрос всех пар элементов, удовлетворяющих условию (Spatial Join). Расстояние м/у многомерными объек.: расст. м/у объектами в пространстве признаков наз-сяся такая величина Dist(P,P′), к-рая удовлетворяет след. аксиомам:
– Dist(P,P′) > 0 – неотрицат. расстояние; – Dist(P,P′) = Dist(P′,P) – симметрия; – Dist(P,P″) + Dist(P″,P′) > Dist(P,P′) – неравенство треугольника; – если Dist(P,P′) ≠ 0, то P ≠ P′ – различимость нетождественных объектов.
25. Представление MBR: – сохраняются координаты двух угловых точек прямоугольника, расположенных на главной диагонали; – в вершине дерева хранятся корд. верхней левой точки и инфа о размере прямоугольника по всем измерениям (длина и ширина); – в вершине дерева размещается корд. геометрического центра прямоугольника (пересеч. диаг.) и инфа о размерах прямоугольника по всем измерениям, поделенная пополам. MBR для группы объектов: иногда в один описывающий прямоугольник помещают не один объект, а целую группу близко расположенных к друг другу объектов. Технология вычисления MBR для группы объектов принципиально ничем не отличается. MBR для групп объектов: минимальную описывающую область формируют путем указания центра этой области и расстояния, на котором должны находиться объекты. Все объекты, попавшие в эту область, объединяются в один элемент (узел или поддерево). Для таких MBR специально разработаны алгоритмы, значительно увеличивающие скорость поиска ближайших соседей в многомерном пространстве. Среди стр-р, оперирующих такими MBR: SS- и SR-деревья.
26. В большинстве иерархических методов доступа предусмотрено объединение рядом находящихся точек в одну общую область. Точки такой области сохраняются в одной дисковой странице, на которую ссылается некоторый лист дерева. Внутренние узлы дерева (индексные узлы) предназначены только для разбиения пространства на подпространства и соответственно уменьшения области поиска. Причем вся область разбивается рекурсивно от корня к листу.
K-D дерево в K измерениях, в зависимости от размерности представляемого пространства имеет вид: 1-d-дерево (в одномерном пространстве) - обычное бинарное дерево поиска; 2-d-дерево (двухмерное дерево, напр., для представления объектов на плоскости), но ветвление в узлах происходит уже по двум направлениям (напр., на нечетных уровнях ветвление происходит по координате x, а на четных – y). В общем случае K-D имеет узлы с k корд., и ветвление на каждом уровне баз-ся на сравнении одной из координат. Разновидности: адаптивные K-D; Bibtree; BSP; LSD и hB. Применение: пространственная индексация, определение скрытых поверхностей, метод быстрого многополюсника, трассировка лучей, квантование цвета.
27. Quad-дерево предназначено для индексирования и поиска данных в оперативной памяти. В настоящее время разработано большое множество различных вариантов Quad, позволяющих использовать данную структуру не только для хранения точечных объектов, но и пространственных областей, графических данных с разной точностью детализации, сложных форм и изменяющихся во времени объектов. Разновидности: оптимальное точечное Quad-дерево, Quad-деревья областей (Region Quad-tree), MX Quad-дерево (MX Quad-tree), PR Quad-дерево (PR Quad-tree), Псевдо Quad-дерево (pseudo Quad-tree). Применение: кодирование изображений.
28. LSD-дерево(Local Split Decision tree). В нем отражена мысль, что пространство в каждой вершине дерева делится локально, независимо от остального дерева, причем деление это бинарное. LSD-дерево можно считать адаптивным K-D, приспособленным для внешней памяти. Оно содержит в себе механизмы выгрузки части узлов во внешнюю память.
29. Классификация методов многомерного хеширования: Схемы хеширования с каталогом – функция хеширования использует дополнительные данные, сохраненные на диске (Файл-решетка, EXCELL). Схемы хеширования без каталога – функция хеширования основана только на математических вычислениях, без использования дополнительных данных (MOLHPE, PLOP). Файл-решетка Основной принцип – решеточное деление пространства. Принципы файла-решётки: Принцип двух дисковых запросов. Запрос на точное совпадение по всем ключам должен вернуть запись или флаг ее отсутствия в индексе за два обращения к внешней памяти. Эффективные диапазонные запросы. Структура данных должна сохранять порядок, определенный для каждого ключевого диапазона (записи, имеющие близкие значения какого-либо ключа, должны располагаться в близких участках памяти). Пример каталога файла-решётки:
Шкалы: [x0, x1, x2] [y0, y1, y2]
Массив решетки:

Алгоритмы файла-решётки: поиск по точному совпадению, поиск по области (диапазонный запрос), добавление объекта, расщепление внешнего блока, расщепление решетки, удаление объекта. Структура каталога файла-решётки: k одномерных массивов, называемых линейными шкалами по осям. Задача этих массивов заключается в хранении координат плоскостей, которые разбивают пространство на решетку. k-мерный массив сопоставления ячеек решетки и блоков внешней памяти, называемый массивом решетки. Двухуровневый файл-решётка

Двойной файл-решётка

30. EXCELL. Ключевым отличием файлов-решеток от EXCELL является то, что при переполнении некоторой ячейки в первых происходит деление только одного интервала на две части (вставка одного значения в линейную шкалу и добавление одного столбца или строки в массив решетки), в то время как в EXCELL происходит деление всех интервалов по соответствующему направлению и удвоение директории. Недостатки: размер каталога растет сверхлинейно по отношению к росту хранимых данных даже при равномерном распределении данных; если же данные распределяются неравномерно, то во многих вариантах файлов-решеток рост размера каталога может стать экспоненциальным.
MOLHPE – многомерное линейное хеширование с частичными расширениями (Multidimensional Orderpreserving Linear Hashing with Partial Expansions). MOLHPE была предложена в 1986 году Г. Крейгилом и Б. Сигиром. Одна из первых схем хеширования без каталога. Принципы MOLHPE: в общих чертах хеширование MOLHPE похоже на файлы-решетки: все пространство поиска разбивается некоторой решеткой на ячейки; с каждой ячейкой связывается некоторый внешний блок, в котором и сохраняются все объекты, попавшие в эту ячейку. Однако алгоритмы, выполняющие эти действия, отличаются от рассмотренных ранее. Главное отличие – стр-ра ф-ции хеширования, к-рая не использует шкал и массива решетки. Вместо этого все вычисления производятся с помощью специальных математ. ф-ций. Алгоритмы MOLHPE: поиск, добавление объекта, расширение, удаление объекта. Замена массива решетки в MOLHPE. Индексы подставляют в некоторую функцию заполнения пространства G, которая и возвращает номер внешнего блока. Таким образом, вместо массива-решетки используется математическая функция G. Замена линейных шкал в MOLHPE. Вместо линейных шкал для вычисления положение ячейки используют функцию Hi – линейное хеширования для i-го измерения.
Объект поиска:
O = (K0, K1)
Определение индекса в решетке:
l0 = H0(K0)
l1 = H1(K1)
Коллизии в MOLHPE. В файле решетки при коллизии (переполнении) происходило изменение (расщепление) решетки. Таким образом модифицировалась функция хеширования и обрабатывались коллизии. В MOLHPE используется принцип цепочек для обработки коллизий.
PLOP – Piecewise Order Preserving hashing. Разработан в 1988 г. Г. Кригелом и Б. Сигером. Является синтезом файл-решеток и MOLHPE. Авторы попытались устранить недостатки обоих схем.
Адресная функция PLOP. Точно такая же, как и у MOLHPE. В адресную функцию подставляются индексы, полученные из иерархических шкал.
31. Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, наз-ся мультиграфом. Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно наз-ся направленным, или ориентированным, и изображается стрелкой. Граф, в котором все ребра ориентир-ные, наз-ся ориентированным графом (орграфом); ребра орграфа часто называют дугами. Дуги именуются кратными, если они не только имеют общие вершины, но и совпадают по направлению. Иногда нужно рассматривать не весь граф, а его часть (часть вершин и часть ребер). Часть вершин и все инцидентные им ребраназываются подграфом; все вершины и часть инцидентных им ребер называются суграфом. Циклом называется замкнутая цепь вершин. Деревом называется граф без циклов. Остовным деревом называется связанный суграф графа, не имеющий циклов. Для неориентированного ребра порядок, в котором указанны соединяемые им вершины, не важен. Для ориентированного ребра важно: первой указывается вершина, из которой выходит ребро. Маршрут, или путь - это послед-ть ребер в неориентированном графе, в котором конец каждого ребра совпадает с началом следующего ребра. Число ребер маршрута называется его длинной.
Поиск в ширину. По анологии с принципом Гюйгенса(каждая посещенная вершина становится источником новой волны). Для реализации: 1) матрица m[1..n, 1..n] - матрица смежности графа; 2) вспомогательный массив queue[1..n], в котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен, так как мы не посещаем вершины дважды. С массивом queue связаны; 3) две переменные - head и tail. В переменной head будет находиться номер текущей вершины, из которой идет волна, а при помощи переменной tail новые вершины помещаются в "хвост" очереди queue; 4) вспомогательный массив visited[1..n], который нужен для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); 5) вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь; 6) переменная f, которая примет значение TRUE, когда путь будет найден. Кроме того, введутся несколько вспомогательных переменных, при организации циклов.
Поиск в глубину. Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную) смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемся к той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадем в вершину B, печатаем путь. Если все вершины исчерпаны - такого пути нет. Для реализации: 1) матрица m[1..n, 1..n] - матрица смежности графа; 2) вспомогательный массив visited[1..n], который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); 3) переменная f, которая примет значение TRUE, когда путь будет найден.
Эйлеровы циклы. Требуется найти цикл, проходящий по каждой дуге ровно один раз. Условия для существования в графе эйлерова цикла: во-первых, граф должен быть связанным: для любых двух вершин должен существовать путь, их соединяющий; во-вторых, для неориентированных графов число ребер в каждой вершине должно быть четным. На самом деле этого оказывается достаточно. Теорема: Чтобы в связанном графе существовал эйлеров цикл, необходимо и достаточно, чтобы число ребер в каждой вершине было четным.
Задача Прима-Краскала. Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длинна телефонных линий была минимальной. Или в терминах теории графов: Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево минимальной длины. В задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение. Древо с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными. До построения дерева каждая вершина i окрашивается в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет. Теорема: Алгоритм Прима–Краскала получает минимальное остовное дерево.
Алгоритм Дейкстры. Задача: дана дорожная сеть, где города и развилки будут вершинами, а дороги – ребрами. Требуется найти кратчайший путь между двумя вершинами. С точки зрения графов: в ориентированной, неориентированной или смешанной сети найти кратчайший путь из заданной вершины во все остальные вершины. Для реализации: 1) массив Visited содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); 2) массив Len содержит расстояния: текущие кратчайшие расстояния от начальной до соответствующей вершины; 3) массив C содержит номера вершин – k-ый элемент C есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю; 4) Matrix – матрица расстояний. Алгоритм:
1 (инициал.). В цикле от 1 до n заполнить значением False массив Visited; заполнить числом i массив C (i–номер стартовой вершины); перенести i-ю строку матрицы Matrix в массив Len; Visited[i]:=True; C[i]:=0;
2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j] Len[k]; Затем выполнять следующие операции: Visited[i]:=True;
если Len[k] > Len[j] + Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j) {Если все Visited[k] отмечены, то длина пути от vi до vk равна C[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}.
3 (выдача ответа). {Путь от vi до vk выдается в обратном порядке следующей процедурой:}
3.1 z:=C[k];
3.2 Выдать z
3.3 z:=C[z]. Если z =0, то конец,
иначе перейти к 3.2.
Теорема: Алгоритм Дейкстры – корректен.
32. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить, таким образом, что линии (ребра) не будут пересекаться. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности: списки связи и перечни ребер. Матрица инциденции - это двумерный массив размерности N×M.
вершина с номером i инцидента ребру с номером j
вершина с номером i не инцидентна ребру с номером j
Недостатки матрицы инцидентности: матрица прямоугольная, трудно редактировать. Плюсы: запись в матричной форме, сразу можно найти связи, можно сразу работать с ориентированными графами. Такие матрицы применяются редко.








Матрица смежности - это двумерный массив размерности N×N.

если вершины с номерами i и j смежны
вершины с номерами i и j не смежны







Число элементов в i- ой строке, значение которых 1, равно полустепени исхода вершин Vi . Аналогично, число элементов равных 1 в j-ом столбце равно полустепени захода вершин Vj. Матрица смежности полностью определяет орграф. Недостатки: много нулевых элементов. Плюсы: очень легко реализуются операции над графами.
33. Суть: выбирается самое дешевое ребро, затем к нему добавляется самое дешевое из оставшихся и т.д. При этом окончательная подсеть должна содержать: все вершины; должна быть связанной; не должна содержать циклов; иметь min возможный вес.
∞ 11 9 7 8
11 ∞ 15 14 13
9 15 ∞ 12 14
7 14 12 ∞ 6
8 13 14 6 ∞



34. Идея метода. Поиск начинается с некоторой фиксированной вершины v. Просматриваются все вершины связанные с ним, и если такая существует, рекурсивно продолжаем поиск, начиная с нее. Если же не существует, то мы возвращаемся назад, чтобы найти новый поиск вершины. Поиск продолжается до тех пор, пока мы рекурсивно не вернемся в исходную точку. Сложность: О(n+m), n- количество вершин, m-количество ребер. Для уверенности в том, что поиск не зацикливается, необходимо предусматривать остановку на определенной глубине. Рекомендуется начинать поиск с глубины равную расстоянию по прямой от старта до цели. Он является оптимальным и по времени и по памяти. В больших задачах целесообразно применять алгоритм последовательных приближений, т.е. найти путь до какой-то промежуточной точки, затем найти путь от промежуточной точки до цели.

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







Граф и его описание

Вычислит. сложность поиска в ширину имеет порядок т+n, каждая вершина помещается в очередь и удаляется из очереди один раз.
Имеется проблема: поиск идет равномерно во всех направлениях, вместо того, чтобы быть направленным в сторону цели.
Улучшения: двунаправленный поиск в ширину.
запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Улучшает простой поиск в ширину (обычно в 2 раза).
36. 1. Выбираем некоторую вершину, остальные n-1 вершины отмечаются как невыбранные.
2. Определяем вес между выбранной вершиной и остальными невыбранными вершинами.
3. Выбирают вершину с наименьшим весом для нее и фиксируют выбранное ребро и вес.
4. Выбранную вершину исключаем из перечня невыбранных, число невыбранных вершин уменьшаем на 1.
1-4 повторяем до тех пор, пока не будут выбраны все вершины, n-1 раз.
















37. Не требует прохода по всем вершинам для нахождения ребра min веса.
1. Начать с полностью несвязного графа из n вершин.
2. Упорядочить ребра графа в порядке возрастания их весов.
3. Начав с 1 ребра в этом перечне, добавлять ребра, соблюдая условие: добавление
не должно приводить к появлению циклов.
4. Повторять 3 пункт до тех пор, пока число ребер не станет равным n-1.









38. Формулировка задачи: определить максимальный поток, протекающий от некоторой вершины S графа (источника) к некоторой вершине T (стоку). При этом каждой дуге (граф ориентированный) (i,j) приписана некоторая пропускная способность С(i,j), определяющая максимальное значение потока, который может протекать по данной дуге.
Области приложения потоковых алгоритмов:
• комбинаторные задачи:
– о допустимых назначениях на должности (иначе, о представителях подмножеств);
– о назначениях на должности с максимальной суммарной эффективностью;
– о назначениях, оптимальных по минимаксу;
– о минимальных множествах ребер или вершин сети, удаление которых нарушает ее связность.
• каноническая область приложений:
– задачи о потоках в сетях (электрических, гидравлических и т.д.);
– составлении расписаний;
• нахождении оптимальных планов перевозок.
Разрез - множество дуг, удаление кот. из сети приводит к "разрыву" всех путей, ведущих из s в t. Пропуск. способность разреза - это суммарная пропускная способность дуг, его составляющих.
Мин.разрез - с мин. пропускной способностью.
Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения.
Грубый подход определения макс. потока:
– генерация всех возможных подмножеств дуг;
– для каждого подмножества дуг проверяем, является ли оно разрезом.
– если является, то вычисляем его пропускную способность и сравниваем ее с минимальным значением.
– при положительном результате сравнения запоминаем разрез и изменяем значение минимума.
39. Суть алгоритма- последовательное (итерационное) построение макс. потока путем поиска на каждом шаге пути (последовательности дуг), поток по которому можно увеличить. При этом узлы (вершины графа) специальным образом помечаются. Базируется на "Технике меток" Форда и Фалкерсона:
На каждой итерации вершина сети может находиться в одном из трёх состояний:
1.вершина не имеет метки 2. вершине присвоена метка и она не просмотрена (не все смежные вершины обработаны) 3. вершине присвоена метка и она просмотрена
На каждой итерации мы выбираем помеченные, но не просмотренные вершины и ищем вершину смежную с ней, которую можно пометить.
Помеченные вершины образуют множество вершин в сети, достиж. из вершины источника. Если среди этих вершин окажется вершина сток, то это означает успешный результат поиска, который позволяет увеличить поток. Если поток нельзя увеличить, то процесс прекращается.
40. Сортировка – процесс целенаправленного перемещения элементов заданной конечной послед-ти, результатом которой является послед-ть, в кот. элементы расположены в порядке возраст. (или убывания) их значений.
Сортировка устойчива, если записи с одинаковыми ключами остаются в прежнем порядке.
Факторы, влияющие на производ-ть (параметры сорт-ки): 1) Число и размер сортируемой записи.
2) Тип и размер ключа. 3) Характер исходной упорядоченности – почти отсортированная последовательность, почти отсортированная наоборот, случайная последовательность. 4)Повторяемость значения ключа. 5) Используемые размеры памяти.
1.Время выполнения (T), характеризует скорость сортировки. 2. Количество сравнений ключей (C) и количество перестановок элементов(P). 3. Использование памяти в процессе сортировки (M). 4. Использование рекурсии(R). Большинство классических сортировок имеют временные затраты, которые варьируются от 0(nlogn) до 0(n2).
Классификация:
1) Внутренняя (сортируемые записи находятся в оперативной памяти):
а)сортировка вставками: простые вставки, бинарные и двухпутевые вставки, вставки в список, сортировка с вычислением адреса
б) обменная сорт.: метод пузырька, параллельная сорт. Бетчера, быстрая сорт., обменная поразрядная
сорт. в) сорт. выбором, простой выбор, выбор из дерева, пирамидальная сорт. г) Сортировки подсчетом (Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей)
2) Внешняя (некот. из сорт. записей находятся во вспомогательной памяти.): алг-тм сорт. выбора, многофазное слияние, каскадное слияние, осциллирующие сорт., внешняя поразрядная сорт…. См. 49
41. Простые вставки (n2/4): исходный массив разбивается на две части: A[1], A[2], ..., A[k-1] - отсортированную часть, A[k], ...,A[n] - не отсортированную часть. На k - м шаге элемент A[k] включается в отсортированную часть, на соответствующее место. При этом часть элементов, больших A[k], (если таковые есть) сдвигаются на одну позицию правее, чтобы освободить место для элемента A[k]. Прежде чем производить сдвиг элементов A[k] сохр. во временной переменной. Поиск подходящ. места для очередного элемента входной послед-ти осущ-ся путем послед-х сравнений с элементом, стоящим перед ним. В завис-ти от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется. В процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда
1. Hайден элемент, меньший x. 2. Достигнуто начало последовательности.
Бинарные вставки: при поиске места, на которое надо вставить элемент ai в уже упорядоченную совокупность a0 , ..., ai-1 , определяется алгоритмом деления пополам Недостаток – много времени на смещение элементов. Сложность – O(n*log n).
Двухп. вставки –1-ый элемент вставляется в середину послед-ти, а место для последующих элементов освобождается при помощи сдвига влево или вправо.
Вставки в список: находится мин элемент (сорт. только указатели) и вставляется в начало.
Дост.: чтобы вставить k-ый элемент организуем прохождение списка до тех пор, пока не будет найдена нужная позиция для k-го элемента или конец списка; вставка осуществляется переадресацией, без сдвига эл-тов послед-ти. Это уменьшает время вставки, но не время поиска. Недостаток – доп. память для указателей.
42. Пузырек: состоит в проходе снизу вверх по массиву. По пути просматр. пары соседних элементов. Если элементы некот. пары находятся в неправ. порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий". Просмотр
до тех пор, пока перестановок больше нет.
Улучшения: 1) Т.к. все эл-ты в позициях >=(n-i+1) уже на своих местах, нет надобности их сравнивать. О(1/2*n2). 2) Черед-е в прямом и обратном направ. (Шейкер-сорт) 3) Для исключения ненужных просмотров (послед-ть уже отсортирована) надо сохранять инфу об
обмене, в случае отсутствия обмена – сорт-ка прекращается.
Быстрая сорт-ка: эффективна для больших послед-тей. Цель каждого шага – помещение очередного элемента на его конечную позицию внутри последовательности. В результате все предшествующие эл-ты будут иметь меньшие значения, а последующие – большие. В результате последовательность делится на 2 части относительно значения первого эл-та, который в данном алгоритме становиться медианой. Аналогичный процесс применяется к каждой из этих частей (рекурсивно), пока все эл-ты не встанут на свои места.
43. Сорт. Шелла. Исходная последовательность разбивается на части. Каждая часть сортируется отдельно (обычно при помощи метода простых вставок). Количество частей k называется шагом. Затем выбирается меньший шаг и алгоритм повторяется. Обычно количество частей должно быть взаимно простыми числами. Последняя сортировка выполняется с шагом 1. Несмотря на большое число циклов, суммарное число перестановок будет меньше. Преимущество достигается за счет того, что части представляют из себя почти упорядоченные последовательности, и в этом случае эффективен алгоритм простых вставок. Сложность – O(n*(log n)*(logn)).
Сорт с вычислением адреса. Связанная последовательность разбивается на части в соответствии с функцией хеширования. В каждую часть включаются элементы меньшие или равные элементам другой части. При этом помещаемые
элементы каждой части сортируются (методом вставки). После этого все части соединяются в 1 послед-ть. Тратится время на выбор ф-ции хеширования и разбиение послед-ти в соответствии с ней. Требуется память для указателей. Сложность:O(n) – в лучшем случае, O(n*n) – в худшем случае.
44. Обменная поразрядная сорт. Идея – двоичное представление ключей и сравнение отдельных битов. 1)Послед-ть сортируется по старшему значащему биту так, чтобы все ключи начинающиеся с 0, оказались перед всеми ключами, начинающимися с 1. Для этого надо найти самый левый ключ k[i], начинающийся с 1, и самый правый k[j], начинающийся с 0. После этого i и j элементы меняются местами, и процесс повторяется, пока i не станет больше j.
До сортировки необходимо знать два параметра: k и m, где k - количество разрядов в самом длинном ключе, а m - разрядность данных: количество возможных значений разряда ключа.
Схема сортировки Бэтчера напоминает сортировку Шелла, но сравнения выполняются по-новому, так что распростр-е обменов не обязательно. Так как в алгоритме Бэтчера, происходит слияние пар отсорт. подпослед-ей, то его можно назвать “обменной сортировкой со слиянием”. Идея – происходит слияние пар отсортированной подпослед-ей. Проблема – как формировать эти пары.
45. Простой выбор. На каждом шаге из последовательности выбирается минимальный элемент и переносится в конец выходной последовательности. Характерным остается наличие двух независимых частей: упорядоченной и неупорядоченной. При исключении выбранного элемента из массива на его место может быть записано очень большое число. Выбранный элемент может удаляться путем сдвига остальной части. Минимальный элемент может меняться местами с очередным. Трудоемкость по количеству сравнений равна n*n/2.
Для нахождения наименьшего элемента из n+1 рассматримаемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = O(n*n). Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов. Алгоритм не использует дополнительной памяти: все операции происходят "на месте". Квадратичный выбор: разбиение последовательности на две части.
Выбор из дерева:
• каждому первоначальному элементу приписывается некоторый узел (лист) в некотором бинарном дереве;
• Затем выбираются два узла (листа). Наибольшее значение из них присваивается узлу – отцу. Этот процесс повторяется до тех пор пока не останется один лист или ни одного. Если остается один лист, то этот узел надо переместить вверх на следующий уровень.
• Затем аналогичный процесс с заново созданными узлами надо повторить до тех пор, пока самое большое число не будет помещено в корень бинарного дерева.
• Узел являющийся листом со значением корня заменяется минимальным числом. Содержимое всех предков до корня этого листа повторно вычисляется.
• Этот процесс повторяется до тех пор, пока не будут выведены все листья первоначального дерева.
46. Куча это последовательность с определенными свойствами упорядоченности. Она похожа на дерево, но по свойствам существенно от него отличается. Если для двоичного дерева выполняется: ключ родителя больше или равен ключу левого сына и меньше или равен значению правого, то для двоичной кучи справедливо: ключ сына меньше или равен ключу родителя key[ parent[x] ] >= key[x]. Можно сделать вывод, что наибольшее число поддерева находится в его корне. Еще одно отличие двоичной кучи от дерева - поля left, right и parent не нужны. Они восстанавливаются однозначно по номеру вершины x: left[x] = 2*x; right[x] = 2*x + 1; parent[x] = x div 2;
Это означает, что куча занимает непрерывный участок памяти. Вершина, у которой нет родителя, называется корнем дерева (root). Для любой кучи это всегда элемент с номером 1. Для нее: parent[1] = 1 div 2 = 0, т.е. не существует. Но для того, чтобы понять, что вершина x - лист и случайно не ссылаться на не существующий элемент, введем понятие размер кучи - это количество вершин в ней.
Высотой вершины равна числу ребер в самом длинном пути от этой вершины к листу. Высота дерева равна высоте его корня.
Пирамидальная сортировка.
– максимальный элемент массива теперь находится в корне дерева (A[1]). Его следует поменять с А[n], уменьшить размер кучи на 1 и восстановить основное свойство в корневой вершине (поскольку поддеревья с корнями left(i) и right(i) не утратили основного свойства кучи, это можно сделать с помощью процедуры savek). После этого в корне будет находиться максимальный из оставшихся элементов.
– Так делается до тех пор, пока в куче не останется всего один элемент.
Время выполнения сортировки составляет O(n log n), т.к. первая часть (построение кучи) требует времени O(n), а каждое из (n−1) выполнений цикла for занимает O(logn).
47. Цель оптимальной сортировки:
– минимизация числа сравнений ключей при сортировке n элементов –минимизация слияний т элементов с n элементами,
–минимизация выбора i-го наибольшего элемента из неупорядоченного набора n элементов
Сортировка с минимальным числом сравнений
Варианты постановки задачи сортировки посредством сравнений.
Если есть n грузов и весы с двумя чашами, то каково минимальное число взвешиваний,
необходимое для того, чтобы расположить грузы по порядку в соответствии с весом, если
в каждой чаше весов помещается только один груз?
Используем дерево сравнений. Каждый внутренний узел содержит два индекса "i : j" и
означает сравнение ключей Кi и Kj. Левое поддерево этого узла соответствует
последующим сравнениям, при Кi < Kj, а правое поддерево — тем действиям, если Кi >
Kj. Каждый лист дерева содержит перестановку Кi, a это обозначает, что было
установлено упорядочение К1 < К2 < • • • < Кп.







Возможны и избыточные сравнения; например, на рис. нет необходимости сравнивать 3:1, поскольку из неравенств К1 < К2 и K2 < K3 следует К1 < Кз.. В дереве сравнений для сортировки n элементов без избыточных сравнений имеется ровно n! внешних узлов
Три метода требуют меньше всего сравнений:
бинарные вставки, выбор из дерева и простое двухпутевое слияние.
Для метода выбора из дерева верхняя оценка числа сравнений либо такая же, как для
метода бинарных вставок, либо такая же, как для двухпутевого слияния, в зависимости от
вида дерева.
Поищем теперь "мини-средние" процедуры, минимизирующие среднее число сравнений в
предположении, что входные данные случайны, т. е. все перестановки равновероятны.
В общем случае среднее число сравнений для метода сортировки есть длина внешнего
пути дерева, деленная на n!. (Напомним, что длина внешнего пути — это сумма всех
расстояний от корня до каждого из внешних узлов) Минимальная длина внешнего пути достигается на таком бинарном дереве с N внешними узлами, у которого имеется 2q — N внешних узлов на уровне q - 1 и 2N – 2q на уровне q, где q = [lg N]. (Корень находится на нулевом уровне.) Таким образом, минимальная длина внешнего пути равна
• (q - 1)(2q - N) + q(2N - 2q) = (q + 1)N - 2q.
• минимальная возможная средняя длина пути не может быть меньше lgN и больше lgN + 0.0861.
48. Дано множество из n чисел; нужно найти тот его элемент, который будет k-м по счѐту,
если расположить элементы множества в порядке возрастания.
Такой элемент называется k-ой порядковой статистикой. минимум (minimum) — это порядковая статистика номер 1. максимум (maximum) — порядковая статистика номер n-1. Медианой (median) называется элемент множества, находящийся (по счѐту) посередине между минимумом и максимумом. Точнее говоря, если n нечѐтно, то медиана — это порядковая статистика номер k-(n+1)/2, а если n четно, то медиан даже две: с номерами kn/2 и k-n/2+1. Можно ещѐ сказать, что, независимо от чѐтности n, медианы имеют номер k= (n+1)/2 и k= (n+1)/2 . В дальнейшем мы будем называть медианой меньшую из двух
(если их две). Одно из очевидных решений задачи вычисления порядковых статистик состоит в
следующем: упорядочить исходную последовательность в порядке не убывания элементов и взять k-й элемент.
Методы решения задач порядковой статистики
Минимум или максимум можно найти за n-1 сравнение. Быстрее нельзя. Одновременный поиск минимума и максимума можно осуществить за 3 n/2 -2сравнений. порядковую статистику за время 0(n) можно найти с помощью:
– вероятностного алгоритма
– детерминированного алгоритма
Эти алгоритмы асимптотически эффективнее очевидного подхода "упорядочи множество
и выбери нужный элемент",
Особенности реальной задачи
1. Если нескольких элементов имеют одно и то же значение, и они должны сохранять
порядок следования, то упорядочение необходимо выполнить одним из методов
устойчивой сортировки, в противном случае можно использовать любой метод
сортировки.
2. Если отыскивается одна или несколько порядковых статистик, выгоднее применение
иного алгоритма.
3. На выбор алгоритма влияет число элементов n исходной последовательности.
4. Если исходная последовательность должна быть сохранена, то для отыскания
порядковых статистик придется создать дополнительный массив ключей. Это выгодно,
когда элементы исходной последовательности имеют сложную структуру и их
перестановки требуют значительного времени.
Алгоритм
(1) Наугад выбрать некоторый элемент A[s] и записать его значение в переменную x.
(2) Просматривая массив слева направо, найти элемент A[i]: A[i] x.
(3) Просматривая массив справа налево, найти элемент A[j] : x A [j].
(4) Если i ≤ j, обменять найденные элементы A[i] и A [j] между собой, на единицу
увеличить i и уменьшить j. После этого вернуться к шагу (2). Иначе – последовательность
разбита на две группы, Если количество элементов в группе с k-ым элементом <2, то
выход.
(5) Иначе переход к группе с k-ым элементом и рекурсивно выполняются шаги 1-4.
Существует линейный метод нахождения порядковых статистик, обеспечивающий в
самом худшем случае время выполнения порядка O(n). Этот метод основан на поиске «хорошего» опорного элемента и применяется для последовательностей с большим
числом элементов.
Пример Найдѐм 3-ю порядковую статистику.
Возьмѐм в качестве опорного элемента на первой итерации А(s)=37 в качестве опорного элемента на второй итерации А(s)=33 в качестве опорного элемента на третьей итерации А(s)=12
3-я порядковая статистика =33.
25 57 48 37 12 92 86 33
25 33 48 37 12 92 86 57
25 33 12 37 48 92 86 57
25 33 12 37 48 92 86 57
25 12 33 37 48 92 86 57
12 25 33 37 48 92 86 57
49. Специфика любого алгоритма внешней сортировки – как разделить последовательность на части и их слить (объединить).
Операции внешней сортировки: 1)находить нужный блок в памяти: перемещение считывающей головки. 2)производить считывание данных по каналу ввода-вывода.
3)в оперативной памяти осуществляются операции сравнения и перемещения. 4)выполняется запись во внешнюю память.
Параметры внешней сортировки: 1)объем оперативной памяти. 2)тип, число и объем запоминающих устройств внешней памяти.
3)число каналов ввода-вывода. 4)число и длина записи. 5)время выполнения операций в оперативной памяти.
Упорядоченный отрезок(серия) – последовательность элементов, для которых выполняется условие упорядоченности.
Длина отрезка – количество элементов в нем.
Прогон(проход) – прохождение файла в одном направлении со считыванием данных в память и
возвратом обратно.
Сложность внешней сортировки состоит из времени: 1)внутренней сортировки частей файла.
2)многократное считывание и запись данных на диск. 3)ходов головки между актами считывания.
4)действий в памяти по упорядочению частиц.
Факторы, учитываемые при выборе метода сортировки:
1)размер сортируемого массива => требуемое количество оперативной памяти. 2)длина ключа.
3)вид ключей. 4)исходное распределение данных.
5)длина записей и логический порядок следования.
Если длина серии фиксирована, то слияние простое. Сортировка, при которой всегда сливаются 2 самые длинные из возможных серий, наз. естественным слиянием.
Внешние сортировки
1)Сортировки слиянием: а) сорт простым слиянием, двухфазная двухпутевая сорт., однофазная двухпутевая сорт., многопутевое сбалансированное слияние, многопутевое слияние и выбор замещением. б) естественное слияние, естественное многопутевое слияние, многофазная, каскадная, осциллирующая
сорт. в)улучшенные методы – рекурсивный алгоритм сортировки, сорт. методом поглощения.2)Другие методы – сорт. с использованием специальных структур, разделительная (поразрядная) сорт., быстрая альтернативная внешняя сортировка.
50. Характеристики сортировки слиянием:
1) Количество вспомогательных файлов, на которые идет распределение серии. N – количество вспомогательных файлов, N=2 – двухпутевая сорт слиянием, N>2 – многопутевая. 2) Количество фаз в реализации сортировки. Фаза – действие по однократной обработке всего множества. Проход(этап) – наименьший процесс, повторение которого составляет процесс сортировки. Двухфазная – 1 фаза-распределение, 2 фаза-слияние. Однофазная - эти две фазы объединены в одну.
С одной стороны, однофазная сортировка более эффективна, чем двухфазная, т.к. фаза распределения фактически не относится к сортировке(во время этой фазы эл-ты не переставляются и не упорядочиваются), а кол-во операций переписи данных такое же, как и на фазе слияния. Но с другой – количество вспомогательных файлов, которые требуются для однофазной сорт, больше, чем для 2-фазной.
Cортировка простым слиянием.
На 1 шаге упорядоченные отрезки имеют длину, равную единице, т.е. состоят из одного элемента. Затем они объединяются и в случае 2-путевого слияния вновь сформированные отрезки будут состоять из 2 эл-тов, а в случае многопутевого – из N эл-тов. Длина серии в алгоритме простого слияния зависит от кол-ва вспомогательных файлов, на которое идет распределение серий. Если k – это номер прохода, а N – кол-во вспомогательных файлов, то длина серии определ-ся формулой N**k. На первых проходах длина серии растет медленно, что значительно сказывается на быстродействии алгоритма. Поэтому для улучшения алг-ма слияний можно использовать внутреннюю
сортировку в качестве вспомогательной. В этом случае на первом проходе часть данных переписывается в оперативную память (в массив), там упорядочивается и тем самым формирует серию большой длины. Тогда для дальнейшего слияния потребуется значительно меньше проходов. Этот способ упорядочения данных наз. простым слиянием с использованием внутренней сортировки.
Сортировка простым слиянием заканчивается, если: --после фазы слияния длина серии не меньше количества элементов в файле;
--на фазе слияния осталась ровно одна серия;
--второй по счет вспомогательный файл для однофазной сортировки после распределения серий остался пустым.
Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Сложность = O(n*log n).
51. 1)Последовательность разбивается на 2 половины: B и C. 2)Части B и С сливаются, причем одиночные элементы этих частей образуют упорядоченные пары.
3)Полученная последовательность A опять разбивается в соответствии с 1), 2), но сливаются упорядоченные пары => упорядоченные четверки. 4)Повторяя предыдущие шаги, сливаем 4-ки в 8-ки и т.д., пока не будет упорядоченной последовательности.
52. Внешняя двухпутевая однофазная (сбалансированная) сортировка
Есть и другой вариант реализации алгоритма сортировки слиянием, когда серии меняются по закону простого слияния. Поскольку длина серии на каждом этапе известна, нетрудно обеспечить прямую адресацию элементов, когда сливаемые серии расположены не на разных концах вектора, а друг за другом: расстояние между их началами составит ровно 2k-1 на k-м этапе. Соответственно, и запись результирующей серии происходит всегда в хвост уже размещенных в области вывода элементов. Этот механизм называется простым однопутевым слиянием.
Сбалансированное многопутевое слияние
В основе метода внешней сортировки сбалансированным многопутевым слиянием является распределение серий исходного файла по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия. Многопутевое слияние является естественным развитием идеи обычного (двухпутевого) слияния Преимуществом сортировки сбалансированным многопутевым слиянием является то, что число проходов алгоритма оценивается как O(log n) (n - число записей в исходном файле), где логарифм берется по основанию n. Порядок числа копирований записей - O(log n). Конечно, число сравнений не будет меньше, чем при применении метода простого слияния. Число перестановок = n* log n.
53. Особенности естественного слияния. Сортировка, при которой сливаются 2 упорядоченные серии – упорядоченное слияние.
Пример 2-путевого 2-фазного естественного слияния.
А – 17 31 05 59 13 41 43 67 11 23 29 47
В – 17 31 13 41 43 67
С – 05 59 11 23 29 47
А – 05 17 31 59 11 13 23 41 29 43 47 67
В – 05 17 31 59
С – 11 13 23 29 41 43 47 67
Сорт. естеств. слиянием заканчивается, если:
-на фазе слияния осталась ровно 1 серия;
-второй по счету вспомогательный файл для однофазной сорт после распределения серий остался пустым. Так как признаком конца серии в естеств. слиянии является результатом слияния двух соседних элементов, то две/несколько серий, распределенных друг за другом, могут объединяться в одну.
Ex - 1 2 9 3 39 11 4 18 13 5 16 24 15 4 25 17 317
F1 – 1 2 9 11 13 15 17 317
3 39 4 18 5 16 24 4 25 //стремиться вверху собрать одну серию.
Естественное слияние наз. сбалансированным, если после фазы равпределения кол-во серий во вспомогательных файлах отличается друг от друга не более чем на 1. В противном случае слияние считается несбалансированным. Чтобы в сбалансир. слиянии серии распределялись корректно, необходимо во время записи очередной серии в файл выполнять следующую проверку: если серия является продолжением предыдущей, то записать в этот файл не 1, а 2 серии:
F1 – 1 2 9 11 4 18 5 16 24 17 317
3 39 13 15 4 25
54. Метод основан на том, что имеется несколько входных файлов с разным числом серий и только 1
выходной файл. При каждом проходе серии из входных файлов сливаются, пока входной файл с наименьшим числом серий не будет исчерпан. Тогда освобожденный файл становиться входным и начинается новый проход. Серии из всех оставшихся файлов сливаются в выходной файл.
Конец сортировки: все серии => 1 серия.
f1 f2 f3
исход. сост. 13 8
проход1 5 0 8
проход2 0 5 3
проход3 3 2 0
Многофазная сортировка более эффективна, чем сбалансир. многопутевая, т.к. при одном и том же
кол-ве файлов число сливаемых файлов больше.
Число проходов при многофазной сортировке будет оптимальным, если количество серий во вход.
файлах будет подчиняться числам Фибоначчи. (Послед-ть Фибоначчи – посл-ть, где каждый эл-т = сумме 2-х предыдущих – 0 1 1 2 3 5 8 13 21…)
Число сравнений в файлах при оптимальном распределении по (f-1) файлов должно быть числами Фибоначчи, порядком (f-2). Недостающее число серий можно дополнять пустыми сериями, распределяя их равномерно между входными файлами. Поскольку число серий в исходном файле может не обеспечивать возможность такого распределения серий, применяется метод добавления пустых серий, которые в дальнейшем как можно более равномерного распределяются между промежуточными файлами и опознаются при последующих слияниях. Понятно, что чем меньше таких пустых серий, т.е. чем ближе число начальных серий к требованиям Фибоначчи, тем более эффективно работает алгоритм.
55. Похожа на многофазную сортировку. Отличие заключается в самом процессе слияния:
сначала проводится (f-1) — путевое слияние в f-ый файл до тех пор, пока файл с номером f-1 не опустеет; затем (f-ый файл уже не затрагивается) проводится (f-2) — путевое слияние в (f-1)-ый файл;
затем (f-3) — путевое в (f-2)-ый файл; ...; потом двухпутевое слияние в третий файл, а в конце копирование из файла номером 2 в первый файл.
Следующий проход работает по аналогичной схеме, только в обратном направлении.
Количество серий в каждом из вспомогательных файлов определяется в соответствии с формулами:
a1° =1 ai° =0, i = 2,3,. , f
a1N = ai+1L +af-iL-1 , i = f-1, f-2,..., 1
Каскадное слияние эффективно при количестве файлов >6.
56. В простейшем случае ключ является некоторым полем внутри записи, располагающимся с некоторым конкретным сдвигом от начала записи. Такой ключ - внутренний или встроенный. В других случаях ключом является относительная позиция записи внутри файла или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи - внешние.
Различают два типа ключей:
Для каждого файла имеется по крайней мере один набор ключей (возможно и несколько таких наборов), которые являются уникальными (т. е. никакие две записи в файле не имеют одинакового значения ключа). Такой ключ называется первичным ключом. Например, если в некотором файле с фамилиями и адресами название города используется как ключ для некоторого поиска, то он, возможно, не будет уникальным, так как в файле могут содержатся две записи с названием одного и того же города. Такой ключ называется вторичным ключом.
3 типа запросов:
1. Определяет конкретное значение ключа.
2. Запрос диапазонов значения ключа.
3. Логический запрос. Комбинация предыдущих запросов при помощи логических операций.
Классификация поиска:
Поиск по ключу; контекстный поиск; исчерпывающий поиск; полнотекстовый поиск; нечеткий поиск; геометрический; многомерный.
57. Этот поиск применяется к структурам типа
массива или связанного списка (для неупорядоченных структур). В худшем случае сложность алгоритма O(n)
Для того, чтобы использовать последовательный поиск со вставкой для некоторого массива, необходимо выделить достаточно памяти для него. Имеется другой метод, при котором нет необходимости периодически уплотнять массив, но который дает меньшую эффективность при отдельных вставках. Суть метода состоит в последовательном просмотре массива в поисках некой удаленной записи и вставки
поверх ее новой записи. Другой метод состоит в связывании всех удаленных записей, и использование этого пространства для
стека с дальнейшим использованием его для вставки. Однако эти методы не приемлемы, если записи должны располагаться в том порядке, в котором они вставлялись.
Если часто используемые записи поместить в начало файла, среднее число сравнений сильно уменьшится. Число обращений к этой записи.
Индексно - последовательный поиск.
В дополнение к отсортированному файлу заводится некоторая вспомогательная таблица, называемая индексом. Каждый элемент индекса состоит из ключа k index и указателя на запись в файле pindex, соответствующего этому ключу. Элементы в индексе также как и элементы файла должны быть отсортированы по этому ключу. Если индекс имеет размер составляющий одну восьмую от размера файла, то каждая восьмая запись представлена первоначально в индексе.
Последовательный поиск выполняется по меньшему индексу, а не по большей таблице. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей. Индекс применяется как для списка так и для массива. Использование связанного списка приводит к нескольким большим накладным расходам по
пространству для указателей, хотя вставки и удаления могут быть выполнены проще.
Если структура данных является такой большой, что даже использование индекса не дает достаточной эффективности, то может быть использован индекс 2 го уровня.
Индекс второго уровня действует как индекс для первичного индекса, который указывает на элементы в последовательной структуре данных. Удаления из индексно - последовательной структуры могут быть сделаны наиболее простым способом - при помощи отметки удаленных записей флагом. Индекс изменять не надо. Вставка в индексно - последовательную структуру является более трудной, поскольку между двумя уже существующими элементами структуры может не быть свободного места, что приводит к необходимости сдвигать большое число элементов структуры.
58. При поиске в таблице суть метода состоит в том, что аргумент сравнивается с ключом среднего элемента. Если они равны, то поиск успешно закончился. В противном случае поиск должен быть осуществлен в верхней или нижней части таблицы аналогично.
Бинарный поиск наилучшим образом может быть определен рекурсивно. Однако, большие накладные расходы, связанные с рекурсией, делают ее неподходящей для использования в практических ситуациях, в которых эффективность является главным фактором. При поиске в связной структуре вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент поиска оказывается меньше ключа, поиск продолжается в левом поддереве, а в случае, когда аргумент оказывается больше ключа,—в правом поддереве. Поиск считается неудачным, если при достижении листьев совпадение не обнаруживается. В противном случае к этому моменту поиск должен закончиться успехом. Каждое сравнение в бинарном поиске уменьшает число возможных кандидатов в два раза. Следовательно максимальное число сравнений ключа равно log2n. Бинарный поиск может быть использован совместно с индексно- последовательной структурой данных. алгоритм бинарного поиска может быть использован только для упорядоченного массива. Затраты времени на поиск по бинарному дереву поиска оказываются такими же, как и затраты времени на поиск в упорядоченной таблице с использованием метода деления пополам. В случае, когда множество ключей заранее неизвестно или когда это множество ключей меняется, вставки и удаления ключей в таблице оказываются довольно трудоемкими. Более рационально использовать в таком случае бинарное дерево поиска, которое позволяет значительно проще вставлять и удалять элементы.
59. В определенном смысле алгоритм имитирует поиск фамилии в телефонном справочнике. Если нужное слово начинается с буквы А, вы наверное начнете поиск где-то в начале справочника. Если Вы заметите, что искомое слово должно находиться гораздо дальше открытой страницы, вы пропустите порядочное их количество, прежде чем сделать новую попытку.

при выполнении итерации поиска между элементами А [l] (крайним слева) и А [r]
(крайним справа), алгоритм предполагает, что значения в массиве растут линейно (отличие от линейности может влиять на эффективность, но не на корректность данного алгоритма).
В соответствии с этим предположением, значение v ключа поиска сравнивается с элементом, индекс которого вычисляется (с округлением) как координата х точки на прямой, проходящей через (l, А [l]) и (r, А [r]), координата у которой равна значению v.
Записав стандартное уравнение для прямой, проходящей через две точки (l, А [l]) и (r, А[r]), заменив в нем у на v и решая его относительно х, получим формулу.
Логика, лежащая в основе этого метода, проста. Мы знаем, что значения массива возрастают (точнее говоря, не убывают) от А [l] до А [r], но не знаем, как именно. Пусть это возрастание — линейное (простейшая из возможных функциональных зависимостей); в таком случае вычисленное по формуле значение индекса — ожидаемая позиция элемента со значением, равным v. После сравнения v с А[x] алгоритм либо прекращает работу (если они равны), либо
продолжает поиск тем же способом среди элементов с индексами либо от l до x — 1, либо
от х + 1 до r, в зависимости от того, меньше ли v значения А [х] или больше. Если взять последовательность с линейным возрастанием
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
то для поиска заданного ключа методом бинарного поиска необходимо четыре сравнения,
а методом интерполяционного поиска одно сравнение. Если взять случайно возрастающую последовательность
9, 17, 25, 33,34, 35, 49, 67, 69, 85, 86, 94, 96, 105, 106, 108, то для поиска заданного ключа (например Х=33) методом бинарного поиска требуется 4 сравнения, а методом интерполяционного поиска 3 сравнения.
Интерполяционный поиск в среднем требует менее log2 log2 n+1 сравнений ключей при поиске в списке из n случайных значений. Бинарный поиск, более выгоден для небольших входных данных, но для файлов большого размера и для приложений, в которых сравнение или обращение к данным — дорогостоящая операция, лучше использовать интерполяционный поиск.
60. Если ключи цифровые, то их можно представить с помощью леса.
180,195,1867

В каждой вершине такого дерева хранится полный ключ, но переход по левой или правой ветви происходит не путем сравнения ключа-аргумента со значением ключа, хранящегося в вершине, а на основе значения очередного бита аргумента. Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 - по правой. Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется
следующий бит аргумента и т.д., пока либо не будут проверены все биты аргумента, или мы не наткнемся на вершину с отсутствующей левой или правой ссылкой. Длина поиска не превышает количество разряда ключа. Для большого количества ключей, большое дерево почти идеально сбалансировано. Если ключи располагаются достаточно плотно, то процесс поиска по цифровому дереву неэффективен. У дерева представленного как некоторый двумерный массив БОР, каждая строка массива представляет 1 из возможных символов, а каждый столбец представляет узел в цифровом дереве. Каждый элемент такого массива является либо указателем на другой столбец, либо ключ и его запись.
61. Mожно произвести над ключом K некоторое арифметическое вычисление и получить функцию f(K), указывающую адрес в таблице, где хранится ключ K и ассоциированная с ним информация. Основная идея ассоциативной адресации состоит в том, чтобы рассматривать адрес как функцию от ключа. Требуется, чтобы этот адрес вычислялся как можно проще и как можно быстрее. Идея хеширования состоит в том, чтобы взять некоторые характеристики ключа и использовать полученную частичную информацию в качестве основы поиска. Вычисляемая функция f(K) будет называться хеш-функцией и это значение будет браться в качестве адреса начала поиска. Хеш-таблица – это обычный массив с адресацией, задаваемой хеш-функцией. Размер хеш-таблицы m должен быть достаточно большим, чтобы в ней оставалось разумно большое число пустых мест. Если число записей n невелико и заранее известно, то можно построить идеальную хеш-функцию. Если же число записей велико, то найти такую функцию очень сложно.
В случае, когда в результате хеширования ключи претендуют на один и тот же адрес приходится отказываться от идеи однозначности.. Отказ от требования взаимно однозначного соответствия между ключом и адресом означает, что для двух различных ключей k1 k2 значение хеш-функции может совпадать: h(k1) = h(k2). Такая ситуация называется коллизией.
Для метода хеширования главными задачами являются: – выбор хеш-функции h так, чтобы уменьшить число коллизий;
– нахождение способа разрешения возникающих коллизий, т.е. где разместить конфликтные записи - внутри самого массива или вне его.
Мерой использования памяти в таблицах с прямым доступом служит коэффициент заполненности, отношение числа записей к числу мест в таблице α = n/m.
Недостатки хеширования:
1. табличный порядок имен обычно не связан с их естественным порядком.
2. худший случай может оказаться хуже, чем при последовательном поиске.
3. таблицы, основанные на вычислении адреса, расширить динамически непросто: это может приводить к потере памяти, если таблица слишком велика, или к малой производительности, если таблица слишком мала.
Процедура занесения элемента делится на три этапа: вычисление хеш-адреса (по хеш-функции); уточнение хеш-адреса (в случае коллизии); размещение ключа (и/или элемента).
Требования при выборе хеш-функции:
- минимальная сложность ее вычисления;
- равномерность распределения значений хеш-функции по хеш-таблице, что позволяет: сократить число коллизий; не допустить скучивания значений ключей в отдельных частях таблицы.Если ключи не являются числами, то они должны быть преобразованы в целые числа перед применением хеш-функций.
Хеш-функция не может вычислять адреса больше чем размер хеш-таблицы, причем для всех ключей К 0 < h(K) < m, где m – размер хеш-таблицы.
Классы хеш-функций:
1)Идеальные (см. 62)
2)Универсальные - метод деления (H=mod(k, m),
где k- целый ключ, m-размер хеш-таблицы); метод умножения (h(K) =ém * ((C * K) mod 1)ù, где С[0..1], é ù возвращает наибольшее целое, которое меньше аргумента); метод "середины квадрата"; метод свертки (слияния); метод преобразования системы счисления; метод деления многочленов; хеш-функция для строковых ключей, и другие.
3)Специальные - Известны различные подходы к формированию специальных хеш функций:
1) Поразрядный анализ, адреса формируются путем выбора и сдвига цифр или битов исходного ключа.2) Кусочно-линейная функция. Пространство ключей, состоящее из целых величин в замкнутом интервале [a, d], делится на j равных подинтервалов длины L.
62. Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса. Или идеальной (perfect hash function) или «минимальной совершенной» хеш-функцией
называется такая хеш функция, когда:
- не возникает коллизий;
- размер хеш таблицы и количество ключей одинаково
Алгоритмы поиска идеальных хеш-функций:
1)Метод проб и ошибок, Дж. Чикелли
Согласно этому методу, h вычисляется как сумма кодов букв ключа. Обозначим через Сj код, соответствующий j-й букве ключа k, Тогда можно записать


Значения C(L) для различных L не обязательно должны быть различными, т. е. хотя все буквы множества L1 ..., Ll различны, среди соответствующих им кодов С1, С2, .., Сl могут быть и одинаковые.
2)Метод обратных чисел, Дж. Джеске
3)Алгоритм, основанный на случайных графах,С. Ботело
63. см. также 62
Коллизия – это ситуация, когда h(K1) = h(K2), в то время как K1 ≠ K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Количество коллизий необходимо минимизировать.
Метод цепочек(многомерное хеширование). Хеш-таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Элемент данных вставляется в соответствующий список в качестве нового узла. Чтобы обнаружить элемент данных, нужно применить хеш-функцию для определения нужного связанного списка и выполнить там последовательный поиск. Метод цепочек быстрее открытой адресации, так как просматривает только те ключи, которые попадают в один и тот же табличный адрес. Здесь элементы таблицы создаются динамически, а длина списка ограничена лишь количеством памяти. Списки образуются по мере необходимости по одному на каждый возможный хеш-адрес таблицы. Сами списки могут размещаться как в памяти, принадлежащей хеш-таблице, так и в отдельной памяти. В первом случае цепочки называются внутренними, а во втором случае — внешними.
Разрешение коллизий методом открытой адресации. Суть метода - пользуясь каким-либо правилом, обеспечивающим перебор всех элементов, просто просматривать один за другим элементы хеш-таблицы.
1)Метод линейного опробования. каждая ячейка таблицы помечена как незанятая. Поэтому при добавлении нового ключа всегда можно определить, занята ли данная ячейка таблицы или нет. Если да, алгоритм осуществляет перебор по кругу, пока не встретится «открытый адрес» (свободное место). Если размер таблицы велик относительно числа хранимых там ключей, метод работает хорошо, поскольку хеш-функция будет равномерно распределять ключи по всему диапазону и число коллизий будет минимальным.
По мере того как коэффициент заполнения таблицы приближается к 1, эффективность процесса заметно падает.
2) Случайное опробование - недостаток метода линейного опробования обусловлен эффектом скучивания, который значительно усиливается при почти заполненной таблице. Проблема первичных скучиваний может быть частично решена, если использовать метод случайного опробования.
Генерируется случайная последовательность позиций в отличие от упорядоченной последовательности, для метода линейного опробования. Генерируемая случайная последовательность должна содержать все целые числа от 1 до m в точности по одному разу. Таблица считается заполненной, если встречается первое дублирование случайного числа. Для метода случайного опробования проблема удаления записей становится более сложной, чем в случае линейного опробования. Поэтому в случае часто меняющейся таблицы для устранения коллизий следует использовать другие методы.
3) Квадратичное опробование. Это схема открытой адресации, при которой hi(k)=h0(k)+ci+di2, где с и d — константы. Благодаря нелинейности этой адресации удается избежать увеличения числа проб при числе коллизий более 2. Однако в случае почти заполненной таблицы не удается избежать «вторичного скучивания». Это связано с тем, что при большом числе ключей коллизии одной группы вступают в коллизию с другими ключами. С одной стороны, этот метод дает хорошее распределение по таблице, а с другой занимает больше времени для просчета.
4) Двойное хеширование - Один из способов преодоления вторичного скучивания состоит в использовании второй функции хеширования, не зависящей от первой. Предположим, например, что первой функцией хеширования является h1, такая, что h1(x1) = h1(х2) = i, где x1 ≠ х2. Теперь, если мы имеем вторую функцию хеширования h2 такую, что h2(x1) ≠ h2(х2) при x1≠ х2, то в качестве значения параметра с можно использовать значение h2(х1) или h2(х2). Если h1 и h2 являются независимыми, две случайные последовательности адресов, сгенерированные с помощью такого метода, будут различными. Следовательно, мы избавляемся от вторичного скучивания. Такая вариация метода открытой адресации называется двойным хешированием.
64. Характеристика методов исчерпывающего поиска. • предполагают генерацию всех решений и выбор из них решения с требуемыми свойствами.
• С учѐтом быстродействия ЭВМ и.п.эффективен в множестве, состоящем не более чем из 108 элементов. Поэтому для того, чтобы эти методы были полезны, к ним нужно относиться как к схемам, с которыми следует подходить к задаче.
• Схемы должны быть хорошо приспособлены к конкретной задаче, так чтобы в результате алгоритм годился для практического использования, а это требует большей изобретательности.
Задачи: • Комбинаторика • Теория графов • Теория расписания • грамматический разбор, • игры и т. д.,
• Т. е. там, где альтернативы перебору нет
Методы и.п.:
– метод проб и ошибок или поиск с возвращением;
– метод ветвей и границ;
– динамическое программирование;
– методы решета;
– приближения исчерпывающего поиска
- эвристические алгоритмы;
- жадные алгоритмы.
Метод проб и ошибок или поиск с возвращением
Идею поиска с возвращением легче всего понять в связи с задачей прохода через лабиринт. Один из способов прохода через лабиринт — это двигаться из начального квадрата в соответствии с двумя правилами: 1. В каждом квадрате выбирать еще не исследованный путь. 2. Если из исследуемого в данный момент квадрата ведут исследованные пути, то нужно вернуться на один квадрат назад по последнему пройденному пути, по которому вы пришли в данный квадрат и выполнить п.1.
• Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило — о том, как выходить из тупика.
Постановка задачи - проход через лабиринт
• Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером
M*N. Элемент матрицы A[i, j]=1, если клетка (i, j) проходима. В противном случае A[i,j]=0.
• Требуется найти кратчайший путь из клетки (1, 1) в клетку (M1, N1).
• Фактически лабиринт представляет собой граф с соответствующей матрицей смежности.
• Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина пути (Way) была больше или равна длине оптимального пути (OptimalWay).
Задача о n ферзях • Задача заключается в размещении n ферзей на шахматной доске размером n n так, чтобы никакие два ферзя не угрожали друг другу, находясь на одной горизонтали, вертикали или диагонали.
• Для n = 1 задача имеет тривиальное решение; легко убедиться, что для n= 2 и n = 3 решений не существует. Поэтому начнем с задачи с четырьмя ферзями и решим ее с помощью поиска с возвратом. Поскольку каждый ферзь должен находиться на собственной горизонтали, все, что надо, — это указать вертикаль для каждого ферзя на доске. Соответсвенно если на очередной горизонтали нельзя разместить ферзя, то задача нерешаема.
Еще применение: маршрут шахматного коня, раскраска карты, укладка рюкзака, расстановка знаков.
65. По сравнению с методом поиска с возвратом метод ветвей и границ требует:
способа получить для каждого узла дерева пространства состояний границу наилучшего значения целевой функции для всех решений,
которые могут быть получены путем дальнейшего добавления компонентов к частичному решению, представленному узлом;
значение наилучшего решения, полученного к этому моменту.
Если такая информация доступна, то мы можем сравнивать значение границы узла со значением наилучшего решения, полученного к этому моменту: если значение границы не лучше значения уже имеющегося наилучшего решения, то эта ветвь обрезается. В этом заключается основная идея метода ветвей и границ.
В общем случае мы завершаем путь поиска в текущем узле дерева пространства состояний алгоритма ветвей и границ по одной из трех следующих причин:1)Значение границы узла не лучше значения наилучшего решения, найденного к этому моменту.2)Узел не представляет допустимых решений из-за нарушения ограничений, налагаемых задачей.
3)Подмножество допустимых решений, представляемое узлом, состоит из одного элемента (следовательно, дальнейший выбор невозможен) - в этом случае мы сравниваем значение целевой функции для этого допустимого решения со значением целевой функции наилучшего полученного к настоящему моменту решения и обновляем последнее текущим, если новое решение оказывается лучше.
Применение: задача о назначениях, задача о коммивояжере, укладка рюкзака.
66. Динамическим программированием называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых на этом шаге решений, оптимизирующее заданную (целевую) функцию F. Метод д.п. применим только тогда, когда функция F удовлетворяет принципу оптимальности Беллмана. Этот принцип требует, чтобы всякий отрезок ai, ai+1,...,am оптимальной последовательности а1,...,аn (1< = i < = т< = n) был бы сам оптимальным среди всех отрезков, совпадающих с ним по числу элементов и в крайних элементах. Это свойство позволяет найти оптимальную последовательность, постепенно удлиняя уже найденные от начала (конца) последовательности отрезки.
Применение этого принципа к решению комбинаторных задач по существу означает использование принципа декомпозиции: вначале находятся решения подзадач, затем они используются для отыскания решения больших подзадач и, наконец, для решения самой задачи.
Два признака, характерных для задач, решаемых методом д.п: 1) Оптимальность для подзадач - необходимо сначала описать структуру оптимального решения. Задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения её подзадач.
2) Перекрывающиеся подзадачи – небольшое число различных подзадач.
Благодаря этому при рекурсивном решении задачи мы многократно выходим на одни и те же подзадачи. В таком случае говорят, что у оптимизационной задачи имеются перекрывающиеся подзадачи.
Примеры применения: перемножение нескольких матриц(Задача об умножении последовательности матриц может быть сформулирована следующим образом: дана последовательность из n матриц A1A2 ×…×An заданных размеров (матрица Ai имеет размер pi-1´pi ); требуется найти такую расстановку скобок в произведении A1A2 …An, чтобы вычисление произведения требовало наименьшего числа умножений); задача об оптимальной триангуляции многоугольника (Дан выпуклый многоугольник Р = áv0, v1, …, vn-1ñ и весовая функция w, определённая на множестве треугольников с вершинами в вершинах Р. Требуется найти триангуляцию, для которой сумма весов треугольников будет наименьшей). Разбиение абзаца на строки; Алгоритм Витерби (Динамическое программирование может быть применено к задаче распознавания речи. В качестве модели рассмотрим ориентированный граф G = (V, Е) и отображение о, сопоставляющее с каждым ребром (u, v) звук s(и, v) из множества возможных звуков å. В графе выделена некоторая вершина v0. Каждому пути, начинающемуся в v0 , соответствует последовательность звуков (элементов å) ).
67. Решето представляет собой метод, который рассматривает конечное множество и исключает все элементы этого множества, не представляющие интереса. Этот метод является логическим дополнением к процессу поиска с возвращением, который перечисляет все элементы множества, представляющие интерес.
• Методы решета полезны прежде всего в теоретико-числовых вычислениях. Например, одним из наиболее известных методов отыскания простых чисел является «решето Эратосфена». Это решето перечисляет составные (не простые) числа между N и N2 для некоторого N
• Легко понять, почему методы решета могут быть полезны. Если в множестве возможных решений элементы можно удобно занумеровать натуральными числами, то хранить нужно только характеристический вектор; в этом векторе i-й разряд равен нулю, если i-й элемент не является решением, и равен единице в противном случае. Таким образом, на множествах, состоящих буквально из миллионов элементов, возможен поиск без явного порождения и исследования каждого элемента множества. Кроме того, в большинстве вычислительных устройств булевы операции можно производить параллельно над многими разрядами, обеспечивая тем самым значительную экономию времени.
Разновидности метода решета
• решето Эратосфена
• Нерекурсивное модульное решето
• обобщенное модульное решето
• Рекурсивное решето
• Двойное решето
• Решето, отбраковывающее изоморфные объекты
68. Эвристические алгоритмы
• Для трудных с вычислительной точки зрения проблем один из подходов состоит в том, чтобы требовать результат близкий к оптимальному. Ослабление ограничений на оптимальность часто приводит к более эффективным алгоритмам, поскольку в этом случае исчерпывающий поиск является только «приближенным». При этом ожидается, что проигрыш в стоимости найденных (квазиоптимальных) решений будет умеренным.
• Не трудно изобрести эвристические алгоритмы, которые быстро находят решение; в действительности, можно обнаружить, что большинство, но не все решения, получаемые эвристикой, являются хорошими. • Теоретически невозможно доказать, что эвристический алгоритм всегда находит решение, близкое к оптимальному.
эвристический подход для улучшения решения задачи о шахматном коне
• Для очередного хода выберем такое поле, в которое можно перейти из минимального числа полей. Так мы оставляем свободными поля, доступные из большего числа полей. Для этого дополнительно к матрице доски используем еще одну матрицу М такого же размера n*n, каждый элемент mi,j которой будет содержать число возможных переходов коня с поля hi,j на другие поля. Так же, как и в предыдущем примере, в элемент hi,j заносится номер хода коня,
одновременно соответствующий элемент mi,j обнуляется. Так как поле hi,j теперь стало
недоступным для перехода с других полей, то соответственно корректируется и матрица
m. • Этот эвристический алгоритм с направленным выбором хода коня превращает
предыдущий алгоритм с возвратом, реализованный с применением рекурсии, в алгоритм без возврата и без рекурсии. Он выполняется всего за (m - 1) ходов (m - число полей на доске).
Характеристика жадных алгоритмов
• Жадные алгоритмы, как и динамическое программирование, применяются в тех случаях,
когда искомый объект строится по частям. Жадный алгоритм делает на каждом шаге «локально оптимальный» выбор.
• Простой пример: стараясь набрать данную сумму денег минимальным числом монет, можно последовательно брать монеты наибольшего возможного достоинства (не превосходящего той суммы, которую осталось набрать). • Жадный алгоритм обычно работает гораздо быстрее, чем алгоритм, основанный на динамическом программировании. Однако жадный алгоритм вовсе не всегда даѐт оптимальное решение. Во многих задачах применимость жадных алгоритмов удаѐтся доказать с помощью так называемых матроидов.
Жадные алгоритмы для задачи о рюкзаке
Шаг 1. Вычислим удельные стоимости всех предметов множества ri= vi /wi , i = 1,2,..., n.
Шаг 2. Отсортируем предметы в невозрастающем порядке по их удельным стоимостям,
вычисленным на шаге 1 (неоднозначности разрешаются произвольным образом).
Шаг 3. До тех пор пока в отсортированном списке не останется ни одного предмета,
повторяем следующие действия: если текущий предмет помещается в рюкзак, мы
помещаем его туда; в противном случае переходим к следующему предмету.
69. Файл - это совокупность элементов данных, сгруппированных для хранения и использования в информационно-вычислительных системах.
• Коллекция записей, описывающая некоторый набор объектов, связанных между собой определенными целями, называется файлом.
• В качестве постоянного носителя для файлов выступает внешняя память.
• Файл снабжается именем, • Над файлом можно выполнить функции доступа, которые позволяют проверять, извлекать или изменять информацию, содержащуюся в нем.
• Любая операционная система (ОС) в своем составе имеет систему управления файлами (СУФ), которая обеспечивает сохранение файлов и функции доступа.
• Запись (иногда называемая группой или сегментом) является коллекцией элементов информации касающейся отдельного объекта.
• Элемент записи (иногда называется полем) — это минимальная значащая единица информации об объекте. • При размещении на внешнем носителе записи объединяются в блоки или физические записи. Блок - минимальная единица данных, которая может быть передана между внешней и основной памятью.
• Количество логических записей, объединенных в один блок, называется коэффициентом блокирования.
• Блок записей передается с ВЗУ в специально выделенную область ОП - буфер. В буфере
физическая запись разблокируется и передается на обработку в другие области ОП. Максимальный размер блока ограничен объемом буфера. Буфер организован как очередь. По мере освобождения буфера в него помещается следующая физическая запись.
• Элемент данных, единственным образом идентифицирующий запись в файле, называется
ключом. Как правило, записи в файле упорядочиваются в соответствии со значениями
ключей.
• Файлы могут группироваться образуя набор файлов. Если между записями этих файлов
существуют некоторые ассоциативные связи или зависимости, то такая коллекция файлов
рассматривается как база данных.
• Отдельная операция, затрагивающая запись или несколько записей, называется
транзакцией. При обработке файлов транзакции часто представляются в форме записи
транзакций.
логическая и физическая структура файла
• Различают логическую и физическую структуру файла • Логическую организацию файла определяет пользователь как совокупность элементов данных. Наиболее часто используются два вида элементов данных; элемент-символ и элемент-запись.
Физическая организация связана с характеристиками используемых устройств внешней памяти и принятой в ОС концепцией размещения данных на них. Обычно при инициализации томов носителей осуществляется их форматирование, которое и определяет форматы хранимых элементов данных файлов. В одних ОС они имеют вид записей. Например, в ОС фирмы IBM OS/370 записи могут иметь форматы фиксированной, переменной или неопределенной длины с ключами или без них. В других ОС, например MS DOS, Unix, Windows, данные в файлах хранятся как последовательности символов.
Файлы – система управления файлами (СУФ) • СУФ, как указывалось, реализует соответствие между логической и физической
организациями файлов. Чем ближе логическая и физическая организации друг к другу, тем
проще осуществляется эта функция. СУФ также обеспечивает независимость программы
пользователя от устройств и от конкретных файлов. Последние определяются только на
этапе выполнения программы при решении определенной задачи. • СУФ тесно связана с системой ввода-вывода ОС. Логическая связь между программой и конкретным файлом устанавливается при выполнении функции открытия файла, эта связь устраняется при закрытии файла. • Учет файлов как единиц хранения ведется посредством каталога, который содержит дескрипторы всех файлов. Форматы и содержание дескрипторов файлов определяются СУФ конкретной ОС.
• В простейшем случае каталог имеет вид линейной таблицы, которая содержит информацию о файлах всех пользователей. Однако при большом количестве файлов поиск
в таком каталоге требует много времени. Поэтому в современных ОС каталоги имеют древовидную структуру. Можно выделить два уровня управления файлами. Первый уровень — это управление файлами в целом, второй уровень обеспечивает доступ к отдельным элементам данных в файле.
70. При программировании на языках высокого уровня регистровая и кэшевая память обычно недоступны для программиста. Для внешней памяти характерны большой объем и существенно замедленный по сравнению с основной памятью доступ. Виртуальная память: система виртуальной памяти выполняет динамическое отображение из пространства виртуальных адресов (адресное пространство, во много раз превосходящее основное адресное пространство) в ocновнoe адресное пространство. Три типа систем виртуальной памяти: 1) системы со страничной памятью; 2) сегментно-страничные системы; 3) системы с сегментацией. Страничные системы: 1) виртуальное адресное пространство разбито на блоки фиксированной длины, называемые страницами. 2) пространство основной памяти разделено на физические секции равного размера, названные страничными кадрами. 3) страничный кадр и страница имеют один и тот же размер. Преобразование виртуального адреса в основной (или реальный) адрес включает отображение страницы в страничный кадр. Виртуальный адрес в страничной системе состоит из двух компонентов р и d, где р обозначает страницу, d — смещение внутри страницы р. Преобразование этого двухкомпонентного адреса в адрес основной памяти, как правило, требует наличия таблицы страниц и алгоритма замены страниц. Таблица страниц связана с заданием каждого пользователя (т. е. множеством программ и данных пользователя). Каждая запись в таблице страниц содержит:1 - бит присутствия (флажок, сигнализирующий о нахождении или отсутствии
страницы в основной памяти); 2 - Адрес страницы (в основной и во вторичной памяти); 3 - Биты защиты, необходимые для контроля типа доступа, разрешенного для страницы. Система с сегментной организацией. В системах с сегментной организацией адресная структура программы базируется на логическом делении программы. Виртуальное адресное пространство каждой программы в системах с сегментацией делится на блоки переменной длины, называемые сегментами, каждый из которых содержит одну из логических областей программы. Для доступа к слову внутри адресного пространства пользователя мы опять, как и при страничной организации, используем адрес, состоящий из двух частей. В адресе (s,d) размещение сегмента задается s, а смещение внутри сегмента — d. Сегментно-страничные системы возникли в результате попытки сохранить большинство преимуществ как страничных, так и сегментных систем. Внешняя фрагментация в них отсутствует, поскольку основной единицей информации, поддерживаемой системой, является страница. Обеспечивается разделение данных, связывание и защита программ вследствие реализации концепций сегментной организации. Внутренняя фрагментация, однако, присутствует, и она может быть снижена только уменьшением размера страницы. Адресация в сегментно-страничных системах. В сегментно-страничных системах виртуальный адрес разбивается на три
компонента —s, p и d, где s — имя сегмента (или адрес в таблице сегментов), р — индекс в таблице страниц сегмента – s и d — смещение внутри страницы, специфицированной индексом р. Пространство виртуальной памяти теперь делится на ряд сегментов переменной длины, состоящих из небольших страниц фиксированной длины. Недостатки этой системы: 1)повышенная стоимость аппаратуры; 2) дополнительные затраты времени процессора из-за необходимости преобразования трехуровневого адреса; 3) требуется больше основной памяти для хранения дополнительных таблиц преобразования адресов (т. е. таблиц сегментов и страниц).
71. Изучение NP-полных задач связано с так называемым вопросом Р≠NP. Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее интересных и сложных проблем теории вычислений.
Р-полиномиальная сложность. Свойства: -они все практически разрешимы; -объем задачи класса Р не зависит от выбора конкретной модели вычислений; -класс полиномиальноразрешимой задачи обладает естественными свойствами замкнутости. В теории NP-полноты рассматриваются только задачи разрешения —задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Для отнесения задачи к тому или иному свойству используется задача распознавания свойств. Часто встречаются задачи оптимизации (optimization problems), в которых требуется минимизировать или максимизировать значение некоторой величины. Прежде чем ставить вопрос о NP-полноте таких задач, их следует преобразовать в задачу разрешения. Обычно в качестве такой задачи разрешения рассматривают задачу проверки, является ли некоторое число верхней (или нижней) границей для оптимизируемой величины. Задачи, для которых нет полиномиальных алгоритмов называются экспоненциальными. Строковая задача называется полиномиальной (polynomial-time solvable), если существует константа k и алгоритм, решающий эту задачу за время О (nk). Сложностным классом (complexity class) Р называется множество всех строковых задач разрешения, которые могут быть решены за полиномиальное время. Недетерминированный полиномиальный алгоритм имеет двухшаговый подход: 1. имеется недет. алг. генерирующий решения такой задачи (угадывание решений). 2. проверяется предложенное решение как решение исходной задачи. Каждый из этих двух шагов имеет полиномиалное решение. Проблема в том, что мы не знаем сколько шагов надо сделать. Класс NP входит в NP полные задачи. NPC – полные задачи, не решаемые задачи, нет точного ответа. NPI – класс задач, имеющий сложность между P и NP. CO-NP – класс NP с противоположным ответом. Св-ва класса NP задач: -никакую NP полную задачу нельзя решить никаким известным полиномиальным алгоритмом; -если существует полиномиальный алгоритм для какой-нибудь NP полной задачи, то существует полин.алг. для всех NP полных задач. Фундамент NP полных задач заложен в работах С.Кука. Наиболее важное положение этой теории: Сводимость за пол. время, т.е. если одна задача сводится за пол. время к другой, то любой полин. алг. решения второй задачи может быть превращен в полин. алг. решения первой. В качестве распределения на классы он предложил задачу распознавания, которая решается за полиномиальное время на недетерминированном устройстве. Для доказательства NP полноты используется 6 ключевых NP полных задач: выполнимость; трехмерное сочетание; вершинное покрытие; задача Тлика; Гамильтонов цикл; разбиение. 2 категории подхода к решению NP полных задач: 1. Подходы, в котором делаются попытки максимального сокращения переборов (метод ветвей и границ, метод неявного перебора). Формируется дерево поиска и мощные оценки, позв-щие отбросить бесперспективные решения (метод динам. прогр-ния, отсечения, Лагранжа). 2. Применяется к оптимизационным задачам. Главный прием – снижение требования. Вместо оптимального ищется хорошее решение. Первый алгоритм наилучший из подходящих.