📄Работа №191888
Тема: СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕРЕВЬЕВ ПОИСКА И СОЗДАНИЕ ОБУЧАЮЩЕЙ СИСТЕМЫ ПО ИХ ПОСТРОЕНИЮ
Тип работы
Магистерская диссертация
Предмет
прикладная информатика
Объем:
62 листов
Год:
2016
Просмотров:
34
5620
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Аннотация 2
ВВЕДЕНИЕ 6
1 ПОСТАНОВКА ЗАДАЧИ 9
2 ПРЕДМЕТНАЯ ОБЛАСТЬ 10
2.1 ДВОИЧНОЕ ДЕРЕВО ПОИСКА 10
2.2. СБАЛАНСИРОВАННОЕ ДЕРЕВО 11
2.2.1 ОПРЕДЕЛЕНИЕ СБАЛАНСИРОВАННОГО ДЕРЕВА 11
2.2.2 БАЛАНСИРОВКА 12
2.2.3 АЛГОРИТМ ДОБАВЛЕНИЯ ВЕРШИНЫ В АВЛ-ДЕРЕВО 13
2.3 В-ДЕРЕВО 14
2.3.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА В-ДЕРЕВА 14
2.3.2 ДОБАВЛЕНИЕ КЛЮЧА В В-ДЕРЕВО 15
2.4 КРАСНО - ЧЕРНОЕ ДЕРЕВО 16
2.4.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА КРАСНО - ЧЕРНОГО ДЕРЕВА 16
2.4.2 СЛУЧАИ ПРИ ВСТАВКЕ КЛЮЧА В ДЕРЕВО 18
2.5 ДЕРЕВО ВАН ЭМДЕ БОАСА 20
2.5.1 ОПРЕДЕЛЕНИЕИ СВОЙСТВА ДЕРЕВА ВАН ЭМДЕ БОАСА 20
2.5.2 ПРОТОСТРУКТУРА ДЕРЕВА ВАН ЭМДЕ БОАСА 21
2.5.3 ДЕРЕВО ВАН ЭМДЕ БОАСА 24
2.5.4 ОПЕРАЦИИ ДЕРЕВА ВАН ЭМДЕ БОАСА 26
2.6 РАНДОМИЗИРОВАННОЕ ДЕРЕВО 27
2.6.1 ОПРЕДЕЛЕНИЕ РАНДОМИЗИРОВАННОГО ДЕРЕВА 27
2.6.2 ВСТАВКА УЗЛА В РАНДОМИЗИРОВАННОЕ ДЕРЕВО 28
2.7 ДЕКАРТОВОЕ ДЕРЕВО 29
2.7.1 ОПРЕДЕЛЕНИЕ ДЕКАРТОВОГО ДЕРЕВА 29
2.7.2 ПОЧЕМУ ДЕРЕВО НАЗЫВАЕТСЯ ДЕКАРТОВЫМ? 30
2.7.3 ОПЕРАЦИИ СЛОЖЕНИЯ И ДЕЛЕНИЯ 30
2.7.4 ОПЕРАЦИИ ВСТАВКИ И УДАЛЕНИЯ УЗЛА 32
2.8 ПРИМЕНЕНИЕ ДЕРЕВЬЕВ ПОИСКА 33
3 ОПИСАНИЕ ОБУЧАЮЩЕЙ СИСТЕМЫ 36
4 СЛОЖНОСТЬ ОПЕРАЦИЙ 46
5 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕРЕВЬЕВ ПОИСКА 47
ЗАКЛЮЧЕНИЕ 52
ЛИТЕРАТУРА 53
ПРИЛОЖЕНИЕ А 55
ПРИЛОЖЕНИЕ Б 58
ВВЕДЕНИЕ 6
1 ПОСТАНОВКА ЗАДАЧИ 9
2 ПРЕДМЕТНАЯ ОБЛАСТЬ 10
2.1 ДВОИЧНОЕ ДЕРЕВО ПОИСКА 10
2.2. СБАЛАНСИРОВАННОЕ ДЕРЕВО 11
2.2.1 ОПРЕДЕЛЕНИЕ СБАЛАНСИРОВАННОГО ДЕРЕВА 11
2.2.2 БАЛАНСИРОВКА 12
2.2.3 АЛГОРИТМ ДОБАВЛЕНИЯ ВЕРШИНЫ В АВЛ-ДЕРЕВО 13
2.3 В-ДЕРЕВО 14
2.3.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА В-ДЕРЕВА 14
2.3.2 ДОБАВЛЕНИЕ КЛЮЧА В В-ДЕРЕВО 15
2.4 КРАСНО - ЧЕРНОЕ ДЕРЕВО 16
2.4.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА КРАСНО - ЧЕРНОГО ДЕРЕВА 16
2.4.2 СЛУЧАИ ПРИ ВСТАВКЕ КЛЮЧА В ДЕРЕВО 18
2.5 ДЕРЕВО ВАН ЭМДЕ БОАСА 20
2.5.1 ОПРЕДЕЛЕНИЕИ СВОЙСТВА ДЕРЕВА ВАН ЭМДЕ БОАСА 20
2.5.2 ПРОТОСТРУКТУРА ДЕРЕВА ВАН ЭМДЕ БОАСА 21
2.5.3 ДЕРЕВО ВАН ЭМДЕ БОАСА 24
2.5.4 ОПЕРАЦИИ ДЕРЕВА ВАН ЭМДЕ БОАСА 26
2.6 РАНДОМИЗИРОВАННОЕ ДЕРЕВО 27
2.6.1 ОПРЕДЕЛЕНИЕ РАНДОМИЗИРОВАННОГО ДЕРЕВА 27
2.6.2 ВСТАВКА УЗЛА В РАНДОМИЗИРОВАННОЕ ДЕРЕВО 28
2.7 ДЕКАРТОВОЕ ДЕРЕВО 29
2.7.1 ОПРЕДЕЛЕНИЕ ДЕКАРТОВОГО ДЕРЕВА 29
2.7.2 ПОЧЕМУ ДЕРЕВО НАЗЫВАЕТСЯ ДЕКАРТОВЫМ? 30
2.7.3 ОПЕРАЦИИ СЛОЖЕНИЯ И ДЕЛЕНИЯ 30
2.7.4 ОПЕРАЦИИ ВСТАВКИ И УДАЛЕНИЯ УЗЛА 32
2.8 ПРИМЕНЕНИЕ ДЕРЕВЬЕВ ПОИСКА 33
3 ОПИСАНИЕ ОБУЧАЮЩЕЙ СИСТЕМЫ 36
4 СЛОЖНОСТЬ ОПЕРАЦИЙ 46
5 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕРЕВЬЕВ ПОИСКА 47
ЗАКЛЮЧЕНИЕ 52
ЛИТЕРАТУРА 53
ПРИЛОЖЕНИЕ А 55
ПРИЛОЖЕНИЕ Б 58
📖 Введение
Историю технологии баз данных принято отсчитывать с начала 1960-х гг., когда появились первые попытки создания специальных программных средств управления базами данных. За прошедшие десятилетия возникали и использовались различные подходы к их организации. Для создания баз данных и работы с ними использовались файлы. Данные хранились в виде списков. Характер обработки определялся всеобщим использованием в качестве носителя магнитной ленты.
Период с 1968г. по 1980г. считают эрой обработки не реляционных баз данных. Сначала была разработана иерархическая модель данных. А затем появилась сетевая модель данных.
С 1980г. по настоящее время - период реляционной модели данных.
С распространением интернета в середине 90-х годов повысилось значение и важность технологии баз данных. Ранние статические веб-страницы уступили дорогу динамическим, в результате чего большие организации начали использовать интернет для публикации своих данных.
Хранение данных не существовало бы без структуры. Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Одним из представителей структуры данных является дерево поиска. Существуют различные деревья поиска. Некоторые из них приведены далее:
• АВЛ-дерево. Предложено в 1962 году Адельсоном-Вельским Георгием Максимовичем и Ландасом Евгением Михайловичем.
• 2-3 деревья. Предложено Д.Э. Хопкрофтом в 1970 году.
• В-дерево. Предложено в 1970 году Рудольфом Байером и Мак-Крейтом.
• Красно-черное дерево. Предложено в 1972 году Рудольфом Байером под названием «симметричные бинарные В-деревья». Название «красно¬черное дерево» структура данных получила в 1978 году в статье Л.Гимпаса и Р.Седжвика.
• Дерево ван Эмде Боаса. Предложено в 1975 году.
•Рандомизированное дерево. Основателем считается Майкл О.Рабин, исследовавший рандомизированный тест простоты чисел в 1977 году.
• Декартово дерево. Предложено в 1996 году Раймундом Сейделем и Сецилией Арагон.
Цель создания деревьев поиска - это быстрый поиск информации в больших базах данных, например таких, как телефонные справочники в сотовых компаниях. С ростом числа пользователей база увеличивается. Существуют компании свыше миллиона пользователей. Деревья поиска позволяют значительно сократить время поиска необходимого элемента в базе данных.
Каждое дерево поиска имеет свои преимущества и недостатки. Поэтому для оптимального выбора древовидной структуры при разработке базы данных следует изучить все возможные деревья. Главной задачей данной работы стало изучение свойств деревьев поиска, а также проведения сравнительного анализа этих свойств.
В настоящее время роль информационных технологий очень важна . Поэтому возникает необходимость создания обучающих систем. Но в нынешнем разнообразии систем нет эффективных программ для изучения деревьев поиска. А эти структуры данных очень важны для хранения и быстрого поиска информации в базах данных и других поисковых системах. Так как обучающие системы служат хорошим помощником для изучения необходимой информации, второй задачей работы стало создание обучающей системы для изучения деревьев поиска и проверке полученных знаний.
Обучающая система - это программное средство, предназначенное для решения определенных педагогических задач, имеющее предметное содержание и ориентированное на взаимодействие с обучаемым. Такая система должна содержать учебный материал по определенной предметной области. Под учебным материалом понимается информация как декларативного (описательного, иллюстрационного) характера, так и задания для контроля знаний и умений, а также модели и алгоритмы, представляющие обучаемые объекты и процессы.
Из всего вышеперечисленного следует цель данной работы - провести сравнительный анализ деревьев поиска и создать эффективную обучающую систему, ориентированную на изучение деревьев поиска.
Период с 1968г. по 1980г. считают эрой обработки не реляционных баз данных. Сначала была разработана иерархическая модель данных. А затем появилась сетевая модель данных.
С 1980г. по настоящее время - период реляционной модели данных.
С распространением интернета в середине 90-х годов повысилось значение и важность технологии баз данных. Ранние статические веб-страницы уступили дорогу динамическим, в результате чего большие организации начали использовать интернет для публикации своих данных.
Хранение данных не существовало бы без структуры. Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Одним из представителей структуры данных является дерево поиска. Существуют различные деревья поиска. Некоторые из них приведены далее:
• АВЛ-дерево. Предложено в 1962 году Адельсоном-Вельским Георгием Максимовичем и Ландасом Евгением Михайловичем.
• 2-3 деревья. Предложено Д.Э. Хопкрофтом в 1970 году.
• В-дерево. Предложено в 1970 году Рудольфом Байером и Мак-Крейтом.
• Красно-черное дерево. Предложено в 1972 году Рудольфом Байером под названием «симметричные бинарные В-деревья». Название «красно¬черное дерево» структура данных получила в 1978 году в статье Л.Гимпаса и Р.Седжвика.
• Дерево ван Эмде Боаса. Предложено в 1975 году.
•Рандомизированное дерево. Основателем считается Майкл О.Рабин, исследовавший рандомизированный тест простоты чисел в 1977 году.
• Декартово дерево. Предложено в 1996 году Раймундом Сейделем и Сецилией Арагон.
Цель создания деревьев поиска - это быстрый поиск информации в больших базах данных, например таких, как телефонные справочники в сотовых компаниях. С ростом числа пользователей база увеличивается. Существуют компании свыше миллиона пользователей. Деревья поиска позволяют значительно сократить время поиска необходимого элемента в базе данных.
Каждое дерево поиска имеет свои преимущества и недостатки. Поэтому для оптимального выбора древовидной структуры при разработке базы данных следует изучить все возможные деревья. Главной задачей данной работы стало изучение свойств деревьев поиска, а также проведения сравнительного анализа этих свойств.
В настоящее время роль информационных технологий очень важна . Поэтому возникает необходимость создания обучающих систем. Но в нынешнем разнообразии систем нет эффективных программ для изучения деревьев поиска. А эти структуры данных очень важны для хранения и быстрого поиска информации в базах данных и других поисковых системах. Так как обучающие системы служат хорошим помощником для изучения необходимой информации, второй задачей работы стало создание обучающей системы для изучения деревьев поиска и проверке полученных знаний.
Обучающая система - это программное средство, предназначенное для решения определенных педагогических задач, имеющее предметное содержание и ориентированное на взаимодействие с обучаемым. Такая система должна содержать учебный материал по определенной предметной области. Под учебным материалом понимается информация как декларативного (описательного, иллюстрационного) характера, так и задания для контроля знаний и умений, а также модели и алгоритмы, представляющие обучаемые объекты и процессы.
Из всего вышеперечисленного следует цель данной работы - провести сравнительный анализ деревьев поиска и создать эффективную обучающую систему, ориентированную на изучение деревьев поиска.
✅ Заключение
В процессе выполнения дипломной работы были изучены деревья поиска: сбалансированное, красно - черное, рандомизированное, декартово, ван Эмде Боаса и В-деревья. Выполнен сравнительный анализ сложности построения и выполнения основных операций над деревьями. Выбор «лучшего» дерева зависит от критериев поставленных задач. Практические рекомендации представлены на рисунке 13.
В результате была создана обучающая система, которая помогает пользователю изучить выбранное дерево поиска, а преподавателю проверить контрольные работы. Созданная обучающая программа может быть использована студентами, а также любым желающим познакомится с данной темой, для самостоятельного изучения. Алгоритмы построения всех деревьев были запрограммированы на языке С++, демонстрационный и контролирующий пошаговые режимы реализованы в визуальной среде Visual Studio. В приложении Б приведен список классов.
В результате была создана обучающая система, которая помогает пользователю изучить выбранное дерево поиска, а преподавателю проверить контрольные работы. Созданная обучающая программа может быть использована студентами, а также любым желающим познакомится с данной темой, для самостоятельного изучения. Алгоритмы построения всех деревьев были запрограммированы на языке С++, демонстрационный и контролирующий пошаговые режимы реализованы в визуальной среде Visual Studio. В приложении Б приведен список классов.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.