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

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

В такой структуре адрес каждого элемента данных определяется путем доступа к нему (маршрута), ведущим от вершины структуры к данному элементу.

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

Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочивания.

1.10.Файлы и файловая структура

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

пользователей некоторое виртуальное представление внешних запоминающих устройств ЭВМ, позволяя работать с ними не на низком уровне команд управления физическими устройствами, а на высоком уровне наборов и структур данных. Таким образом, файловая система – это система управления данными.

Имя файла имеет особое значение – оно фактически несет в себе адресные функции в иерархических структурах. Кроме того, имя может иметь расширение, в котором хранятся сведения о типе данных. Если имена создаваемых файлов пользователь может задавать произвольно, то в использовании расширений следует придерживаться некоторой традиции. Например, в операционной системе MS DOS файлы с расширениями: .com, .exe, .bat – исполняемые; .bat, .txt, .doc – текстовые; .pas, .bas, .c, .for – тексты программ на известных языках программирования: Паскале, Бейсике, Си, Фортране соответственно; .dbf – файл базы данных. В различных операционных системах существуют ограничения на длину имени и расширения имени файла. Так, в MS DOS длина имени файла не должна превышать восьми символов, а расширение – трех, т. е. используется стандарт 8.3. В операционной системе Windows ограничения значительно менее жесткие.

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

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

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

25

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

каталога или файла в такой структуре задает путь переходов между каталогами и файлами в логической структуре каталогов (см. рис. 1.5).

	D	Структура самых файлов может
		быть тривиальной. Например, текст

может

сохраняться

в

виде

DIS

DOS

Мои документы

последовательности

байтов,

соответствующих

кодировке

таблицы

ASCII. Однако в большинстве случаев

вместе с данными приходится хранить

Fax

Security

Издательство

и

некоторую

дополнительную

информацию.

Способ

организации

данных в файле, т. е. структура файла,

Объекты

Информатика

Рисунки

называется форматом.

Формат файла

определяет

способ

правильной

Рис. 1.5. Иерархическая система каталогов

интерпретации

хранимых

данных.

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

В большинстве случаев пользователю ничего не нужно знать о внутреннем устройстве файлов. Это уровень абстракции интерфейса операционных систем.

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

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

qместо возникновения информации;

qстадия ее обработки;

qспособ отображения информации;

qстабильность информации;

qфункция управления информации.

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

26

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

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

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

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

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

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

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

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

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

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

Исторически возникли два подхода к определению количества информации в синтаксическом смысле: вероятностный и “объемный”. Вероятностный подход развил в конце 1940 гг. американский математик Шеннон , а “объемный” возник с изобретением ЭВМ. Понятия “информация”, “неопределенность”, “возможность выбора” тесно связаны. Получаемая информация уменьшает число возможных вариантов выбора (т. е. неопределенность), а полная информация не оставляет вариантов вообще. “Объемный” подход самый простой. За единицу информации здесь принимается один бит. При этом невозможно нецелое число битов. Это количество информации, при котором неопределенность уменьшается вдвое, т. е. это ответ на вопрос, требующий односложного разрешения – да или нет. Однако бит слишком мелкая единица измерения информации. На практике чаще применяются более крупные единицы, например, байт и производные от него:

§1 Килобайт (Кбайт) = 1024 байт = 210 байт;

Клод Элвуд Шеннон (1916 – 2001) – американский математик.

27

§1 Мегабайт (Мбайт) = 1024 Кбайт = 220 байт;

§1 Гигабайт (Гбайт) = 1024 Мбайт = 230 байт;

§1 Терабайт (Тбайт) = 1024 Гбайт = 240 байт.

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

При вероятностном подходе необходимо определить величину, измеряющую неопределенность – энтропию, которая обычно обозначается буквой H. За количество информации, которое получено в ходе осуществления опыта принимается разность неопределенностей “до” и “после” опыта: I = H1− H 2 . Очевидно, что в случае, когда получен конкретный результат, имевшаяся неопределенность снята (H 2 = 0), и, таким

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

Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной кости, имеющей N граней. Величина N и энтропия данного опыта H связаны между собой некоторой функциональной зависимостью H = f (N ). Определим вид этой функции. Если варьировать число граней N и число бросаний кости M , то общее число исходов опыта

будет равно X = N M . Ситуацию с бросанием кости M раз можно рассматривать как некую сложную систему, состоящую из независимых друг от друга подсистем – “однократных бросаний кости”. Энтропия такой системы в M раз больше, чем энтропия одной системы,

т. е. f (X )= f (N M )= M × f (N ). Но

ln X = M ln N ,

отсюда

M = ln X

ln N

.

Подставим

ln X

полученное значение M в формулу для f (X ), тогда

f (X )=

f (N ). Обозначая через K

K = f (N )

ln N

положительную константу

ln N

= H

ln N

, т. к. H = f (N ), получим

H = K ln N .

Обычно принимают K = 1

ln 2

, таким образом получаем формулу Хартли

H = log2 N

(1.11.1)

Очевидно, что H будет равно единице, если N = 2, т. е. в качестве единицы информации принимается её количество, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов. Если рассматривать N равновероятных исходов, то можно считать, что на долю каждого исхода приходиться одна N -я часть общей

неопределенности опыта H

N

= log2

N

, а вероятность i -го исхода P равна 1

N

.Тогда

N

i

N

æ

ö

N

N

1

1

ç

1

÷

= -åPi log2 Pi = -å N log2

N .

(1.11.2)

H = åPi log2 ç P ÷

i=1

è

i ø

i=1

i=1

Формула (1.11.2) называется формулой Шеннона.

Пример 1. Определим количество информации, связанное с появлением каждой буквы в сообщении: “Жил-был у бабушки серенький козлик”.

В этом сообщении 34 знака. Частоты и вероятности появлений букв в сообщении приведены в табл. 1.11.

По формуле Хартли имеем H = log2 19 » 4.25 бит, аналогично по формуле Шеннона

Ральф Хартли (1881 – 1970) – американский инженер и изобретатель.

28