Основные структуры данных

Понятие ДАННЫЕ будет пронизывать весь курс, поэтому необходимо ознакомиться с основными структурами данных: линейная, иерархическая и табличная.

Пример: книга - разобрали на отдельные листы и смешали, набор данных есть, но подобрать адекватный метод получения информации трудно. Если же собрать все листы в правильной последовательности, мы получим простейшую структуру данных – ЛИНЕЙНУЮ. Однако читать придется с самого начала до конца, что не всегда удобно.

Для быстрого поиска требуемой информации применяется ИЕРАРХИЧЕСКАЯ структура. Оглавление – разделы – параграфы и т.д. Элементы структуры более низкого уровня обязательно входят в элементы более высокого уровня.

Теперь представьте, мы связали линейную и иерархическую структуры, то есть связали разделы, главы, параграфы с номерами страниц (содержание). Тем самым, мы создали НАВИГАТОРА, который еще более упростит поиск – ТАБЛИЧНАЯ структура.

Обработка данных

Обработка данных или преобразование данных включает следующие операции:

• сбор данных;

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

• фильтрация данных, уменьшение уровня «шума»;

• сортировка данных, повышение доступности информации;

• архивация данных, организация хранения;

• защита данных;

• транспортировка данных;

• преобразование данных, важнейшая и наиболее дорогая задача информатики, как правило, связанная с изменением носителя.

Способы представления информации и два класса эвм

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

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

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

Представление данных в эвм.

За основу представления данных в ЭВМ, как правило, принята двоичная система счисления. Как и десятичная система счисления, двоичная система (в которой используются лишь цифры 0 или 1) является позиционной системой счисления, т.е. в ней значение каждой цифры числа зависит от положения (позиции) этой цифры в записи числа. Каждой позиции присваивается определенный вес.

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

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

Типы данных

Основными типами данных в вычислительной технике являются: бит, байт и слово. Компьютеры работают в основном с байтами, которые являются основной операционной единицей компьютерных данных. Машинное слово (слово) технический термин, означающий 16 бит или 2 байта одновременно. Двойное слово – 4 байта, расширенное слово – 8 байт.

С тарший бит (15) Бит Младший бит (0)

1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1

Байт Байт

С Л О В О

Для представления данных существует три основных формата:

• двоичный с фиксированной запятой;

• двоичный с плавающей запятой;

• двоично-кодированный десятичный (BCD).

Если надо закодировать целое число со знаком, то старший бит регистра (ячейки памяти) используется для хранения знака (0 при положительном знаке числа и 1 при отрицательном) – формат с фиксированной запятой.

Знак числа 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1

Цифры числа

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

3,1415926 = 0,31415926 * 10¹

500 000 = 0,5 * 10⁶

123 456 789 = 0,1 * 10¹⁰

Первая часть числа называется мантиссой - М, а вторая – порядком q

Для того чтобы оперировать дробными числами или числами очень большой длины, используется понятие плавающей запятой. Плавающая запятая действует по принципу экспоненциального формата – числа вида ^­­­­ ­_-⁺M *q^+p

15 14 13 8 7 0

Знак числа (мантиссы)

Знак порядка Модуль Модуль

мантиссы порядка

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

Для реализации скоростных вычислений с плавающей запятой применяются числовые сопроцессоры (FPU – floating point unit). Данные в нем хранятся в 80-ти разрядных регистрах.

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

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

15 12 11 8 7 4 3 0

Код операции Адрес 1-го Адрес 2-го Адрес

операнда операнда результата

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

Выводы

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

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

Информация не может существовать вне взаимодействия объектов и она не теряется ни одним из них в процессе взаимодействия.

Информация устраняет неопределенность, уменьшает хаос и энтропию системы.

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

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