Лидовский в и теория информации м высшая школа 2002г 120с

Обновлено: 05.07.2024

Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению 654600 — Информатика

и вычислительная техника, специальности 220200 — Автоматизированные системы обработки информации и управления

Лидовский В. В. Теория информации: Учебное пособие. —

М.: Компания Спутник+, 2004. — 111 с. — ISBN 5-93406-661-7.

Электронная версия от 23.11.2004

В учебном пособии излагаются основные понятия и факты теории информации. Рассмотрены способы измерения, передачи и обработки информации. Значительное внимание уделено свойствам меры информации, характеристикам канала связи, помехозащитному, уплотняющему и криптографическому кодированию. Кроме того, рассмотрены вопросы формализации информации, в частности, в документах Internet. Изложение сопровождается большим количеством примеров и упражнений.

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

Библиогр. 23 назв. Ил. 28.

РЕЦЕНЗЕНТЫ: Кафедра “Управления и моделирования систем” Московской государственной академии приборостроения и информатики (зав. кафедрой — д-р. тех. наук С. Н. Музыкин), доцент Н. Я. Смирнов

Для подготовки издания использовались системы plain T E X, A M S-Fonts, P I CT E X и TreeT E X

Настоящее пособие достаточно полно освещает основные положения теории информации в соответствии с Государственным образовательным стандартом РФ от 1995 г. по специальности “Автоматизированные системы обработки информации и управления” (220200). Содержание некоторых глав (2, 9, 33–36) пособия выходит за рамки стандарта для означенной специальности, но затронутые в них темы актуальны и органично вписываются в материал пособия.

Содержание пособия во многом базируется на некоторых вводных понятиях курса “Теория вероятностей”: дискретная случайная величина (д.с.в.), закон распределения вероятностей, математическое ожидание (м.о.) и т.п. Кроме того, от читателя требуется умение выполнять соответствующие операции с матрицами, многочленами и булевыми величинами.

В главах с 1 по 9 рассмотрены общие вопросы, определяющие практические подходы к использованию понятия информация, т.е. дано определение основных терминов, используемых при работе с информацией, очерчен круг вопросов, рассматриваемых в теории информации, приведены способы хранения, обработки, преобразования, передачи и измерения информации.

В главах 10–18 рассматриваются способы сжатия информации. Рассмотрены как статистические методы (Шеннона-Фэно, Хаффмена, арифметический), так и словарные методы Лемпела-Зива. Для статистических методов приведены варианты адаптивных алгоритмов кодирования. Приводятся формулы для оценки предельной степени сжатия информации. Обзорно рассматриваются способы сжатия информации с потерями и типы файлов, содержащих сжатые данные.

Глава 19 посвящена физическому уровню передачи информации по каналам связи. Рассматриваются методы расчета пропускной способности (емкости) канала, теорема Шеннона и обратная ей теорема, способы кодирования дискретной информации для передачи. Полное раскрытие названных тем требует привлечения мощного аппарата средств теории вероятностей и теории связи, выходящих за рамки соответствующих курсов студентов втузов, поэтому эти темы раскрыты лишь частично,

в обзорном порядке.

В главах 20–27 рассматриваются способы построения и использо-

вания избыточных кодов для защиты от помех. Приводятся фундаментальные характеристики таких кодов. Для понимания материала 23-й главы необходимо знакомство с начальными элементами теории групп.

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

В заключительных главах рассмотрены некоторые вопросы использования информации в Internet.

Используемые обозначения, не определенные явно в основном материале, приводятся в Приложении Е.

Ссылки на литературу из Приложения Ж, содержащую обоснования приведенных фактов или дополнительные подробности, заключаются в квадратные скобки.

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

Автор считает необходимым выразить искреннюю благодарность всем тем, кто помог ему в создании этого пособия, в особенности, Пантелееву П. А., Лидовской В. В. и Бурашникову С. Р.

1. Предмет и основные разделы кибернетики

Теория информации рассматривается как существенная часть кибернетики.

Кибернетика — это наука об общих законах получения, хранения, передачи и переработки информации. Ее основной предмет исследования — это так называемые кибернетические системы, рассматриваемые абстрактно, вне зависимости от их материальной природы. Примеры кибернетических систем: автоматические регуляторы в технике, ЭВМ, мозг человека или животных, биологическая популяция, социум. Часто кибернетику связывают с методами искусственного интеллекта, т. к. она разрабатывает общие принципы создания систем управления и систем для автоматизации умственного труда. Основными разделами (они фактически абсолютно самостоятельны и независимы) современной кибернетики считаются: теория информации, теория алгоритмов, теория автоматов, исследование операций, теория оптимального управления и теория распознавания образов.

Родоначальниками кибернетики (датой ее рождения считается 1948 год, год соответствующей публикации) считаются американские ученые Норберт Винер (Wiener, он — прежде всего) и Клод Шеннон (Shannon, он же основоположник теории информации).

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

в основу кибернетики изучение законов передачи и преобразования информации.

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

В СССР значительный вклад в развитие кибернетики внесли академики Берг А. И. и Глушков В. М.

В нашей стране в 50-е годы кибернетика была объявлена лженаукой и была практически запрещена, что не мешало, однако, развиваться всем ее важным разделам (в том числе и теории информации) вне связи с обобщающим словом “кибернетика”. Это было связано с тем, что сама по себе кибернетика представляет собой род философии, в коечем конфликтной с тогдашней официальной доктриной (марксистсколенинской диалектикой).

Теория информации тесно связана с такими разделами математики как теория вероятностей и математическая статистика, а также прикладная алгебра, которые предоставляют для нее математический фундамент. С другой стороны теория информации исторически и практически представляет собой математический фундамент теории связи. Часто теорию информации вообще рассматривают как одну из ветвей теории вероятностей или как часть теории связи. Таким образом, предмет “Теория информации” весьма узок, т.к. зажат между “чистой” математикой и прикладными (техническими) аспектами теории связи.

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

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

2. Формальное представление знаний

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

ASCII (American Standard Code for Information Interchange), использу-

емая повсеместно с вычислительной техникой. Она сопоставляет печатным и управляющим символам (управляющими являются, например, символы, отмечающие конец строки или страницы) числа от 0 до 127. Следующая программа на языке Паскаль выведет на экран все печатные символы этой таблицы и их коды:

for i := 32 to 126 do

На практике обычно используют не сам исходный ASCII, а так называемый расширенный ASCII (ASCII+), описывающий коды 256 символов (от 0 до 255). Первые 128 позиций расширенного ASCII совпадают со стандартом, а дополнительные 128 позиций определяются производителем оборудования или системного программного обеспечения. Кроме того, некоторым управляющим символам ASCII иногда назначают другое значение.

Хотя таблицы кодировки используются для формализации информации, сами они имеют неформальную природу, являясь мостом между реальными и формальными данными. Например, коду 65 в ASCII соответствует заглавная латинская буква A, но не конкретная, а любая. Этому коду будет соответствовать буква A, набранная жирным прямым шрифтом, и буква A, набранная нежирным с наклоном вправо на 9.5 ◦ шрифтом, и даже буква A готического шрифта. Задача сопоставления реальной букве ее кода в выбранной таблице кодировки очень сложна и частично решается программами распознания символов (на-

пример, Fine Reader).

Каков код букв W и w в ASCII?

3. Виды информации

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

Дискретная информация удобнее для обработки человеком, но непрерывная информация часто встречается в практической работе, поэтому необходимо уметь переводить непрерывную информацию в дискретную (дискретизация) и наоборот. Модем (это слово происходит от слов модуляция и демодуляция) представляет собой устройство для такого перевода: он переводит цифровые данные от компьютера в звук или электромагнитные колебания-копии звука и наоборот.

При переводе непрерывной информации в дискретную важна так называемая частота дискретизации ν, определяющая период (T = 1/ν) между измерениями значений непрерывной величины (см. рис. 1).

* Конвертация файла может нарушить форматирование оригинала. По-возможности скачивайте файл в оригинальном формате.

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.

Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.

Для решения уравнения 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 — .

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.

НОД(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.

23. The Unicode Standard, Version 3.0 — Addison Wesley Longman Publisher, 2000, ISBN 0-201-61633-5.

Усл. печ. л. 6.81. Тираж 70 экз. Заказ 60.

. самые разные категории читателей найдут в книге что-то интересное для себя.

. будущим слушателям соответствующих курсов (в различных высших учебных заведениях) она очень пригодится, поскольку заполняет существенный пробел в учебной литературе на русском языке.

В учебном пособии излагаются основные понятия и факты теории информации. Рассмотрены способы измерения, передачи и обработки информации. Значительное внимание уделено свойствам меры информации, характеристикам канала связи, помехозащитному, уплотняющему и криптографическому кодированию. Кроме того, рассмотрены вопросы формализации информации, в частности, в документах Inteet. Изложение сопровождается большим количеством примеров и упражнений.
Для студентов втузов соответствующих специальностей и всех интересующихся вопросами точной работы с информацией и методами построения кодов с полезными свойствами.

Голдман С. Теория информации

формат djvu
размер 8.48 МБ
добавлен 21 октября 2010 г.

Москва. 1957 год. Издательство иностранной литературы. Сохранность хорошая. "Теория информации" Голдмана является первой большой монографией по этому вопросу, выпускаемой на русском языке. Созданная за последнее десятилетие новейшая математическая дисциплина - теория информации - тесно связана с рядом теоретических и прикладных разделов науки: с теорией вероятностей, кибернетикой, радиотехникой и др. Книга рассчитана на широкий круг читателей, в.

Гоппа В.Д. Введение в алгебраическую теорию информации

формат djvu
размер 733.5 КБ
добавлен 10 марта 2010 г.

М.: Наука, Физматлит, 1995. -112 с. Развивается алгебраический подход к теории информации. Теория информации трактуется как абстрактная теория слов со своими специфическими задачами, связанными с хранением слов в памяти компьютера, обработкой слов и их передачей по каналам связи. На множестве слов канонически присутствует алгебраическая структура, связанная с действием симметрической группы на словах. Эта структура используется для определения ин.

Духин А.А. Теория информации

формат pdf
размер 15.62 МБ
добавлен 27 декабря 2009 г.

Колмогоров А.Н. Теория информации и теория алгоритмов

формат djvu
размер 4.58 МБ
добавлен 26 октября 2009 г.

Москва.: Наука, 1987. -304с В настоящую работу включены работы по теории информации и теории алгоритмов и их приложениям к различным областям знания. комментарии специалистов дают представление о развитии работ А. Н. Колмогорова и современном состоянии рассматриваемых в них проблем. О понятии алгоритма К общему определению количества информации Теория передачи информации Энтропия и ёмкость множеств в функциональных пространствах Подходы к оценк.

Контрольная работа - Теория информации

формат doc
размер 108.47 КБ
добавлен 14 марта 2010 г.

Кудряшов Б.Д. Теория информации

формат pdf
размер 1.22 МБ
добавлен 09 февраля 2011 г.

Учебное пособие. - СПб.: СПбГУ ИТМО, 2010. - 188 с. Теория информации - наука, появление на свет которой связывают с опубликованием Клодом Шенноном работы "Математическая теория связи" в 1948 г. С точки зрения Шеннона, теория информации - раздел математической теории связи. Пособие включает четыре раздела: Измерение информации дискретных источников; Неравномерное кодирование дискретных источников; Кодирование для дискретных каналов с шумом; Непре.

Лекции по теоретическим основам информации (ТОИ)

формат doc
размер 369.03 КБ
добавлен 12 января 2010 г.

Ломакин Д.В., Туркин А.И. Прикладная теория информации и кодирования

формат pdf
размер 975.4 КБ
добавлен 20 декабря 2010 г.

Ломакин Д. В., Туркин А. И. Прикладная теория информации и кодирования. Конспект лекций. Горьковский политехнический институт, Горький, 1988. Изложены теоретические основы прикладной теории информации и методы ее использования в различных областях науки и техники. Рассматривается роль теории информации и теории кодирования в задачах создания эффективных автоматизированных систем управления и связи. Предназначено для студентов специальности 22.0.

Мирянов В.И. Методическое пособие по курсу Теория информации и кодирования

формат doc
размер 2.03 МБ
добавлен 30 октября 2010 г.

Харкевич А.А. Теория информации и ее приложения

формат djvu
размер 4.8 МБ
добавлен 02 ноября 2010 г.

Сборник переводов иностранных статей по теории информации и ее приложениям к связи. Москва: Гос. изд. физико-математической литературы - 1959. - 329 с. В последние годы чрезвычайно бурное развитие получила теория информации, связанная с техникой электрической связи, электронными счетно-решающими устройствами и другими актуальнейшими проблемами современной техники. Предлагаемый сборник содержит некоторые из наиболее интересных и часто упоминаемых.

Читайте также: