Алгоритм. Способы записи. Компоненты, образующие алгоритмический язык

Код Хаффмана

Код Шеннона-Фэно

Эффективное кодирование. Код Хаффмана. Код Шеннона-Фано.

Кодирование, которое осуществляет удаление или уменьшение избыточности из закодированных сообщений, называется эффективным. Возможность эффективного кодирования основана на теореме Шеннона, согласно которой: Минимальное среднее количество элементов на выходе кодирующего устройства, соответствующее одному символу дискретного сообщения, можно сделать сколь угодно близким к максимальной энтропии источника.

Эффективное кодирование осуществляется с применением неравномерных кодов, в которых более короткие кодовые комбинации соответствуют более вероятным символам сообщения, а более длинные — менее вероятным символам.

Основными требованиями, предъявляемыми к эффективному коду, являются:

- однозначность декодирования, т. е. каждому символу кодируемого сообщения должна соответствовать своя кодовая комбинация и для всех символов комбинации должны быть различны;

- в среднем на один символ сообщения должно приходиться минимальное число элементов кодовой комбинации эффективного кода;

- ни какая более короткая комбинация эффективного кода не должна являться началом другой, более длинной комбинации.

1. Все символы записать в порядке не возрастания вероятностей

2. Символы разбить на 2 группы с приблизительно равными сумами вероятности

3. В левой группе символов код начинать с 0, в правой с 1

4. Каждую группу снова разбить на 2 по тому же принципу и присвоить слева 0, с права 1

5. Продолжить разбивать до тех пор пока в каждой группе не останется по 1 символу

1. Все символы записать в порядке не возрастания вероятностей

2. Объединить 2 редких символа с наименьшей вероятностью в одну группу с вероятностью равной сумме вероятностей этих символов.

3. Повторять операцию со 2го шага пока все символы не будут разбиты на 2 группы: в левой с 0, в правой 1

4. Повторять с каждой группой отделяя крайние правые символы, присваивая всегда слева0, справа 1. Пока не будет закодирован каждый символ.

Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.

Свойства:

- Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.

- Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.

- Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.

- Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

- Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

- Результативность — завершение алгоритма определёнными результатами.

- Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.

- Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.

Формы записи алгоритма:

1) словесная или вербальная (языковая, формульно-словесная);

2) дракон-схема;

3) псевдокод (формальные алгоритмические языки);

4) схематическая:

5) структурограммы (схемы Насси-Шнайдермана);

6) графическая (блок-схемы, выполняется с требованиями стандарта).

Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код).

Алгоритмический язык (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.

1) Алфавит - это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст на этом языке - никакие другие символы в тексте не допускаются.

2) Синтаксис - это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная фраза. Точнее говоря, синтаксис языка представляет собой набор правил, устанавливающих, какие комбинации символов являются осмысленными предложениями на этом языке.

3) Семантика определяет смысловое значение предложений языка. Являясь системой правил истолкования отдельных языковых конструкций, семантика устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке.

Дата добавления: 2015-04-23