Пример абстракции нелинейных структур.

Бинарное дерево – ор. Граф, каждая родительская вершина которого имеет не более 2ух дочерних. Вершина, не имеющая родителей, называется корнем. Вершина, не имеющая потомков, называется истоком.

Пример дерево оптимального префиксного кодирования.

ДОПК – это структура данных, которая используется в алгоритме сжатия (алгоритм Хаффмана).

Математика

М А Т Е И К

2 3 2 1 1 1

Построение дерева:

1. Пока длинна вектора частот больше либо равна 2 выполнять

   1. Упорядочить вектор частот по убыванию

   2. Построить элементарное дерево на 2ух последних элементах списка

   3. Заменить 2 последних элемента суммой их частот

Все символы входного потока соответствуют листьям дерева.

Разметить дуги дерева влево 0 вправо 1.

Кодом символа будем считать последовательность элементов разметки дуг на пути от корня к листу соответствующего символа. ДОПК.

Не один из кодов не является префиксом другого (т.е. не является началом кода другого символа).

Математика – 80 бит

ДОПК – 25 бит

Декодирование

1. Пока не конец входного потока выполнять

   1. Установить указатель текущей вершины в корень дерева

   2. Пока текущая вершина не лист выполнять

      1. Читать бит входного потока

      2. Спуститься в дочернюю вершину по дуге разметка, которой совпадает со считаным битом

      3. Сделать вершину текущей

   3. Отправить символ соответствующий листу в выходной поток.

Проблемы практического применения алгоритма Хаффмана.

1. Необходимость дополнительного просмотра файла для построения таблицы частот.

2. Увеличение объема сжатого файла за счет модели кодирования

   1. Модель дерева

   2. Таблица частот

   3. Вектор длин поля

Максимальная длина кода байта.

Оптимальная передача модели кодирования

Применение алгоритма Хаффмана увеличивает размер сжатого файла на длину словаря.

3. Проблема кода переменной длины.

3.1. Переменная длина

3.2. Выравнивание байта

Передать декодеру длину входного потока кодера.

Включить в набор символов исходной кодировки включить фиктивный символ с нулевой частотой.

Основы теории вычислительной сложности алгоритмов. Принципы оценки сложности алгоритмов.

Оценка эффективности должна формулироваться в машинно-независимых терминах. Такой машинно-независимой единицей является элементарная операция.

Оценка вычислительной эффективности вычисляется для худшего случая.

Можно оценивать эффективность в терминах размерности задач.

Оценка эффективности строится для разумно большого кол-ва элементов данных.

Методика построение оценки эффективности по коду программы.

Шаг 1. Исключаем из рассмотрения линейные участки (не содержащие явных и скрытых циклов).

Шаг 2. Из оценки исключаются циклы кол-во повторений, которых не зависит от размерности задачи.

Шаг 3. Если кол-во повторений цикла линейно зависит от размерности задачи (n) то эффективность такого цикла является линейной.

Шаг 4. Циклы, при выполнении которых размерность задачи кратно уменьшается, имеют логарифмическую зависимость.

Шаг 5. Оценка эффективности последовательных циклов складывается. Оценки эффективности вложенных циклов перемножаются.

Шаг 6. Упрощение полученной функции от размерности задачи n. именно в соответствии с шагом 3 исключаем коэффициенты и составляющие оценки высоких порядков малости.