Обоснование алгоритма Дейкстры

↑

▷ Содержание

Стр 1 из 2Следующая ⇒

1.Рекурсивное описание вычислительного процесса и структуры данных. Результат шага даётся через результат предшествующего шага. Такое описание называется рекурсией. Даёт краткое описание процесса. Пример. Скалярное произведение (a,b)= a1·b1 + a2·b2 + a3·b3. Запишем алгоритм скалярного произведения для произвольной длины вектора Σ=0, Σ=Σ+ai·bi. Пусть: 1) Элементы векторов располагаются последовательно слева направо, 2) Имеется указатель текущего элемента, 3) Определена операция "следующий элемент". Введение рекурсии (реализация циклов) требует установления отношения следования между элементами данных (т.е. введение понятия соседства и перехода к следующему). Использование рекурсивно (итеративно) описанного действия предполагает наличие структуры операндов, и эта структура является свойством операндов.

2. Структуры данных и математические структуры.Одной из наиболее общих математических абстракций является понятие алгебраической системы < А, О, R >, где A - множество операндов, О - множество операций →А, R - множество отношений ,  - арность операций,   - арность отношений. Если операций нет - модель (структура). Если отношений нет - универсальная алгебра. Математическая структура S=(M₁,…,M_k; p₁,…,p_s) есть одно или несколько множеств М₁,…,М_к, элементы которых находятся в некоторых отношениях р₁,…,p_s.М₁,…,М_к – базисные множества структуры. Каждое отношение p_i есть двоичная функция, аргументами которой являются элементы базисного множества. Если аргументы функции находятся в отношении, то значение p_i = ИСТИНА. Структура данных есть модель данных в виде математической структуры. Примеры: 1) множество операндов и операций и порядок их записи (арифметическое выражение), 3) множество узлов детали и порядок их соединения (чертеж), 4) множество людей и родственные связи между ними (генеалогическое дерево), 5) множество населенных пунктов и пути сообщения (карта).

3. Переменные структуры и схемы структуры.(a1, a2, a3)  – вектор – переменная. Переменная – множество значений и имя, которому можно присвоить конкретное значение. Структура данных S_a=(М_а, R; p_a, p₁), которая соответствует рассмотрению структуры как переменной величины, называется схемой структуры.

4. Понятие экземпляра, схемы структуры.Структура данных S_a^*=(М_а, R; p_a, p₁^*) с установленными значениями элементов, называется экземпляром. p₁^* - отражает не отношения между элементами, а индивидуальные свойства элемента. Изолированные элементы множества, не связанные стрелками, не изображаются на графе. Структура данных S_a=(М_а, R; p_a,p₁), которая соответствует рассмотрению структуры как переменной величины, называется схемой структуры.

5. Линейные структуры данных.Структуры с бинарными отношениями допускают случай графического изображения. Элементы множества изображаются точками или кружками; пары (ai,aj), для которых отношение истина, соединяются стрелкой от первого аргумента ко второму. Образ структуры с бинарными отношениями - ориентированный граф. Структуры, которым соответствует ориентированный граф с вершинами, лежащими на одной ломаной, называют линейными. Есть два особых элемента:

начальный элемент a₁: ("j) p(a_j,a₁)=л не имеет предшествующего элемента; конечный элемент a_n: ("j) p(a_n,a_j)=л не имеет следующего элемента.

6. Структура машинной памяти. Вектор памяти как образ линейной структуры. Машинный образ абстрактной структуры данных называется структурой хранения данных. Структура памяти S= ({ячейки}, {адреса}, {значения}; ра, рв). Отношение следования между элементами памяти реализовано программным путем (в отличие от структур программ). Программа может реализовать только те отношения, которые могут быть охарактеризованы как отношения целых чисел (адресов). Возможный способ хранения вектора – использование непрерывной области памяти. Два элемента являются соседними, если адрес одного из них отличается на единицу от адреса другого.  Такое размещение не фиксируется в  аппаратуре, а должно быть реализовано программой. Значение a (база) – может играть роль имени всего вектора, смещение до элемента определяется номером элемента. Структура хранения подобного типа (т.е. последовательность однотипных элементов единиц памяти с адресами, возрастающих на единицу), обеспечивающая реализацию абстрактных линейных структур данных (векторов), обычно называется вектором памяти или одноместным (одноиндексным) массивом.

7. Практическая работа 1: Структура хранения множеств. Множество – набор элементов. Для множества определены операции: проверка наличия элемента aÎA, добавление элемента A+a, удаление элемента A –a.  Теоретико-множественные операции: объединение AÈB, пересечение  AÇB, вычитание A\B. Универс U – множество всех элементов. Конкретизация (допущения и ограничения):  элементы множества проиндексированы (каждому элементу соответствует уникальный индекс), множество индексов элементов составляют непрерывный диапазон целых значений. Тогда любое множество AÌU может быть описано характеристическим вектором a=(a₁ a₂… a_n), ,

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

8. Практическая работа 2: Структуры хранения для матриц специального вида.Ленточные матрицы. Для хранения элементов можно выделить непрерывный вектор памяти размера 3*n-2. Адрес (a_ij) = a + 3*(i-1) + (j-i). Треугольные матрицы. Подход 1. Матрицы подобного вида можно представить как матрицы общего вида и использовать для хранения двухиндексные массивы. Используется память V_исп= n², необходимая память V_необ= n (n+1) /2. Эффективность использования памяти E_mem» 0.5. Подход 2. Исключение хранения элементов ниже главной диагонали (построчная запись в массив). Адрес(a_ij) = a + i*n – i*(i-1)/2 + (j-i), 0 £ i,j £ n-1. Ускорение доступа – использование вектора указателей на первые элементы каждой строки. Адрес(a_ij) = pRow[i] + (j-i), 0 £ i,j £ n-1. Подход 3. Представление матрицы в виде набора векторов. Подход 4. Матрица как вектор векторных элементов (шаблоны).

9. Динамические структуры.Структуры данных являются операндами операций обработки. Результаты вычислений также являются структурами, модель которых может как совпадать, так и отличаться от структуры исходных данных. Пример. Организация последовательного вызова подпрограмм. Для возврата в точку вызова необходимо запоминать адрес возврата. При завершении вызываемой подпрограммы для возврата используется последний запомненный адрес. В ходе вызова подпрограмм количество запоминаемых адресов постоянно изменяется (увеличивается при вызове очередной подпрограммы и уменьшается после завершения работы текущей подпрограммы). Отличительная особенность – структура исходных и результирующих данных являются близкими. Выполним анализ примера. Текущий набор адресов – линейная структура S_n=(a₁ a₂ … a_n). Пусть T – операция исключения последнего адреса. Тогда T(a₁ a₂ … a_n a_n+1) = (a₁ a₂ … a_n). Пусть P – операция добавления нового адреса. Тогда P(a_n+1; (a₁ a₂ … a_n)) = (a₁ a₂ … a_n a_n+1). Орграф результата является подорграфом орграфа операнда или включает его. Последовательное применение операций T и P позволяет получить набор состояний стека адресов. Пусть: P₁ - отношение следования, порождаемое операцией вставки, P₂  - отношение следования, порождаемое операцией исключения. Тогда стек есть структура S=(M_i,P₁, P₂), в которой каждый элемент – структура, в любой момент существует только один конкретный элемент из M, элементы частично упорядочены по включению. Динамическая структура есть математическая структура, которой соответствует частично-упорядоченное (по включению) базовое множество M, элементы которого являются структурами данных. При этом отношения включения индуцируются операциями преобразования структуры данных.

10. Практическая работа 3: Структуры хранения динамических структур типа стек. S - стек, |S| - количество элементов в стеке, S_n^k - стек, n – размер памяти, k – количество значений, d - код выполнения операции (=1 – стек пуст, =2 – стек полон). Операции: S(n) ® S_n⁰ - создание стека, S<<x ® S^' – вставка в стека (при k=n Þ S^' = S и d=2), S>>x ® S^' - исключение из стека (при k=0 Þ S^' = S и d=1), a₀(S) - предикат проверки пустоты стека (a ₀(S)=1 при k=0), a(S) - предикат проверки переполнения памяти (a(S)=1 при k=n). Аксиомы: S=S(n) Þ S = S_n⁰ и a ₀(S)=1 – созданный стек является пустым, S^'=S<<x Þ a₀(S)=0 – стек, в который выполнена вставка, не пуст, S^'=S>>x Þ a(S) =0 – стек после операции исключения не полон, S^'=(S<<x)>>y Þ x=y – при выборке значения из стека извлекается последнее вставленное значение, S^'=S>>x, a₀(S)=1 Þ S^' = S и d=1 – выборка значения из пустого стека устанавливает код завершения d=1, S^'=S<<x, a(S)=1 Þ S^' = S и d=2 – вставка значения в полный стек устанавливает код завершения d=2. Для хранения элементов базисного множества выделяется вектор памяти размера, достаточного для хранения максимально возможного количества значения в стеке. Хранение значений в памяти осуществляется последовательно от младшего элемента вектора к старшему. Для запоминания количества хранимых в стеке значений используется индекс последнего занятого элемента в векторе.

11. Практическая работа 4: Структуры хранения динамических структур типа очередь. Очередь (вставка в конец очереди, исключение из начала – дисциплина FIFO – first in, first out). Вставка значений происходит в начало очереди, исключение значений – с конца очереди Þ для индикации начала и конца очереди требуется два индекса. Li – конец, Hi – начало. Выборка из элемента с индексом Li и увеличение Li

Вставка - увеличение Hi и запись в элемент с индексом Hi. В ходе вычислений может возникнуть ситуация Li= Hi=n-1. Тогда вставка нового значения невозможна, а E_mem»0. Способы достижения полного использования памяти: сдвиг значений очереди после выборки очередного значения (т.е. обеспечение Li=0) – возрастание накладных расходов, использование левого участка свободной области при достижении Hi=n-1 (т.е. при отсутствии свободной памяти справа). Структура хранения, получаемая из вектора расширением отношения следования парой p(an,a1), называется циклическим или кольцевым буфером. Реализация кольцевого буфера логически может быть обеспечена переходом индексов Li и Hi при достижении граничного значения MemSize-1 на индекс первого элемента вектора памяти.

12. Сравнение структур хранения линейных и динамических структур.

Линейные структуры

Динамические структуры

Базисное множество – множество элементов

Элементы базисного множества являются структурами ("ДС – структуры структур")

Базисное отношение – отношение следования

Базисное отношение – отношение следования

В структуре хранения хранятся все элементы структуры

В структуре хранения хранится только текущий элемент структуры

Отношение следования реализуется при помощи адресной арифметики

Отношение включения реализуется при помощи программ

Программы, реализующие отношение включения, называются средствами поддержания динамической структуры.

13. Статическое и динамическое распределение памяти.Распределение памяти до начала процесса вычислений называется статическим. Распределение памяти в ходе выполнения программы называется динамическим распределением памяти. Процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область памяти называется перепаковкой памяти или просто перепаковкой.

14. Управление памятью путем перепаковки структур хранения.Процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область памяти называется перепаковкой памяти или просто перепаковкой. Перепаковка обеспечивает эффективное использование одного ресурса ЭВМ (памяти) за счет другого ресурса (времени). Для выполнения перепаковки требуется разработка управляющих программ. Выполнение функций анализа свободной памяти, планирование размещения структур, переписывание структур называется управление памятью. Комплекс программ, реализующих управление памятью, называется системой управления памятью. Необходимость перепаковки обуславливается принятым способом реализации отношений следования.

15. Практическая работа 5: Структура хранения нескольких стеков в общей памяти.N – количество стеков, m – размер памяти. Свойства: Li₀=0 - условие неподвижности 1 стека, Hi_k=Li_k-1 - условие пустоты, Hi_k<Li_k+1 - условие неперекрытия, Hi_k=Li_k+1-1 - условие переполнения. Для выполнимости последних двух условий для всех стеков введем фиктивный стек N, для которого Li_N=m. Будем предполагать, что все стеки используются с одинаковой интенсивностью Þ память распределяется всем стекам поровну: Li₀=0, Li_N=m, Li_k=Li_k-1+ m / N, 1 £ k < N. Выполняется при попытке вставки нового значения в стек s, у которого отсутствует свободная память: F = S (Hi_k-Li_k-1-1),1 £ k < N.   F =0 – свободной памяти нет, F =1 – свободен 1 элемент памяти и его следует отдать стеку s, F >1 – необходимо перераспределить свободную память. Для гарантированного выделения свободной памяти стеку s при наличии только одного свободного элемента памяти (случай 2), выполним: Hi_s=Hi_s+1 – перед началом процедуры оценки свободной памяти, Hi_s=Hi_s -1 – после завершения перепаковки. Снова предположим, что все стеки используются с одинаковой интенсивностью Þ свободная память должна распределиться всем стекам поровну: Li'₀= Li₀, Li'_N= Li_N, Li'_k=Li'_k-1+ (Hi_k-1-Li_k-1+1) + F / N, 1 £ k < N. На равномерности распределения памяти может сказаться целочисленность операции деления.

16. Роль гипотез о росте структур при разработке систем управления памятью путем перепаковки.Гипотезы о поведении структур служат основой для принятия решений о распределении памяти. Формирование гипотез происходит в результате теоретического анализа модели решаемой задачи или может быть выполнено на основе статистических данных, получаемых в ходе вычислительных экспериментов с проектируемой программной системой. Гипотеза 1: Стеки используются с одинаковой интенсивностью, память разделяется между стеками поровну. Гипотеза 2: Интенсивность использования стеков различается. Конструктивное предположение о характере такой неравномерности может состоять в гипотезе сохранения локальных тенденций роста стеков, т.е. в каждый момент времени использование стеков на последующих шагах вычислений характеризуется точно таким же поведением, что и на предшествующих этапах обработки данных. Сохранение локальных тенденций роста: показатель роста стека d_i = max ( 0, DataCount' _i – DataCount _i), суммарный показатель роста D = S d_i, 0 £ i < N,  правило распределение памяти для стеков в соответствии с их показателями роста Li'_k=Li'_k-1+ (Hi_k-1-Li_k-1+1) + F*(d_i / D), 1 £ k < N. Гипотеза 3: Использование вероятностных предположений о поведении стеков. Пусть есть q, 0£q£1, вероятность выполнимости гипотезы сохранения локальных тенденций роста. Тогда Li'_k=Li'_k-1+ (Hi_k-1-Li_k-1+1) + (1-q)*(F/N)+q*F*(d_i / D), 1 £ k < N.

17. Оценка параметров модели в ходе выполнения программ (адаптация).Пусть s есть количество выполненных перепаковок памяти за некоторый отрезок времени Dt. Величина s зависит от значения q, и для повышения эффективности функционирования системы следует определить такое q, чтобы количество перепаковок было минимальным, т.е. min s(q). Возможная схема определения оптимального значения q может состоять в следующем: выполним оценку величины s на последовательных друг за другом отрезках времени Dt и определим величину изменения количества выполненных перепаковок: D s = s'- s, примем следующее правило корректировки  значения q: q' = q + Dq, если Ds £ 0, q' = q - Dq, если Ds > 0, где Dq есть параметр схемы адаптации.

18. Линейный список.Необходимость перепаковки для обеспечения динамического распределения памяти возникает в силу принятого способа реализации отношения следования - следующий элемент структуры располагается в следующем элементе памяти (с адресом, большим на 1). Устранение перепаковки возможно только при кардинальном изменении способа реализации основных отношений – необходимо допустить размещение следующих элементов структуры в произвольных элементах памяти (там, где имеется свободные области памяти). Возможность такого подхода может быть обеспечена запоминанием для каждого текущего элемента структуры адреса памяти, где хранится следующий элемент. Интерпретация содержимого элемента памяти (значение или адрес следующего элемента) в самом простом варианте может быть обеспечена фиксированным форматом используемых участков памяти. Под квантом памяти понимается последовательность элементов памяти с последовательно-возрастающими адресами. Именем (адресом) этой группы считается адрес первого слова кванта. Элементы кванта называются полями. В общем случае, набор элементов памяти, связанных с одним именем, называют звеном. Далее будут использоваться двухэлементные звенья памяти, в которых первое поле будет использоваться для хранения значений, а второе поле – для запоминания адресов. Способ задания отношения следования, в котором фиксация месторасположения следующего элемента производится путем запоминания соответствующего адреса памяти, называется сцеплением (пары, хранящие a_i и a_i+1, сцеплены адресными указателями). Для изображения структуры хранения с использованием сцепления звенья памяти рисуются в виде прямоугольников, а сцепление звеньев показывается в виде стрелок. Индикация последнего звена в списке обычно производится записью в поле адреса некоторого барьера – фиктивного (неадресного) значения (как правило, 0 или -1). Для доступа к звеньям списка должен быть известен адрес первого звена списка. Указатель, в котором этот адрес запоминается, называется переменной связи. Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.

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

21. Практическая работа 6: Реализация структуры хранения нескольких стеков с использованием списков на языке высокого уровня.Звено списка представляется в виде объекта класса TLink. Образ памяти, выделенной для хранения стека, определяется в виде массива звеньев-объектов. Все свободные звенья объединяются в один список свободных звеньев. Звенья этого списка используются при необходимости свободной памяти, в этот список звенья должны возвращаться после освобождения. Вставка звена в список свободных звеньев: новое звено включается в начало списка свободных. Выборка звена из списка свободных звеньев: для выделения используется первое звено списка свободных. Структура хранения стека – линейный список (начало списка – вершина стека). Вставка в стек: звено для нового значения берется в списке свободных. Выборка из стека: исключаемое звено из стека должно оказаться в списке свободных. Схемы работы со стеком и со списком свободных звеньев совпадают. Список свободных звеньев есть стек.

22. Сравнение непрерывной и списковой структур хранения.

Непрерывная память

Списки

Перепаковка для динамического распределения памяти

Динамическое распределение памяти эффективно реализуется при помощи списка свободных звеньев

В структуре хранения хранятся только данные

В структуре хранения хранятся данные и указатели

К элементам структуры данных обеспечивается прямой доступ

К элементам структуры данных обеспечивается последовательный доступ

23. Динамическое распределение памяти в языке С/С++ (выделение и освобождение памяти).Среда выполнения обеспечивает динамически распределяемую область памяти: звено, выделение звена – pTemp = new TDatLink(), освобождение звена – delete pTemp.

24. Реализация стека с использованием динамически распределяемой памяти.Вставка в стек: PTDatLink pTemp; pTemp = new TDatLink(); pTemp-> SetDatValue(Val); pTemp->SetNextLink(pFirst); pFirst = pTemp. Выборка из стека: PTDatLink pTemp = pFirst; Val = pFirst->GetDatValue(); pFirst = pFirst->GetNextLink(); delete pTemp.

25. Пример использования стеков: поразрядная сортировка. 1) Разложить значения по стекам (номер стека - младшая цифра), 2) Собрать значения из стеков (от старшего стека), 3) Разложить значения по стекам (номер стека - старшая цифра), 4) Собрать значения из стеков (от младшего стека).
26. Пример использования стеков: преобразование арифметических выражений в польскую форму записи. Формат записи выражения. Выражение синтаксически правильно (без ошибок). Допускаются только однобуквенные идентификаторы для операндов. В записи выражения нет пробелов; выражение заканчивается знаком '=': A+(B-C)*D-F/(G+H)=. Алгоритм: 1) Для операций вводится приоритет: '*' '/' (3), '+' '-' (2), '(' (1), '=' (0), 2) Для хранения данных используется 2 стека (1 – для результата, 2 – для операций), 3) Исходное выражение просматривается слева направо, 4) Операнды по мере их появления помещаются в стек 1 , 5) Символы операций и левые скобки помещаются в стек 2, 6) При появлении правой скобки последовательно изымаются элементы из стека 2 и переносятся в стек 1. Данные действия продолжаются либо до опустошения стека 2 либо до попадания в стеке 2 на левую скобку, 7) Если текущая операция, выделенная при обходе выражения, имеет меньший (более низкий) приоритет, чем операция на вершине стека 2, то такие операции из стека 2 переписываются в стек 1.   

27. Практическая работа 7: Разработка общего представления линейного списка для обеспечения списковой структуры хранения. Представим значения в виде объектов классов, являющихся производными из одного общего базового класса. В поле значения звена списка будем размещать указатель на объект значение. pFirst – указатель на первое звено списка, pLast – указатель на последнее звено списка, pCurrLink – указатель на текущее звено списка, pPrevLink – указатель на звено, предшествующее текущему, CurrPos – номер текущего звена, ListLen – количество звеньев в списке. Для повышения общности схемы реализации будем использовать вместо величины NULL константу pStop для фиксации ситуаций,
в которых указатель не содержит адрес какого-либо звена списка. Информационные методы: IsEmpty – проверить, не является ли список пустым, GetListLength – получить количество звеньев списка. Методы доступа к значениям в списке: GetDatValue – получить указатель на значение из звена списка (обращение возможно только к первому (FIRST), текущему (CURRENT) или последнему звеньям списка (LAST); желаемый вариант доступа задается через параметр метода). Методы навигации по списку (итератор): Reset – установить текущую позицию на первое звено, GoNext – переместить текущую позицию на звено вправо, IsListEnded – проверка завершения списка (под ситуацией завершения списка понимается состояние после применения GoNext для текущей позиции, установленной на последнем звене списка, т.е. когда pPrevLink=pLast, pCurrLink=pStop), GetCurrentPos – получить номер текущего звена, SetCurrentPos – установить текущую позицию на звено с заданным номером. Вставка звеньев: InsFirst – вставить звено перед первым звеном списка, InsLast – вставить звено после последнего звена, InsCurrent – вставить звено перед текущим звеном списка. При выполнении операций вставки звеньев следует учитывать, что список может быть пустым. После выполнения вставки необходимо обеспечить корректность значений указателей первого, текущего и последнего звеньев списка. При корректировке указателей следует учитывать возможность различного положения текущей позиции списка: текущая позиция является первым звеном (pCurrLink=pFirst), текущая позиция является вторым звеном (pPrevLink=pFirst), текущая позиция находится внутри списка, текущая позиция является последним звеном (pCurrLink=pLast), текущая позиция выходит за пределы списка (pPrevLink=pLast). Удаление звеньев: DelFirst – удалить первое звено списка, DelCurrent – удалить текущее звено, DelList – удалить список.
28. Общая характеристика стандартной библиотеки шаблонов. В стандарте языка С++ предусматривается наличие в среде программирования стандартной библиотеки шаблонов (Standard Template Library, STL).

Основные понятия библиотеки STL. Библиотека включает в свой состав большое количество контейнеров, представляющих собой структуры данных, в которых могут храниться объекты. В числе имеющихся контейнеров: vector<T> - вектор переменного размера, list<T> - двусвязный список, queue<T> - очередь, stack<T> - стек, deque<T> - дек, priority_queue<T> - приоритетная очередь, set<T> - множество, multiset<T> - множество с повторением элементов, map<key,val> - ассоциативный массив (таблица), multimap<key,val> - ассоциативный массив с повторением ключей. Для быстрого и эффективного построения вычислительных процедур, библиотека обеспечивает итераторы для всех видов контейнеров, которые представляют унифицированный механизм последовательного доступа к элементам контейнеров.

Общая схема: <класс-контейнер>::iterator Iter; - объявление итератора, Iter = <объект-контейнер>.begin(); - установка на первый элемент, Iter != <объект-контейнер>.end(); - проверка на завершение,  ++Iter – переход к следующему элементу.

В зависимости от типа контейнера, итератор может обеспечивать прямой доступ, быть одно- или дву- направленным, предназначенным только для чтения или записи и др. Библиотека содержит для контейнеров большое количество реализованных обобщенных алгоритмов. В числе таких алгоритмов: for_each() - вызвать функцию для каждого элемента, find() - найти первое вхождение элемента, find_if() - найти первое соответствие условию, count() - подсчитать число вхождений элемента, count_if() - подсчитать число соответствий условию, replace() - заменить элемент новым значением, copy() - скопировать элементы, unique_copy() - скопировать только различные элементы, sort() - отсортировать элементы, merge() - объединить отсортированные последовательности и др.

1. Система для арифметических действий над полиномами (представление полиномов, управление памятью, выполнение операций). Полиномы как формальный объект хорошо изучены в математике. Математическая модель – алгебра полиномов. Под многочленом понимается выражение из нескольких термов, соединенных знаками сложения или вычитания. Терм включает коэффициент и моном, содержащий одну или несколько переменных, каждая из которых может иметь степень P = S Coeff*X^AY^BZ^C. В число возможных вычислительных процедур над полиномами входят действия по вычислению значений полинома при заданных значениях переменных, а также большинство известных математических операций (сложение, вычитание, вычисление частных производных, интегрирование и т.п.). Возможный вариант структуры хранения – стеки. Одна из наиболее частных операций – приведение подобных мономов. Для ускорения поиска подобных элементов целесообразно ввести какое-либо правило упорядочения мономов (отношение следования). Возможный подход – организация порядка по аналогии с упорядочением слов в словарях (лексикографический порядок). Установим старшинство переменных в порядке XYZ. Тогда X^A1Y^B1Z^C1> X^A2Y^B2Z^C2 Û Установленный порядок является линейным Þ правило следования может быть сформулировано в более простом виде. Пусть область возможных значений степеней переменных имеет вид                         0 £ A, B, C < 10. Тогда можно установить взаимно-однозначное соответствие троек (A, B, C) и целых чисел следующим образом (A, B, C) ~ ABC =A*100+B*10+C
Обратное соответствие определяется при помощи выражений A=E(ABC%100), B=E(ABC-A*100)%10, C=ABC-A*100-B*10. Получаемые по степеням целые величины ABC (будем называть их далее свернутыми степенями или индексами) порождают тот же самый, ранее установленный, порядок следования мономов X^A1Y^B1Z^C1> X^A2Y^B2Z^C2 Û ABC₁>ABC₂^. Приведенные выражения представляют собой правила позиционной системы счисления (где N=10 есть основание системы). Таким образом, на множестве мономов определено отношение следования и многочлен может быть рассмотрен как линейная структура, элементами которой являются термы. В ходе вычислений количество мономов в полиноме может изменяться Þ полиному соответствует динамическая структура. Целесообразной структурой хранения полинома является линейный список

2. Представление многочленов от нескольких переменных. Исключение хранения мономов с нулевыми коэффициентами. Структура хранения полинома, тождественно равного нулю,
не содержит звеньев (список вырождается). Данная ситуация может отражаться установкой нулевого значения указателю на список, но тогда все программы для полиномов должны включать специальные действия по обнаружению и обработке этого уникального состояния полинома. Возможное решение проблемы может состоять во введении дополнительного служебного звена, размещаемого в начале списке (звено-заголовок). Звено-заголовок маркируется логически-недопустимым значением индекса монома. Аналогичным образом можно уйти от проверки нулевого указателя последнего звена, установив в последнем звене в качестве следующего звена первый элемент списка (звено-заголовок). Данная модификация приводит к использованию в качестве структуры хранения циклический список. Структура хранения нулевого полинома имеет вид:

3. Схема наследования программ для обеспечения структуры хранения полиномов.

4. Реализация программ для обеспечения работы с линейным циклическим списком.Можно уйти от проверки нулевого указателя последнего звена, установив в последнем звене в качестве следующего звена первый элемент списка (звено-заголовок). Данная модификация приводит к использованию в качестве структуры хранения циклический список

5. Структура класса для представления на ЭВМ полиномов от нескольких переменных. Класс THeadRing является производным от класса TDatList. Надо переопределить методы: THeadRing  – добавить создание звена-заголовка, ~THeadRing – добавить удаление звена-заголовка, InsFirst – добавить установку указателя звена-заголовка на pFirst, DelFirst – добавить установку указателя звена-заголовка на pFirst. Класс TPolinom обеспечивает поддержку структуры хранения и реализацию операций обработки над полиномами. Методы класса: TPolinom – конструктор задания полинома по массиву параметров, GetMonom – получение указателя на моном из текущего звена списка, operator+ – сложение полиномов, operator= – присваивание.

6. Алгоритм сложения многочленов от нескольких переменных. Основные алгоритмические моменты метода сложения полиномов operator+ состоят в следующем: результат сложения запоминается в объекте первого операнда; операция сложения сводится к последовательной обработке мономов полиномов-операндов p и q: если моном p меньше монома q, то моном q добавляется в полином p; и текущая позиция в q сдвигается вправо; если моном p старше монома q, то текущая позиция в p сдвигается вправо; если моном p равен моному q, то коэффициенты мономов складываются и запоминаются в p; далее если результат сложения равен 0, то моном в p удаляется и текущая позиция
в q сдвигается вправо; если же результат сложения ненулевой, то текущая позиция сдвигается вправо и в p и в q.

7. Представление текста связным списком. Текст – линейная последовательность символов, линейная последовательность слов (слово - линейная последовательность символов), линейная последовательность строк, строки состоят из слов, слова – из символов и т.д. Математическая модель текста – иерархическая структура представления (дерево). Уровень символов – список символов. Уровень слов – список слов. Уровень строк – список строк. На всех уровнях представления (кроме символов) значение задается указателем на соответствующую структуру ниже расположенного уровня. Разработанная структура хранения называется связным (иерархическим) списком. Абстрактная структура типа дерева представима в виде связного списка. В списке существуют делимые и неделимые (атомарные, терминальные) элементы. Визуальное представление текста содержит только атомарные элементы, структура хранения должна включать все элементы. Разные типы звеньев – трудности при управлении памятью, дублирование программ обработки. Единый тип звена: typedef Tlink *PTLink; class TLink{PTLink pNext; int Atom; // =1 – звено-атом union {PTLink pDown; char Symb;}.

8. Операторы объединения списков и расчленения списка. Размер введенного унифицированного звена – 10 байт (=16 при учете округления при динамическом выделении памяти). Для представления символов такой вид звена является неэкономичным. Возможное решение проблемы – повышение уровня атомарности.

Целесообразный уровень – уровень строк. Структура звена: #define TextLineLength 20, typedef char TStr[TextLineLength]; class TTextLink : public TDatValue { protected: TStr Str; TTextLink *pNext, *pDown;};. Указатель pNext есть ссылка на следующий элемент того же уровня. Указатель pDown есть ссылка на структуру хранения ниже расположенного уровня. Признак атомарности элемента pDown==NULL. Для ссылки на ниже расположенный уровень используется указатель pDown. Поле Str можно использовать для именования структурных элементов текста (название всего текста, его разделов, подразделов и т.д.). Базовые операции обработки звена: порождение звена (конструктор): TTextLink ( TStr s=NULL, PTTextLink pn=NULL, PTTextLink pd=NULL ); переход к следующей звену: PTTextLink GetNext() { return pNext; }, переход на подуровень: PTTextLink GetDown() { return pDown; }. Структура: PTTextLink pFirst;// корень дерева, PTTextLink pCurrent;// текущая строка, stack<PTTextLink> Path;// стек траектории, Навигация:

int GoFirstLink(void);// к первой строке, int GoDownLink (void);// к след. строке по Down, int GoNextLink (void);// к след. строке по Next, int GoPrevLink (void); // к пред. позиции. Указатель текущей строки pCurrent не включается в стек траектории движения по тексту. В стеке Path размечаются указатели на все звенья, лежащие на пути от начала текста до текущего звена. Операция удаление строки не выполняется, если исключаемый элемент не является атомарным.

9. Алгоритм обхода иерархического списка. Печать текста: схема обхода – текст текущей строки, текст подуровня, текст следующего раздела текста того же уровня (top-down-next). while (1) { if ( pLink != NULL ) { cout << pLink->Str;// обработка звена, St.push(pLink); // запись в стек, pLink = pLink->pDown;//переход на подуровень}  else if ( St.empty() ) break; else {pLink = St.top(); St.pop();//выборка из стека, pLink = pLink->pNext; //переход по тому же уровню}. Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}'). Общая схема алгоритма: повторить: ввод строки, ЕСЛИ '}' ТО Завершить, ЕСЛИ '{' ТО Выполнить рекурсивно Ввод_текста, Добавить строку на том же уровне.

10. Копирование списка.Для копирования текста необходимо предварительно скопировать разделы текста, на которые указывают указатели pDown и pNext
Þ алгоритмы обхода NDT или DNT. Для навигации по тексту-копии также необходим стек; использование стеков исходного текста и текста-копии должны быть согласованы. Для навигации по исходному тексту и тексту-копии используется один – объединенный – стек. Каждое звено текста копируется за два прохода: 1 проход – при подъеме из подуровня (pDown): создание копии звена, заполнение поля pDown (подуровень уже скопирован), запись в поле Str значения Copy (для распознания звена при попадании на него при втором проходе), запись в поле pNext указателя на звено-оригинал (для возможности последующего копирования текста исходной строки), запись указателя на звено-копию в стек. 2 проход – при извлечении звена из стека: заполнение полей Str и pNext, указатель на звено-копию запоминается в переменной cpl.

11. Сборка мусора. При удалении разделов текста для освобождения звеньев следует учитывать следующие моменты: обход всех звеньев удаляемого текста может потребовать длительного времени, при множественности ссылок на разделы текста (для устранения дублирования одинаковых частей) удаляемый текст нельзя исключить – этот текст может быть задействован в других фрагментах текста. Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL). Подобный способ выполнения операций удаления текста может привести к ситуации, когда в памяти, используемой для хранения текста, могут присутствовать звенья, на которые нет ссылок в тексте и которые не возвращены в систему управления памятью для повторного использования. Элементы памяти такого вида носят наименование "мусора". Наличие "мусора" в системе может быть допустимым, если имеющейся свободой памяти достаточно для работы программ. В случае нехватки памяти необходимо выполнить "сборку мусора". Возможный подход доступа к системе управления памятью – разработка специальной системы управления при помощи перегрузки операторов new и delete. Для системы управления память выделяется полностью при начале работы программы; вся память форматируется и представляется в виде линейного списка свободных звеньев. Для фиксации состояния памяти в классе TTextLink создается статическая переменная MemHeader типа TTextMem. Для выделения и форматирования памяти определяется статический метод InitMemSystem класса TTextLink. При запросе памяти в операторе new выделяется первое свободное звено. При освобождение звена в операторе delete звено включается в список свободных звеньев. Для различения звеньев «мусора» и текста – маркировка текстовых звеньев и звеньев списка свободных звеньев.

12. Плексы как представление рисунков, состоящих из точек и соединяющих их отрезков. Рассмотрим в качестве базовых объектов основные геометрические фигуры – точку, окружность, прямоугольник и т.д.

Информационное описание объектов – параметры фигуры (координаты, размер, радиус и др.). В общем случае, описание фигуры включает значение координат некоторой опорной точки. Операции обработки геометрических объектов включают методы для задания и изменения параметров; расширим набор операций процедурами визуализации (например, на экране дисплея) и скрытия фигур. Для обеспечения возможности динамической визуализации геометрических объектов введем тип данных, значения которого вычисляются в соответствии с задаваемым формульным выражением.

Составной объект – набор геометрических объектов (как базовых, так и составных), рассматриваемых при выполнении операций обработки как единый объект. Геометрический объект может быть сконструирован с использованием уже существующих объектов (например, ломаная может быть определена через набор конечных точек составляющих отрезков). Геометрический объект может быть образован при помощи сборки существующих объектов – рассмотрим данный способ построения новых объектов на примере рисунков (чертежей), образованных только из объектов двух базовых типов: точек и линий. Узел структуры хранения представляет линию чертежа. Указатель на начальную точку линии может также указывать на линию, т.е. конечная точка предыдущей линии является начальной точкой следующей линии. Структура хранения данного вида называется плексом (содержит элементы разного типа). Плекс является общей структурой хранения сетевых моделей данных. Повторяющая точка на чертеже должна быть представлена одним и тем же объектом (не следует допускать множественности представления одного и того же значения). Разработанная структура хранения позволяет обеспечить представление чертежей, которые можно нарисовать без отрыва карандаша от бумаги.

13. Алгоритм обхода плекса. Алгоритм 1. // общая схема алгоритма обхода для плекса: // переход на крайнюю левую точку, while ( pN Ï TChartPoint ) { St.push(pN); pN = pN->GetFirstPoint();}//подъем по плексу и рисование, pF = pN; while ( !St.Empty() ) {pN = St.top(); St.Pop(); pL = pN->GetLastPoint();//рисование линии <pN,pF,pL> pF = pL;}. Переходим на крайнюю левую точку ,поднимаемся по плексу (пока стек не пуст, достаем точки траектории и рисуем линии). Алгоритм 2. Рекурсивный вариант (общая схема): TChartPoint *Show ( TChart *pN ) {if (pN != NULL) pL = NULL; else if (pN Î TChartPoint) pL = pN; else {pF = Show(pN->GetFirstPoint()); pL = Show(pN->GetLastPoint());//рисование линии <pN,pF,pL>} return pN;}. Линии, определяемые при обходе плекса, помещаются в стек. При линии, извлекаемой из стека, последовательно определяются начальная и конечная точки. Для определения начальной точки используется метод GetFirstPoint линии. Если получаемый указатель указывает на линию, обработка текущей линии откладывается (линия помещается в стек) и начинается анализ новой линии, данная процедура выполняется итеративно до получения линии, с которой начали.

14. Алгоритм вставки линии. Для итеративного выполнения рекурсии определим класс для описания линии. Алгоритм обхода для плекса с подплексами. Линии, определяемые при обходе плекса, помещаются в стек. При линии, извлекаемой из стека, последовательно определяются начальная и конечная точки. Для определения начальной точки используется метод GetFirstPoint линии; если получаемый указатель указывает на линию, обработка текущей линии откладывается (линия помещается в стек) и начинается анализ новой линии; данная процедура выполняется итеративно до получения линии с известной начальной точкой. Для определения конечной точки используется
метод GetLastPoint линии; если получаемый указатель указывает на линию, обработка текущей линии снова откладывается – текущая линия помещается в стек; после этого формируется описание новой линии, которая также помещается в стек и цикл алгоритма обхода повторяется. При получении линии с определенными граничными точками следует выполнить обработку линии (нарисовать); из стека извлекается новая линия, для которой конечная точка обработанной линии используется в качестве первой неизвестной граничной точки. Выполнение обхода завершается при опустошении стека линий.

15. Плекс, как представление арифметического выражения. Плекс может рассматриваться как структура представления для выражений самого общего вида (линия – операция, точки – операнды)

Пример: Арифметическое выражение (a*b+c)*(d-e/f):

1. Организация доступа по имени. Таблицы. Поиск по ключу (просмотр и двоичный поиск).Для чтения или записи значения необходимо указать адрес элемента памяти. Для человека более привычный способ указания данных – имя. Пусть K - множество имен, A - множество адресов, тогда отношение "иметь имя" есть функция f: K ® A. Возможный способ – табличное задание функции. Таблица - последовательность строк (записей). Запись может состоять из нескольких полей. Одно из полей должно задавать имя записи (ключ), остальные поля образуют тело записи. Операции с таблицей: поиск записи по ключу, вставка новой записи, удаление записи. Таблица – динамическая структура данных. Базисное множество – семейство линейных структур из записей, базисное отношение включения определяется операциями вставки и удаления записей. Пусть K - множество имен, A - множество значений, A*= A+æ - расширенное множество (æÏA), Z = K´A* - множество записей (z =<k,a>ÎZ), Z- множество всех подмножеств Z. Тогда таблица есть структура T = <Z, p>, где p - базисное отношение включения, t_n^kÎT - текущий элемент (состояние) из k записей (n – размер памяти). Основные операции: поиск по ключу, вставка записи, исключение записи. Дополнительные операции: создание таблицы, предикат проверки пустоты, проверка переполнения памяти. При завершении операции формируется код выполнения d

=1 – таблица пуста, =2 – таблица заполнена, =3 – записи в таблице нет, =4 – запись в таблице уже есть. Аксиомы: созданная таблица является пустой, таблица после операции вставки не пуста, таблица после исключения записи не полна, после вставки записи в таблице поиск этой же записи должен быть успешным, после удалении записи в таблице данная запись должна отсутствовать, результат поиска не зависит от операций вставки и удаления записей с другими ключами. Теоретико-множественные операции: пересечение, объединение, вычитание таблиц. Поиск – линейный (последовательный) просмотр. Вставка – добавление в конец списка. Удаление – исключение (стирание) с уплотнением (ex., путем переписыванием последней записи в удаляемую строку). Сложность операций просматриваемых таблиц: Поиск: Tmin=1, Tmax=N, Tср=N/2 (поиск имеющихся в таблице записей), =p(N/2)+(1-p)N (p-вероятность наличия записи). Вставка: Tср=p(N/2)+(1-p)(N+1)=N+1 (вставка без дублирования). Удаление: Tср=p(N/2+1)+(1-p)N.

Двоичный поиск. В начале поиска искомый ключ сравнивается с ключом записи, располагаемой в середине таблицы. Если искомый ключ имеет меньшее значение, это будет означать, что необходимая запись располагается в первой половине таблицы, если больше – во второй части таблицы (за одно сравнение интервал неопределенности уменьшается в два раза). Далее процедура поиска повторяется аналогично для соответствующей части таблицы.
2. Упорядоченные таблицы. Алгоритм сортировки включением. Таблицы, в которых записи располагаются в порядке возрастания (или убывания) ключей, называются сортированными (упорядоченными). Упорядоченность таблиц может быть организована только при возможности сравнения ключей (на множестве ключей задано отношение линейного порядка). Действия, связанные с размещением записей в порядке возрастания (или убывания) ключей называют сортировкой. Алгоритм сортировки называют устойчивым, если он никогда не меняет относительный порядок в таблице двух записей с равными ключами.  Упорядочивание данных, при котором все значения располагаются в ОП, называются внутренней сортировкой. Сортировка включением. Идея похода – вставка нового значения в упорядоченный набор данных. В ходе сортировки упорядочиваемый набор данных разбивается на две части – упорядоченный (слева) и неупорядоченный (справа) блоки. Оценка сложности: Tmin = N (при сортировке упорядоченного массива), Tmax =

3. Упорядоченные таблицы. Алгоритм сортировки слиянием. Таблицы, в которых записи располагаются в порядке возрастания (или убывания) ключей, называются сортированными (упорядоченными). Действия, связанные с размещением записей в порядке возрастания (или убывания) ключей называют сортировкой. Идея похода – возможность эффективного объединения упорядоченных наборов данных.

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

Оценка сложности: N – количество сравнений при слиянии, log₂N – количество уровней рекурсии, T_min = T_max = T_ср = N log₂N. Процедура слияния использует дополнительную память. Пространственная сложность алгоритма (сложность по памяти): V = N.

4. Упорядоченные таблицы. Алгоритм быстрой сортировки. Таблицы, в которых записи располагаются в порядке возрастания (или убывания) ключей, называются сортированными (упорядоченными). Действия, связанные с размещением записей в порядке возрастания (или убывания) ключей называют сортировкой. Идея похода (Hoare C.A.R.)– использование процедуры разделения упорядочиваемого набора на две части, в одной из которых располагаются значения, меньшие некоторого порогового (ведущего) элемента массива, в другой – соответственно большие значения. Подобный способ разделения может быть выполнен без привлечения дополнительной памяти. При наличии процедуры разделения алгоритм сортировки может быть определен рекурсивно – необходимо разбить упорядочиваемый набор на два блока с меньшими и большими значениями соответственно и затем последовательно отсортировать полученные блоки.

Оценка сложности: T_min = N log₂N, T_max = N^2.

Оценка сложности: T_ср= 1.4(N+1) log₂ N.

5. Представление таблиц с использованием деревьев поиска. Сложность вставки и удаления в упорядоченных таблицах вызвана использованием непрерывной памяти, что приводит, как следствие, к необходимости перепаковок данных. Устранение перепаковок возможно только при использовании списковой памяти, но в этом случае теряется возможность прямого доступа к данным. Достижение эффективности двоичного поиска при списковой структуре хранения требует прямого доступа к звену со средней записью таблицы; из этого звена должна существовать возможность доступа (указатели) к средним звеньям левой и правой частей таблицы и т.д.

"Вычисленная" структура хранения является деревом поиска.

6. Деревья поиска. Алгоритмы обхода. Связный граф без циклов называется деревом. Структура типа дерева (древовидная структура) с базовым типом T – это либо пустая структура, либо узел (вершина) со значением типа T, с которым связано конечное число древовидных структур (поддеревьев) с базовым типом T. Если для любой вершины бинарного дерева значения в левом потомке меньше значения узла, а значение в правом потомке больше значения узла, то такое дерево называется деревом поиска. Обработка дерева – выполнение необходимой операции для каждой узла дерева. Реализация подобного типа действий предполагает умение обхода (обхода) дерева

Представим дерево в общем виде: T – top (корень), L – left (левое поддерево), R – right (правое поддерево).

Тогда возможны следующие варианты обхода: T, L, R – сверху вниз; L, T, R – слева направо; L, R, T – снизу вверх; T, R, L – сверху вниз; R, T, L – справа налево; R, L, T – снизу вверх. Пример: представление арифметического выражения в виде бинарного дерева. Печать значений дерева поиска (схема LTR, рекурсия). void TTreeTable :: PrintTreeTab(ostream &os, PTTreeNode pNode) { if ( pNode != NULL ) { // печать дерева с вершиной pNode, PrintTreeTab(os,pNode->pLeft); pNode->Print(os); os << endl; PrintTreeTab(os,pNode->pRight);}}
7. Деревья поиска. Алгоритмы поиска и вставки.

// поиск в дереве поиска – рекурсия. PTTreeNode

 FindRecord(TKey k,PTTreeNode pNode){if ( pNode != NULL ) { // лист, if ( pNode->Key < k ) // вправо, pNode = FindRecord(k,pNode->Right); if ( pNode->Key > k ) // влево, pNode = FindRecord(k,pNode->Left);} return pNode;}. Введение барьера.

// поиск в дереве поиска – рекурсия PTTreeNode

 FindRecord(TKey k,PTTreeNode pNode){if(pNode->Key<k) // вправо, pNode = FindRecord(k,pNode->Right);if (pNode->Key > k ) // влево, pNode = FindRecord(k,pNode->Left); return (pNode==pBarrier) ? NULL : pNode;}.

Поиск до тупика и вставка. void TTreeTable :: InsRecord ( TKey k, PTDatValue pVal ) { // вставить запись, if ( IsFull() ) SetRetCode(TabFull); else if ( FindRecord(k) != NULL ) SetRetCode(TabRecDbl); else { SetRetCode(TabOK); *ppRef = new TTreeNode(k,pVal); DataCount++;}}

8. Деревья поиска. Алгоритм удаления. Возможные варианты: удаление листа, удаление узла с одним потомком.

Удаление узла с двумя потомками.

void TTreeTable :: DelRecord ( TKey k ) { // удалить запись

if ( FindRecord(k) == NULL ) SetRetCode(TabNoRec); // SKIP_ON

else {

SetRetCode(TabOK);

PTTreeNode pNode = *ppRef;

if ( pNode->pRight == NULL ) *ppRef = pNode->pLeft; // один потомок слева

else if ( pNode->pLeft == NULL ) *ppRef = pNode->pRight; // один потомок справа

else { // два потомка - поиск крайнего справа у левого поддерева

PTTreeNode pN = pNode->pLeft, *ppR = &pNode->pLeft;

while ( pN->pRight != NULL ) {

   ppR = &pN->pRight; pN = *ppR;

} // вместо удаления pNode удается pN

pNode->pValue = pN->pValue; // значение в pNode

pNode->Key = pN->Key;

pNode = pN; *ppR = pN->pLeft; // обход удаляемого pN

}

delete pNode;

}                                               // SKIP_OFF

}

9. Сбалансированные и идеально сбалансированные деревья поиска. Общая схема балансировки при вставке. Дерево является идеально сбалансированным, если для каждого его узла количество узлов в левом и правом поддеревьях различаются не более, чем на 1. (Адельсон-Вельский, Ландис) Дерево является сбалансированным, если для каждого его узла высота левого и правого поддеревьев различаются не более, чем на 1 (АВЛ-деревья). Свойства: идеально сбалансированные деревья являются сбалансированными, операции обработки сбалансированных деревьев (поиск, вставка, удаление) имеют сложность log₂N. Балансировка. Пусть дано сбалансированное дерево, в котором рассмотрим поддерево с корнем в некотором узле r. Обозначим через L и R левую и правую части этого поддерева с высотами h_L и h_R соответственно. Пусть высота h_L после вставки в L нового узла увеличилась на 1. Возможны три ситуации: h_L = h_R : после вставки высоты L и R разные, но условие балансировки не нарушено, h_L < h_R : после вставки h_L = h_R и балансировка поддеревьев улучшается, h_L > h_R : после вставки условие балансировки нарушено, необходима балансировка. Следовать по пути поиска, пока не окажется, что ключа нет в дереве. Включить новый узел, определить новый показатель сбалансированности. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла. При необходимости балансировки после вставки
(для примера, в левое поддерево) можно выделить
две ситуации: высота левого поддерева левого узла больше (т.е. Balance = -1), высота левого поддерева левого узла меньше (т.е. Balance = +1). Однократный левый (LL) поворот.

Двукратный слава направо (LR) поворот.

10. Таблицы с вычислимым входом. Запись и поиск при переполнении (способ открытого перемешивания).Функция преобразования значения ключа к номеру (адресу) строки памяти для хранения записи H: K ® L (L={0,…,M-1}) называется функцией (хеширования, перемешивания, рассеивания) расстановки (hash - мешанина, путаница).Таблицы, представление которых организуется при использовании функции расстановки, называются таблицы с вычислимыми адресами (хеш-таблицы, перемешиваемые таблицы). Ситуация, когда для расположения записи функцией расстановки определяется уже занятая строка памяти, называется относительным переполнением (коллизией). Уменьшение эффекта сгущений может быть достигнуто при применении способа открытого или линейного перемешивания s' = (s+p)modM (1£p<M). Возможное решение состоит в выборе взаимно-простых значений для M и p. В более общем виде правило разрешения коллизии может быть представлено как функция вторичного перемешивания s'=h'(s). Теорема. Алгоритм открытого перемешивания при взаимно-простых M и p гарантирует нахождение свободных строк структуры хранения таблицы. Доказательство. Рассмотрим множество G={0,1,…,M-1} c операцией aÅb=(a+b)mod M. Свойства операции: G замкнута относительно Å, операция ассоциативна и коммутативна,  $ нулевой и обратные элементы Þ Множество G с операцией Å является группой. Выделим подмножество G'={0, a, a Å a,…}. Такое множество G' с операцией Å тоже является группой (такие группы называются циклическими). Обозначим a Å a Å…Å a через na (a - число повторений). Если n>0, то минимальное значение n, при котором na=0, называется порядком элемента a и обозначается |a|(т.е. порядок определяет количество итераций открытого перемешивания, после которого начнется повторение строк). Целое значение в операции (n a) / M получится только при n=M (т.к. a<M и для взаимно простых а и M). Но это означает также, что na=0, и, тем самым, |a|=M. Отсюда следует G=G'. При разрешении коллизии просматриваемые строки могут рассматриваться как список, в котором порядок следования определяется при помощи алгоритмического правила. Тем самым, удаление записи в середине подобного списка не должно разрушать связность записей. Это может быть достигнуто специальной маркировкой строк с удаленными записями. Строка структуры хранения имеет три возможных состояния – свободное, занятое, пустое (пустое состояние строки возникает после удаления хранимой в строке записи). Вставка (окончательный вариант). 1) Если n==M, ТО { Переполнение; Останов }, 2) f=-1 // f – номер первой найденной пустой строки, 3) s = h(key) // применение функции расстановки, 4) ЕСЛИ s занята и K[s]==key, ТО {Дублир.; Останов }, 5) ЕСЛИ s пустая и (f<0), ТО { f = s }, 6) ЕСЛИ s свободна и (f < 0), ТО { K[s]=key; Останов }, 7) ЕСЛИ s свободна и (f >-1), ТО { K[f]=key; Останов }, 8) (!) Коллизия {s = (s+p) mod M и переход к п. 4 }. Поиск. 1) f=-1 // f – номер первой найденной пустой строки, 2) s = h(key) // применение функции расстановки, 3) ЕСЛИ s занята и K[s]==key, ТО { Останов }, 4) ЕСЛИ s пустая и (f<0), ТО { f = s }, 5) ЕСЛИ s свободна, ТО { Останов }, 6) (!) Коллизия { s = (s+p) mod M и переход к п. 3 }.

1. Способы представления графов. Ориентированный граф G представляет собой набор G=(V,R), где V = {v₁,v₂,…, v_n } есть множество вершин графа, R = { (i,j): i,jÎV } есть множество дуг (ребер) графа. Понятия теории графов: вершина-родитель (предок) и вершина-потомок, входящие/исходящие дуги, путь, длина пути, размер (глубина) графа. Дополнительные понятия: размеченный граф (вершины имеют метки-значения), взвешенный граф (дугам графа приписывается вес), длина пути с учетом весов дуг, кратчайший путь. Выбор структуры хранения графов. Использование матрицы смежности (для неориентированных графов можно применить верхние треугольные матрицы). Представление наборов исходящих дуг в виде множеств смежных вершин. Использование списков исходящих дуг для вершин графа. Оценка походов: объем используемой памяти, эффективность выполнения основных операций обработки (вставка/удаление вершин/вершин, поиск вершины/дуги, реализация обходов). Используем для учебного изучения структуру хранения на основе списков исходящих дуг.

2. Реализация структуры хранения графов. Структура хранения вершины.

class TGraphNode : public TDatValue {protected: string Name; // имя вершины графа int Value; // метка (значение) int Index; // индекс (номер) TDatList Links; // список исходящих дуг  public: // вставка/исключение дуг void InsLink(TGraphNode *pGn, int val); void DelLink(string NodeName);}; Структура хранения дуги (звено). class TGraphLink : public TDatValue { protected: int Value; // вес дуги // начальная и конечная вершины PTGraphNode pFirst, pLast;};

Структура хранения графа

class TGraph : public TDatValue { protected:

int NodeNum; // количество вершин

int LinkNum; // количество дуг

TTreeTable Nodes; // множество вершин графа public: TGraph ();

int GetNodeNum (void) { return NodeNum; }

int GetLinkNum (void) { return LinkNum; }

// вставка вершин и дуг графа

void InsNode ( string nm, int val=0 );

void InsLink ( string fn, string ln, int val=1); };

3. Алгоритм обхода графов. Поиск в глубину. (depth-first search). Обработка очередной вершины графа продолжается рекурсивной процедурой обработки смежных вершин. Для запоминания набора достигнутых, но еще не обработанных вершин, можно использовать стек. Для исключения циклов и запоминания набора уже обработанных вершин можно использовать множество TSet. TSearchMode Mode; // способ обхода PTGraphNode pCurrNode; // текущая вершина // достигнутые, но не обработанные вершины TDataRoot *pStream; // множество вершин, достигнутых в ходе обхода TBitField *pFound;. Инициализация (Reset); инициализация структур, вставка первой вершины в поток pStream и ее отметка в множестве pFound, выполнение метода GoNext. Проверка завершения (IsGraphEnded): return pCurrNode==NULL; // текущее звено? Переход к следующей вершине графа (GoNext): получить вершину из потока pStream, поместить смежные вершины, если они еще не достигнуты, в поток pStream, отметить смежные вершины в множестве pFound.

4. Алгоритм обхода графов. Поиск в ширину. (breadts-first search). Для каждой вершины сначала выполняется обработка непосредственно смежных вершин. Для запоминания набора достигнутых, но еще не обработанных вершин, можно использовать очередь. Для исключения циклов и запоминания набора уже обработанных вершин можно использовать множество TSet. TSearchMode Mode; // способ обхода PTGraphNode pCurrNode; // текущая вершина // достигнутые, но не обработанные вершины TDataRoot *pStream; // множество вершин, достигнутых в ходе обхода TBitField *pFound;. Инициализация (Reset); инициализация структур, вставка первой вершины в поток pStream и ее отметка в множестве pFound, выполнение метода GoNext. Проверка завершения (IsGraphEnded): return pCurrNode==NULL; // текущее звено? Переход к следующей вершине графа (GoNext): получить вершину из потока pStream, поместить смежные вершины, если они еще не достигнуты, в поток pStream, отметить смежные вершины в множестве pFound.

5. Задача поиска кратчайших путей. Алгоритм Дейкстры. В ходе работы алгоритма определяются расстояния кратчайших путей от заданной вершины до всех достижимых вершин графа. Для запоминания длин найденных путей используется массив pDist (если до вершины нет найденного пути, соответствующее значение массива устанавливается в бесконечность). Вершины, уже вошедшие в построенные кратчайшие пути, фиксируются при помощи множества pFound. На каждой итерации алгоритма строится кратчайший путь до вершины, до которой этот путь еще не был определен (т.е. до вершины, не принадлежащей множеству pFound); данная вершина определяется минимальным расстоянием в массиве pDist среди вершин, до которых еще не найден кратчайший путь.

Найденная вершина фиксируется в множестве pFound; далее из этой вершина строятся пути до вершин, не вошедших в pFound и, если этот длина этих путей меньше, чем значения в массиве pDist, значения длин путей в pDist корректируется. Для восстановления найденных кратчайших путей для каждой вершины определим массив pPred, в котором будем запоминать для вершин номера предшествующих по кратчайшему пути вершин.

Теорема 5.2. Пусть G=(V,E) – взвешенный ориентированный граф с неотрицательной весовой функцией w:E®R и исходной вершиной s. Тогда после применения алгоритма Дейкстры

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте