I Введение 1
II Классификация алгоритмически неразрешимых
проблем 2
1 Машина с неограниченными регистрами 2
2 Неразрешимые проблемы теории алгоритмов. 9
3 Арифметическая иерархия. 12
III Алгоритмические проблемы теории кодирования 14
4 Однозначность кодирования в конечных кодах 15
5 Алгоритмические проблемы кодирования в бесконечных
кодах 16
IV Заключение

Купить

Пусть задан алфавит A, где
A {' a1; a2;ang
Словом в алфавите A будет называться конечная последовательность символов, обозначим его А.
A = ац air
Длина слова А будет обозначаться через 1(А) и равна г. Через S(A) обозначим множество всех непустых слов в алфавите A.
Пусть задан алфавит В, где
В = {b1,b2,bm
Через В обозначим слово в алфавите Ви S (B) множество всех непустых слов в алфавите В. Пусть существуют М некоторое подмножество S(A) и N некоторое подмножество S(В). Тогда отображение F переводит каждое слово A 2 M в слово B 2 N, где В - код слова А, а переход от А к В - кодирование.
F (A) = В^
Схемой кодирования Е называется отображение букв алфавита A в множество S(B)
ai —— Bi,
а2 — В2, ar —— Bq
Таким образом каждому слову A = ai1, air, ставится в соответствие слово В = Bi±, Bir. В1, Bq называются элементарными кодами. Кодирование Fs : S(A) — S(В) называется алфавитным кодированием и обозначается Е. Произведение слов AB понимается как последовательное написание слов А и В.
Если слово B имеет вид B = B1B2, то в таком случае слово B1 является префиксом слова В, а слово B2 суффиксом. Суффиксом и префиксом так же может быть пустое слово, обозначим его через Л. Суффикс и префикс слова В называются собственными, если они отличаются от пустого слова и от самого слова В. Кодирование Fs обладает свойством префикса если для любых слов Bi и Bj (i = j) слов о Bi не является префиксом слова Bj.

Купить