Практические работы (задачи) / Задача 5

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский технический университет связи и информатики»

Кафедра «Сетевые информационные технологии и сервисы»

Задача №5

по дисциплине

«Принципы построения систем управления базами данных и знаний»

Выполнила:

Вариант №13

Проверил: доцент, к.т.н., Гадасин Д.В.

Москва, 2023

Оглавление

Условие задачи 3

Индивидуальное задание 3

Ход решения 4

Условие задачи

Пусть каждый блок позволяет размещение A записей данных или B пар вида «ключ-указатель», но допускается существование дубликатов значений ключа поиска. Максимальное количество дубликатов для одного ключа равняется C. Пусть имеется разреженный индекс, но для каждого различного значения ключа существует только один элемент индекса, указывающий на первую по порядку запись данных, обладающих этим ключом. Если изначально ни один из блоков в оперативную память не загружен, найти:

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

2. Решить задание 1, при наличии разреженного индекса, содержащего соответствующую пару «ключ-указатель» для каждой записи, включая и те, которые обладают повторяющимися значениями ключа.

Индивидуальное задание

Вариант	A	B	C
13	64	88	16

1. – количество записей данных в одном блоке

2. – количество пар «ключ-указатель» в одном блоке

3. – максимальное количество дубликатов

Ход решения

1. По алгоритму бинарного поиска определим количество операций S, требуемых для отыскания всех записей данных с заданным значением К ключа поиска:

S = = 64 = 7 + 64 = 71

2) По алгоритму бинарного поиска определим количество операций S, требуемых для отыскания всех записей данных с заданным значением К ключа поиска и при наличии разреженного индекса, содержащего соответствующую пару «ключ-указатель» для каждой записи, включая и те, которые обладают повторяющимися значениями ключа:

S = = = 7 + 1024 = 1031

Ответ: 71 операция; 1031 операция