Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Постановка вопроса
Информация для целей ее машинного хранения и обработки всегда должна быть представлена в строго определенной форме. На нашем уровне культурного развития наиболее распространенной формой представления информации являются тексты. С точки зрения информатики текст является последовательностью знаков (литер), или, точнее говоря, конечной последовательностью знаков. Существует много различных систем представления, базирующихся на последовательностях знаков. Наряду с этим способом имеется много и других возможностей представления информации. В этой главе будет рассматриваться представление информации в виде последовательностей знаков из некоторого конечного их набора. Различные системы представления информации по-разному удобны для целей ее машинной обработки.
Поиски простых и экономичных представлений информации с помощью последовательностей знаков приводят к вопросам кодирования информации и кодам. Кодировка, или код, позволяют осуществлять переход от одной заданной системы представления рассматриваемой информации в виде знаков и последовательностей знаков к другому представлению той же информации также в виде знаков и их последовательностей.
При выборе способа кодировки и его обсуждения в первую очередь учитываются две цели: экономичность представления и обработки, а также мера надежности от ошибок. Прежде всего - из естественных соображений эффективности - интересны по возможности короткие кодовые слова, с тем чтобы представление информации в виде кодов было по возможности компактным, наглядным и более дешевым. Кроме того,и обработка информации в выбранной системе представления должна быть простой и экономичной. С другой стороны, если в процессе передачи или обработки информации в кодовых словах появляются случайные незначительные ошибки, то , естественно, хотелось бы быть в состоянии такие «испорченные» кодовые слова по меньшей мере выявлять и даже - несмотря на это - соответствующим образом их декодировать. Если установить заданную среднюю частоту (вероятность) появления кодируемой информации и тем самым среднюю частоту появления отдельных знаков в представлении кодируемой информации, то кажется естественным так умело выбрать кодировку, чтобы средняя длина кода была по возможности меньше. Отсюда весьма уместно - при задании вероятности помех - так выбрать кодировку, чтобы вероятность невыявления помех была достаточно малой.
С помощью этого перевода вместо абстрактного отображения между натуральными числами
f: N” -> N
рассматривается конкретное отображение между последовательностями знаков
f : (Т*)» -> Т*
со следующим свойством (для всех xj,..., Хn Î N):
 |
Это равенств говорит, что , вместо того чтобы вычислять значение функции f для аргументов х1, ..., хn, можно определить представления гер(x1), ..., гер(xn) аргументов и для них вычислить значение f . С помощью функции abs можно из результата применения f к rep(x1), ..., rep(xn) получить значение функции для аргументов (Xi), ..., (Хn). Из приведенного выше равенства получается коммутирующая диаграмма, показанная на рис.9.1.
f
 |
Rep abs¯
 |
f
Рис. 9.1. Коммутирующая диаграмма
Эту схему отношений между абстрактным и конкретным представлением можно найти также во многих областях пошагового уточнения представления данных в программировании и относящихся к этому функций. Тогда говорится об аспекте абстракции.
Употребительными формами представления чисел являются представление соответствующим количеством штрихов, двоичное или десятичное представления и разложением на простые числа. Существует зависимость между сложностью вычислений и выбором конкретного представления. Для определения понятия вычислимости дополнительно требуется, чтобы функции гер и abs сами были вычислимы в интуитивном смысле.
Конкретные алгоритмы работают всегда с представлениями натуральных чисел.
Нужно, чтобы конкретные представления были также реалистически приемлемы для обращения. Поэтому предполагается, что Т есть конечное множество.
