Книги по разным темам
Pages: | 1 | ... | 12 | 13 | 14 | Для решения уравнения ax 1 (mod m), где НОД(a, m) = 1, можно использовать теорему Эйлера-Ферма, т.е. x a(m)-1 (mod m), но это весьма трудоемкий способ. Получим решения искомого уравнения через формулу для решения эквивалентного уравнения ax - my = 1.
По алгоритму Евклида для получения НОД двух заданных чисел нужно одно число делить на другое, затем делить делитель на получаемый остаток до тех, пока остаток не станет равным нулю. Последний больший нуля остаток будет искомым НОД.
Для чисел a и m последовательность шагов алгоритма Евклида выглядит как a = mq0 + a1, m = a1q1 + a2, a1 = a2q2 + a3,...
an-2 = an-1qn-1 + an, an-1 = anqn, a где a1, a2,..., an Ч остатки. Разложение в цепную дробь по послеm довательности частных q0,..., qn имеет вид a a1 1 1 = q0 + = q0 + = q0 + = = q0 +.
m m m a2 q1 + q1 + aaq2 + q3 + Обозначим за Pk/Qk дробь, получаемую из приведенной цепной дроби отбрасыванием членов с индексами, большими k. Например, P0/Q0 = q0, P1/Q1 = q0+1/q1 = (q0q1+1)/q1 и т.д. Числитель, Pk, и знаменатель, Qk, можно вычислять рекуррентно по следующим формулам:
P-2 = 0, P-1 = 1, Q-2 = 1, Q-1 = 0;
при k 0 Pk = qkPk-1 + Pk-2, Qk = qkQk-1 + Qk-2.
По определению Pn = a и Qn = m. Кроме того, Fn = PnQn-1-Pn-1Qn = (qnPn-1+Pn-2)Qn-1-Pn-1(qnQn-1+Qn-2) = = -Pn-1Qn-2 +Pn-2Qn-1 = -Fn-1 = = Fn-2 = = (-1)n+1F-1 = = (-1)n+1(P-1Q-2 - P-2Q-1) = (-1)n+или (-1)n+1PnQn-1 - Pn-1(-1)n+1Qn = 1, что означает a(-1)n+1Qn-1 - m(-1)n+1Pn-1 = 1, т.е. x = (-1)n-1Qn-1 и y = (-1)n-1Pn-1.
Процесс получения числителей и знаменателей удобно оформить в виде таблицы:
k -2 -1 0 1 2 n - 1 n qk q0 q1 q2 qn-1 qn Pk 0 1 P0 P1 P2 Pn-1 Pn Qk 1 0 Q0 Q1 Q2 Qn-1 Qn.
Таким образом, корни уравнения ax 1 (mod m) вычисляются по формуле x = (-1)n-1Qn-1.
Пример. Решить уравнение 1181x 1 (mod 1290816). Сначала по алгоритму Евклида получается следующая цепочка соотношений:
1181 = 1290816 0 + 1181, 1290816 = 1181 1092 + 1164, 1181 = 1164 1 + 17, 1164 = 17 68 + 8, 17 = 8 2 + 1, 8 = 1 8.
Затем составляется таблица для вычисления Q5:
k -2 -1 0 1 2 3 4 qk 0 1092 1 68 2 Qk 1 0 1 1092 1093 75416 151925 1290816.
Таким образом, искомый x равен 151925.
Гипотеза. Задача разложения целого числа с заданным числом разрядов на множители является труднорешаемой*.
На сегодняшний день существуют весьма быстрые алгоритмы для проверки данного числа на простоту, но для разложения 200-значного числа на множители лучшим современным компьютерам по лучшим современным алгоритмам может потребоваться миллиарды лет.
Эта гипотеза лежит в основе методов Диффи-Хеллмана.
* Задача называется труднорешаемой, если время ее решения зависит от объема входных данных по экспоненциальному закону и не может быть сведено к полиномиальному Приложение Е. Используемые обозначения P (A) Ч вероятность события A.
P (A/B) Ч вероятность события A, если известно, что событие B произошло. Условная вероятность.
P (A, B) Ч вероятность одновременного наступления событий A и B.
N Ч множество натуральных чисел.
Z2 Ч множество из 0 и 1 Ч {0, 1}.
R Ч множество вещественных чисел.
R2 Ч числовая плоскость.
i xi Ч сумма xi по всем возможным значениям индекса i.
xij Ч сумма xij по всем возможным значениям пар индексов i,j i и j.
k Cn Ч биномиальный коэффициент в формуле бинома Ньютона n n! k k (p + q)n = Cnpkqn-k, Cn = k!(n - k)! k=или число возможных разных выборок 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 нацело.
f: A B Ч функция f с областью определения A и областью, содержащей все значения f, B.
f g Ч композиция функций f и g, т.е. (f g)(x) = f(g(x)).
(X, +, ) Ч поле над множеством X с аддитивной операцией + и мультипликативной операцией.
Приложение Ж. Список литературы 1. Биркгоф Г., Барти Т. Современная прикладная алгебра Ч М.: Мир, 1976.
2. Блейхер Р. Теория и практика кодов, контролирующих ошибки Ч М.: Мир, 1986.
3. Борн Г. Форматы данных Ч Киев: Торгово-издательское бюро BHV, 1995.
4. Букчин Л. В., Безрукий Ю. Л. Дисковая подсистема IBM-совместимых персональных компьютеров Ч М.: МИКАП, 1993.
5. Винер Н. Кибернетика Ч М.: Наука, 1983.
6. Воробьев Н. Н. Признаки делимости Ч М.: Наука, 1988.
7. Глушков В. М. Основы безбумажной информатики Ч М.: Наука, 1987.
8. Джордж Ф. Основы кибернетики Ч М.: Радио и Связь, 1984.
9. Кенцл Т. Форматы файлов Internet Ч СПб: Питер, 1997.
10. Нельсон М. Верификация файлов //УЖурнал д-ра ДоббаФ 1/93.
11. Нефедов В. Н., Осипова В. А. Курс дискретной математики Ч М.: МАИ, 1992.
12. Нечаев В. И. Элементы криптографии Ч М.: Высшая школа, 1999.
13. Мастрюков Д. Алгоритмы сжатия информации //УМониторФ 7/93Ц6/94.
14. Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки Ч М.: Мир, 1976.
15. Перспективы развития вычислительной техники: в 11 кн.: Справочное пособие/Под ред. Ю. М. Смирнова. Кн. 9. Ч М.: Высшая школа, 1989.
16. Розанов Ю. А. Лекции по теории вероятностей Ч М.: Наука, 1986.
17. Титце У., Шенк К. Полупроводниковая схемотехника Ч М.: Мир, 1983.
18. Чисар И., К Я. Теория информации Ч М.: Мир, 1985.
ернер 19. Шеннон К. Работы по теории информации и кибернетики Ч М.:
Издательство иностранной литературы, 1963.
20. Яглом А., Яглом И. Вероятность и информация Ч М.: Наука, 1973.
21. Введение в криптографию /Под общей редакцией В. В. Ященко.
Ч М.: МЦНМОЧЧеРо, 2000.
22. HTML 4.01 Specification /Edited by D. Ragget, A. L. Hors, I. Jacobs Ч W3C: 1999.
23. The Unicode Standard, Version 3.0 Ч Addison Wesley Longman Publisher, 2000, ISBN 0-201-61633-5.
Приложение З. Предметный указатель ADC (A/C) Ч связи дискретный ARJ 21, Ч Ч непрерывный ASCII 6, 76, 88, код блочный BMP Ч циклический bzip2 Ч древовидный адаптивный алгоритм сжатия инЧ групповой формации Ч квазисовершенный 61, алгоритм Евклида Ч линейный аналоговая информация Ч оптимальный арифметическое кодирование Ч полиномиальный байт (byte) Ч последовательный бинарные файлы Ч совершенный бит (bit) Ч с проверкой четности 50, блочные коды Ч Ч тройным повторением 50, бод (baud) Ч Голея цифровая информация Ч Хэмминга циклические коды кодирование декодирование Ч арифметическое дискретная информация Ч Ч адаптивное древовидные коды Ч помехозащитное двоичный (m, n)-код Ч префиксное емкость канала связи 10, Ч Диффи-Хеллмана 72, физическая разметка текста Ч Хаффмена формальное представление знаЧ Ч адаптивное ний Ч Шеннона-Фэно 21, функция ошибок Ч LZ77 Ч Эйлера Ч LZ78 гибридные вычислительные машиЧ LZSS ны Ч LZW групповой код кодировка ГОСТ информация количество информации Ч аналоговая компьютер Ч цифровая контрольная сумма Ч дискретная квазисовершенный код 61, Ч непрерывная Ч семантическая 20 лидер смежного класса канал без УшумовФ 46 линейные коды логическая разметка текста 77 систематические помехозащитные коды CCITT 44, словарные методы сжатия матричное кодирование совершенный код метод блокирования статистические методы сжатия модуляция частотная непрерывная информация строка ошибок нераскрываемый шифр таблица декодирования неравенство (нижняя граница) ХэмЧ кодировки 6, минга Ч стилей Ч (верхняя граница) ВаршамоваГильберта 56 тег (tag) HTML нижняя граница Плоткина 57 текстовые файлы упорядоченное бинарное дерево обратная теорема о кодировании при наличии помех 49 управление (основная категория кибернетики) общая схема передачи информации 10 вес двоичного слова оптимальный код 61 взаимно простые числа основная теорема о кодировании при DAC (D/A) наличии помех 49 запись с групповым кодированим Ч Ч Ч Ч Ч отсутствии помех 22 (RLL) основной факт теории передачи ин- шифр без передачи ключей формации 49 Ч нераскрываемый CGI 80 Ч простой замены CP1251 94 Ч с открытым ключом CP866 94 Ч Ч подписью CRC 69 шифры с ключевым словом полиномиальное кодирование 65 Ч Диффи-Хеллмана 72, последовательные коды 53 шифры-перестановки префиксное кодирование 19 электронная подпись примитивный многочлен 68, 98 элемент текста HTML процедурная разметка текста 77 энтропия пропускная способность (емкость) частота дискретизации канала 10, 46 частотная модуляция расстояние Хэмминга 53 DES расширенный ASCII (ASCII+) 6 АЦП разметка текста (markup). 77 АВМ репитер 45 БЧХ-коды FM Циклический избыточный код GIF ЦАП gzip ЦВМ HTML Двоичный симметричный канал HTTP ISDN Информация JPEG 44, Канал информационный koi8-r Ч связи LHA Каноническое разложение числа LZ77 35, LZ78 38, Кибернетика LZSS 37, Кодирование LZW 39, Коды с исправлением ошибок MFM Ч Ч обнаружением ошибок MPEG Компьютерный шрифт PDF 78, Криптография PostScript 78, КОИ-7 RAR КОИ-8 RLE Линии связи RLL Полиномиальный код RSA Последовательность Фибоначчи SGML 78, TEX 78, Теорема о выборках TIFF Ч Шеннона UCS Ч Эйлера-Ферма Unicode 77, 88, 91, Теория информации URI, URL Устройства канала связи UTF Задержка сигнала во времени WWW Шум в канале связи 10 XML 78, Энтропия 13, 18 ZIP 21, Приложение И. Именной указатель Адлеман (Adleman) Котельников Берг Лагранж (Lagrange) Боуз (Bose) Лемпел (Lempel) Цезарь (Caesar) Найквист (Nyquist) Диффи (Diffie) Плоткин (Plotkin) Дойл (Doyle) По (Poe) Евклид (Euclid, E ` ) Рид (Reed) Ферма (Fermat) Ривест (Rivest) Фибоначчи (Fibonacci) Соломон (Solomon) Фишер (Fisher) Сторер (Storer) Фэно (Fano) 21, 23, 49 Уэлч (Welch) Гильберт (Gilbert) 56 Варшамов Глушков 5 Винер (Wiener) Голей (Golay) 67 Зив (Ziv) Хаффмен (Huffman) 23, 28 Шамир (Shamir) Хеллман (Hellman) 72 Шеннон (Shannon) 4, 12, 18, 21, 23, Хоккенгем (Hocquengem) 68 49, Хэмминг (Hamming) 53, 56, 61, 67 Шиманский (Szimanski) Клаузиус (Clausius) 12 Эйлер (Euler) Кнут (Knuth) 81 Чоудхури (Chaudhuri) ОГЛАВЛЕНИЕ Введение......................................................1 Предмет и основные разделы кибернетики................... 2 Формальное представление знаний........................... 3 Виды информации............................................ 4 Хранение, измерение, обработка и передача информации.... 5 Базовые понятия теории информации....................... 6 Способы измерения информации............................ 7 Вероятностный подход к измерению дискретной и непрерывной информации................................... 8 Смысл энтропии Шеннона.................................. 9 Семантическая информация................................. 10 Сжатие информации........................................ 11 Простейшие алгоритмы сжатия информации............... 12 Арифметическое кодирование............................... 13 Адаптивные алгоритмы сжатия. Кодирование Хаффмена...14 Адаптивное арифметическое кодирование................... 15 Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива................ 16 LZ-алгоритмы распаковки данных. Примеры............... 17 Особенности программ-архиваторов........................ 18 Сжатие информации с потерями............................ 19 Информационный канал..................................... 20 Помехозащитное кодирование............................... 21 Математическая модель системы связи..................... 22 Матричное кодирование..................................... 23 Групповые коды............................................. 24 Совершенные и квазисовершенные коды.................... 25 Полиномиальные коды...................................... 26 Понятие о кодах Боуза-Чоудхури-Хоккенгема...............27 Циклические избыточные коды..............................28 Основы теории защиты информации........................ 29 Криптосистема без передачи ключей........................30 Криптосистема с открытым ключом........................ 31 Электронная подпись........................................32 Стандарт шифрования данных.............................. 33 Информация в Internet...................................... 34 HTML, XML и SGML....................................... 35 TEX..........................................................36 PostScript и PDF............................................ Приложения А Ответы на все упражнения..................................Б Управляющие коды ASCII.................................. В Кодировка видимых символов ASCII........................ Г Кодировка букв русского алфавита......................... Д Элементы теории чисел..................................... Е Используемые обозначения................................. Ж Список литературы........................................ З Предметный указатель..................................... И Именной указатель......................................... ДЛЯ ЗАМЕТОК УЧЕБНОЕ ПОСОБИЕ Владимир Викторович Лидовский ТЕОРИЯ ИНФОРМАЦИИ Издательство Компания Спутник+ 109428, Москва, Рязанский проспект, д. 8а Подписано в печать 17.03.2004. Формат 6090/16.
Усл. печ. л. 6.81. Тираж 70 экз. Заказ 60.
... самые разные категории читателей найдут в книге что-то интересное для себя.
... будущим слушателям соответствующих курсов (в различных высших учебных заведениях) она очень пригодится, поскольку заполняет существенный пробел в учебной литературе на русском языке.
Pages: | 1 | ... | 12 | 13 | 14 | Книги по разным темам