– Новосибирск: Сибирский гос. ун-т телекоммуникаций и информатики,
2006. – 105 с.
Учебное пособие предназначено для студентов технических
специальностей, обучающихся по направлению 210400
«Телекоммуникации» и изучающих дисциплину «Структуры и алгоритмы
обработки данных». Пособие содержит необходимый теоретический
минимум по данному предмету и варианты заданий для самостоятельного
выполнения.
Содержание:
Необходимые понятия и определения.
Основные структуры данных.
Задача сортировки массивов.
Трудоемкость методов сортировки массивов.
Задача сортировки последовательностей.
Теорема о сложности сортировки.
Задача поиска элементов с заданным ключом.
Методы сортировки с квадратичной трудоемкостью.
Метод прямого выбора.
Пузырьковая сортировка.
Шейкерная сортировка.
Варианты заданий.
Метод Шелла.
Метод прямого включения.
Быстрые методы сортировки массивов.
Пирамидальная сортировка.
Метод Хоара.
Проблема глубины рекурсии.
Работа с линейными списками.
Указатели. Основные операции с указателями.
Основные операции с линейными списками.
Методы сортировки последовательностей.
Метод прямого слияния.
Цифровая сортировка.
Двоичный поиск в упорядоченном массиве.
Алгоритм двоичного поиска.
Сортировка данных с произвольной структурой.
Сравнение данных произвольной структуры.
Сортировка по множеству ключей. Индексация.
Индексация через массив указателей.
Двоичные деревья.
Основные определения и понятия.
Различные обходы двоичных деревьев.
Вычисление основных характеристик дерева.
Деревья поиска.
Поиск в дереве.
Идеально сбалансированное дерево поиска.
Случайное дерево поиска.
Определение случайного дерева поиска.
Добавление вершины в дерево.
Удаление вершины из дерева.
Сбалансированные по высоте деревья (АВЛ-деревья).
Определение и свойства АВЛ-дерева.
Повороты при балансировке.
Добавление вершины в дерево.
Удаление вершины из дерева.
Б-деревья.
Определение Б-дерева порядка m.
Поиск в Б-дереве.
Построение Б-дерева.
Определение двоичного Б-дерева.
Добавление вершины в дерево.
Деревья оптимального поиска (ДОП).
Определение дерева оптимального поиска.
Точный алгоритм построения ДОП.
Приближенные алгоритмы построения ДОП.
Хэширование и поиск.
Понятие хэш-функции.
Метод прямого связывания.
Метод открытой адресации.
Элементы теории кодирования информации.
Необходимые понятия.
Кодирование целых чисел.
Алфавитное кодирование.
Оптимальное алфавитное кодирование.
Почти оптимальное алфавитное кодирование.
Необходимые понятия и определения.
Основные структуры данных.
Задача сортировки массивов.
Трудоемкость методов сортировки массивов.
Задача сортировки последовательностей.
Теорема о сложности сортировки.
Задача поиска элементов с заданным ключом.
Методы сортировки с квадратичной трудоемкостью.
Метод прямого выбора.
Пузырьковая сортировка.
Шейкерная сортировка.
Варианты заданий.
Метод Шелла.
Метод прямого включения.
Быстрые методы сортировки массивов.
Пирамидальная сортировка.
Метод Хоара.
Проблема глубины рекурсии.
Работа с линейными списками.
Указатели. Основные операции с указателями.
Основные операции с линейными списками.
Методы сортировки последовательностей.
Метод прямого слияния.
Цифровая сортировка.
Двоичный поиск в упорядоченном массиве.
Алгоритм двоичного поиска.
Сортировка данных с произвольной структурой.
Сравнение данных произвольной структуры.
Сортировка по множеству ключей. Индексация.
Индексация через массив указателей.
Двоичные деревья.
Основные определения и понятия.
Различные обходы двоичных деревьев.
Вычисление основных характеристик дерева.
Деревья поиска.
Поиск в дереве.
Идеально сбалансированное дерево поиска.
Случайное дерево поиска.
Определение случайного дерева поиска.
Добавление вершины в дерево.
Удаление вершины из дерева.
Сбалансированные по высоте деревья (АВЛ-деревья).
Определение и свойства АВЛ-дерева.
Повороты при балансировке.
Добавление вершины в дерево.
Удаление вершины из дерева.
Б-деревья.
Определение Б-дерева порядка m.
Поиск в Б-дереве.
Построение Б-дерева.
Определение двоичного Б-дерева.
Добавление вершины в дерево.
Деревья оптимального поиска (ДОП).
Определение дерева оптимального поиска.
Точный алгоритм построения ДОП.
Приближенные алгоритмы построения ДОП.
Хэширование и поиск.
Понятие хэш-функции.
Метод прямого связывания.
Метод открытой адресации.
Элементы теории кодирования информации.
Необходимые понятия.
Кодирование целых чисел.
Алфавитное кодирование.
Оптимальное алфавитное кодирование.
Почти оптимальное алфавитное кодирование.