Основные операции для работы с d-кучами
Содержание
1. Общие указания............................................................................ 6
2. Основные операции для работы с d-кучами.......................... 10
3. Лабораторные работы............................................................... 12
3.1. Нахождение кратчайших путей в графе............................ 12
Постановка задачи...................................................................... 12
Структура данных для представления графа............................ 12
Алгоритм Дейкстры, реализованный на основе d-кучи............ 13
Алгоритм Дейкстры, использующий метки............................... 14
Алгоритм Форда–Беллмана....................................................... 15
Задания для лабораторной работы № 1.................................... 16
3.2. Нахождение минимального остова графа......................... 17
Постановка задачи...................................................................... 17
Стратегии решения задачи......................................................... 17
Алгоритм Борувки...................................................................... 18
Алгоритм Краскала.................................................................... 19
Алгоритм Прима......................................................................... 20
Round Robin алгоритм................................................................ 21
Задания для лабораторной работы № 2.................................... 21
3.3. Создание и использование словаря.................................... 22
Постановка задачи...................................................................... 22
Решение задачи создания и использования словаря................. 22
Тривиальный алгоритм.............................................................. 23
Алгоритм с использованием АВЛ-дерева.................................. 23
Задания для лабораторной работы № 3.................................... 23
3.4. Поиск фрагмента в тексте.................................................... 24
Постановка задачи...................................................................... 24
Наивный алгоритм поиска фрагмента в тексте.......................... 25
Алгоритм Кнута-Морриса-Пратта............................................. 25
Задания для лабораторной работы № 4.................................... 26
3.5. Сортировка............................................................................ 27
Постановка задачи...................................................................... 27
Сортировка с помощью d-кучи.................................................. 27
Быстрая сортировка.................................................................... 27
Задания для лабораторной работы № 5.................................... 28
3.6. Построение выпуклой оболочки n точек на плоскости... 29
Постановка задачи...................................................................... 29
Построение выпуклой оболочки с помощью сортировки........ 29
Задания для лабораторной работы № 6.................................... 30
3.7. Поиск пары пересекающихся отрезков.............................. 31
Постановка задачи...................................................................... 31
Наивный алгоритм поиска пересечения..................................... 32
Эффективный алгоритм поиска пересечения............................. 32
Задания для лабораторной работы № 7.................................... 33
4. Приложение: генерация графов для экспериментов............. 34
Литература...................................................................................... 35
Общие указания
Предмет "Лабораторный практикум по АРА" предполагает выполнение ряда вариантов лабораторных работ.
Целью каждого варианта каждой лабораторной работы является реализация, сравнение и анализ двух алгоритмов, решающих одну и ту же задачу.
Заданный студенту вариант лабораторной работы считаются выполненными им после представления и утверждения самостоятельно им написанных двух программ и отчёта. (Самостоятельность означает, что после изучения соответствующего материала каждый символ в исходном коде своей программы и каждый символ в своём отчёте студент придумывает и пишет (или набирает) сам, совершенно необходимо понимая при этом абсолютно всё, что содержится в его отчёте и исходном коде его программ.)
Студент на основе троекратного внимательнейшего изучения общих указаний и задания для соответствующих вариантов лабораторной работы, а также на основе внимательнейшего изучения всего кода своих программ и всего своего отчёта должен самостоятельно заблаговременно найти все неточности в программах или отчёте и также самостоятельно заблаговременно все неточности исправить. Причём так поступать необходимо каждый раз, когда кем-либо обнаруживается хотя бы одна неточность в программах или отчёте данного студента.
Первая программа должна читать из файла входную информацию и записывать результаты работы каждого исследуемого алгоритма, а также время его работы в соответствующий данному алгоритму новый файл с именем, начинающимся с “output”. Таким образом, выходная информация для первого алгоритма должна быть записана в первый файл, а выходная информация для второго алгоритма должна быть записана во второй файл. Вторая программа предназначена для проведения экспериментов и должна соответствовать разделу 2 задания для соответствующих вариантов лабораторной работы. Для каждой программы в электронном виде должны быть представлены: все исходные файлы, имя основного из которых начинается с “prog”, выполняемый exe-файл с именем, начинающимся с “prog”, и инструкция по работе программы, содержащаяся в файле, имя которого начинается с “instruction”. Указанные выполняемые exe-файлы требуется получить таким образом, при котором они не нуждались бы для своей полноценной работы в каких-либо не входящих в них библиотеках. К первой программе также должен быть приложен файл с соответствующей входной информацией, имеющий начинающееся с “input” имя и размер не более ста байт.
Отчёт должен быть представлен как в электронном (в файле с начинающемся с “отчёт” именем), так и в печатном виде и содержать следующие разделы:
· описание алгоритмов,
· обоснование теоретических оценок временной сложности алгоритмов,
· описание реализующих алгоритмы программ,
· проведенные эксперименты,
· сравнение алгоритмов,
· выводы.
В разделе "Описание алгоритмов" следует поставить задачу и описать все исследуемые решающие её алгоритмы.
В разделе "Обоснование теоретических оценок временной сложности алгоритмов " следует сформулировать утверждения, представляющие оценки временной сложности всех исследуемых алгоритмов, и подробнейшим образом их доказать.
В разделе "Проведенные эксперименты" следует отобразить результаты всех экспериментов, указанных в разделе 3 задания для соответствующих вариантов лабораторной работы, с помощью графиков. В каждом эксперименте варьируется один параметр, обозначим его через K, в некоторых пределах K0<K<K1, при этом для каждого K фиксируется время t(K) работы алгоритма. На рисунке, соответствующем этому эксперименту, должны быть приведены графики функций t(k) для всех исследуемых алгоритмов. Графики должны быть нарисованы так, чтобы им непосредственно предшествовали параметры эксперимента, были указаны названия осей и их единицы деления (в частности, единица деления вертикальной оси должна соответствовать 1 секунде), было написано, какой график какому алгоритму соответствует.
В разделе "Сравнение алгоритмов" следует сделать на основе практических данных, для получения которых приветствуется проведение дополнительных экспериментов, заключение о предпочтительности использования того или иного алгоритма в конкретных рассмотренных случаях и выяснить, соответствует ли сделанное заключение теоретическим оценкам временной сложности алгоритмов.
В разделе "Выводы" следует сделать на основе практических данных, для получения которых приветствуется проведение дополнительных экспериментов, заключение о предпочтительности использования того или иного в максимально более общих случаях и выяснить, соответствует ли сделанное заключение теоретическим оценкам временной сложности алгоритмов.
Соответствующие самостоятельно написанные студентом две программы и отчёт считаются представленными, если данный студент представил в печатном виде отчёт и в электронном виде каталог (с именем “(Фамилия)_(ИО)_(N)_(a)”, где “(фамилия)” означает фамилию данного студента, “(ИО)” есть инициалы имени и отчества данного студента, “(N)” есть номер соответствующей лабораторной работы и “(a)” есть номер соответствующего ее варианта), содержащий:
файл “отчёт*.*” с отчётом,
подкаталог “prog1_source” со всеми исходными файлами для первой программы,
подкаталог “prog1_exe” с выполняемым exe-файлом для первой программы, с файлом инструкции “instruction*.*” и с файлом примера “input*.*”,
подкаталог “prog2_source” со всеми исходными файлами для второй программы,
подкаталог “prog2_exe” с выполняемым exe-файлом для второй программы и с файлом инструкции “instruction*.*” и с файлом примера “input*.*”.
Соответствующие две программы и отчёт утверждаются после их представления и приведения к надлежащему виду.
Задание по предмету "Лабораторный практикум по АРА" состоит из 3-х частей.
1-ая часть (обязательная) заключается в получении и выполнении студентом одного из вариантов 2-200 лабораторной работы № 5 (номер полученного таким образом варианта в данном разделе “Общие указания” обозначается через k).
Все соответствующие программы студентом должны быть представлены на занятии 8-ой недели (24.10.2011 – 30.10.2011) (1-ый этап). Если программы студентом не представлены на занятии 8-ой недели (24.10.2011 – 30.10.2011), то:
— данный студент в день этого занятия обязан сказать своим родителям следующее: “Моя текущая успеваемость делает невозможным получение положительной оценки по курсу “Анализа и разработки алгоритмов””,
— задание 1-ой части для данного студента дополняется (k+10)-ым вариантом лабораторной работы № 5.
Соответствующий отчёт студентом для каждого из заданных ему вариантов лабораторной работы № 5 должен быть представлен на занятии 12-ой недели (21.11.2011 – 27.11.2011) (2-ой этап). Если отчёт для какого-либо из заданных вариантов лабораторной работы № 5 студентом не представлен на занятии 12-ой недели (21.11.2011 – 27.11.2011), то:
— данный студент в день этого занятия обязан сказать своим родителям следующее: “Моя текущая успеваемость делает невозможным получение положительной оценки по курсу “Анализа и разработки алгоритмов””,
— задание 1-ой части для данного студента дополняется (k+20)-ым вариантом лабораторной работы № 5.
2-ая часть (обязательная) заключается в получении и выполнении k-го варианта лабораторной работы № 6.
Все соответствующие заданным вариантам лабораторной работы № 6 программы студентом должны быть представлены на занятии 14-ой недели (5.12.2011 – 11.12.2011) (3-ий этап). Если программы не представлены на занятии 14-ой недели (5.12.2011 – 11.12.2011), то:
— данный студент в день этого занятия обязан сказать своим родителям следующее: “Моя текущая успеваемость делает невозможным получение положительной оценки по курсу “Анализа и разработки алгоритмов””,
— задание 2-ой части для данного студента дополняется (k+10)-ым вариантом лабораторной работы № 6.
Соответствующий отчёт студентом для каждого из заданных ему вариантов лабораторной работы № 6 должен быть представлен на занятии занятии 16-ой недели (19.12.2011 – 25.12.2011) (4-ый этап). Если отчёт не представлен на занятии 16-ой недели (19.12.2011 – 25.12.2011), то:
— данный студент в день этого занятия обязан сказать своим родителям следующее: “Моя текущая успеваемость делает невозможным получение положительной оценки по курсу “Анализа и разработки алгоритмов””,
— задание 2-ой части для данного студента дополняется (k+20)-ым вариантом лабораторной работы № 6.
3-ая часть (необязательная) заключается в выборе и выполнении какого-либо варианта какой-либо лабораторной работы с номером 1,2,3,4,7. Все соответствующие программы должны быть представлены на занятии 14-ой недели (5.12.2011 – 11.12.2011) (5-ый этап). Соответствующий отчёт должен быть представлен на занятии 16-ой недели (19.12.2011 – 25.12.2011) (6-ой этап).
Студенты, выполнившие 1-ую и 2-ую части задания по данному предмету с соблюдением сроков для первых четырёх этапов, тем самым выполнили основное задание.
Студенты, выполнившие 1-ую, 2-ую и 3-ю части задания по данному предмету с соблюдением сроков для всех шести этапов, получают положительную оценку на зачёте или экзамене.
Лабораторные работы
Постановка задачи
Пусть G = (V, E, W) - ориентированный граф без петель со взвешенными ребрами, где множество вершин V={1, … , n}, множество ребер E Í V´V, |E| = m, и весовая функция W(u,v) каждому ребру (u, v)ÎE ставит в соответствие его вес - неотрицательное число. Требуется найти кратчайшие пути от заданной вершины sÎV до всех остальных вершин.
Если исходный граф не является ориентированным, то для использования описанных ниже алгоритмов следует превратить его в ориентированный, заменив каждое его ребро {u,v} на два ребра (u,v) и (v,u) того же веса.
Решением задачи будем считать два массива:
· массив dist[1..n], (dist[i] – кратчайшее расстояние от вершины s до вершины i).
· массив up[1..n], (up[i] – предпоследняя вершина в построенном кратчайшем пути из вершины s в вершину i).
В описываемых ниже алгоритмах “+¥” может быть заменено на любое число, превосходящее длину любого кратчайшего пути из вершины s в любую другую вершину графа G.
Алгоритм Форда–Беллмана
Алгоритм Форда–Беллмана (см. [5]), представленный процедурой LDG_FORD_BELLMAN, сначала полагает dist[s]=0 и dist[i]:= +¥ при всех iÎV\{s}, а затем (n-1) раз выполняет следующие действия:
для каждого ребра (i, j) Î E графа G = (V, E) такого, что j ≠ s, заменяет dist[j] на min{dist[j], dist[i]+W(i, j)}.
procedure LDG_FORD_BELLMAN (var dist; var up; ADJ; n,s);
begin
for i:= 1 to n do begin up[i]:= 0; dist[i]:= +¥ end; dist[s]:= 0;
for k:= 1 to n-1 do for i:= 1 to n do begin
p:= ADJ[i].next;
while p ≠ nil do begin
j:= p^.name;
if j ≠ s then if dist[j] > dist[i]+p^.w then begin
dist[j] := dist[i]+p^.w; up[j]:= i;
end;
p:= p^.next;
end;
end;
end;
Временная сложность алгоритма Форда-Беллмана есть O(n×m).
Задания для лабораторной работы № 1
Предлагается попарное сравнение различных алгоритмов нахождения кратчайших путей от вершины sÎV до всех остальных вершин в графе G = (V, E), имеющем n вершин и m ребер.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант d=1, …, 10
А - алгоритм Дейкстры, реализованный на основе (d+1)–кучи,
В - алгоритм Дейкстры, реализованный на основе (d+2)–кучи;
Вариант d=11, …, 20
А - алгоритм Дейкстры, реализованный на основе (d-9)–кучи,
В - алгоритм Дейкстры, использующий метки;
Вариант d=21, …, 30
А - алгоритм Дейкстры, реализованный на основе (d-19)–кучи,
В - алгоритм Форда-Беллмана;
Вариант 31
А - алгоритм Дейкстры, использующий метки,
В - алгоритм Форда-Беллмана.
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· число n вершин и число m ребер графа,
· натуральные числа q и r, являющиеся соответственно нижней и верхней границей для весов ребер графа.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. n = 1, … ,104+1 с шагом 100, q = 1, r =106, количество ребер: а) m ≈ n2/10, б) m ≈ n2 (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.2. n = 101, … ,104+1 с шагом 100, q = 1, r = 106, количество ребер: а) m ≈ 100×n, б) m ≈ 1000×n (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.3. n = 104+1, m = 0, … ,107 с шагом 105, q = 1, r = 106 (нарисовать графики функций TА(m) и ТВ(m) );
3.4. n = 104+1, q = 1, r = 1, … ,200 с шагом 1, количество ребер: а) m ≈ n2, б) m ≈ 1000×n (нарисовать графики функций TА(r) и ТВ(r) для обоих случаев).
4. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.
Постановка задачи
Пусть G = (V, E, W) - неориентированный граф без петель со взвешенными ребрами и пусть множество вершин V={1, …, n}, множество ребер E Í V´V, |E| = m и весовая функция W(u, v) каждому ребру (u, v)ÎE ставит в соответствие неотрицательное число - его вес.
Требуется найти минимальный остов графа, то есть минимальное по весу поддерево графа G, содержащее все его вершины.
Решением задачи будем считать массив ET[1..n-1, 1..2], в котором пара (ET[i, 1], ET[i, 2]) является i-м ребром построенного минимального остовного дерева.
Стратегии решения задачи
Рассмотрены несколько стратегий решения поставленной задачи, которые основываются на определенных правилах окрашивания вершин и ребер графа в два цвета (по традиции – синий и красный). В процессе окрашивания множество ребер, получивших к данному моменту синий цвет, представляет собой набор деревьев, являющихся фрагментами некоторого минимального остова. Ребра, получившие красный цвет, не входят ни в один минимальный остов. В итоге ребра, получившие синий цвет, представляют искомый остов.
Стратегия 1(Boruvka).
Вначале все вершины окрашиваются в синий цвет, а все ребра остаются неокрашенными.
Повторяющийся шаг: для каждого синего дерева выбирается инцидентное ему неокрашенное ребро минимальной стоимости, концы которого не являются вершинами одного и того же синего дерева, и окрашивается в синий цвет (если есть несколько ребер минимальной стоимости, то выбирается то, порядковый номер которого меньше).
Стратегия 2(Kruskal).
Вначале все вершины окрашиваются в синий цвет, а все ребра остаются неокрашенными, множество ребер сортируется в порядке неубывания стоимостей.
Повторяющийся шаг: выбирается очередное неокрашенное ребро в порядке неубывания стоимости; если оба его конца принадлежат одному и тому же синему дереву, то ребро окрашивается в красный цвет, в противном случае – в синий.
Стратегия 3 (Prim).
Вначале в синий цвет окрашивается произвольная вершина, а все остальные вершины и ребра остаются неокрашенными.
Повторяющийся шаг:выбирается инцидентное синему дереву неокрашенное ребро минимальной стоимости; если оба его конца принадлежат одному и тому же синему дереву, то ребро окрашивается в красный цвет, в противном случае – в синий.
Стратегия 4 (Yao).
Вначале все вершины окрашиваются в синий цвет, а все ребра остаются неокрашенными.
Повторяющийся шаг: выбирается произвольное синее дерево, являющееся максимальным по включению множеством синих ребер, образующих связный подграф, и инцидентное ему неокрашенное ребро минимальной стоимости; выбранное ребро красится в синий цвет.
В алгоритмах, реализующих данные стратегии, будем применять разделенные множества с использованием рангов и сжатия путей (см. [5]). Для коллекции K разделенных множеств будем использовать операции:
· Найти(i, j, K) - найти имя i подмножества коллекции K, содержащее элемент j;
· Объединить(i, j) - объединить подмножества коллекции с именами i и j.
Алгоритм Борувки
В данном алгоритме (см. [2]) используется представления исходного графа G массивом E[1..m] его ребер и массивом W[1..m] весов данных ребер.
procedure MSP_BORUVKA(var ET; var mt; G; n,m);
begin
for s:= 1 to n do NME[s]:= 0;
Создать коллекцию K из n синглетонов множества {1, 2, … , n};
mt:= 0;
while FIND_NME(NME,K,E,G,n,m) do for s:= 1 to n do if NME[s]>0 then begin
a=E[NME[s]][1]; b=E[NME[s]][2]; Найти(i, a, K); Найти(j, b, K);
if i ¹ j then begin mt:= mt+1; ET[mt]:= E[NME[s]]; Объединить(i,j,K); end;
NME[s]:= 0;
end;
end;
Функция FIND_NME осуществляет повторяющийся шаг стратегии Борувки: для каждого синего дерева, представленного в коллекции множеством своих вершин, которое имеет имя s, находит инцидентное ему неокрашенное ребро минимальной стоимости с наименьшим номером NME(s), концы которого не являются вершинами одного итого же синего дерева. При этом функция FIND_NME возвращает значение true, если хотя бы одно такое ребро найти удалось, и возвращает значение false, если этого сделать не получилось.
function FIND_NME(var NME; K; E; G; n,m) : boolean;
begin
FIND_NME = false;
for t:= 1 to m do begin
a=E[t][1]; b=E[t][2];
Найти(i,a,K); Найти(j,b,K);
if i¹j then begin
if NME[i]=0 then begin
NME[i]:= t; FIND_NME=true;
end else if W[t]<W[NME[i]] then NME[i]:= t;
if NME[j]=0 then begin
NME[j]:= t; FIND_NME=true;
end else if W[t]<W[NME[j]] then NME[j]:= t;
end;
end;
end;
Временная сложность алгоритма Борувки есть O(m×log n).
Алгоритм Краскала
procedure MSP_KRASKAL(var ET; var mt; G; n,m);
begin
Отсортировать массив E по невозрастанию весов его элементов;
Создать коллекцию из n синглетонов множества {1, 2, … , n};
mt:= 0;
for i:= 1 to m do begin
Найти имя a подмножества, содержащего элемент E[i][1];
Найти имя b подмножества, содержащего элемент E[i][2];
if a ≠ b then begin
Объединить подмножества коллекции с именами a и b;
mt:= mt+1; ET[mt]:= E[i];
end;
end;
end;
Временная сложность алгоритма Краскала есть O((m+n)×log n)).
Алгоритм Прима
В данном алгоритме (см. [2]) используется представление исходного графа G окрестностями его вершин. Для окрестности i–ой вершины графа G = (V, E) мы будем использовать введенное обозначение OG(i). При этом заметим, что при непосредственном программировании следует использовать структуру ADJ[1..n]. В алгоритме используются также массивы
· a[1..n] (a[x] - вес минимального по весу ребра, соединяющего вершину x с построенным фрагментом минимального остова),
· b[1..n] (b[x] - имя второй вершины этого ребра) и
· VT[1..n] (VT[y]=1, если вершина y входит в построенный фрагмент минимального остова).
Алгоритм начинает свою работу с любой вершины uÎV. Для определенности положим, что u является первой вершиной.
procedure MSP_PRIM(var ET; var mt; G; n,m);
begin
for i:= 1 to n do VT[i]:= 0; mt:= 0; u=1; VT[u]:= 1;
for xÎOG(u) do begin
a[x]:= W(x,u); b[x]:= u;
end else a[x]:= +¥;
while mt<n-1 do begin
u:= argmin{a[x] : VT[x]:= 0};
if a[u]:= +¥ then begin writeln(‘граф несвязен’); exit; end;
q:= b[u];
VT[u]:= 1; mt:= mt+1;
ET[mt][1]:= u; ET[mt][2]:= q;
for xÎOG(u) do if VT[x]=0 then if a[x]>W(x,u) then begin
a[x]:= W(x,u); b[x]:= u;
end;
end;
end;
Временная сложность алгоритма Прима есть O(n2).
Примечание.Используемый в псевдокоде знак +¥ обозначает число, которое больше веса любого ребра исходного графа G.
Round Robin алгоритм
procedure MSP_RRA(var ET; var mt; G; n,m);
begin
mt:= 0;
Создать пустую коллекцию K разделенных подмножеств множества V;
Создать пустой двусторонний список Q корневых элементов разделенных множеств из K;
for uÎV do begin Создать(u, K); Добавить u к концу списка Q;
Создать ленивую левостороннюю кучу H(u) из ребер, инцидентных u;
end;
while |Q|>1 do begin
Изъять первый элемент f из списка Q;
Найти элемент edge минимального веса в куче H(f);
a:= edge[1]; b:= edge[2]; Найти(i,a,K); Найти(j,b,K);
if i¹j then begin
mt:= mt+1; ET[mt]:= edge;
Удалить i и j из списка Q;
Объединить(i,j,K);
z:= корневой элемент подмножества, полученного объединением подмножеств с корневыми элементами и
i и j;
H(z):= ленивая левосторонняя куча, полученная слиянием куч H[i] и H[j];
Добавить z к концу списка Q;
end;
end;
end;
Временная сложность Round Robin алгоритма есть O(m×log log n).
Примечание.Элемент (ребро) в ленивой куче H[t] считается пустым, если концы этого ребра принадлежат одному и тому же множеству из коллекции K.
Задания для лабораторной работы № 2
Предлагается попарное сравнение различных алгоритмов нахождения минимального по весу остовного дерева в графе G = (V, E), имеющего n вершин и m ребер.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант 1
· А - алгоритм Борувки,
· В - алгоритм Краскала;
Вариант 2
· А - алгоритм Борувки,
· В - алгоритм Прима;
Вариант 3
· А - алгоритм Прима,
· В - алгоритм Краскала;
Вариант 4
· А - алгоритм Борувки,
· В - Round Robin алгоритм.
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· число n вершин и число m ребер графа,
· натуральные числа q и r, являющиеся соответственно нижней и верхней границей для весов ребер графа.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. n = 1, … ,104+1 с шагом 100, q = 1, r =106, количество ребер: а) m ≈ n2/10, б) m ≈ n2 (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.2. n = 101, … ,104+1 с шагом 100, q = 1, r = 106, количество ребер: а) m ≈ 100×n, б) m ≈ 1000×n (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.3. n = 104+1, m = 0, … ,107 с шагом 105, q = 1, r = 106 (нарисовать графики функций TА(m) и ТВ(m) );
3.4. n = 104+1, q = 1, r = 1, … ,200 с шагом 1, количество ребер: а) m ≈ n2, б) m ≈ 1000×n (нарисовать графики функций TА(r) и ТВ(r) для обоих случаев).
4. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.
Постановка задачи
Для множества слов S={S1, S2, … ,Sn}, имеющих соответственно толкования T={T1, T2, … ,Tn }, создать словарь и для последовательности слов P=(P1, P2, … ,Pk) с буквами из алфавита A={a1, a2, … ,am} определить для каждого слова Pi из P по словарю, принадлежит ли оно множеству S, и если принадлежит, то найти его толкование TPi (см. [1], [3]).
Тривиальный алгоритм
В данном алгоритме в качестве структуры данных для словаря используется список. Временная сложность исполнения процедуры СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ СЛОВАРЯ может быть оценена величиной O((k+n)×n).
Задания для лабораторной работы № 3
1. Написать программу, реализующую тривиальный алгоритм и алгоритм с использованием АВЛ-дерева для решения поставленной задачи, основываясь на псевдокоде процедуры СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ СЛОВАРЯ.
2. Написать программу, реализующую оба алгоритма, для проведения экспериментов, в которых можно выбирать:
· количество букв в алфавите,
· число n слов в словаре,
· число k слов в последовательности,
· количество s букв в словах,
· способ независимого друг от друга задания слов словаря (множество S) и слов последовательности P из числа следующих:
· непосредственный ввод,
· псевдослучайное образование слов выбранной длины, составленных из равновероятно встречающихся букв алфавита,
· образование требуемого количества слов, являющихся по выбору либо лексикографически минимальными, либо лексикографически максимальными в данном алфавите A.
Выходом данной программы должно быть время работы T1 тривиального алгоритма и время работы T2 использующего АВЛ-деревья алгоритма в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. S и P составлены из n и k соответственно псевдослучайных семибуквенных слов в 33-буквенном алфавите, n=104+1, k=1, … ,104+1 с шагом 100 (нарисовать графики функций T1(k) и T2(k)),
3.2. S и P состоят из n и k соответственно лексикографически минимальных семибуквенных слов в 33-буквенном алфавите, n=104+1, k=1,…,104+1 с шагом 100 (нарисовать графики функций T1(k) и T2(k)),
3.3. S состоит из n лексикографически минимальных, а P состоит из k лексикографически максимальных семибуквенных слов в 33-буквенном алфавите, n = 104+1, k = 1, … ,104+1 с шагом 100 (нарисовать графики функций T1(k) и T2(k)).
4. Сформулировать и обосновать (на основе псевдокодов алгоритмов и практических данных, для получения которых можно провести дополнительные эксперименты) вывод о том, в каких случаях целесообразно применять тривиальный алгоритм, а в каких ― алгоритм, использующий АВЛ-деревья.
Поиск фрагмента в тексте
Постановка задачи
Для слов Y = Y1 Y2 … Yn и X = X1 X2 … Xm в алфавите A найти все вхождения слова Y в X. В дальнейшем под решением этой задачи мы будем понимать такую функцию f: {1, 2, … ,m}®{0, 1, 2, … , n}, что f[j] = n, если Y1 Y2 … Yn =X j-(n-1) X j-(n-2) … X j (на j-ой букве слова X заканчивается очередное вхождение в него слова Y), и f[j]<n в противном случае. Для избавления псевдокодов алгоритмов от мешающих их пониманию деталей, мы будем в дальнейшем считать, что 1≤n≤m.
Задания для лабораторной работы № 4
1. Написать программу, реализующую тривиальный алгоритм и алгоритм Кнута-Морриса-Пратта поиска фрагмента в тексте, основываясь соответственно на псевдокодах процедур SFT_TRIVIAL и SFT_KMP.
2. Написать программу, реализующую оба алгоритма, для проведения экспериментов, в которых можно выбирать:
· количество букв в алфавите,
· способ независимого друг от друга задания слов X и Y из числа следующих:
· непосредственный ввод слова,
· образование слова выбранной длины, составленного из выбранных букв алфавита, встречающихся равновероятно,
· образование слова вида (B1 B2 … Bs)k на основе ввода числа k и слова B1B2 … Bs.
3. Выходом данной программы должно быть время работы T1 тривиального алгоритма и время работы T2 алгоритма Кнута-Морриса-Пратта в секундах.
4. Провести эксперименты на основе следующих данных:
4.1. Y=(ab)k и X=(ab)1000*k, k = 1, … ,1001 с шагом 10 (нарисовать графики функций T1(k) и T2(k));
4.2. A={a,b}, Y=(a)m, слово X состоит из 106+1 букв алфавита A, встречающихся равновероятно, m = 1, … ,106+1 с шагом 104 (нарисовать графики функций T1(m) и T2(m));
4.3. Y=aaaaa и X=(aaaaab)h, h = 1, … ,106+1 с шагом 104 (нарисовать графики функций T1(h) и T2(h)).
5. Сформулировать и обосновать (на основе псевдокодов алгоритмов и практических данных, для получения которых можно провести дополнительные эксперименты) вывод о том, в каких случаях целесообразно применять тривиальный алгоритм, а в каких ― алгоритм Кнута-Морриса-Пратта.
Сортировка
Постановка задачи
Упорядочить массив a[1..n] по неубыванию в соответствии с линейным порядком (£), заданным на элементах данного массива, путем перестановки его элементов. (Отношение строгого порядка (<), как обычно, определяется следующим образом: b<c, если b£c и b ≠ c.)
Сортировка с помощью d-кучи
Реализация алгоритма сортировки с помощью d-кучи (см. [1], [5]) массива a длины n осуществляется процедурой SORT_D(a, n). При этом к моменту выполнения последнего for-цикла массив a был упорядочен по невозрастанию, а после его исполнения упорядочивается по неубыванию.
В данной задаче массивом ключей d-кучи является массив a, массив имен и сами имена элементов не используются, поэтому из псевдокодов всех операций с d-кучей следует выбросить все части кода для работы с именами элементов и массивом имен.
procedure SORT_D(var a; n,d);
begin
ОБРАЗОВАTЬ_ОЧЕРЕДЬ(a,n,d);
nq:= n; while nq>1 do ИЗЪЯТИЕ_МИНИМУМА (a1, a, n, d);
for i := 1 to (n mod 2) do a[i]Ûa[n-i+1];
end;
Временная сложность сортировки с помощью d–кучи, где d³2, есть O(n×log n).
Быстрая сортировка
Быстрая сортировка (см. [1]) относится к типу алгоритмов “разделяй и властвуй”. Данный алгоритм, сортирующий массив a[1..n] по неубыванию, представлен процедурой SORT_QUICK(a, 1, n). Операция РАЗДЕЛЯЙ(a, i, j, i1) путем перестановки элементов массива a изменяет его так, чтобы a[i], …, a[i1-1] ≤ a[i1] ≤ a[i1+1], …, a[j], и одновременно определяет число i1.
procedure SORT_QUICK (var a, i, j);
begin
if i < j then begin
РАЗДЕЛЯЙ (a, i, j, i1);
SORT_QUICK (a, i, i1-1); SORT_QUICK (a, i1+1, j);
end;
end;
procedure РАЗДЕЛЯЙ (var a, i, j, var i1);
begin
k:= (i+j)mod(2); b:= a[k];
i1:= i; j1:= j;
repeat
while a[j1] < b & j1 > i do j1:= j1-1;
while a[i1] > b & i1 <j do i1:= i1+1;
if i1 <= j1 then begin
a[i1]Ûa[j1]; i1:= i1+1; j1:= j1-1;
end;
until i1 > j1;
end;
Временная сложность быстрой сортировки n элементного массива оценивается сверху величиной O(n2), однако, в среднем быстрая сортировка выполняется за время O(n×log n).
Задания для лабораторной работы № 5
Предлагается попарное сравнение различных алгоритмов сортировки массива, состоящего из натуральных чисел.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант d=2, …, 101
· А - сортировка d-кучей,
· В - сортировка (d+1)-кучей;
Вариант d=102, …., 200
· А - сортировка (d-100)-кучей,
· В - быстрая сортировка.
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· количество n элементов в исходном массиве a,
· верхнюю q и нижнюю w границы для значений элементов массива,
· заполнение массива a:
· псевдослучайное,
· автоматическое по неубыванию,
· автоматическое по невозрастанию.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. q=1, w=109, n=1, … ,106+1 с шагом 104, заполнение массива a:
· псевдослучайное,
· по возрастанию,
· по убыванию
(нарисовать графики функций TА(n) и ТВ(n) для всех трех случаев).
3.2. q =1, w=1, … ,100 с шагом 1, n=106, заполнение массива a:
· псевдослучайное,
· по возрастанию,
· по убыванию.
(нарисовать графики функций TА(w) и ТВ(w) для всех трех случаев),
4. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.
Постановка задачи
Для точек a1, …, an, где n≥1, ai=(ai,1, ai,2)ÎR2 при i=1, …, n, указать вершины b1, …, bm выпуклой оболочки Conv(a1, …, an) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a1, …, an) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки - сама эта точка.
Задания для лабораторной работы № 6
Предлагается попарное сравнение различных использующих сортировку алгоритмов построения выпуклой оболочки n точек на плоскости с целочисленными координатами.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант d=2, …, 101
· А - используется сортировка d-кучей,
· В - используется сортировка (d+1)-кучей;
Вариант d=102, …., 200
· А - используется сортировка (d-100)-кучей,
· В - используется быстрая сортировка.
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· количество n точек в исходном массиве a,
· натуральные числа q и w для псевдослучайного размещения всех n точек в двух режимах:
(1) в прямоугольнике со сторонами длиныq и w,
(2) на границе (на сторонах) этого прямоугольника.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. q = 106, w = 106, n = 1, …, 106+1 с шагом 104, размещение точек псевдослучайное:
· в режиме (1),
· в режиме (2)
(нарисовать графики функций TА(n) и ТВ(n) для обоих случаев),
3.2. q = w = 0, …, 106 с шагом 104, n = 106, размещение точек псевдослучайное:
· в режиме (1),
· в режиме (2)
(нарисовать графики функций TА(n) и ТВ(n) для обоих случаев),
4. Сформулировать и обосновать вывод (на основе практических данных, для получения которых можно провести дополнит