Организация данных и операции с ними

Современные ЭВМ работают с большими наборами данных. Рассмотрим, каким образом массивы данных представляются в памяти ЭВМ.

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

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

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

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

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

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

Если данные хранятся в организованной структуре, то каждый элемент приобретает адрес. Адреса - это тоже данные, и их тоже надо хранить и обрабатывать.

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

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

- сбор данных – накопление информации с целью обеспечения достаточной полноты для принятия решений;

- формализация данных – приведение данных, поступающих из разных источников, к одинаковой форме;

- фильтрация данных – отсеивание «лишних данных»;

- сортировка данных – упорядочение данных по заданному признаку;

- архивация данных – организация данных в удобной и легкодоступной форме;

- защита данных – комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

- транспортировка данных – прием и передача данных между удаленными участниками информационного процесса;

- преобразование данных – перевод данных из одной формы в другую.

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

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

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

Рассмотрим, каким образом представляется и преобразуется числовая информация в памяти ЭВМ, для этого введем понятие «система счисления».

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

Все системы счисления делятся на аддитивные (непозиционные) и позиционные.

Аддитивными называются системы счисления, в которых любое число получается путем сложения или вычитания базисных чисел. Примером такой системы является римская система. В римской системе базисными являются числа 1,5,10,50,100,500,1000, которые обозначаются знаками I,V,X,L,C,D,M соответственно. В данной системе значение числового знака не зависит от его расположения в записи числа.

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

Десятичная запись любого числа X в виде последовательности цифр выглядит следующим образом:

X= a_na_n-1 …a₁a₀a_-1…a_-m…                                                                              (3)

Запись произвольного числа в K -ичной позиционной системе счисления основывается на представлении этого числа в виде полинома:

 X= a_n Kⁿ+a _n-1 K^n-1+ …+a₁ K¹+a₀ K⁰+a_-1 K^-1+…a_-m K^-m… (4),

где каждый коэффициент a_i  может быть одним из базисных чисел и изображается одной цифрой.

Число K единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется K -ичной. Например, основанием десятичной системы является число 10; двоичной - число 2 и т.д. 

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

Произвольное число X в двоичной системе представляется в виде полинома:

X= a_n 2ⁿ+a _n-1 2^n-1+ …+a₁ 2¹+a₀ 2⁰+a_-1 2^-1+…a_-m 2^-m… (5),

где каждый коэффициент a_i может быть либо 0, либо 1.

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

Правила сложения и умножения чисел в двоичной форме имеют вид:

0+0=0                                                 0+1=1                              1+1=10.

0 0=0                                               0 1=0                        1 1=1.

Чтобы перевести целое число в двоичный код, необходимо делить его пополам до тех пор, пока частное не будет рано единице. Совокупность остатков от каждого деления, записанная справа налево вместе с последним числом, и образует двоичный аналог десятичного числа (19₁₀=10011₂).

В восьмеричной системе счисления базисными являются числа 0,1,2,3,4,5,6,7. Запись любого числа в этой системе основывается на его разложении по степеням числа 8 с коэффициентами, являющимися базисными числами.

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

В шестнадцатеричной системе счисления базисными являются числа от нуля до 15. Обычно для обозначения первых десяти целых чисел от нуля до 9 используют арабские цифры, а для следующих целых чисел от 10 до 15 используются буквенные обозначения A, B, C, D, E, F.

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