📄Работа №60068
Тема: Октодерево для хранения и обработки линейных запросов поиска
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
60 листов
Год:
2017
Просмотров:
69
4760
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
1 Линейные запросы поиска 6
1.1 Определения 6
1.2 Визуальное представление 8
1.3 Сведение к линейным запросам 9
2 Октодерево для обработки линейных запросов поиска 11
2.1 Определение 11
2.2 Структура 13
2.2.1 Построение 14
2.2.2 Запросы 16
2.3 Реализация 17
3 Анализ структуры данных 19
3.1 Аналоги 19
3.1.1 Массив 19
3.1.2 Простое октодерево 19
3.1.3 K-мерное дерево 19
3.1.4 Таблица асимптотик 20
3.2 Сравнение эффективности 20
3.2.1 Генерация данных 20
3.2.2 Эффективность построения структуры 21
3.2.3 Эффективность обработки запросов 22
3.3 Анализ 22
Заключение 25
Список литературы 26
1 Линейные запросы поиска 6
1.1 Определения 6
1.2 Визуальное представление 8
1.3 Сведение к линейным запросам 9
2 Октодерево для обработки линейных запросов поиска 11
2.1 Определение 11
2.2 Структура 13
2.2.1 Построение 14
2.2.2 Запросы 16
2.3 Реализация 17
3 Анализ структуры данных 19
3.1 Аналоги 19
3.1.1 Массив 19
3.1.2 Простое октодерево 19
3.1.3 K-мерное дерево 19
3.1.4 Таблица асимптотик 20
3.2 Сравнение эффективности 20
3.2.1 Генерация данных 20
3.2.2 Эффективность построения структуры 21
3.2.3 Эффективность обработки запросов 22
3.3 Анализ 22
Заключение 25
Список литературы 26
📖 Введение
Информация являлась и является одним из самых ценных ресурсов. С появлением вычислительной техники в XX-м веке стала актуальна проблема хранения, упорядочивания и поиска информации. Человек пишет книги, сочиняет
музыку, делает фотографии, снимает видео — это только самые популярные
виды информации. Каждый год её количество только увеличивается. В следствие чего возрастает нагрузка на вычислительные машины. Требуются все более быстрые и быстрые алгоритмы. Для каждого отдельного типа информации
стараются подобрать как можно более оптимальный алгоритм.
При хранении информации встает проблема её поиска по нескольким, зачастую числовым, параметрам. Одним из ярких и визуальных примеров является
трёхмерное пространство с заданным в нём множеством точек. Необходимо по
различным интерактивным ограничивающим запросам находить соответствующую им информации [1]. Частным случаем данного примера может быть база
данных, содержащая список людей с их датами рождений. Среди которых, например, требуется находить записи с годами от 1990 до 2000, месяцами от 1 до
7, а днями от 15 до 30.
Ещё во второй половине XX-го века были начаты и ведутся до сих пор разработки алгоритмов для хранения, упорядочивания и поиска элементов трёхмерного пространства [2, 3]. Многие из них основаны на мощном фундаменте
из сбалансированных деревьев, частным случаем которых являются двоичные
деревья поиска [4]. Изменение условий, накладываемых на такие структуры
данных, позволяет варьировать алгоритмическую сложность, балансируя между сложностями операций построения, изменения и поиска.5
Такие структуры данных используются в совершенно различных областях:
от военных тренажеров до симуляции и визуализации различных физических
явлений [5], что только увеличивает к ним интерес.
музыку, делает фотографии, снимает видео — это только самые популярные
виды информации. Каждый год её количество только увеличивается. В следствие чего возрастает нагрузка на вычислительные машины. Требуются все более быстрые и быстрые алгоритмы. Для каждого отдельного типа информации
стараются подобрать как можно более оптимальный алгоритм.
При хранении информации встает проблема её поиска по нескольким, зачастую числовым, параметрам. Одним из ярких и визуальных примеров является
трёхмерное пространство с заданным в нём множеством точек. Необходимо по
различным интерактивным ограничивающим запросам находить соответствующую им информации [1]. Частным случаем данного примера может быть база
данных, содержащая список людей с их датами рождений. Среди которых, например, требуется находить записи с годами от 1990 до 2000, месяцами от 1 до
7, а днями от 15 до 30.
Ещё во второй половине XX-го века были начаты и ведутся до сих пор разработки алгоритмов для хранения, упорядочивания и поиска элементов трёхмерного пространства [2, 3]. Многие из них основаны на мощном фундаменте
из сбалансированных деревьев, частным случаем которых являются двоичные
деревья поиска [4]. Изменение условий, накладываемых на такие структуры
данных, позволяет варьировать алгоритмическую сложность, балансируя между сложностями операций построения, изменения и поиска.5
Такие структуры данных используются в совершенно различных областях:
от военных тренажеров до симуляции и визуализации различных физических
явлений [5], что только увеличивает к ним интерес.
✅ Заключение
В настоящее время алгоритмы обработки линейных запросов находят своё
применение в различных областях, от военной промышленности до сферы развлечений. Одним из самых мощных фундаментов данных алгоритмов являются сбалансированные деревья. Для которых введение дополнительных условий
позволяет балансировать между производительностью и потреблением памяти, времени работы для определенного типа запросов. Поэтому была предложена модификация дерева, в которой каждая вершина имеет не более восьми
потомков, а разбивается так, чтобы разность между размером минимального
и максимального потомка была минимальна. И есть основания полагать, что
предложенный алгоритм является хорошей альтернативой для уже существующих, так как работает эффективнее на определённых типах данных. И для
проверки данного предположения был разработан программный комплекс для
численных экспериментов и сравнения производительностей алгоритмов.
В результате проверки на различных входных данных было выявлено улучшение производительности на таких типах данных как: равномерное распределение, распределение в виде сетки, разряженное распределение с большими
одиночными скоплениями. Что подтверждается теоретическими расчетами анализа алгоритма.
применение в различных областях, от военной промышленности до сферы развлечений. Одним из самых мощных фундаментов данных алгоритмов являются сбалансированные деревья. Для которых введение дополнительных условий
позволяет балансировать между производительностью и потреблением памяти, времени работы для определенного типа запросов. Поэтому была предложена модификация дерева, в которой каждая вершина имеет не более восьми
потомков, а разбивается так, чтобы разность между размером минимального
и максимального потомка была минимальна. И есть основания полагать, что
предложенный алгоритм является хорошей альтернативой для уже существующих, так как работает эффективнее на определённых типах данных. И для
проверки данного предположения был разработан программный комплекс для
численных экспериментов и сравнения производительностей алгоритмов.
В результате проверки на различных входных данных было выявлено улучшение производительности на таких типах данных как: равномерное распределение, распределение в виде сетки, разряженное распределение с большими
одиночными скоплениями. Что подтверждается теоретическими расчетами анализа алгоритма.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.