Контрольная работа 1. «Коллекция данных – дерево поиска»

1. Спроектировать и реализовать АТД «BST – дерево» для коллекции, содержащей ключи и данные произвольного типа. Типы ключей и данных задаются клиентской программой в виде параметров шаблонного класса «BST – дерево».

Интерфейс АТД «BST – дерево» включает следующие операции:

· опрос размера дерева (количества узлов),

· очистка дерева (удаление всех узлов),

· проверка дерева на пустоту,

· поиск данных с заданным ключом,

· включение в дерево нового узла с заданным ключом и данными,

· удаление из дерева узла с заданным ключом,

· обход узлов в дереве по схеме, заданной в варианте задания, и вывод ключей в порядке обхода,

· дополнительная операция, заданная в варианте задания.

· операция создания прямого итератора для перемещения от узла с минимальным ключом до узла с максимальным ключом,

· операции итератора:

–  *,

–  ++,

–  ==

· вывод структуры дерева на экран.

2. Выполнить отладку и тестирование всех операций АТД «BST – дерево» и итератора с помощью меню операций.

3. Предъявить распечатанный отчёт, содержащий следующие пункты:

1) титульный лист,

2) общее задание (пункты 1 – 4) и вариант задания,

3) формат АТД,

4) определение класса для коллекции «BST – дерево»,

5) выводы,

6) список использованной литературы,

4. Предъявить тексты программ с реализацией класса и меню (файл в формате .docx).

Варианты заданий

1.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в итерационной форме.

· Схема операции обхода: L_t → R_t → t.

· Дополнительная операция: поиск k –го по порядку ключа в дереве (нумерация узлов в дереве начинается с нуля).

2.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.

· Схема операции обхода: t → L_t → R_t.

· Дополнительная операция: определение длины внутреннего пути дерева (длина внутреннего пути = сумма глубин внутренних узлов).

3.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в итерационной форме.

· Схема операции обхода: Lt → t → Rt.

· Дополнительная операция: определение узла в дереве с максимальной глубиной.

4.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в итерационной форме.

· Схема операции обхода: L_t → t → R_t..

· Дополнительная операция: определение длины внешнего пути дерева (длина внешнего пути = сумма глубин внешних узлов).

5.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в итерационной форме.

· Схема операции обхода: t → L_t → R_t..

· Дополнительная операция: объединение двух BST-деревьев.

6.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.

· Схема операции обхода: t → L_t → R_t.

· Дополнительная операция: вставка элемента в корень дерева.

7.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.

· Схема операции обхода: L_t → t → R_t..

· Дополнительная операция: формирование критериев сбалансированности, хранящихся в узлах дерева (критерий сбалансированности узла = высота правого поддерева узла – высота левого поддерева узла).

8.​

· Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.

· Схема операции обхода: L_t → R_t → t.

· Дополнительная операция: поиск для заданного ключа предыдущего по значению ключа в дереве.

Методические указания:

1. Для АТД «BST-дерево» разрабатываются шаблонный класс. Параметрами шаблона являются тип ключей и тип данных, хранящихся в узлах дерева.

2. Для итератора дерева разрабатывается открытый внутренний класс, определённый в теле класса дерева.

3. Для узлов дерева разрабатывается скрытый внутренний класс, определённый в теле класса дерева.

4. Для реализации операций АТД, рекомендуется использовать алгоритмы, приведённые в файле Pseudocodes.doc.

5. Для разработанного класса дерева разрабатывается программа тестирования отдельных операций с помощью меню. Тестирование через меню выполняется для BST-дерева небольшого размера. Тестирующая программа выполняет вызов метода коллекции для выбранной операции без предварительной проверки допустимости входных параметров и состояния коллекции. После выполнения операции необходимо вывести на экран результат выполнения операции. При выводе результата, возвращённого методом, не преобразовывать его значение в поясняющий текст.

6. При выводе структуры дерева на экран необходимо отражать только ключи, хранящиеся в узлах. Также необходимо выводить вспомогательный параметр узла, если он введён в узел BST-дерева для дополнительной операции, заданной в варианте задания.

Контрольная работа 2. «Коллекция данных – граф»

1. Спроектировать и реализовать АТД «Граф». Интерфейс АТД «Граф» включает операции:

Конструктор пустого графа для заданных числа вершин, типа, и формы представления

V( ) - опрос числа вершин в графе,

E( ) - опрос числа ребер в графе,

Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,

Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,

Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,

SetEdge(v1,v2, data) задание параметров ребра,

Task() решение задачи по варианту

Show() вывод структуры графа на экран.

2. Выполнить отладку и тестирование всех операций АТД «Граф» с помощью меню операций.

3. Разработать программу визуализации графа и работы алгоритмов. Программа должна обеспечивать визуальный просмотр структуры графа (V £ 20, E £ 30), результатов работы алгоритмов.

4. Предъявить распечатанный отчёт, содержащий следующие пункты:

1) титульный лист,

2) общее задание и вариант задания,

3) формат АТД «Граф»,

4) определение класса для коллекции «Граф»,

5) описание алгоритма задачи, заданной вариантом,

6) список использованной литературы,

5. Предъявить тексты программ с реализацией класса и меню (файл в формате .docx).

Варианты заданий

1) Реализация АТД « Взвешенный орграф». Граф представлен в виде списков смежности (L-граф). Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным входящим эксцентриситетом).

2) Реализация АТД «Ориентированный взвешенный граф». Граф представлен в виде списков смежности (M-граф). Алгоритм определения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния.

3) Реализация АТД « Орграф». Граф представлен в виде списков смежности (L-граф). Алгоритм определения исходящих из заданной вершины кратчайших путей на основе алгоритма Дейкстры.

4) Реализация АТД « Неориентированный взвешенный граф». Граф представлен в виде матрицы смежности (M-граф). Алгоритм Крускалла – построение минимального остова.

5) Реализация АТД « Орграф». Граф представлен в виде списков смежности (L-граф). Алгоритм преобразования орграфа в ациклический орграф DAG за счет изменения ориентации обратных ребер.

6) Реализация АТД « Неориентированный граф». Граф представлен в виде матрицы смежности (M-граф). Алгоритм формирования списка ребер – мостов в неориентированном графе.

7) Реализация АТД «Взвешенный орграф». Граф представлен в виде матрицы смежности (M-граф). Алгоритм определения списка вершин для пути, соответствующего диаметру графа, на основе алгоритма Флойда (диаметр – максимальный исходящий эксцентриситет в графе, путь - последовательность вершин, лежащих на пути с суммарным весом ребер, равным диаметру).

8) Реализация АТД « Взвешенный орграф». Граф представлен в виде списков смежности (L-граф). Определение радиуса и определения списка вершин для соответствующего радиусу пути на основе алгоритма Дейкстры. (радиус – минимальный входящий эксцентриситет в графе, путь- последовательность вершин, лежащих на пути с суммарным весом ребер, равным радиусу).

Методические указания.

1) Простой граф не должен допускать вставку параллельных ребер и петель.

2) АТД «Простой граф» реализуется в виде шаблонного класса. Параметрами шаблона является тип веса ребра графа.

3) Граф может быть представлен в виде списков смежности (L-графа) или матрицы смежности(M-графа) Элементы списков смежности или матрицы смежности содержат номер смежной вершины и вес ребра.

4) Для реализации алгоритма, заданного в варианте задания, разработать метод графа «Задача». Рекомендуется использовать алгоритмы, описанные в электронном учебном пособии "Структуры и алгоритмы обработки данных" (http://edu.nstu.ru/courses/saod/index.htm )

5) Через программу – меню должна обеспечиваться возможность модификации структуры графа (вставка или удаление ребер, изменение параметров, связанных с ребрами).

6) Результат решения задачи на графе фиксируется в программной структуре, которая возвращается методом графа для решения задачи Task().

7) Через программу – меню должна обеспечиваться визуализация структуры графа и результатов задачи по варианту. Визуальный просмотр структуры графа на экране обеспечивается для небольших графов (V £ 20, E £ 30).

Лабораторная работа № 1. «Коллекция данных - хеш – таблица»

Задание к лабораторной работе №1

Спроектировать, реализовать и провести тестовые испытания интерфейса коллекции «Хеш-таблица», содержащей объекты произвольного типа. Тип объектов задаётся клиентской программой.

АТД «Хеш-таблица» представляет ассоциативное, неупорядоченное множество элементов, доступ к которым выполняется с использованием ключа.

Коллекция реализуется в одном из двух вариантов: АТД «Хеш-таблица с цепочками коллизий», АТД «Хеш-таблица с открытой адресацией»,

Интерфейс АТД «Хеш-таблица» включает следующие операции:

· опрос количества элементов таблице ,

· опрос ёмкости таблицы,

· опрос пустоты таблицы,

· очистка таблицы,

· поиск элемента по ключу,

· вставка элемента по ключу,

· удаление элемента по ключу,

· вывод структуры хеш-таблицы на экран,

· опрос значения хеш-функции для ключа текущей операции,

· опрос числа проб, выполненных текущей операцией,

· создание итератора таблицы

· интерфейс итератора:

- конструктор,

- оператор * для доступа по чтению/записи к данным текущего элемента

- оператор ++ для перехода к следующему элементу в таблице,

- оператор == для сравнения двух итераторов.

2. Получить экспериментальную оценку качества реализованной хеш-функции - c², усреднённую по нескольким экспериментам.

3. Выполнить отладку и тестирование всех операций коллекции «Хеш-таблица» с помощью меню операций.

4. Предъявить распечатанный отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1) титульный лист,

2) общее задание и вариант задания,

3) формат АТД «Хэш - таблица»,

4) формат АТД «Итератор хеш-таблицы»

5) справочные определения классов для коллекций «Хэш - таблица» и «Итератор хеш- таблицы»,

6) описание методики получения экспериментальной оценки c² для заданной ёмкости хеш-таблицы и полученная оценка c², усреднённая по нескольким экспериментам.

5. Предъявить тексты программ с реализацией класса и меню (файл в формате .docx).

Варианты задания:

1. Форма представления: хеш – таблица с цепочками коллизий

Тип ключа k - строка текста произвольной длины (символы – маленькие буквы латинского алфавита).

Преобразование к натуральному значению k’ методом конкатенации битовых образов символов.

Метод хеширования k’- модульный.

2. Форма представления: хеш – таблица с открытой адресацией

Тип ключа k - вещественное число на интервале [-10 000.000 , +10 000.000].

Преобразование k к натуральному значению k’ с точностью 10^-3- и выбор 6 цифр из середины квадрата k’.

Метод хеширования k’- мультипликативный. Метод разрешения коллизий - квадратичный.

3. Форма представления: хеш – таблица с цепочками коллизий

Тип ключа k - целое число на интервале [0 , +1 000 000 000].

Преобразование k к натуральному значению k’ методом выбора цифр.

Метод хеширования - модульный.

4. Форма представления: хеш – таблица с цепочками коллизий

Тип ключа k - строка текста произвольной длины (символы – заглавные буквы латинского алфавита).

Преобразование k к натуральному значению k’ по схеме Горнера.

Метод хеширования k’– мультипликативный.

5. Форма представления: хеш – таблица с открытой адресацией

Тип ключа k - вещественное число на интервале [100000.0000, +150000.0000].

Преобразование k к натуральному значению с точностью 10^-4 и свёртка k к значению k’ на интервале [10000, +20000].

Метод хеширования k’ - модульный.

Метод разрешения коллизий - квадратичное хеширование.

6. Форма представления: хеш – таблица с цепочками коллизий

Тип ключа k - строка текста произвольной длины (символы – заглавные буквы латинского алфавита).

Преобразование k к натуральному значению k’ методом конкатенации битовых образов символов.

Метод хеширования k’ - мультипликативный.

7. Форма представления: хеш – таблица с открытой адресацией

Тип ключа k - натуральное число на интервале [1000000000 , 3000000000].

Преобразование k к натуральному значению k’ методом свёртки.

Метод хеширования k’- модульный.

Метод разрешения коллизий - квадратичный.

8. Форма представления: хеш – таблица с открытой адресацией

Тип ключа k - строка текста произвольной длины (символы – заглавные буквы кириллицы).

Преобразование k к натуральному значению k’ по схеме Горнера.

Метод хеширования k’- мультипликативный.

Метод разрешения коллизий - линейный.

Методические указания к выполнению лабораторной работы

1. Коллекции «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» разрабатываются, как шаблонные классы-контейнеры. Параметрами шаблона являются тип ключа и тип данных.

2. Ёмкость массива для хеш-таблицы вычисляется конструктором коллекции в зависимости входного параметра – предельного количества элементов в таблице. При расчёте ёмкости учитывается тип хеш-таблицы, метод хеширования и рекомендуемая величина коэффициента загрузки α:

α = 2 для хеш-таблицы с цепочками коллизий,

α = 0.5 для хеш-таблицы с открытой адресацией.

3. Для тестирования качества хеш-функции разрабатывается программа получения оценки c². При этом достаточно использовать количество ключей, в 20 раз превышающее ёмкость хеш-таблицы.

4. Для тестирования класса хеш-таблицы разрабатывается программа тестирования отдельных операций через меню.

5. Тестирование операций через меню выполняется для небольшого размера таблицы (до 10 элементов). После выполнения операции необходимо выводить на экран возвращённый ею результат, индекс и число выполненных зондирований.

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

Лабораторная работа №2 Тестирование трудоёмкости хеш-таблицы

Задание к лабораторной работе №2

1. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекции «Хеш-таблица» в зависимости от коэффициента заполнения α. Использовать класс «Хеш-таблицы», разработанный в лабораторной работе №1.

2. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.

3. Предъявить распечатанный отчёт, содержащий следующие пункты:

· описание методики тестирования трудоёмкости операций поиска, вставки и удаления в зависимости от коэффициента заполнения α,

· таблицы и графики с полученными оценками трудоёмкости операций в зависимости от коэффициента заполнения α.

· сравнительный анализ теоретических и экспериментальных оценок эффективности операций,

· выводы,

· список использованной литературы,

4. Предъявить тексты программы тестирования средней трудоёмкости операций поиска, вставки и удаления (файл в формате .docx).

Программа тестирования трудоёмкости хеш-таблицы

Для получения экспериментальных оценок основных операций хеш-таблицы рекомендуется к использованию программа-драйвер тестирования.

Драйвер тестирования задаёт модель потока операций гипотетической клиентской программы. Поток состоит из чередующихся равновероятных операций поиска, вставки и удаления данных. Операции используют равновероятные ключевые значения данных. Вероятность повтора ключевого значения в потоке близка к нулю. Общее количество операций пропорционально количеству данных в таблице перед тестированием. Для операций задаётся вероятность промаха (неуспеха). Для операций поиска или удаления промахом считается поиск или удаление значения, отсутствующего в коллекции. Если в коллекции запрещено хранение данных с одинаковыми значениями, то вставка нового значения, уже присутствующего в коллекции, ведёт к промаху операции вставки.

Порядок действий программы-драйвера следующий. Перед тестированием эффективности операций коллекции задаётся количество элементов, для хранения которых предназначена хеш-таблица. В качестве исходных данных для тестирования задаётся коэффициент заполнения α. Для коллекции «Хеш-таблица с цепочками коллизий» α задаётся неравенством 0,1 £ α £ 10. Для коллекции «Хеш-таблица с открытой адресацией» α задаётся неравенством 0,1 £ α £ 1.

По заданным параметрам программа формирует исходное состояние хеш-таблицы, занося в нее случайную выборку данных. На этапе тестирования программа генерирует в потоке чередующиеся операции вставки, удаления и поиска, фиксируя при этом суммарную трудоёмкость для каждого вида операций. Размер коллекции и коэффициент заполнения во время и в конце тестирования не должны отличаться от первоначального.

По окончанию тестирования программа выводит на экран усреднённую трудоёмкость для каждого вида операций и размер коллекции после тестирования и коэффициент заполнения α.

Ниже приведён текст программы для тестирования хеш-таблицы, реализованной в лабораторной работе №1.

#include <iostream> #include "hash.h" using namespace std;

Тест трудоёмкости операций хеш-таблицы void test (int n, double alpha)

{//n – максимальное количество ключей в таблице

// alpha – коэффициент заполнения хеш-таблицы для n ключей

//создание таблицы для ключей типа Tk Hash<Tk,int > table(n);

//k - количество ключей для вставки в хеш-таблицу

//table.capacity()- ёмкость массива в хеш-таблице int k = table.capacity()* alpha;

//массив для ключей, которые присутствуют в таблице Tk* m=new Tk [k];

//заполнение таблицы и массива элементами со случайными ключами for(int i=0; i<k; i++)

{

m[i]=genkey(); // genkey()- генерация случайного ключа типа Tk table.insert(m[i],1);

}

//вывод размера таблицы и коэффициента заполнения до теста cout<<"items count:"<<table.Size()<<endl; cout<<"alpha:"<<(double)table.Size()/table.Capacity() << endl;

//обнуление счётчиков трудоёмкости вставки, удаления и поиска double I=0, D=0, S=0;

//генерация потока операций, 10% - промахи операций for(int i=0;i<k/2;i++)

if(i%10==0) //10% промахов

{

table.delete(genkey()); D+=table.CountProbe(); table.insert (m[rand()%k],1); I+=table.CountProbe();

try

{

table.Search(genkey()); S+=table. CountProbe();

}

//обработка исключения при ошибке операции поиска catch(int){S+=table.CountProbe();}

}

else //90% успешных операций

{

int ind=rand()%k; table.delete(m[ind]); D+=table.CountProbe(); Tk key= genkey(); table.insert (key,1); I+=table.CountProbe(); m[ind]=key;

try

{

table.Search(m[rand()%k]); S+=table.CountProbe();

}

//обработка исключения при ошибке операции поиска catch(int){S+=table.CountProbe();}

}

//вывод результатов:

//вывод размера таблицы и коэффициента заполнения после теста cout<<"items count:"<<table.Size()<<endl; cout<<"alpha:"<<(double)table.Size()/table.Capacity() << endl;

//вывод теоретических оценок трудоёмкости операций cout<<BigO(alpha)<<endl;//BigO(alpha)- //вывод теор. оценок

//вывод экспериментальной средней оценки трудоёмкости вставки cout<<"Count insert: " << I/(k/2.0) <<endl;

//экспериментальной средней оценки трудоёмкости удаления cout<<"Count delete: " << D/(k/2.0) <<endl;

//экспериментальной средней оценки трудоёмкости поиска cout<<"Count search: " << S/( k/2.0) <<endl;

//освобождение памяти массива m[] delete[] m;

}