Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/practicum/db.pdf Дата изменения: Mon Sep 6 18:11:02 2010 Дата индексирования: Mon Oct 1 20:55:23 2012 Кодировка: Windows-1251

Практикум по курсу теория баз данных (Э.Э.Гасанов)
1. Простейшие структуры данных (разминочные задачи)
1.1. Краткое описание

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

ћ добавление элемента, ћ удаление элемента, ћ редактирование элемента структуры.
Остальные операции с указанной структурой задаются в зависимости от поставленной задачи. Так же программа должна оценивать время выполнения основных операций.
1.2. Вид решения

Решение должно быть представлено в виде программы (т.е. компилирующегося кода) и отчета о проделанной работе. Который в свою очередь должен содержать файлы выходных данных соответствующие тестовым файлам (содержащим входные данные). 1

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

2. Структуры данных и операции над ними
2.1. Краткое описание

Написать программу, реализующую на основе указанных структур данных ассоциативный массив (типа "целое неотрицательное число в целое неотрицательное число"). Замерить время работы операций с этим массивом для различных реализаций. Операции должны считываться из файла, результаты работы также записываются в файл. Файлы с запросами выдаются. Каждая реализация структуры данных должна реализовывать следующие функции: добавление элемента с заданным ключом и значением, удаление элемента с заданным ключом, поиск элемента с заданным ключом, запись в массив всех значений в порядке, указанном для данной структуры данных (для проверки что реализована именно эта структура данных).
2.2. Вид решения

Решение состоит из:

ћ программы, т.е. компилируемого исходного кода; ћ отчета, сделанного по итогам работы программы.

2


Программа должна принимать на вход тип реализации (его номер) и файл с запросами. Сначала все запросы должны быть считаны в оперативную память (и преобразованы при этом из текстового формата в бинарный). Затем запросы поочередно обрабатываются. Результаты выполнения запросов записываются в оперативную память. После обработки всех запросов все результаты записываются в файл ответа в текстовом виде. Кроме того, если среди запросов встречаются особые запросы на замеры времени создается файл, содеражащий время работы программы между этими замерами. Также в конце работы программы значения содержащихся в ассоциативном массиве элементов записываются в обычный массив в порядке, указанном для используемой структуры данных. Этот массив записывается в еще один файл. Таким образом в результате обработки файла с запросами программа должна создавать 3 файла (либо 2, если замеров времени не было): файл с ответами, файл с результатами замеров времени и файл с содержанием ассоциативного массива в конце работы программы. Файлы с запросами являются текстовыми файлами, где каждый запрос записан на отдельной строке. Формат запросов следующий: 1. insert <ключ> <значение> добавление в ассоциативный массив записи с указанными ключом и значением. Если в массиве уже есть запись с таким ключом, то ничего добавлять не требуется. 2. delete <ключ> удалить из ассоциативного массива запись с указанным ключом. Если записи с таким ключом в массиве нет, ничего делать не нужно. 3. find <ключ> найти в ассоциативном массиве запись с указанным ключом. 4. checkpoint произвести замер времени. Для каждого обработанного запроса (кроме запросов на замер времени) в файле ответа должна содержаться одна строчка с ответом в следующем формате: 1. для запросов на добавление символ 1 если новая запись была добавлена и символ 0 если в массиве уже есть запись с таким ключом; 2. для запросов на удаление значение удаляемой записи или -1, если записи с таким ключом нет; 3. для запросов на поиск значение для найденной записи или -1, если записи с таким ключом нет. Файл ответа должен заканчиваться пустой строкой. 3


2.3. Проверка корректности

Для проверки корректности работы программы учащемуся выдается несколько примеров небольших файлов запросов и соответствующих им файлов ответов (+ файлы с правильными конечными состояниями структур данных).
2.4. Примеры структур данных

Примеры предлагаемых структур данных:

ћ упорядоченный и неупорядоченный динамические массивы; ћ упорядоченный список; ћ бинарное дерево поиска; ћ 2-3 дерево; ћ сбалансированное дерево; ћ красно-черное дерево; ћ B-дерево; ћ хэш-множество на основе одной из вышеперечисленных структур данных.
Возможно, имеет смысл давать студентам заготовку программы, так, чтобы им нужно было только написать структуры данных, реализующие заданный интерфейс.

3. Информационно-графовая модель данных
3.1. Теоретические упражнения
3.1.1. Понятие информационного графа

По аналогии с одномерной задачей интервального поиска приведите тип, описывающий n-мерные задачи интервального поиска. Опишите тип, задающий задачи интервального поиска на n-мерном булевом кубе, которые состоят в поиске в конечном подмножестве n-мерного булевого куба всех тех точек, которые попадают в подкуб, задаваемый запросом. Какова мощность множества запросов у данного типа? Задача о метрической близости состоит в том, чтобы по произвольно взятой точке-запросу единичного n-мерного куба n-мерного евклидового пространства найти
1. 2. 3.

4


f

s s s Es Es Es Es ' ' ' } } T T T T ? 2 2 2 2 2 ? f,y f,y2 f,y3 f,y4 ,y1 6 ? 2 p p p p f,y5 ? u e ! ? u e ! ? ? e ? e ? ? 1e ? 2 1e ? 2 ? p e? p p ep? ? ? 2 g,yd u e ! s g,y3 1 f,y5 ? e ? d ? 2 1 1e ? 2f,y ? f,y2 ? 1d 2 3 ep? p? dp ? p Q k g,y g,y5 s d 2 d 1d 1 2 2 dp p B Е r g,yr r 4 ЕЕ g,3 r Е r Е 1 rr ЕЕ 2 rpc Е

y1 f
s T

2 ,y

2

Es T

y2 f

2 ,y

3

y3 f

2 ,y

4

y4 f

2 ,y

5

y5 f

2 ,y

6

y

6

y1 f

1 ,y

1

y2 f

1 ,y

2

y3 f

1 ,y

3

y

s ? ?

4

? ? ? ? ? ?

f

1 ,y

4

g-,3 Рис. 1:

в конечном подмножестве этого куба (библиотеке) все точки, находящиеся на расстоянии не более, чем R от точки запроса. Опишите тип, задающий задачи о метрической близости. Опишите тип, задающий задачи включающего поиска. Напомним, что в задаче включающего поиска имеется некоторое конечное множество свойств, и каждый элемент библиотеки (множества данных) обладает или не обладает каждым из этих свойств. Запрос задает некоторое подмножество множества свойств, и необходимо найти все элементы библиотеки, которые обладают всеми свойствами из запроса. Рассмотрим следующую задачу поиска, которая может возникнуть, например, при разгадывании кроссвордов. Элементы библиотеки (записи) есть слова фиксированной длины n в алфавите {0, 1}. Запрос задает некоторый набор позиций и значения букв в этих позициях. Необходимо найти в библиотеке все записи, у которых в позициях, задаваемых запросом, стоят буквы, совпадающие с соответствующими значениями позиций запроса. Опишите тип, задающий эти задачи поиска. Сравните полученный тип с типом задач интервального поиска на булевом кубе (см. упражнение 2).
4. 5.

3.1.2. Критерий допустимости информационных графов

F

Пусть S = X, X, = тип поиска идентичных объектов, множество предикатов задается соотношением 0, если x = a F = {f=,a (x) = : a X }, (1) 1, если x = a базовое множество имеет вид F = F, , V = {y1, y2, . . . , yk } X . Приведите пример информационного графа над базовым множеством F , разрешающего ЗИП I = X, V , =
6.

5


тип поиска идентичных объектов, множество переключа1, если x = a G = {g=,a (x) = : a X }, (2) 2, если x = a базовое множество имеет вид F = , G , V = {y1, y2, . . . , yk } X . Приведите пример информационного графа над базовым множеством F , разрешающего ЗИП I = X, V , = . Пусть X = {1, 2, ..., N }, S = X, X, = тип поиска идентичных объектов, множество переключателей имеет вид 1, если x < a 2, если x = a : a X }, (3) G = {ga (x) = 3, если x > a базовое множество имеет вид F = , G , V = {3, 5, 7, 11, 13, 17, 19}. Постройте информационный граф над базовым множеством F , разрешающий ЗИП I = X, V , = . Пусть X = {1, 2, ..., N }, S = X, X, = тип поиска идентичных объектов, V = {y1 , y2 , . . . , yk } X . Предположим, что y1 < y2 < ћ ћ ћ < yk . Метод блочного поиска с размером блока m, решающий задачу I = X, V , = , состоит в следующем. Если на вход алгоритма поиска подается запрос x X , то, начиная с i = 1 до i = k/m, просматриваем записи yiћm. Если x > yiћm, то увеличиваем i на 1, иначе по очереди просматриваем записи y(i-1)m+1, y(i-1)m+2, . . . , yiћm и сравниваем их с запросом x. При равенстве мы нашли нужную запись, если же ни для какой записи равенства не наблюдается, то ответ на запрос x пуст. Опишите базовое множество и постройте информационный граф над этим базовым множеством, который бы решал ЗИП I = X, V , = методом блочного поиска. Пусть X = {1, 2, ..., N }, V X , c отношение поиска, задаваемое на X Ч V и определяемое соотношением xc y (y V )&(x y )&(ѓ(y )((y V )&(x y )&(y < y ))), (4) т.е. xcy, если y V , ближайшее справа к x. При выполнении этих условий ЗИП I = X, V , c называется задачей о близости. Пусть базовое множество имеет вид F = , G , где множество переключателей G задается соотношением 1, если x a G = {g,a (x) = : a X }. (5) 2, если x > a Постройте информационный граф над базовым множеством F , разрешающий ЗИП I = X, V , c , если V = {3, 5, 7, 11, 13, 17, 19}. Одномерная задача о доминировании задается типом Sdom1 = [0, 1], [0, 1], . Пусть V = {y1, y2, . . . , yk } [0, 1]. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП I = [0, 1], V , .
7.

Пусть S = телей имеет вид

.

X, X, =

8.

9.

10.

11.

6


y1 f
s T

2 ,y

2

Es T
2

y2 f

2 ,y

3

Es } T
3

y3 f

2 ,y

4

Es T

y4 f f

2 ,y

5

Es } T

y5 f f

2 ,y

6

y

6

Es T

y1 f
s '

1 ,y

1

y2
s ? ?

y3 f
s '

1 ,y

3

y

4

f

2 ,y

1

6 ? ? ? ? q q q q q q ? ? u e u e ! ? ! ? u ! ? e e e ? ? e ? ? ? e e ? e ? 1 ?2 ? ? 1e ? 2 1e ? 2 e ? ? ? e? q e? q q e? q g,y ? ? 5 g,yd 2 T s g,y3 s d 1 d d ? f,y ?1 5 d d ?1 ? f,y4 1 2 2 1d 2 f,y2 f,y3 d ? ? dq ? q dq ? q Q k g,y g,y6 s d 2 d d 1d 2 1 2 d q q B Е r g,yr r 4 ЕЕ gћ,3 r Е rr ЕЕ 1r 2 Е rrЕЕ d q

f

2 ,y

f

2 ,y



2 ,y



4

2 ,y 5

f

2 ,y

s ? ?

g-,3 Рис. 2: Решение одномерной задачи интервального поиска

если u a (11) если u > a , задачу информационного поиска I = Xint, V , int ? Обоснуйте ответ. Докажите, что информационный граф, изображенный на рисунке 2, разрешает одномерную задачу интервального поиска I = Xint, V , int , где V = {y1, y2, y3, y4, y5, y6} библиотека, изображенная на рисунке 3.
g,a (u, v ) = 1, 2,
13.

Пусть Sint = Xint, Yint, int тип одномерного интервального поиска, где отношение int определяется соотношением (u, v )int y u y v , (6) где (u, v) X, y Y , V = {y1, y2, . . . , y6}, где y1 = 1/6, y2 = 1/4, y3 = 3/8, y4 = 2/5, y5 = 3/4, y6 = 7/8. Разрешает ли информационный граф, изображенный на рисунке 1, где функции определяются соотношениями 1, если u a 1 f,a (u, v ) = , (7) 0, если u > a 1, если v a 2 f,a (u, v ) = , (8) 0, если v < a gћ,m (u, v ) = max(1, ]u ћ m[), (9) 1, если v - u < 1/m g-,m (u, v ) = , (10) 2, если v - u 1/m
12.

7


0

q

y

r

1

y

r

2

q

y3 y4
r r

q

y5
r

y

r

6

1/3

2/3
Рис. 3:

1

q

Пусть Sint = Xint, Yint, int тип одномерного интервального поиска, где отношение int определяется соотношением (6), V = {1/8, 1/7, 1/5, 3/7, 3/5, 4/5, 7/8}. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП I = Xint, V , int .
14.

3.1.3. Полнота для информационных графов

Пусть S = X, X, = тип поиска идентичных объектов, базовое множество имеет вид F = , G , где множество переключателей G задается соотношением (5). Будет ли полно базовое множество F для типа S ? Задача включающего поиска, описанная в упражнении 4, может быть задана b b типом Sbool = B n, B n, , где B n n-мерный булев куб, отношение поиска на B n Ч B n , определяемое следующим соотношением
15. 16.

(12) Приведите пример базового множества, полного для типа Sbool . Приведите пример минимального по мощности базового множества, полного для типа Sbool .
(x1 , . . . , xn ) (y1 , . . . , yn ) xi yi , i = 1, n.
b

3.1.4. Сложность информационных графов

Пусть X = {1, 2, ..., N }, S = X, X, =, P, тип поиска идентичных объектов, где = 2X , P равномерная вероятностная мера, то есть для любого x X выполняется P(x) = 1/N . 1. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 6. 2. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 7. 3. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 8. Для базового множества и ЗИП, приведенных в упражнении 8, постройте информационный граф со сложностью, не большей, чем 1.48.
17.

8


4. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 9, если N = 100. Для какого значения параметра m сложность будет минимальна. Для какого значения параметра m В-сложность будет минимальна. Для какого значения параметра m объем будет минимальным. Если X = {1, 2, ..., N } и на X задана равномерная вероятностная мера, то посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 10. Пусть на множестве запросов X = [0, 1] задана равномерная вероятностная мера. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 11. Пусть на множестве запросов Xint = {(u, v) : 0 u v 1} задана равномерная вероятностная мера. Посчитайте сложность, В-сложность и объем информационного графа, изображенного на рисунке 2.
18. 19. 20.

3.1.5. Мощностная нижняя оценка

Пусть X = {1, 2, ..., N }, S = X, X, =, P, тип поиска идентичных объектов, где = 2X , P равномерная вероятностная мера, то есть для любого x X выполняется P(x) = 1/N , V = {3, 5, 7, 11, 13, 17, 19}. Приведите мощностную нижнюю оценку для ЗИП I = X, V , = . Пусть Sdom1 = [0, 1], [0, 1], , P, тип одномерной задачи о доминировании, где P равномерная вероятностная мера на [0, 1], V = {y1, y2, . . . , yk } [0, 1]. Приведите мощностную нижнюю оценку для ЗИП I = [0, 1], V , . Пусть Sint = Xint, Yint, int тип одномерного интервального поиска и на множестве запросов Xint = {(u, v) : 0 u v 1} задана равномерная вероятностная мера. V = {y1, y2, . . . , yk } [0, 1]. Приведите мощностную нижнюю оценку для ЗИП I = Xint , V , int . Оцените сверху полученную величину.
21. 22. 23. 24.

1, 2, . . . , I= B
n

Пусть V = {y1, y2, . . . , yk } B n и число единиц в наборе yi равно ti (i = k ). Приведите мощностную нижнюю оценку для задачи включающего поиска b , V, .

3.2. Задачи реальный сценарий
3.2.1. Краткое описание

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

ћ Сформулировать задачу в терминах информационно-графовой модели
9




определить множество элементов базы данных Y определить понятие библиотеки V определить множество запросов X определить отношение равенства (x, y ), x X, y Y

ћ для произвольной базы данных привести алгоритм построения графа, решающего задачу поиска в этой базе


построить граф для какой-нибудь конкретной базы данных вычислить сложность этого графа (временную T и объемную Q) посчитать (или оценить) сложность графа для поставленной задачи и произвольной базы данных (optional) сложность должна удовлетворять заданным условиям

ћ реализовать алгоритм решения поставленной задачи на компьютере


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

3.2.2. Примеры задач реальный сценарий

Задача представляет из себя написание словаря, который на ввод пользователем слова на одном из языков выводит все возможные переводы на другой язык. В качестве языков могут быть выбраны как реальные языки (английский, русский), так и абстрактные (A+ , B + ). Решение задачи предполагает написание конструкции, которая принимает пары (a, b) A Ч B и заполняет ими базу данных. Конструкция должна обладать свойством быстрого доступа, т.е. должна быстро выдавать ответы на запрос. Для этого хорошо подходит, например, хэш-дерево, ключем в котором является первая буква слова (две буквы слова, если букв в алфавите мало), потом вторая буква, если это необходимо, и т.д. Интернет-магазин. Предположим, у нас есть интернет-магазин, продающий товары одной категории, который представляет возможность пользователю запросить параметры товара и выбрать из подходящих наиболее интересный. Задача представляет из себя поиск в базе данных объектов, которые удовлетворяют заданным критериям. А именно, каждый товар есть, по сути, набор атрибутов (a1 , a2 , . . . , as ) A1 Ч A2 Ч . . . Ч As , где A1 , A2 , . . . , As некоторые
Русско-англо-русский словарь.

10


множества, такие как {0, 1}, отрезок натурального ряда 1, . . . , ri или отрезок вещественных чисел [0, 1]. Запрос также представляет из себя вектор длины s из множества (A1 {}) Ч (A2 {}) Ч . . . Ч (As Ч As {}), где означает, что пользователю не интересен данный параметр, а для остальных это либо значение из At , которое должен принимать параметр k товаров (для булевых и целых параметров), или интервал из At Ч At , в котором должен лежать параметр k товара (для натуральных или вещественных параметров). Граф, решающий данную задачу должен представлять из себя конструкцию, последовательно проверяющую параметры запроса и отсекающую неподходящие варианты товара. Каждая функция должна учитывать дополнительный вариант значения запроса .
3.3. Моделирование информационных графов
3.3.1. Создание класса информационный граф

Задача состоит в написании класса (class), моделирующего информационный граф. Основной метод класса это метод поиска. Входным данным метода является запрос, а выходными данными множество записей, являющихся ответом информационного графа на запрос и целое число, равное количеству вычисленных предикатов и переключателей на данном запросе.
3.3.2. Реализация алгоритма поиска

Задается некоторый тип задач информационного поиска. Необходимо реализовать две процедуры. Первая процедура получает на вход библиотеку (множество записей). В результате работы процедуры должен быть построен информационный граф, задаваемый описанным в предыдущем разделе классом и решающий заданную задачу информационного поиска. Вторая процедура основывается на методе поиска, реализованного в предыдущем разделе. На вход процедуре поступает поток запросов на поиск, на выходе получается поток ответов (подмножеств библиотеки) и количество вычисленных функций в среднем на потоке.
3.3.3. Типы задач поиска

Предлагаемые к реализации типы задач поиска и алгоритмы их решения:

ћ задача о близости в линейно упорядоченном множестве и алгоритм решения с использованием хэш-функции;

11

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

12