Методичка Теория информации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное бюджетное государственное образовательное учреждение высшего профессионального образования

Ростовский государственный строительный университет

Утверждено на заседании кафедры высшей математики 11.06.2011, протокол №10

Методическое указание по дисциплине «Информатика»

для студентов 1, 2-го курсов ДТИ, ИИЭС

Теория информации

Ростов-на-Дону

2011

1

УДК 681.3.06

Методическое указание по дисциплине «Информатика» для студентов 1, 2-го курсов ДТИ, ИИЭС по теме «Теория информации». – Ростов-на- Дону: Ростовский государственный строительный университет, 2011, 32 с.

Представлен материал, необходимый для освоения курса «Информатика» по теме «Теория информации» для студентов инженерно-технических специальностей. Содержатся основные сведения раздела 2: Технические и программные средства реализации информационных процессов, раздела 10: Основы защиты информации и сведений, составляющих государственную тайну, раздела 11: Методы защиты информации. В каждой части содержатся контрольные тестовые вопросы.

Составитель: канд.физ.-мат.наук, доцент Л.А.Кладенок ассистент Л.И.Сенникова

Рецензенты:

канд.физ.-мат.наук,, доцент В.В.Шамраева

Общее редактирование и компьютерный набор Л.А.Кладенок

© Ростовский государственный строительный университет, 2011

2

1. Информация, ее представление и измерение

Понятие информации является наиболее сложным для понимания и обычно во вводных курсах информатики не определяется, принимается как исходное базовое понятие, понимается интуитивно, наивно. Часто это понятие отождествляется неправильным образом с понятием "сообщение".

Понятие "информация" имеет различные трактовки в разных предметных областях. Например, информация может пониматься как:

абстракция, абстрактная модель рассматриваемой системы (в математике);

сигналы для управления, приспособления рассматриваемой системы (в кибернетике);

мера хаоса в рассматриваемой системе (в термодинамике);

вероятность выбора в рассматриваемой системе (в теории вероятностей);

мера разнообразия в рассматриваемой системе (в биологии) и др.

Рассмотрим это фундаментальное понятие информатики на основе понятия "алфавит".

Формальное определение алфавита: алфавит – конечное множество различных знаков, символов, для которых определена операция конкатенации (приписывания, присоединения символа к символу или цепочке символов); с ее помощью по определенным правилам соединения символов можно получать слова (цепочки знаков) и словосочетания (цепочки слов) в этом алфавите (над этим алфавитом).

Буквой или знаком называется любой элемент x алфавита X, где x X . Понятие знака неразрывно связано с тем, что им обозначается ("со смыслом"), они вместе могут рассматриваться как пара элементов (x, y), где x – сам знак, а y – обозначаемое этим знаком.

Конечная последовательность букв алфавита называется словом в алфавите (или над алфавитом).

Длиной |p| некоторого слова p над алфавитом Х называется число составляющих его букв.

Слово (обозначаемое символом Ø) имеющее нулевую длину, называется

пустым словом: |Ø| = 0.

Множество различных слов над алфавитом X обозначим через S(X) и назовем

словарным запасом (словарем) алфавита (над алфавитом) X.

Вотличие от конечного алфавита, словарный запас может быть и бесконечным.

Слова над некоторым заданным алфавитом определяют сообщения.

Валфавите должен быть определен порядок следования букв (порядок типа "предыдущий элемент – последующий элемент"), то есть любой алфавит имеет

упорядоченный вид X = {x1, x2, …, xn} .

Таким образом, алфавит должен позволять решать задачу лексикографического (алфавитного) упорядочивания, или задачу расположения слов над этим алфавитом, в соответствии с порядком, определенным в алфавите (то есть по символам алфавита).

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

3

Классификации информации:

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

Информация по отношению к источнику или приемнику бывает трех типов:

входная, выходная и внутренняя.

Информация по отношению к конечному результату бывает исходная,

промежуточная и результирующая.

Информация по ее изменчивости бывает постоянная, переменная и смешанная. Информация по стадии ее использования бывает первичная и вторичная.

Информация по ее полноте бывает избыточная, достаточная и недостаточная.

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

Свойства информации:

полнота;

актуальность;

адекватность;

понятность;

достоверность;

массовость;

устойчивость;

ценность и др.

Основные свойства информации, определяющие ее качество:

Объективность и субъективность. (Более объективна та информация, в которую методы обработки вносят субъективный элемент)

Полнота информации -достаточность данных для принятия решений.

Достоверность информации — это уровень посторонних сигналов, зарегистрированных в полезном сигнале.

Адекватность информации — степень соответствия реальному объективному состоянию дела.

Доступность информации — мера возможности получить ту или иную информацию.

Актуальность информации — это степень соответствия информации текущему моменту времени.

Семантический аспект информации [semantic aspect of information] —

характеристика информации с точки зрения ее смысла, содержания. Для

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

Смысловую сторону информации изучает семантика, являющаяся разделом семиотики — науки о знаках и знаковых системах.

1 Тезаурус (от греч. θησαυρός — сокровище) в современной лингвистике — особая разновидность словарей общей или специальной лексики, в которых указаны семантические отношения (синонимы, антонимы, паронимы, гипонимы, гиперонимы и т. п.) между лексическими единицами. Таким образом, тезаурусы, особенно в электронном формате, являются одним из действенных инструментов для описания отдельных предметных областей.

4

Прагматический аспект информации [pragmatical aspect of information] —

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

Методы получения информации можно разбить на три большие группы.

1.Эмпирические методы или методы получения эмпирических данных.

2.Теоретические методы или методы построения различных теорий.

3.Эмпирико-теоретические методы (смешанные) или методы построения теорий на основе полученных эмпирических данных об объекте, процессе, явлении.

Охарактеризуем кратко эмпирические методы.

1.Наблюдение – сбор первичной информации об объекте, процессе, явлении.

2.Сравнение – обнаружение и соотнесение общего и различного.

3.Измерение – поиск с помощью измерительных приборов эмпирических фактов.

4.Эксперимент – преобразование, рассмотрение объекта, процесса, явления с целью выявления каких-то новых свойств.

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

Охарактеризуем кратко теоретические методы.

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

2.Идеализация – получение знаний о целом или его частях путем представления в мышлении целого или частей, не существующих в действительности.

3.Формализация – получение знаний о целом или его частях с помощью языков искусственного происхождения (формальное описание, представление).

4.Аксиоматизация – получение знаний о целом или его частях с помощью некоторых аксиом (не доказываемых в данной теории утверждений) и правил получения из них (и из ранее полученных утверждений) новых верных утверждений.

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

Охарактеризуем кратко эмпирико-теоретические методы.

1.Абстрагирование – выделение наиболее важных для исследования свойств, сторон исследуемого объекта, процесса, явления и игнорирование несущественных и второстепенных.

2.Анализ – разъединение целого на части с целью выявления их связей.

3.Декомпозиция – разъединение целого на части с сохранением их связей с окружением.

4.Синтез – соединение частей в целое с целью выявления их взаимосвязей.

5.Композиция — соединение частей целого с сохранением их взаимосвязей с окружением.

6.Индукция – получение знания о целом по знаниям о частях.

5

7.Дедукция – получение знания о частях по знаниям о целом.

8.Эвристики, использование эвристических процедур – получение знания о целом по знаниям о частях и по наблюдениям, опыту, интуиции, предвидению.

9.Моделирование (простое моделирование), использование приборов – получение знания о целом или о его частях с помощью модели или приборов.

10.Исторический метод – поиск знаний с использованием предыстории, реально существовавшей или же мыслимой.

11.Логический метод – поиск знаний путем воспроизведения частей, связей или элементов в мышлении.

12.Макетирование – получение информации по макету, представлению частей в упрощенном, но целостном виде.

13.Актуализация – получение информации с помощью перевода целого или его частей (а следовательно, и целого) из статического состояния в динамическое состояние.

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

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

Информационная система – это система, в которой элементы, структура, цель, ресурсы рассматриваются на информационном уровне (хотя, естественно, имеются и другие уровни рассмотрения).

Информационная среда – это среда (система и ее окружение) из взаимодействующих информационных систем, включая и информацию, актуализируемую в этих системах.

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

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

Контрольный тест №1:

1)Семантический аспект – это характеристика информации с точки зрения...

a)ее смысла

b)количества информации

c)полезности

d)структуры информации

2)Прагматический аспект информации рассматривает

a)отношения между единицами информации

b)дает возможность раскрыть ее содержание и показать отношение между смысловыми значениями ее элементов

c)информацию с точки зрения ее практической полезности для получателя

d)определяет значение символа естественного алфавита

3)Информацию, достаточную для решения поставленной задачи, называют…

6

a)полной

b)достоверной

c)актуальной

d)объективной

4)Свойство информации, заключающееся в достаточности данных для принятия решений, есть …

a)содержательность

b)полнота

c)достоверность

d)объективность

5)Информация достоверна, если она…

a)отражает истинное положение дел

b)полезна

c)достаточна для принятия решений

d)используется в современной системе обработки информации

6)Представление информации в виде слов определяет характер информации:

a)вербальный

b)смысловой

c)целочисленный

d)знаковый

2. Системы счисления

Можно считать, что любое число имеет значение (содержание) и форму представления.

Значение числа задает его отношение к значениям других чисел («больше», «меньше», «равно») и, следовательно, порядок расположения чисел на числовой оси. Форма представления, как следует из названия, определяет порядок записи числа с помощью предназначенных для этого знаков. При этом значение числа является инвариантом, т.е. не зависит от способа его представления. Это означает также, что число с одним и тем же значением может быть записано по-разному, т.е. отсутствует взаимнооднозначное соответствие между представлением числа и его значением.

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

Способ представления числа определяется системой счисления.

Система счисления – это правило записи чисел с помощью заданного набора специальных знаков – цифр.

Людьми использовались различные способы записи чисел, которые можно объединить в несколько групп: унарная, непозиционные и позиционные.

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

7

Из непозиционных наиболее распространенной можно считать римскую систему счисления. В ней некоторые базовые числа обозначены заглавными латинскими буквами: 1 — I, 5 — V, 10 — X, 50 — L 100 — С, 500 — D, 1000 — М.

Все другие числа строятся комбинаций базовых в соответствии со следующими правилами:

если цифра меньшего значения стоит справа от большей цифры, то их значения суммируются; если слева — то меньшее значение вычитается из большего;

цифры I, X, С и М могут следовать подряд не более трех раз каждая;

цифры V, L и D могут использоваться в записи числа не более одного раза.

Например, запись XIX соответствует числу 19, МDХLIХ — числу 1549. Запись чисел в такой системе громоздка и неудобна, но еще более неудобным оказывается выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел больше М не позволяют римскими цифрами записать любое число (хотя бы натуральное). По указанным причинам теперь римская система используется лишь для нумерации.

В настоящее время для представления чисел применяют, в основном, позиционные системы счисления.

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

Наиболее распространенной и привычной является система счисления, в которой для записи чисел используется 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Число представляет собой краткую запись многочлена, в который входят степени некоторого другого числа — основания системы счисления. Например:

575,15 5 102 7 101 5 100 1 10 1 5 10 2.

Вданном числе цифра 5 встречается трижды, однако значение этих цифр различно и определяется их положением (позицией) в числе. Количество цифр для построения чисел, очевидно, равно основанию системы счисления. Также очевидно, что максимальная цифра на 1 меньше основания. Причина широкого распространения именно десятичной системы счисления понятна — она происходит от унарной системы с пальцами рук в качестве "палочек".

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

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

8

k 1):

Z pk

По принципу, положенному в основу десятичной системы счисления, очевидно, можно построить системы с иным основанием. Пусть р — основание системы счисления. Тогда любое число Z (пока ограничимся только целыми

числами), удовлетворяющее условию ( k 0 , целое), может быть

представлено в виде многочлена со степенями (при этом, очевидно, максимальный показатель степени будет равен

		k 1
Z p ak 1	pk 1 ak 2 pk 2 ... a1 p1 a0	p0 a j p j . (1)
		j 0
Из коэффициентов при степенях основания строится сокращенная запись
числа:
	Z p (ak 1ak 2 ...a1a0 ).
Индекс р числа	Z указывает, что оно записано в	системе счисления с

основанием р, общее число цифр числа равно k. Все коэффициенты a j — целые числа, удовлетворяющие условию: 0 a j p 1.

Уместно задаться вопросом: каково минимальное значение р ? Очевидно, p 1 невозможно, поскольку тогда все a j 0 и форма (1) теряет смысл. Первое

допустимое значение p 2 — оно и является минимальным для позиционных

систем.

Система счисления с основанием 2 называется двоичной. Цифрами двоичной системы являются 0 и 1, а форма (1) строится по степеням 2. Интерес именно к этой системе счисления связан с тем, что любая информация в компьютерах представляется с помощью двух состояний — 0 и 1, которые легко реализуются технически.

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

Представление чисел в различных системах счисления

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

Например: |||||1= 510 = 1012 = 516.

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

Перевод целых чисел из одной системы счисления в другую

Обозначим преобразование числа Z, представленного в p-ричной системе счисления в представление в q -ричной системе как Z p Zq . Теоретически

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

недесятичных систем счисления (полагая в общем случае, что	р, q 0).
По этой причине более удобными с практической точки зрения оказываются
варианты преобразования с промежуточным переводом	Z p Zr	Zq с
9

основанием r, для которого арифметические операции выполнить легко. Таким удобным основанием является r = 10, т.е. перевод осуществляется через десятичную систему счисления.

Преобразование Z p Zr Zq

Идея алгоритма перевода предельно проста: положим начальное значение

Zq : 0 ; из	числа	Z p вычтем	1 по		правилам	вычитания	системы	р ,	т.e.
Z p : Z p 1,	и добавим ее к		Z q	по	правилам	сложения	системы	q,	т.е.
Zq : Zq 1.	Будем	повторять	эту	последовательность действий,				пока	не

достигнем Z p 0 .

Промежуточный переход к унарной системе счисления в данном случае осуществляется неявно — используется упоминавшееся выше свойство независимости значения числа от формы его представления. Рассмотренный алгоритм перевода может быть легко реализован программным путем.

Преобразование Z p Zw Zq

Очевидно, первая и вторая части преобразования не связаны друг с другом,

что дает	основание	рассматривать	их по отдельности. Алгоритмы	перевода
Zw Zq	вытекают из следующих соображений. Многочлен (1) для			Z q может
быть представлен в виде:
	m 1
	Zq b j	q j ((...(bm 1	q bm 2 ) q bm 3 ) q ... b1 ) q b0 , (2)
	j 0
где т — число разрядов в записи Zq ,			а bj ( j 0,...,m 1) — цифры числа Z q .
Разделим число		Z q на две части по разряду номер i. Число, включающее

m i разрядов с (m i) -го по i-й, обозначим i , а число с i разрядами с (i 1) -го

по 0-й — i . Очевидно, i [0, m 1],		0 m 1 Zq .
Z q bm 1bm 2	...bi bi 1...b1b0 .
i	i

Позаимствуем из языка VBA обозначение двух операций: \ — результат целочисленного деления двух целых чисел и mod— остаток от целочисленного деления 13 \ 4 = 3; 13 mod 4 = 1.

Теперь

если

принять

m 1

bm 1 ,

то в

(2)

усматривается

следующее

рекуррентное соотношение: i

i 1 bi из которого,

в свою очередь, получаются

выражения:

i 1 i \ q ;

bi

i

mod q .

(3)

Аналогично,

если

принять

0 b0 ,

то

для

правой

части

числа будет

справедливо

другое рекуррентное

соотношение:

i

i 1

b qi ,

из которого

i

следуют:

b

i

\ qi ;

i 1

i

mod qi .

(4)

i

10