Главная | Обратная связь

Всякую обработку сообщений можно рассматривать как кодирование.

Правило v должно задавать некоторый способ построения сообщения исходя из сообщения .

Говорят, что правило обработки v сохраняет информацию, если соответствие σ является отображением, Тогда мы имеем диаграмму:

где композиция отображений α , и σ совпадает с композицией ν и α’ : σ α= α’ ν

В таком случае последняя диаграмма называется коммутативной, а отображение σ называют правилом обработки информации. В оответствии с тем, является σ обратимым отображением или нет, мы различаем следующие случаи: 1. Если σ - обратимое отображение, т.е. информация при обработке не теряется, то соответствующую обработку сообщений называют перешифровкой.

1.1. Если и ν обратимо, то мы имеем простой случай перекодировки: по сообщению m'= α(m) можно восстановить не только исходную информацию, но и само исходное сообщение m, Особенно часто встречается тот частный случай, когда I = I’, а σ -тождественное отображение. В идеале всякая передача сообщений должна иметь именно такой вид.

1.2. Если σ обратимо, а σ - нет, то несколько сообщений m M будут кодироваться одним и тем же сообщением m' M’. Но так как при этом никакой информации не теряется, то это означает, что исходное множество сообщений M было избыточным: в M имеется несколько сообщений, которые несут одну и ту же информацию. Перешифровку ν такого рода мы называем сжимающей. Если к тому же α’ обратимо, то мы называем ν вполне сжимающей.

2. Если σ - необратимое отображение, т. е. разные сведения i I отображаются в одну и ту же информацию i’ I’, то соответствующую обработку сообщений ν называют избирательной. Особенно часто встречается случай, когда I’ - подмножество I , и σ для сведений из I’ является тождественным отображением. В этом случае σ производит выбор из заданного множества сведений. Выбор может быть уже предопределён тем, что несколько различных m M отображаются в одно сообщение m' M’. Однако обработка сообщений v вполне могла быть обратимой. В этом случае выбор осуществляется "односторонней" интерпретацией α’.

15. Понятие об алгоритме. Структура алгоритма. Характеристики алгоритмов. Универсальные алгоритмические модели: машина Тьюринга, частично-рекурсивные функции и нормальный алгоритм Маркова. Их свойства и применение.

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

Основные требования:

1)любой алгоритм имеет вход, выход и промежуточные данные. 2)Данные должны быть четко определены. 3)Данные требуют наличия места для своего размещения. 4)Алгоритм состоит из элементарных шагов, действий. 5)Последовательность шагов должна быть четко детерменирована. 6)Алгоритм должен останавливаться после конечного числа шагов.

Для алгоритма можно выделить 7 характеризующих его параметров:

1) совокупность возможных исходных данных, 2) совокупность возможных результатов, 3)совокупность возможных промежуточных результатов, 4) правило начала, 5) правило непосредственной переработки, 6)правило окончания, 7) правило извлечения результата.

Алгоритмические модели:

1)рекурсивная функция. Х→У, у = f(x)

Рекурсивные функции являются частичными функциями, т.е. функциями, не

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

Основан на представлении алгоритма как о некотором детерминированном устройстве способный в каждый момент времени выполнять определенные операции.

Предложил идею Черче. Всякий алгоритм однозначно ставит в соответствие исходным данным результат.

2)машина Тьюринга состоит из:

1) управляющего устройства, которое может находиться в одном из состояний,

образующих конечное множество Q = {q1, q2,…, qn }; 2) ленты, разбитой на ячейки, в каждой из которых может быть записан один из символов конечного алфавита А = {а1, …, am}; 3) устройства обращения к ленте, т. е. считывающей и пишущей головки, которая в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (быть может, совпадающий с прежним или пустой, т.е. стирает символ), сдвигается на ячейку влево или вправо или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом).Сходимость обязательна.

Алгорифм Маркова

Элементарной операцией над последовательностями знаков может считаться замена подслова на некоторое слово (текстовая замена). Будем исходить из множеств M и M’ слов над общим набором знаков V(это можно делать без ограничения общности). Отдельную операцию замены (продукцию) будем записывать в виде а -> b и понимать её так:

если а является подсловом заданного слова х, то заменить это подслово на b. В случае если подслово а встречается в х несколько раз, словом b заменяется то из них, которое стоит в самой левой позиции. Далее, если дано (конечное) множество таких продукций, перечисленных в определённом порядке, то текстовая замена должна производиться посредством применения самой первой (относительно этого порядка) из применимых продукций. Всё это повторяется до тех пор, покуда возможно, или же до применения особым образом отмеченной продукции („останавливающей").Такого рода алгоритмы называют алгорифмами Маркова