Тип работы:
Предмет:
Язык работы:


Алгоритмические проблемы теории кодирования

Работа №87018
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы27
Год сдачи2017
Стоимость4750 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 2
Не подходит работа?

Узнай цену на написание

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.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


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


[1] Питерсон У., Уэлдон Э. Коды исправляющие ошибки. М.: Мир, 1976.
- 594 с.
[2] Катленд Н. Вычислимость. Введение в теорию рекурсивных функций М.: Мир, 1983. - 256 с.
[3] Соар Р.П.Вычислимо перечислимые множества и степени. М.: КМО, 2000. - 576 с.
[4] Кудряшов В.Д. Теория Информации. М.: Питер, 2009. - 322 с.
[5] Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2010. - 384 с.
[6] Кельберт М., Сухов Ю. Вероятность и статистика в примерах и задачах. Том 3. Теория информации и кодирования. М.: МЦНМО, 2014.
- 568 с.
[7] Новиков Ф.А. Дискретная математика. М.: Питер, 2015. - 304 с.


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ