Методичка. Учебное пособие В. М. Лопатин издание второе, стереотипное 1 17
 Скачать 4.33 Mb.
|
|
Единицы измерения и хранения данных Для измерения количества информации используют в основном два подхода. 1. Символьный (алфавитный) подходоснован на делении информационного блока на простые информационные элементы с последующим подсчетом числа этих элементов. В случае текстового блока простым информационным элементом выбирают символ и для каждого символа используют 1 байт памяти. При записи в памяти каждый байт регистрируется в виде двоичного восьмиразрядного кода. Количество информации измеряют при этом простым подсчетом числа символов и выражают его в количестве байтов. Использование числа символов для опреде- ления количества информации в тексте лежит в основе алфавитного подхода. Алфавитный подход основан на том, что всякое сообщение можно закодиро- вать с помощью конечной последовательности символов некоторого алфавита. Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой (равновероятно), то количество информации, которое несет каждый символ (информационный вес одного символа), вычисляется по формуле 2 log , I N = (1) где N – мощность алфавита (полное количество символов, составляющих алфа- вит выбранного кодирования). Из (1) следует, что мощность алфавита можно вы- числить по формуле 2 . I N = (2) В алфавите, который состоит из двух символов (двоичное кодирование), каж- дый символ несет 1 бит (log 2 2 = 1) информации. Если мощность алфавита состав- ляет четыре символа, то каждый символ несет 2 бита информации (log 2 4 = 2); в алфавите из восьми символов – 3 бита (log 2 8 = 3) и т. д. Один символ из алфавита мощностью 256 несет в тексте 8 бит (log 2 256 = 8) информации. Если весь текст состоит из k символов, то при алфавитном подходе размер содержащейся в нем информации H определяется по формуле , H k I = ⋅ (3) где I – информационный вес одного символа в используемом алфавите. 13 / 17 14 Максимальное количество слов L из m букв, которое можно составить из ал- фавита мощностью N, определяется по формуле m L N = (4) При увеличении объемов информации используют единицу измерения байт с приставками кило-, мега-, гига- и т. д. Соотношения между единицами измере- ния количества информации представлены в табл. 1. Таблица 1 Единицы измерения количества информации Наименование единицы Форма записи Кол-во единиц Кол-во байтов Кол-во бит Килобайт Кбайт 1024 байт 2 10 2 13 Мегабайт Мбайт 1024 Кбайт 2 20 2 23 Гигабайт Гбайт 1024 Мбайт 2 30 2 33 Терабайт Тбайт 1024 Гбайт 2 40 2 43 Петабайт Пбайт 1024 Тбайт 2 50 2 53 Экзабайт Эбайт 1024 Пбайт 2 60 2 63 При переходе от одной единицы измерения к другой используется два про- стых соотношения: 1 байт = 8 бит; 1 Кбайт = 1024 байт. Используя данные, приведенные в табл. 1, можно выполнять перевод из од- них единиц измерения в другие. Например, для перевода величины 100 Мбайт в биты необходимо выполнить следующие преобразования 100Мбайт = 100∙1024∙1024 байт = 100∙1024∙1024∙8бит. Символьный подход чаще всего применяется для оценки емкости памяти за- поминающих устройств, объема файлов или объема передаваемых сообщений. При этом содержание самой информации не учитывается и не принимается во внимание. Пример. Рассчитаем мощность алфавита, с помощью которого записано со- общение, содержащее 8192 символа и занимающее объем 1/256 Мбайт. Исходные данные: k = 8192, H = 1/256 Мбайт. Найти мощность алфавита N. 14 / 17 15 Решение: Мощность алфавита находится по формуле N = 2 I , где I – информационный вес одного символа. Информационный вес символа I связан с общим объемом информации фор- мулой I = H/k. Определяем значение I, соблюдая размерность исходных данных: I = H/k = 1024·1024·8/256·8192=2 10 ·2 10 ·2 3 /2 8 ·2 13 = 2 2 = 4 бит. Определяем N = 2 4 = 16 символов. Ответ: Мощность алфавита составляет 16 символов. 2. Содержательный (вероятностный) подход, в котором учитывается со- держание информации, а точнее – вероятность реализации события. При этом более информативным считается то событие, которое менее вероятно, т. е. менее всего ожидалось. В содержательном подходе для подсчета количества информа- ции I используют формулу Шеннона: 2 log , I P = − (5) где P – вероятность реализации события. Так, при случайном доставании белого шара из коробки, в которой находятся 6 черных и 2 белых шара, количество информации I, соответствующей этому со- бытию, равно 2 2 log 2 / 8 log 4 2 бит. I = − = = Единицей измерения информации, рассчитанной по формуле (5), является бит. 1 бит соответствует ситуации, при которой возможен исход двух равнове- роятных событий, т. е. P = 1/2. Единица измерения «бит», или «bit», получила свое название от английского словосочетания «binary digit» – «двойная цифра». В памяти компьютера на физическом уровне бит представлен одной ячейкой, ко- торая может находиться в одном из двух возможных состояний, первое из кото- рых соответствует единице, второе – нулю. Наряду с формулой (5), в которой используется логарифм по основанию 2, а единицей измерения служит бит, могут применяться другие основания алго- ритма и другие единицы измерения. Десятичному алгоритму соответствует еди- ница измерения дит (за единицу измерения принимается такое количество ин- формации, которое необходимо для исхода десяти равновероятных событий),а натуральному алгоритму – единица измерения нат. Формула (5) предназначена для оценки информативности одиночного собы- тия. Для оценки информативности нескольких событий, имеющих разную веро- ятность, формула Шеннона преобразуется к виду 2 1 log n i i i I P P = =− , (6) где n – количество ожидаемых событий. 15 / 17 16 Формула (6) отражает также величину изменения энтропии, которое соответ- ствует получению информации I. Пример. Определим количество информации, связанное с появлением каж- дого символа в сообщениях, записанных на русском языке при условии: а) появ- ление каждого из 34 символов равновероятно; б) символы в тексте встречаются с разной вероятностью p i (в соответствии с табл. 2). Таблица 2 Вероятность появления символов в текстах на русском языке i Символ p i i Символ p i i Символ p i 1 Пробел 0,175 13 К 0,028 24 Г 0,012 2 0 0,090 14 М 0,026 25 Ч 0,012 3 Е 0,072 15 Д 0,025 26 И 0,010 4 Ё 0,072 16 П 0,023 27 X 0,009 5 А 0,062 17 У 0,021 28 Ж 0,007 6 И 0,062 18 Я 0,018 29 Ю 0,006 7 Т 0,053 19 Ы 0,016 30 Ш 0,006 8 Н 0,053 20 З 0,016 31 Ц 0,004 9 С 0,045 21 Ь 0,014 32 Щ 0,003 10 Р 0,040 22 Ъ 0,014 33 Э 0,003 11 В 0,038 23 Б 0,014 34 Ф 0,002 12 Л 0,035 а) При условии равновероятного появления каждый символ несет информа- цию: 2 2 log log 34 5,09; a I N = = = б) с учетом разной вероятности имеем ( ) 34 2 2 1 1 log log 4,71 4,71. n б i i i i i i I P P P P = = =− = − ⋅ = − − = Округляем в большую сторону для равновероятного случая и получаем 6 бит, a I = а при условии разной вероятности 5 бит. б I = Это значит, что количе- ство информации для каждого символа в тексте на русском языке равно 5 бит, а при упрощенном равновероятном условии – на 1 бит больше. Если события равновероятны и возможное число этих событий равно N, то P = 1/N,и формула Шеннона при этом преобразуется в формулу Хартли, 16 / 17 17 2 2 1 log log I N N = − = (7) Например, при случайном доставании туза пик из колоды, в которой нахо- дится 32 карты, количество информации I, соответствующей этому событию, равно 2 2 log 32 5log 2 5 бит. I = = = Если же в колоде находится не 32, а 36 карт, то расчет по формуле (7) дает результат 2 log 36 5,1 7, I = = который означает, что 5 бит будет недостаточно и полученный результат нужно округлить в сторону большего целого значения, т. е. I = 6 бит. В содержательном подходе учитывается исключительно вероятность реали- зации события и при этом не имеет значения объем информации, необходимый для регистрации события или сообщения. Преобразование и обработка данных На практике для измерения количества информации чаще используется сим- вольный подход, в котором наименьшей единицей измерения является байт. При этом группа байтов выстраивается по тематическому признаку и образует файл. Ф а й л — это совокупность некоторого числа байтов, которая имеет уникаль- ное собственное имя. Обычно в отдельном файле хранят данные одного типа. Файл выступает в виде единицы хранения данных, которая подвергается опера- циям обработки и преобразования. Имя файла складывается из имени, котороеприсваивает пользователь, и расширения файла. Имя, которое присваивает пользователь, может иметь до 256 символов (рус- ских или английских), расширение – 3–4 символа (английских). Расширение файла – последовательность символов, отделяемая от имени точкой и предназначенная для идентификации типа файла. Расширение файла отражает формат файла – правила кодирования данных, которые используются в соответствующих программах. Если говорят, что данные сохраняются в неко- тором формате, то это значит, что имеется программа, которая умеет обрабаты- вать этот формат. Файлы, имеющие одинаковую информацию, могут отличаться форматом представления данных. Например, графические файлы, содержащие одинаковое изображение, в разных графических редакторах имеют разное рас- ширение. Перевод файла из одного представления в другое называется перефор- матированием, или конвертацией. К о н в е р т а ц и я файла – преобразование с видоизменением данных, предна- значенное для перехода к другим условиям обработки. Конвертация выполня- ется с помощью программ, которые называются конверторами. Иногда конвер- тация файла связана с потерей части данных. 17 / 17 18 Сведения о файлах собираются в файловой структуре. Файловая структура построена по табличному принципу. В таблицу зано- сятся имена файлов и данные о размещении файлов. При размещении файлов в качестве наименьшей единицы измерения используют один сектор, размер ко- торого фиксирован (обычно 512 байт). Группа секторов объединяется в кластер, размер которого строго не фиксирован (рис. 4). Каждый кластер имеет адрес, ко- торый используется при обращении к данным. Кластер является наименьшей единицей адресации, а данные об адресах кластеров собираются в таблицах фай- ловой структуры [1]. К л а с т е р – минимальный объем дискового пространства, выделяемый для сохранения файла и состоящий из одного или нескольких смежных секторов. Рис. 4. Структурные элементы диска При сохранении файла его данные записываются в один или несколько по- следовательно расположенных кластеров. После сохранения файла кластеры становятся занятыми, при этом кроме имени файла сохраняются сведения о его размере, дате и времени сохранения, а также адрес первого кластера файла. По- сле каждого преобразования файла его данные перезаписываются на новом ме- сте. Если на диске не хватает свободного неразрывного места для сохранения файла, то возможна фрагментация файла – разделение на части с распределе- нием частей в несмежных кластерах. В процессе хранения данные, которые представлены в файлах, могут быть обработаны и преобразованы. Обработка данных включает в себя набор различ- ных операций, некоторые из них перечислены ниже. 1. Сбор данных– накопление данных с целью получения достоверной ин- формации, достаточной для принятия решения. 1 / 17 19 2. Формализация– приведение данных из разных источников к одинаковой форме с целью сравнения и дальнейшей обработки. 3. Фильтрация– отсеивание избыточных данных или удаление информаци- онного шума с целью повышения достоверности информации. 4. Сортировка– перегруппировка данных и их упорядочение по заданному параметру для удобства пользования и доступности. 5. Архивация– организация хранения данных в компактной и доступной форме для снижения затрат и защиты информации. 6. Защита– включает комплекс мер, направленных на предотвращение ко- пирования, модификации или утраты данных. 7. Транспортировка – передача или прием данных, осуществляемых между отправителем и получателем, в соответствии с принятыми правилами обмена. 8. Преобразование – обработка и переформатирование данных или приве- дение к удобной для практического использования форме. Обработку и преобра- зование данных выполняют с помощью специальных программ, каждая из кото- рых предназначена для выполнения специфического набора операций и пред- ставления обработанных данных в новом формате. 2 / 17 20 Представление числовых данных Окружающая нас информация всегда существует в закодированной форме. Форма кодирования определяется системой, с помощью которой осуществляется представление информации. Известны следующие системы кодирования: − естественные человеческие языки – кодирование понятий с помощью речи; − азбука Морзе – кодирование алфавита последовательностью коротких и длинных сигналов; − система Брайля – кодирование алфавита рельефно-точечным шрифтом (для незрячих и плохо видящих людей). В общем виде можно сказать, что кодирование – это изменение типа данных или переход от одного формата к другому, более подходящему для хранения, передачи или обработки информации. В информатике и вычислительной технике существует своя система кодирования, которая называется двоичным кодирова- нием. Система двоичного кодирования основана на представлении данных через двоичную систему счисления. Системы счисления Система счисления – способ записи чисел с помощью заданного набора специальных символов, которые называются цифрами. Основаниесистемысчисления – количество цифр, используемых для за- писи чисел. Различают позиционные и непозиционные системы счисления. Непозиционнаясистемы счисления– система, в которой символы не ме- няют своего значения при смене их местоположения (позиции) в изображении числа. К непозиционной системе относится римская система, используемые в ней обозначения показаны в табл. 3. Запись чисел в римской системе счисления осу- ществляется по простым правилам: 1) если цифра слева меньше, чем цифра справа, то левая цифра вычитается из правой (IX: 10 – 1 = 9; XС: 100 – 10 = 90); Таблица 3 Непозиционная римская система счисления Римские цифры Значение (обозначаемое количество) Римские цифры Значение (обозначаемое количество) I 1 C 100 V 5 D 500 X 10 M 1000 L 50 3 / 17 21 2) если цифра справа меньше или равна цифре слева, то эти цифры складыва- ются (VII: 5 + 1 + 1 = 7; XXXV: 10 + 10 + 10 + 5 = 35); 3) нельзя записывать подряд 4 одинаковых цифры. Пример записи числа 984 в римской системе счисления: 900 – CM, 80 – LXXX, 4 – IV, отсюда 984 = CMLXXXIV. В математическом аппарате информатики используются десятичная, двоич- ная, восьмеричная и шестнадцатеричная системы счисления (табл. 4). Все эти системы счисления относятся к системам позиционноготипа, в которых вели- чина, обозначаемая цифрой в записи числа, зависит от ее позиции. Таблица 4 Позиционные системы счисления Название системы Основание системы Обозначение Цифры и символы для записи чисел Двоичная 2 Bin 0 1 Восьмеричная 8 Oct 0 1 2 3 4 5 6 7 Десятичная 10 Dec 0 1 2 3 4 5 6 7 8 9 Шестнадцатерич- ная 16 Hex 0 1 2 3 4 5 6 7 8 9 A B С D E F Для перевода чисел из одной системы счисления в другую используют про- стые математические алгоритмы или делают перевод с помощью калькулятора. Использование калькулятора, например, позволяет представить и сравнить число R в разных системах счисления: R = 1234 10 = 10011010010 2 = 2322 8 = 4D2 16 В этой записи подстрочный индекс используется для обозначения основания системы счисления. Общая формула для представления числа R в системе счис- ления с основанием q имеет вид: 0 1 · · k i j q i j i n j R a q a q − = =− = + , (8) где n – количество символов a i с положительными показателями степеней; k – количество символов a j с отрицательными показателями степеней. Формула (8) позволяет представить любое число в развернутой форме записи: 386,15 10 = 3 ⋅10 2 + 8 ⋅10 1 + 6 ⋅10 0 + 1 ⋅10 -1 + 5 ⋅10 –2 , 1111, 01 2 = 1 ⋅2 3 + 1 ⋅2 2 + 1 ⋅2 1 + 1 ⋅2 0 + 1 ⋅2 –2 , 6ВF,A 16 = 6 ⋅16 2 + В ⋅16 1 + F ⋅16 0 + A ⋅16 –1 4 / 17 |