Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
Format) — 1–6-байтные, наиболее совместимые си или 4-байтные. Unicode в прикладных программах реализуется лишь частично, ив полном объеме пока нигде не поддерживается. В Linux используется UTF-8. 94 Достаточно широко используется кодирование на основе ASCII: VI. На базе КОИ — можно использовать при отсутствии кириллических шрифтов, код получается вычитанием 128 от соответствующего кода в koi8-r, что, как правило, дает код латинской буквы, близкой фонетически к русской. В кодировке VI нет видимого символа для для Ъ. Далее следует таблица, в которой представлены все перечисленные способы кодирования букв русского алфавита. В этой таблице в колонке 1 находятся символы букв, в колонке 2 часть названия букв в 3.2 (названия строчных кириллических букв начинается словами, а заглавных — CYRILLIC CAPITAL LETTER, то, полное название буквы Д — CYRILLIC CAPITAL LET- TER DE), в колонках с I по V коды десятичные и шестнадцатеричные соответствующих таблиц кодировки, а в колонке VI — символ для КОИ-7. Кроме перечисленных можно встретить еще используемую до введения кодировок ГОСТ болгарскую кодировку, называемую также MIC, Interprog или старый вариант ВЦ АН СССР. На компьютерах под управлением Macintosh OS используется также своя собственная таблица кодировки для русских букв, по своему набору знаков почти совпадающая с CP1251. 95 1 а D0 160 A0 224 E0 193 C1 1072 б D1 161 A1 225 E1 194 C2 1073 в D2 162 A2 226 E2 215 D7 1074 0432 где 197 C5 1077 еж з D7 167 A7 231 E7 218 DA 1079 и D8 168 A8 232 E8 201 C9 1080 й I 217 D9 169 A9 233 E9 202 CA 1081 кл мн оп р E0 224 E0 240 F0 210 D2 1088 ст уф х E5 229 E5 245 F5 200 C8 1093 ц E6 230 E6 246 F6 195 C3 1094 ч E7 231 E7 247 F7 222 DE 1095 ш E8 232 E8 248 F8 219 DB 1096 щ E9 233 E9 249 F9 221 DD 1097 ъ HARD SIGN 234 EA 234 EA 250 FA 223 DF 1098 ы EB 235 EB 251 FB 217 D9 1099 044B ь SOFT SIGN 236 EC 236 EC 252 FC 216 D8 1100 044C э ED 237 ED 253 FD 220 DC 1101 ю EE 238 EE 254 FE 192 C0 1102 044E я EF 239 EF 255 FF 209 D1 1103 044F Q 96 1 А B0 128 80 192 C0 225 E1 1040 Б B1 129 81 193 C1 226 E2 1041 В B2 130 82 194 C2 247 F7 1042 ГДЕ 229 E5 1045 ЕЖ З B7 135 87 199 C7 250 FA 1047 И B8 136 88 200 C8 233 E9 1048 Й I 185 B9 137 89 201 C9 234 EA 1049 КЛ МН ОП Р C0 144 90 208 D0 242 F2 1056 СТ УФ Х C5 149 95 213 D5 232 E8 1061 Ц C6 150 96 214 D6 227 E3 1062 Ч C7 151 97 215 D7 254 FE 1063 Ш C8 152 98 216 D8 251 FB 1064 Щ C9 153 99 217 D9 253 FD 1065 Ъ HARD SIGN 202 CA 154 9A 218 DA 255 FF 1066 Ы CB 155 9B 219 DB 249 F9 1067 Ь SOFT SIGN 204 CC 156 9C 220 DC 248 F8 1068 042C Э CD 157 9D 221 DD 252 FC 1069 Ю CE 158 9E 222 DE 224 E0 1070 Я CF 159 9F 223 DF 241 F1 1071 042F q 97 Приложение Д. Элементы теории чисел Каноническим разложением числа m называется разложение его на простые сомножители в виде m = p α 1 1 p α 2 2 · · · p α k k , где p 1 , p 2 , . . . , p k — все различные простые делители числа m, а α 1 , α 2 , . . . , α k — целые положительные числа. Функцией Эйлера называется, отображение ϕ: N → N, ϕ(m) = p α 1 −1 1 (p 1 − 1)p α 2 −1 2 (p 2 − 1) · · · p α k −1 k (p k − 1), p α 1 1 p α 2 2 · · · p α k k — каноническое разложение Например, ϕ(2) = 1, ϕ(12) = ϕ(2 2 3) = 2 1 (2 − 1)3 0 (3 − 1) = 2 ∗ 2 = 4, ϕ(1000) = ϕ(2 3 5 3 ) = 2 2 5 2 4 = 4 ∗ 25 ∗ 4 = Числа m и n называются взаимно простыми, если у них нет общих делителей больших 1, те. НОД(m, n) = Функция Эйлера от числа m равна числу чисел меньших m и взаимно простых с m Для взаимно простых m и n верно равенство ϕ(mn) = Число примитивных многочленов степени n над полем (Z 2 , +, равно ϕ(2 n − 1)/n Теорема Эйлера-Ферма [7]. Для взаимно простых m и a имеет место соотношение a ϕ(m) ≡ 1 (mod Для решения уравнения ax ≡ 1 (mod m), где НОД(a, m) = 1, можно использовать теорему Эйлера-Ферма, те. x ≡ a ϕ(m)−1 (mod m), но это весьма трудоемкий способ. Получим решения искомого уравнения через формулу для решения эквивалентного уравнения ax − my = По алгоритму Евклида для получения НОД двух заданных чисел нужно одно число делить на другое, затем делить делитель на получаемый остаток до тех, пока остаток не станет равным нулю. Последний больший нуля остаток будет искомым НОД. Для чисел a и m последовательность шагов алгоритма Евклида выглядит как a = mq 0 + a 1 , m = a 1 q 1 + a 2 , a 1 = a 2 q 2 + a 3 , a n−2 = a n−1 q n−1 + a n , a n−1 = a n q где a 1 , a 2 , . . . , a n — остатки. Разложение a m в цепную дробь по последовательности частных q 0 , . . . , q имеет вид a m = q 0 + a 1 m = q 0 + 1 m a 1 = q 0 + 1 q 1 + a 2 a 1 = · · · = q 0 + 1 q 1 + 1 q 2 + 1 q 3 + · · Обозначим за P k /Q k дробь, получаемую из приведенной цепной дроби отбрасыванием членов с индексами, большими k. Например, P 0 /Q 0 = q 0 , P 1 /Q 1 = q 0 +1/q 1 = (и т.д. Числитель, P k , и знаменатель, можно вычислять рекуррентно последующим формулам 0, P −1 = 1, Q −2 = 1, Q −1 = при k 0 P k = q k P k−1 + P k−2 , Q k = q k Q k−1 + По определению P n = a и Q n = m. Кроме того P n Q n−1 −P n−1 Q n = (q n P n−1 +P n−2 )Q n−1 −P n−1 (q n Q n−1 +Q n−2 ) = = −P n−1 Q n−2 + P n−2 Q n−1 = −F n−1 = · · · = F n−2 = · · · = (−1) n+1 F −1 = = (−1) n+1 (P −1 Q −2 − P −2 Q −1 ) = (или P n−1 (−1) n+1 Q n = что означает a(−1) n+1 Q n−1 − m(−1) n+1 P n−1 = те. x = (и y = (Процесс получения числителей и знаменателей удобно оформить в виде таблицы −1 0 1 2 · · · n − 1 n q k q 0 q 1 q 2 · · · q n−1 q n P k 0 1 P 0 P 1 P 2 · · · P n−1 P n Q k 1 0 Q 0 Q 1 Q 2 · · · Таким образом, корни уравнения ax ≡ 1 (mod m) вычисляются по формуле x = (Пример. Решить уравнение 1181x ≡ 1 (mod 1290816). Сначала по алгоритму Евклида получается следующая цепочка соотношений = 1290816 ∗ 0 + 1181, 1290816 = 1181 ∗ 1092 + 1164, 1181 = 1164 ∗ 1 + 17, 1164 = 17 ∗ 68 + 8, 17 = 8 ∗ 2 + 1, 8 = 1 ∗ 8. 99 Затем составляется таблица для вычисления Q 5 : k −2 −1 0 1 2 3 4 5 q k 0 1092 1 68 2 8 Q k 1 0 1 1092 1093 75416 151925 Таким образом, искомый x равен Гипотеза. Задача разложения целого числа с заданным числом разрядов на множители является труднорешаемой*. На сегодняшний день существуют весьма быстрые алгоритмы для проверки данного числа на простоту, но для разложения 200-значного числа на множители лучшим современным компьютерам по лучшим современным алгоритмам может потребоваться миллиарды лет. Эта гипотеза лежит в основе методов Диффи-Хеллмана. * Задача называется труднорешаемой, если время ее решения зависит от объема входных данных по экспоненциальному закону и не может быть сведено к полиномиальному Приложение Е. Используемые обозначения (A) — вероятность события A. P (A/B) — вероятность события A, если известно, что событие произошло. Условная вероятность (A, B) — вероятность одновременного наступления событий A и — множество натуральных чисел множество из 0 и 1 — {0, 1}. R — множество вещественных чисел числовая плоскость x i — сумма x по всем возможным значениям индекса i. i,j x ij — сумма x ij по всем возможным значениям пар индексов i и j. C k n — биномиальный коэффициент в формуле бинома Ньютона + q) n = n k=0 C k n p k q n−k , C k n = n! k!(n − или число возможных разных выборок k элементов из множества из n элементов, число сочетаний из n по k. dim(X) — размерность вектора X, число компонент X. #X — количество элементов в множестве X, мощность X. НОД(n, m) — наибольший общий делитель n и m. НОК(n, m) — наименьшее общее кратное n и m. a ≡ b (mod n) — числа a и b сравнимы по модулю n, те. разность a − b делится на n нацело : A → B — функция f с областью определения A и областью, содержащей все значения f , B. f ◦ g — композиция функций f и g, те. (f ◦ g)(x) = f (g(x)). (X, +, ×) — поле надмножеством с аддитивной операцией + и мультипликативной операцией ×. 101 Приложение Ж. Список литературы. Биркгоф Г, Барти Т. Современная прикладная алгебра — М Мир. Блейхер Р. Теория и практика кодов, контролирующих ошибки М Мир, 1986. 3. Борн Г. Форматы данных — Киев Торгово-издательское бюро, 1995. 4. Букчин Л. В, Безрукий ЮЛ. Дисковая подсистема совместимых персональных компьютеров — М МИКАП, 1993. 5. Винер Н. Кибернетика — М Наука, 1983. 6. Воробьев Н. Н. Признаки делимости — М Наука, 1988. 7. Глушков В. М. Основы безбумажной информатики — М Наука. Джордж Ф. Основы кибернетики — М Радио и Связь, 1984. 9. Кенцл Т. Форматы файлов Internet — СПб: Питер, 1997. 10. Нельсон М. Верификация файлов Журнал д-ра Добба” 1/93. 11. Нефедов В. Н, Осипова В. А. Курс дискретной математики М МАИ, 1992. 12. Нечаев В. И. Элементы криптографии — М Высшая школа, 1999. 13. Мастрюков Д. Алгоритмы сжатия информации Монитор. Питерсон Р, Уэлдон Э. Коды, исправляющие ошибки — М Мир. Перспективы развития вычислительной техники в 11 кн Справочное пособие/Под ред. Ю. М. Смирнова. Кн. 9. — М Высшая школа, 1989. 16. Розанов Ю. А. Лекции по теории вероятностей — М Наука. Титце У, Шенк К. Полупроводниковая схемотехника — М Мир. Чисар ИК ернер Я. Теория информации — М Мир, 1985. 19. Шеннон К. Работы по теории информации и кибернетики — М.: Издательство иностранной литературы, 1963. 20. Яглом А, Яглом И. Вероятность и информация — М Наука. Введение в криптографию Под общей редакцией В. В. Ященко. — М МЦНМО—ЧеРо, 2000. 22. HTML 4.01 Specification /Edited by D. Ragget, A. L. Hors, I. Jacobs — W3C: http://www.w3c.org/TR/REC-html401-19991224, 1999. 23. The Unicode Standard, Version 3.0 — Addison Wesley Longman Pub- lisher, 2000, ISBN 0-201-61633-5. 102 Приложение З. Предметный указатель (A/C) 8 ARJ 21, 43 ASCII 6, 76, 88, 91 BMP 44 bzip2 адаптивный алгоритм сжатия информации алгоритм Евклида аналоговая информация арифметическое кодирование байт (byte) бинарные файлы бит (bit) блочные коды бод (baud) цифровая информация циклические коды декодирование дискретная информация древовидные коды двоичный, код емкость канала связи 10, физическая разметка текста формальное представление знаний функция ошибок 51 — Эйлера гибридные вычислительные машины групповой код информация 12 — аналоговая 7 — цифровая 7 — дискретная 7 — непрерывная 7 — семантическая канал без шумов 46 — связи дискретный 46 — — непрерывный код блочный 53 — циклический 67 — древовидный 53 — групповой 58 — квазисовершенный 61, 63 — линейный 57 — оптимальный 61 — полиномиальный 66 — последовательный 53 — совершенный 61 — с проверкой четности 50, 51 — — тройным повторением 50, 52 — Голея 67 — Хэмминга кодирование 49 — арифметическое 25 — — адаптивное 33 — помехозащитное 50 — префиксное 19 — Диффи-Хеллмана 72, 100 — Хаффмена 23 — — адаптивное 28 — Шеннона-Фэно 21, 23 — LZ77 35 — LZ78 38 — LZSS 37 — кодировка ГОСТ количество информации компьютер контрольная сумма 53 квазисовершенный код 61, лидер смежного класса линейные коды 57 103 логическая разметка текста 77 CCITT 44, матричное кодирование метод блокирования модуляция частотная непрерывная информация 7 нераскрываемый шифр неравенство (нижняя граница) Хэм- минга 56 — (верхняя граница) Варшамова- Гильберта нижняя граница Плоткина обратная теорема о кодировании при наличии помех общая схема передачи информации оптимальный код основная теорема о кодировании при наличии помех 49 — — — — — отсутствии помех основной факт теории передачи информации полиномиальное кодирование последовательные коды префиксное кодирование примитивный многочлен 68, процедурная разметка текста пропускная способность (емкость) канала 10, расстояние Хэмминга расширенный ASCII (ASCII+) разметка текста (markup). 77 репитер систематические помехозащитные коды словарные методы сжатия совершенный код статистические методы сжатия 35 строка ошибок таблица декодирования 59 — кодировки 6, 76 — стилей тег (tag) HTML текстовые файлы упорядоченное бинарное дерево управление (основная категория кибернетики) вес двоичного слова взаимно простые числа 98 DAC (запись с групповым кодированим (RLL) 48 шифр без передачи ключей 72 — нераскрываемый 72 — простой замены 70 — с открытым ключом 73 — — подписью шифры с ключевым словом 71 — Диффи-Хеллмана 72, 100 шифры-перестановки электронная подпись элемент текста HTML энтропия частота дискретизации частотная модуляция АЦП 8 АВМ 9 БЧХ-коды 68 104 Циклический избыточный код ЦАП 8 ЦВМ Двоичный симметричный канал 50 Информация Канал информационный 45 — связи Каноническое разложение числа 98 Кибернетика Кодирование Коды с исправлением ошибок 51 — — обнаружением ошибок Компьютерный шрифт Криптография КОИ КОИ Линии связи Полиномиальный код 66 Последовательность Фибоначчи 47 Теорема о выборках 8 — Шеннона 49 — Эйлера-Ферма Теория информации Устройства канала связи Задержка сигнала во времени Шум в канале связи Энтропия 13, 18 FM 47 GIF 44 gzip 43 HTML 78 HTTP 78 ISDN 11 JPEG 44, 45 koi8-r 94 LHA 43 LZ77 35, 40 LZ78 38, 41 LZSS 37, 41 LZW 39, 41 MFM 48 MPEG 45 78, 83 PostScript 78, 82 RAR 43 RLE 44 RLL 48 RSA 73 SGML 78, 80 TEX 78, 81 TIFF 44 UCS 94 Unicode 77, 88, 91, 94 URI, URL 78 UTF 94 WWW 78 XML 78, 81 ZIP 21, 43 105 Приложение И. Именной указатель Адлеман (Adleman) 73 Берг 5 Боуз (Bose) Цезарь (Caesar) 70 Диффи (Diffie) 72 Дойл (Doyle) Евклид (Euclid, E ` υκλ Ферма (Fermat) Фибоначчи (Fibonacci) 47 Фишер (Fisher) 12 Фэно (Fano) 21, 23, Гильберт (Gilbert) 56 Глушков 5 Голей (Golay) 67 Хаффмен (Huffman) 23, 28 Хеллман (Hellman) 72 Хоккенгем (Hocquengem) 68 Хэмминг (Hamming) 53, 56, 61, 67 Клаузиус (Clausius) Кнут (Knuth) 81 Котельников Лагранж (Lagrange) 59 Лемпел (Lempel) 35 Найквист (Nyquist) 8 Плоткин (Plotkin) По (Poe) 70 Рид (Reed) 68 Ривест (Rivest) Соломон (Solomon) 68 Сторер (Storer) 37 Уэлч (Welch) 39 Варшамов 56 Винер (Wiener) 4 Зив (Ziv) 35 Шамир (Shamir) 73 Шеннон (Shannon) 4, 12, 18, 21, 23, 49, 70 Шиманский (Szimanski) Эйлер (Euler) 98 Чоудхури (Chaudhuri) 68 106 ОГЛАВЛЕНИЕ Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 Предмет и основные разделы кибернетики . . . . . . . . . . . . . . . . . . . 4 Формальное представление знаний . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Виды информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Хранение, измерение, обработка и передача информации . . . . 8 Базовые понятия теории информации . . . . . . . . . . . . . . . . . . . . . . . 10 Способы измерения информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Вероятностный подход к измерению дискретной и непрерывной информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Смысл энтропии Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Семантическая информация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Сжатие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Простейшие алгоритмы сжатия информации . . . . . . . . . . . . . . . 23 Арифметическое кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Адаптивные алгоритмы сжатия. Кодирование Хаффмена . . .28 Адаптивное арифметическое кодирование . . . . . . . . . . . . . . . . . . . 33 15 Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива . . . . . . . . . . . . . . . . 35 алгоритмы распаковки данных. Примеры . . . . . . . . . . . . . . . 40 Особенности программ-архиваторов . . . . . . . . . . . . . . . . . . . . . . . . 42 Сжатие информации с потерями . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Информационный канал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Помехозащитное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Математическая модель системы связи . . . . . . . . . . . . . . . . . . . . . 51 Матричное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Групповые коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Совершенные и квазисовершенные коды . . . . . . . . . . . . . . . . . . . . 61 Полиномиальные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Понятие о кодах Боуза-Чоудхури-Хоккенгема . . . . . . . . . . . . . . .67 Циклические избыточные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Основы теории защиты информации . . . . . . . . . . . . . . . . . . . . . . . . 70 Криптосистема без передачи ключей . . . . . . . . . . . . . . . . . . . . . . . . 72 Криптосистема с открытым ключом . . . . . . . . . . . . . . . . . . . . . . . . 73 Электронная подпись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Стандарт шифрования данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Информация в Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 34 HTML, XML и SGML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 35 TEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81 36 PostScript и PDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 107 Приложения А Ответы на все упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Б Управляющие коды ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 В Кодировка видимых символов ASCII . . . . . . . . . . . . . . . . . . . . . . . . 91 Г Кодировка букв русского алфавита . . . . . . . . . . . . . . . . . . . . . . . . . 94 Д Элементы теории чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Е Используемые обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Ж Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 З Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 И Именной указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 108 ДЛЯ ЗАМЕТОК УЧЕБНОЕ ПОСОБИЕ Владимир Викторович Лидовский ТЕОРИЯ ИНФОРМАЦИИ Издательство Компания Спутник, Москва, Рязанский проспект, д. 8а Подписано в печать 17.03.2004. Формат Усл. печ. л. 6.81. Тираж 70 экз. Заказ 60. ... самые разные категории читателей найдут в книге что-то интересное для себя. будущим слушателям соответствующих курсов (в различных высших учебных заведениях) она очень пригодится, поскольку заполняет существенный пробел в учебной литературе на русском языке. Александр Шень |