[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Алгоритмы /

Основные понятия теории алгоритмов - часть третья

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

Пусть заданы алфавиты: A={p,r,s,t} – входной и B={a,b,c,d,f,g,h} – выходной. Тогда отображение символов А символами В, т.е. кодом, является примером кодирующего отображения. Для построения искомого отображения достаточно заменить все символы любого слова ai в алфавите А соответствующими кодами алфавита В. Так, если слово x=sstr, то Гx=fghfghabcceg есть код исходного слова x.

Процесс, обратный кодированию, т.е. замена в слове bj кодов алфавита В символами из А, называется декодированием и обозначается как Г-1bj=ai. Например, для слова b=fghfghabcceg в алфавите В декодирование Г-1b дает слово a=sstr.

Если при кодировании слова ai получается некоторое слово bj и декодирование дает исходное слово ai(Гai=bj, Г-1bj=ai), то имеет место обратимость кодирования. Условие обратимости кодирования иначе называется условием взаимной однозначности соответствующего кодирующего отображения. В приведенном выше примере обратимость существует. Но, если зданы A={a,b,c}, B={r,s}, Га=r, Гb=s, Гс=rs и слово aabca в алфавите А, то обратимость отсутствует, так как Гaabca=rrsrsr, а Г-1rrsrsr=aababa (либо одно из слов acaba, aabca, acca).

Для обратимости кодирования должны выполняться следующие условия:
  • коды разных символов исходного алфавита А должны быть различны;
  • код любого символа алфавита А не может совпадать ни с каким из начальных подслов кодов других символов этого алфавита.
Пояснение этих утверждений сводится к следующему. Пусть слово q=b1,b2, ...,bn является кодом слова p=a1,a2, ...,am в алфавите А. Тогда по коду q можно однозначно восстановить слово р. В силу второго условия только одно начальное подслово слова q будет совпадать с каким-либо символом алфавита А. Ясно, что таким подсловом является символ а1. Применяя аналогичные рассуждения к оставшемуся отрезку слова q, можно однозначно восстановить один за другим все символы слова р. Следовательно, любому данному коду может соответствовать только одно слово в А, что доказывает обратимость кодирующего отображения.

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

Кодирование позволяет сводить изучение произвольных алфавитных отображений к алфавитным отображениям в некотором стандартном алфавите. Наиболее часто в качестве стандартного алфавита выбирается двоичный алфавит, состоящий из двух символов. В качестве таких символов обычно используются цифры 0 и 1, т.е. С={0,1}. Подавляющее большинство современных ЭВМ обрабатывают информацию, закодированную именно в двоичном стандартном алфавите.

Пусть А – произвольный, а С – стандартный алфавиты и n - число символов в алфавите А, а m - число символов в алфавите С. В этом случае всегда можно выбрать длину слова L, удовлетворяющую условию mL>=n и закодировать все символы в алфавите А словами длины l в алфавите С так, чтобы коды различных букв были разными (действительно, число различных слов длины L в m-символьном алфавите равно mL). Любое такое кодирование будет нормальным и порождает обратимое кодирующее отображение слов в алфавите А в слова в алфавите С (см. ниже диапазон представления чисел в машине).




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Алгоритмы /

Основные понятия теории алгоритмов - часть первая
09-04-2009   

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

Кол. просмотров: общее - 2979 сегодня - 1

Основные понятия теории алгоритмов - часть вторая
09-04-2009   

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

Кол. просмотров: общее - 3015 сегодня - 0

Основные понятия теории алгоритмов - часть третья
09-04-2009   

К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В... подробнее

Кол. просмотров: общее - 3076 сегодня - 0

Основные понятия теории алгоритмов - часть четвертая
09-04-2009   

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

Кол. просмотров: общее - 2768 сегодня - 0

Оценка сложности алгоритмов
09-04-2009   

С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов... подробнее

Кол. просмотров: общее - 2960 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects