Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

Постановка вопроса


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

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

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


С помощью этого перевода вместо абстрактного отображения между натуральными числами

f: N” -> N

рассматривается конкретное отображение между последовательностями знаков

f : (Т*)» -> Т*

со следующим свойством (для всех xj,..., Хn Î N):



f(xi, ..., Хn) = abs(f(rep(xi), ..., rep(Xn))).

Это равенств говорит, что , вместо того чтобы вычислять значение функции f для аргументов х1, ..., хn, можно определить представления гер(x1), ..., гер(xn) аргументов и для них вычислить значение f . С помощью функции abs можно из результата применения f к rep(x1), ..., rep(xn) получить значение функции для аргументов (Xi), ..., (Хn). Из приведенного выше равенства получается коммутирующая диаграмма, показанная на рис.9.1.

f

N”             N

Rep ­          abs¯

(Т*)»         T*

f

Рис. 9.1. Коммутирующая диаграмма

Эту схему отношений между абстрактным и конкретным представлением можно найти также во многих областях пошагового уточнения представления данных в программировании и относящихся к этому функций. Тогда говорится об аспекте абстракции.

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

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

Нужно, чтобы конкретные представления были также реалистически приемлемы для обращения. Поэтому  предполагается, что Т есть конечное множество.


Содержание раздела