Анализ алгоритмов объединения древовидных структур данных

 

Объект исследования – древовидные структуры данных.

Результаты, полученные лично автором: выделены сферы применения и особенности некоторых алгоритмов объединения древовидных структур данных, показано отсутствие универсального алгоритма.

 

Древовидная структура является одним из способов представления иерархической структуры в графическом виде. Древовидной структурой называется благодаря тому, что граф выглядит как перевернутое дерево. По этой же причине говорят, что корневой узел (корень) находится на самом верху, а листья − внизу.

На практике, очень часто приходится решать такие задачи, как объединение генеалогических деревьев, объединение веток в системах версионирования файлов, объединение специальных видов деревьев (например, деревьев поиска) для оптимизации индексации в базах данных, древовидная кластеризация и т.д. И тогда возникает вопрос об алгоритмах объединения деревьев. Рассмотрим такие алгоритмы.

1. Объединение двух AVL-деревьев. Дано два дерева T1 и T2, все ключи в T1 меньше ключей в T2, h(T1) ≤ h(T2). В дереве T1 удаляем самую правую вершину, назовём её b. Высота дерева T1 может уменьшиться на единицу. В дереве T2 идём от корня всегда в левое поддерево и, когда высота этого поддерева P будет равна высоте дерева T1, делаем новое дерево S, корнем S будет вершина b, левым поддеревом будет дерево T1, а правым дерево P. Теперь в дереве T2 у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево S и запускаем балансировку. Таким образом, дерево T2 будет результатом слияния двух АВЛ-деревьев. Этот алгоритм эффективен в задачах объединения деревьев поиска и оптимизации индексации в базах данных.

2. Объединение двух декартовых деревьев. Пусть дано два дерева − A и B, при этом известно, что каждый ключ в дереве A меньше любого ключа в дереве B. Операция слияния состоит в том, чтобы получить дерево C, содержащее все элементы обеих изначальных деревьев. Делается определим, кто будет корнем нового дерева. У нас два претендента: корень A и корень B. Но корень дерева должен иметь максимальный приоритет. Поэтому выберем корнем тот узел, у которого приоритет больше. Допустим, это корень дерева A. Так, как все элементы дерева B пойдут в правое поддерево. Тогда правым поддеревом A станет дерево, полученное слиянием того, что было в правом поддереве A с B. Если же приоритет корня B больше, то мы делаем B корнем, а его левое поддерево – результатом слияния A и левого поддерева B. Этот алгоритм эффективно применяется для объединения веток в системах версионирования файлов.

3. Объединение красно-черных деревьев. Объединение двух красно-чёрных деревьев Т1 и Т2 по элементу x выполняется, когда key[T1] ≤ x и x ≤ key[T2], где key[T] максимальные ключи дерева T. Найдём чёрные высоты деревьев. Предположим также, что hb[T1] ≤ hb[T2]. Тогда в дереве T1 ищем среди чёрных вершин, имеющих чёрную высоту hb[T2], вершину y с наибольшим ключом. Пусть Ty − поддерево с корнем y. Объединяем это дерево с T2 в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины. Если hb[T1] ≤ hb[T2], то слияние происходит аналогично, только теперь мы ищем в дереве T2 среди чёрных вершин, имеющих чёрную высоту hb[T1], вершину y с наименьшим ключом. Применения этого алгоритма эффективно для объединения генеалогических деревьев.

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

Материал поступил в редколлегию 03.04.2017

УДК 519.233.3

В.С. Фокин

Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.ф.-м.н., Л.И. Пугач

[email protected]

 

РАЗРАБОТКА КОМПЛЕКСА ПРОГРАММ ДЛЯ

СТАТИСТИЧЕСКОГО ИССЛЕДОВАНИЯ УСПЕВАЕМОСТИ СТУДЕНТОВ БГТУ

 

Объект исследования: данные об успеваемости студентов факультета информационных технологий БГТУ.

Результаты, полученные лично автором: разработан комплекс программ, исследующих статистические закономерности успеваемости по груп-пам, потокам и дисциплинам, и проверяющих разнообразные статистические гипотезы об успеваемости.

 

Цель работы: разработать программу, исследующую статистические за-кономерности успеваемости по группам, потокам и дисциплинам, и прове-ряющую различные статистические гипотезы об успеваемости.

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

Была поставлена задача:

а) создать электронную базу данных по результатам сессий студентов факультета информационных технологий БГТУ;

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

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

Работая с базой данных, нам удалось проделать следующую работу:

1. Выявить «проблемные» группы и предметы.

2.Выявить статистические связей в успеваемости по различным предметам.

3. Выявить тенденции в успеваемости групп по годам учебы и по семестрам.

4. Сравнить успеваемость различных групп и потоков.

Нами научно обоснована применимость в этой работе следующих методов:

а) T-критерий Стьюдента (пример: сравнить среднюю успеваемость группы по двум предметам или двух групп по общему предмету)

б) Критерий «Хи-квадрат» (пример: оценить стабильность успеваемости группы путём расчёта частот оценок по курсам/семестрам)

в) Коэффициент корреляции Пирсона (пример: оценить силу связи между оценками группы по двум предметам).

Материал поступил в редколлегию 03.04.2017

 

УДК 004.05

Д.С. Хромеев

Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., А.О. Трубаков

[email protected]

 

КАЛЕНДАРНЫЙ ПЛАН ПРОЕКТА ПО РАЗРАБОТКЕ СИСТЕМЫ