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

Тема 1. Основные понятия о типах и структурах данных 
Логическая и физическая организация структуры данных. Операции над 
логическими и физическими структурами. Абстрактный тип данных: 
спецификация, представление, реализация; Связь между понятием структуры 
данных и алгоритмом. Свойства алгоритмов. Емкостная и временная 
сложность алгоритмов (ПК13). Классификация алгоритмов по сложности. 
Основные принципы, лежащие в основе создания эффективных алгоритмов. 
Формализация в своей предметной области с учетом ограничений 
используемых методов исследования (ПК-2). 
Тема 2. Классификация структур данных 
Статические структуры - вектора, массивы, записи и таблицы. 
Организация статических структур на алгоритмических языках. Алгоритмы над 
статическими структурами данных. 
Полустатические структуры данных (стеки, очереди, деки). Стек, очередь 
и дек как абстрактные типы данных: функциональные спецификации и 
аксиомы. Представление и реализация (непрерывная, ссылочная в связанной 

---

8 
памяти и на базе вектора) на алгоритмических языках. Алгоритмы над 
полустатическими структурами данных. 
Линейные динамические структуры - односвязные и двусвязные списки. 
Организация динамических структур на алгоритмических языках. Некоторые 
алгоритмы, использующие динамические структуры данных. Использование 
методов 
и 
инструментальных 
средств 
исследования 
объектов 
профессиональной деятельности (ПК-3). 
Тема 3. Нелинейные связные структуры 
Многосвязные списки. Сетевые структуры. Рекурсивные структуры 
данных. Древовидные структуры. 
Использование методов и инструментальных средств исследования 
объектов профессиональной деятельности (ПК-3). 
Тема 4. Древовидные структуры 
Типы деревьев. Спецификация дерева, леса. Хранение древовидных 
структур: стандартная форма; инверсная форма; Обходы дерева или леса. 
Прошитые деревья. 
Бинарные деревья. Представления бинарных деревьев. Преобразование 
дерева в двоичное дерево. Обходы и редактирование бинарных деревьев. 
Оптимальные и случайные деревья. Сбалансированные деревья: (АВЛ-деревья, 
красно-черные деревья, расширяющиеся деревья). 
N-арные деревья: деревья цифрового поиска; нагруженные деревья; 
patricia-деревья; синтаксические деревья. Применение N-арных деревьев. 
Сильно ветвящиеся деревья. 2-3-деревья, их применение для словарей, 
сцепляемых очередей, очередей с приоритетами. Прошитые словари и очереди. 
Классические B-деревья. Алгоритмы поиска, вставки и удаления в B-деревьях. 
Разновидности B-деревьев. Применение сильноветвящихся деревьев.
Обоснование принимаемых проектных решений, осуществление 
постановки и выполнения экспериментов по проверке их корректности и 
эффективности (ПК-4). 

---

9