Международные системы байтового кодирования
Информатика и ее приложения интернациональны. Это связано как с объективными потребностями человечества в единых правилах и законах хранения, передачи и обработки информации, так и с тем, что в этой сфере деятельности (особенно в ее прикладной части) заметен приоритет одной страны, которая благодаря этому получает возможность «диктовать моду».
Компьютер считают универсальным преобразователем информации. Тексты на естественных языках и числа, математические и специальные символы - одним словом все, что в быту или в профессиональной деятельности может быть необходимо человеку, должно иметь возможность быть введенным в компьютер.
В силу безусловного приоритета двоичной системы счисления при внутреннем представлении информации в компьютере кодирование «внешних» символов основывается на сопоставлении каждому из них определенной группы двоичных знаков. При этом из технических соображений и из соображений удобства кодирования-декодирования следует пользоваться равномерными кодами, т.е. двоичными группами равной длины.
Попробуем подсчитать наиболее короткую длину такой комбинации с точки зрения человека, заинтересованного в использовании лишь одного естественного алфавита - скажем, английского: 26 букв следует умножить на 2 (прописные и строчные) - итого 52; 10 цифр, будем считать, 10 знаков препинания; 10 разделительных знаков (три вида скобок, пробел и др.), знаки привычных математических действий, несколько специальных символов (типа #, $, & и др.) — итого ~ 100. Точный подсчет здесь не нужен, поскольку нам предстоит решить простейшую задачу: имея, скажем, равномерный код из групп по N двоичных знаков, сколько можно образовать разных кодовых комбинаций. Ответ очевиден К = 2N. Итак, при N = 6 К = 64 - явно мало, при N = 7 К = 128 - вполне достаточно.
Однако, для кодирования нескольких (хотя бы двух) естественных алфавитов (плюс все отмеченные выше знаки) и этого недостаточно. Минимально достаточное значение N в этом случае 8; имея 256 комбинаций двоичных символов, вполне можно решить указанную задачу. Поскольку 8 двоичных символов составляют 1 байт, то говорят о системах «байтового» кодирования.
Наиболее распространены две такие системы: EBCDIC (Extended Binary Coded Decimal Interchange Code) и ASCII (American Standard Information Interchange).
Первая - исторически тяготеет к «большим» машинам, вторая чаще используется на мини- и микро-ЭВМ (включая персональные компьютеры). Ознакомимся подробнее именно с ASCII, созданной в 1963 г.
В своей первоначальной версии это - система семибитного кодирования. Она ограничивалась одним естественным алфавитом (английским), цифрами и набором различных символов, включая «символы пишущей машинки» (привычные знаки препинания, знаки математических действий и др.) и «управляющие символы». Примеры последних легко найти на клавиатуре компьютера: для микро-ЭВМ, например, DEL - знак удаления символа.
В следующей версии фирма IBM перешла на расширенную 8-битную кодировку. В ней первые 128 символов совпадают с исходными и имеют коды со старшим битом равным нулю, а остальные коды отданы под буквы некоторых европейских языков, в основе которых лежит латиница, греческие буквы, математические символы (скажем, знак квадратного корня) и символы псевдографики. С помощью последних можно создавать таблицы, несложные схемы и др.
Для представления букв русского языка (кириллицы) в рамках ASCII было предложено несколько версий. Первоначально был разработан ГОСТ под названием КОИ-7, оказавшийся по ряду причин крайне неудачным; ныне он практически не используется.
В табл. 1.9 приведена часто используемая в нашей стране модифицированная альтернативная кодировка. В левую часть входят исходные коды ASCII; в правую часть (расширение ASCII) вставлены буквы кириллицы взамен букв, немецкого, французского алфавитов (не совпадающих по написанию с английскими), греческих букв, некоторых спецсимволов.
Знакам алфавита ПЭВМ ставятся в соответствие шестнадцатиричные числа по правилу: первая - номер столбца, вторая - номер строки. Например: английская 'А' - код 41, русская 'и' - код А8.
Таблица 1.9 Таблица кодов ASCII (расширенная)
Одним из достоинств этой системы кодировки русских букв является их естественное упорядочение, т.е. номера букв следуют друг за другом в том же порядке, в каком сами буквы стоят в русском алфавите. Это очень существенно при решении ряда задач обработки текстов, когда требуется выполнить или использовать лексикографическое упорядочение слов.
Из сказанного выше следует, что даже 8-битная кодировка недостаточна для кодирования всех символов, которые хотелось бы иметь в расширенном алфавите. Все препятствия могут быть сняты при переходе на 16-битную кодировку Unicode, допускающую 65536 кодовых комбинаций.
Контрольные вопросы
1. Как определяется алфавит?
2. Что такое код?
3. Как объяснить большую помехоустойчивость передаваемых сообщений, составленных на русском языке?
4. Что определяют первая и вторая теоремы Шеннона?
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
ОСНОВНЫЕ ПОНЯТИЯ
Такая структура, какграф (в качестве синонима используется также термин «сеть») , имеет самые различные применения в информатике и в смежных прикладных областях, поэтому познакомимся с основными понятиями теории графов.
Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества V1, v2,..., vM называютсявершинами графа (при графическом представлении им соответствуют точки). Элементы второго множества е1, е2, ...,eN называютребрами. Каждое ребро определяется парой вершин (при графическом представлении ребро соединяет две вершины графа). Если ребра графа определяются упорядоченными парами вершин, то такой граф называюториентированным (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление). Ориентированный граф с пятью вершинами и семью ребрами изображен на рис. 1.6.
Рис. 1.6. Пример ориентированного графа
Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называетсяпетлей (например, ребро е7). Граф без петель и параллельных ребер называется простым.
Если ребро ek определяется вершинами vi и vj (будем обозначать этот факт следующим образом: ek = (vi, vj), то говорят, что ребро ekинцидентно вершинам vi и vj. Две вершины vi и vj называются смежными, если в графе существует ребро (vi, vj).
Последовательность вершин vi1, vi2,..., vik, таких, что каждая пара (vi,(j-1), vij) при 1 < j ≤ k определяет ребро, называетсямаршрутом в графе G. Вершины vil и vik называютконцевыми вершинами маршрута, все остальные входящие в него вершины -внутренними.
Маршрут, в котором все определяемые им ребра различны, называют цепью. Цепь считают замкнутой, если ее концевые вершины совпадают. Замкнутая цепь, в которой все вершины (за исключением концевых) различны, называется циклом. Незамкнутая цепь, в которой все вершины различны, носит название путь. Если в ориентированном графе существует путь из vi в vj, то говорят, что вершина vj достижима из вершины vi.
Две вершины vi и vj называют связанными в графе G, если в нем существует путь, для которого эти вершины являются концевыми. Граф G называется связным, если каждые две вершины в нем являются связанными. На рис. 1.7 изображен простой неориентированный связный граф.
Последовательность вершин v1, v5, i4, v3 , например, определяет путь, а последовательность вершин v1, v5, i4, v3, vl, v1 - цикл.Деревом будем называть неориентированный связный граф без циклов.Лес - это любой граф без циклов. На рис. 1.8 показаны возможные деревья с пятью вершинами.
Рис. 1.7. Пример неориентированного связного графа
Рис. 1.8. Примеры деревьев
Анализ приведенных здесь понятий и определений показывает, что в качестве моделей графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов, между которыми существуют определенные связи, отношения, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в разделах: операционные системы, алгоритмизация, структуры данных, информационное моделирование и др.
ПРЕДСТАВЛЕНИЕ ГРАФОВ
Важным вопросом, особенно для приложений теории графов, является определение возможных способов представления графов. Самый простой способ - полное перечисление множеств V и Е. Однако, очевидно, что в этом случае выявление у графа различных характеристик и свойств будет крайне затруднительным. Граф можно представить в виде некоторого графического изображения и визуально определить некоторые свойства и характеристики заданного графа. Однако, при наличии в графе'большого числа ребер и вершин этот способ также мало пригоден. Рассматривая различные возможные способы представления графов, мы должны иметь в виду потребность ввода соответствующей информации в компьютер. В этой связи ввод информации в числовом виде предпочтителен, хотя современные технические средства допускают ввод и графической информации (таблиц, текста, графиков, рисунков и т.д.), после чего может производиться обработка такой информации.
Матрица смежности. Если вершины графа G помечены метками v1, v2,..., vn, то элементы матрицы смежности A(G) размера V, xV определяются следующим образом: A(i.j) = 1, если vi смежна с vj; A(ij) = 0 в противном случае (рис. 1.9, а).
Матрица инцидентности. Если вершины графа G помечены метками v1, v2,..., vm, а ребра - метками е1, е2,..., еп, то элементыматрицы инцидентности I(G) размера М х N определяются правилом: B(ij) = 1, если vi инцидентна ej; B(iJ) = 0 в противном случае (см. рис. 1.9, б).
Рис. 1.9, а. Матрица смежности Рис. 1.9, б. Матрица инцидентности
Для ориентированного графа G, имеющего N вершин можно рассмотреть матрицу достижимости C(G) размера N х N, элементы которой определяются так: С(I, J) = 1, если вершина vj достижима из vi; C(I, J) = 0 в противном случае. Ниже приведен пример ориентированного графа и его матрицы достижимости, рис. 1.10.
Рис. 1.10. Матрица достижимости ориентированного графа
Контрольные вопросы
1. Каким образом определяется граф?
2. Что является путем в графе?
3. Как определяется такой вид графа, как дерево?
4. Какими способами можно задать граф?
АЛГОРИТМ И ЕГО СВОЙСТВА
6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОНЯТИЮ «АЛГОРИТМ»
Понятие алгоритма - одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким и кибернетике.
Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике -теории алгоритмов.
Особенность положения состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия. Поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером.
Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.