Структуры и алгоритмы обработки данных

Тема 5. Задачи поиска и кодирования (сжатия) данных 
Кодовые деревья, оптимальные префиксные коды; Пример использования 
бинарных деревьев в задаче упаковки сообщений: префиксные коды и 
бинарные 
деревья, 
метод 
кодирования 
Фано-Шеннона, 
критерий 
оптимальности кода, алгоритмы кодирования (сжатия) информации по 
Хаффману (построение дерева, кодирование и декодирование), доказательство 
оптимальности кода Хаффмана, неравенство Крафта, энтропия, теорема 
кодирования в отсутствие шума (энтропийная оценка). 
Обоснование принимаемых проектных решений, осуществление 
постановки и выполнения экспериментов по проверке их корректности и 
эффективности (ПК-4). 
Тема 6. Многомерные структуры данных 
Понятие многомерного объекта; виды запросов к многомерным 
хранилищам данных; расстояние между многомерными объектами; 
Минимальный описывающий регион (MBR); Области использования 
многомерных структур. Точечные методы доступа: Классификация точечных 
методов доступа: Иерархические методы доступа (
K-D-дерево, K-D-B-дерево 
,LSD-дерево, Quad-дерево); Многомерное хеширование (Файл-решетка, 
Хеширование EXCELL, Многомерное линейное хеширование с частичным 
расширением - MOLHPE,
Многомерное линейное хеширование с сохранением 
порядка – PLOP). Кривые, заполняющие пространство: Упорядочивание по 
ключам, Кривая z-порядка, Кривая Гильберта, Кривая, основанная на кодах 
Грея. 
Пространственные 
методы 
доступа
.
Методы 
преобразования 
пространственных объектов.
Преобразование в пространство большей 
размерности
. 
Кривые, заполняющие пространство для объемных объектов. 
Структуры с перекрытием областей (R-дерево, R-дерево Грина, R*-дерево, SS-
дерево, SR-дерево, TV-дерево) Структуры с разделением объектов (BSP-дерево,
R+-дерево) 
Многослойные 
структуры. 
Многослойный 
файл-решетка. 
Подготовка презентации, научно-технического отчета по результатам 

---

10 
выполненной работы, оформлять результаты исследований в виде статей и 
докладов на научно-технических конференциях (ПК-5).