- •Структуры и алгоритмы обработки данных Методическое пособие
- •Ктн е. В. Курапова, кф-мн е. П. Мачикина
- •Оглавление
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Варианты заданий
- •Двоичные деревья
- •Основные определения и понятия
- •Различные обходы двоичных деревьев
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Идеально сбалансированное дерево поиска
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Случайное дерево поиска
- •Определение случайного дерева поиска
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сбалансированные по высоте деревья (авл-деревья)
- •Определение и свойства авл-дерева
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Определение б-дерева порядка m
- •Поиск в б-дереве
- •Алгоритм на псевдокоде
- •Построение б-дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Определение двоичного б-дерева
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Деревья оптимального поиска (доп)
- •Определение дерева оптимального поиска
- •Точный алгоритм построения доп
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Элементы теории кодирования информации
- •Необходимые понятия
- •Кодирование целых чисел
- •Алфавитное кодирование
- •Оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Почти оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
- •Структуры и алгоритмы обработки данных
- •630102, Г. Новосибирск, ул. Кирова, 86.
Алфавитное кодирование
Кодирование F может сопоставлять код всему сообщению из множества S как единому целому или строить код сообщения из кодов его частей. Элементарной частью сообщения является одна буква алфавита А={a1,a2,…,an}.
Пример 1 А={a1,a2,a3} , B={0,1} a1 1001, a2 0, a3010
сообщение a2a1a2a3 010010010
Пример 2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:
А 01, В 1000, С 1010, D 100, E 0, …
Побуквенное кодирование задается таблицей кодовых слов:σ = < α1 β1, … , αn βn>, αiA, βi B*.Множество кодовых слов V={βi} называется множеством элементарных кодов. Побуквенное кодирование пригодно для любого множества сообщений S: F: A* B*, αi1 …αik=α A*, F(α)=βi1…βik.
Количество букв в слове α=α1…αk называется длиной слова |α| = k. Пустое слово обозначим Λ. Если α=α1α2, то α1 – начало (префикс) слова α, α2 – окончание (постфикс) слова α.
Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если βi1 …βik = βj1 …βjt , то k=t и при любых s=1,…,k is=js , т.е. любое кодовое слово единственным образом разлагается на элементарные коды. Например, код из первого примера не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами a3a3 или a2a1a2.
Побуквенный код называется префиксным, если в его множестве кодовых слов ни одно слово не является началом другого, т.е. элементарный код одной буквы не является префиксом элементарного кода другой буквы. Например, код из первого примера не является префиксным, поскольку элементарный код буквы a2 является префиксом элементарного кода буквы a3.
Утверждение. Префиксный код является разделимым.
Доказательство (от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность β, что она представлена различными способами из элементарных кодов: β=βi1, …,βik = βj1, …,βjt (побитовое представление одинаковое) и существует L такое, что при любом S<L следует (βis= βjs) и (βit≠ βjt), т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда βiL…βik = βjL, …,βjt, т.е. последовательности элементарных кодов разные и существует β/, что βiL=βjLβ/ или βjL=βiLβ/ , т.е. βiL – начало βjL, или наоборот. Получили противоречие с префиксностью кода.
Заметим, что разделимый код может быть не префиксным.
Пример. Разделимый, но не префиксный код: A={a,b}, B={0,1}, φ = {a0, b01}
Приведем основные теоремы побуквенного кодирования.
Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов L1,…,Ln необходимо и достаточно, чтобы
.
Доказательство.Докажем необходимость. Пусть существует префиксный код с длинами L1,…,Ln. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).
Рисунок 64 Полное двоичное дерево с помеченными вершинами
В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – 2r-Li вершин. Всего вершин в поддереве 2r. Тогда,,.
Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастаниюL1≤ L2≤ … ≤ Ln. Выберем в двоичном дереве вершину V1 на L1 уровне. Уберем поддерево с корнем в вершине V1. В оставшемся дереве возьмем вершину V2 на уровне L2 и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам V1, V2,…, Vn образуют префиксный код.
Пример. Построить префиксный код с длинами L1=1, L2=2, L3=2 для алфавита A={a1,a2,a3}. Проверим неравенство Крафта для набора длин . Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с 23 помеченными вершинами и выберем вершины дерева, как описано выше. Тогда элементарные коды могут быть такими a1 0, a210, a3 11.
Рисунок 65 Построение префиксного кода с заданными длинами
Процесс декодирования выглядит следующим образом. Просматриваем полученное сообщение, двигаясь по дереву. Если попадем в кодовую вершину, то выдаем соответствующую букву и возвращаемся в корень дерева и т.д.
Теорема (МакМиллан). Для того, чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов L1,…,Ln , необходимо и достаточно, чтобы .
Доказательство. Покажем достаточность. По теореме Крафта существует префиксный код с длинами L1,…,Ln, и он является разделимым.
Докажем необходимость утверждения. Рассмотрим тождество
Положим . Тогда тождество можно переписать следующим образом
,
где ,– число всевозможных представлений числаj в виде суммы . Сопоставим каждому представлению числаj в виде суммы последовательность нулей и единиц длины j по следующему правилу
,
где bs элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом, и .Используя предельный переход получим при.
Пример. Азбука Морзе – это схема алфавитного кодирования
A01, B1000, C1010, D100, E0, F0010, G110, H0000, I00, J0111, K101, L0100, M11, N10, O111, P0110, Q1101, R010, S000, T1, U001, V0001, W011, X1001, Y1011, Z1100.
Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку
Следовательно, этот код не является разделимым. На самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщение. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений (особенно с высокой скоростью) является некоторым искусством, а не простой технической процедурой.