1.4. Структуры данных

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

когда данные упорядочены. Для упорядочивания данных

применяют следующие структуры: линейные (списки), табличные,

иерархические (дерево).

Линейная структура. Линейная структура данных (или список) —

это упорядоченная структура, в которой адрес данного однозначно

определяется его номером (индексом). Примером линейной

структуры может быть список учебной группы или дома, стоящие на

одной улице.

В списках, как правило, новый элемент начинается с новой

строки. Если элементы располагаются в строчку, нужно внести

разделительный знак между элементами. Поиск осуществляется по

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

девять разделителей).

Если элементы списка одной длины, структура называется

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

элемента — d, зная номер элемента — п, его начало определяется

соотношением d (n— 1).

Табличная структура данных. Табличная структура данных — это

упорядоченная структура, в которой адрес данного однозначно

определяется двумя числами — номером строки и номером столбца, на

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

45

Если элементы располагаются в строчку, нужно внести два

разделительных знака — разделительный знак между элементами

строки и разделительный знак между строками.

Поиск, аналогично линейной структуре, осуществляется по

разделителям. Если элементы таблицы одной длины, структура

называется матрицей данных, разделители в ней не требуются. При длине

одного элемента — d, зная номер строки — m и номер столбца n, a

также строк и столбцов М, N, найдем адрес его начала:

d [N(m - 1) + (n - 1)].

Таблица может быть и трехмерная, тогда три числа

характеризуют положение элемента и требуются три типа разделителей, а может

быть и п-мерная.

Иерархическая структура. Нерегулярные данные, которые

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

представлены в иерархической структуре, в которой адрес каждого элемента

определяется путем (маршрутом доступа), идущим от вершины

структуры к данному элементу.

Иерархическую структуру образуют, например, почтовые

адреса (рис. 1.6).

Краснодарский

край

Семикаракорский

район

Ворошиловский

Россия

Ростовская

область

Ставропольский

край

Ростов Красносулинский Белокалитвинский

район район

Большая

Садовая

Буденновский

Рис. 1.6. Пример иерархической структуры данных

Адрес одного из домов, расположенных, к примеру, на улице

Большая Садовая, может выглядеть следующим образом:

Россия\Ростовская область\Ростов\ул. Большая Садовая\д. 1.

46

Линейная и табличная структуры более просты, чем

иерархическая структура, но если в линейной структуре появляется новый

элемент, то упорядоченность сбивается. Например, если в списке

студентов появляется новый человек, то расположенный по алфавиту

список нарушается.

В иерархической структуре введение нового элемента не

нарушает структуры дерева, недостатком ее является трудоемкость

записи адреса и сложность упорядочения.

1.5. Хранение данных

Для устройств обработки данных, к которым относится и

компьютер, большое значение имеет организация метода хранения

информации на внешних носителях, позволяющих сохранять данные

энергонезависимо. Способ хранения данных на таких носителях

должен обеспечивать их целостность, доступность и защищенность. В

настоящее время наиболее популярными внешними носителями

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

которой может измеряться триллионами байтов. В этом случае

эффективный способ хранения особенно важен. Разработчики

программного обеспечения предложили оригинальный способ организации

хранения информации: в виде файлов.

Под файлом понимается именованная область носителя,

содержащая данные произвольной длины и воспринимаемая

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

оно сопоставлено адресу размещения файла на носителе. Носитель

имеет служебную таблицу, в каждой строке которой записано имя

файла и адрес его местонахождения на носителе. Эта таблица

используется специальной программой, которая называется файловой сие-

темой. Для доступа к данным она получает имя файла, находит по

таблице его местоположение на носителе и возвращает содержимое

файла. Как правило, процесс обработки информации сопровождается

ее последующим сохранением. Для этого компьютерная программа

объединяет какой-либо блок обрабатываемых данных в единое

целое, снабжает его именем и передает файловой системе для записи

на внешний носитель.

Имя файла состоит из некоторого набора символов и для боль-

47

шинства файловых систем может содержать до 256 знаков. Имя

файла может быть дополнено расширением, которое определяет тип

информации, хранящейся в файле. Расширение содержит от одного до

трех символов и отделяется от имени точкой. Большинство программ

при создании файла автоматически добавляют к имени свое

уникальное расширение, которое помогает им в дальнейшем опознавать

«свои» файлы. Например, файлы, созданные программой Microsoft

Word, имеют расширение .doc, расширение .xls добавляет программа

Microsoft Excel.

Кроме имени, файловая система, создавая файл, снабжает его

дополнительной информацией: датой и временем создания (или

модификации), размером сохраненных данных, правами доступа к

информации, хранящейся в нем. Эта информация называется

атрибутами файла и предоставляет возможности файловой системе

оперативно работать с файлами.

Файл в числовом виде хранит информацию разных типов,

например, текстовую, звуковую, графическую и т.д. Программа,

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

дальнейшей работе с файлом записанные данные можно было

распознать и правильно извлечь. Способ представления данных в

файле называется форматом файла. Формат определяет внутреннюю

организацию информации, хранимой в файле. Открывая файл,

прикладная программа проверяет его формат. Если он соответствует

распознаваемым ею форматам, информация, хранящаяся в файле,

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

системы автоматически распознают формат файла и самостоятельно

запускают работающую с ним прикладную программу. Имеется

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

этого используется его расширение. Анализируя расширение,

операционная система определяет тип и структуру файла. Многие

форматы файлов стандартизированы и используются соответствующими

программными приложениями, работающими под управлением

различных операционных систем.

Как было уже сказано, задачу централизованного управления

данными решает файловая система. Она выполняет функции

распределения внешней памяти, отображения имен файлов в

соответствующие адреса и обеспечения доступа к данным.

Для удобства работы файлы объединяют в группы, их имена рас-

48

полагают в файле специального вида, называемом каталогом или

папкой. Каталоги образуют иерархическую (древовидную) структуру.

Каталоги, размещенные на вершине иерархии, называются

каталогами первого уровня. Каталоги первого уровня могут содержать

каталоги второго уровня и т.д. Каждый каталог содержит описание

файлов или каталогов следующего уровня иерархии. Так же как и

файлу, каталогу задается имя и атрибуты, позволяющие файловой

системе манипулировать им: создавать, удалять, перемещать,

добавлять в него файлы, каталоги и т.д.

1.6. Математические основы

информатики

Как было отмечено ранее, информатика — прикладная наука,

находящаяся на стыке многих наук. Вместе с тем она опирается на

спектр разделов такой фундаментальной науки, как математика.

Наиболее важное прикладное значение для информатики имеют булева

алгебра, используемая в разработке алгоритмов программ и в

синтезе цифровых устройств, теория множеств и теория графов,

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

1.6.1. Алгебра высказываний (булева алгебра)

Основные понятия

Основное понятие булевой алгебры — выказывание. Под простым

высказыванием понимается повествовательное предложение, о

котором можно сказать, истинно оно или ложно (третьего не дано).

Высказывания обозначаются латинскими буквами и могут принимать

одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА

(обозначим 1). Например, содержание высказывания А: «дважды два равно

четырем» истинно А = 1, а высказывание В: «три больше пяти»

всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать

содержательная часть высказываний, а только их истинность. Два

высказывания А и В называются равносильными, если они имеют

одинаковые значения истинности, записывается А = В.

49

Логические операиии

Сложное высказывание можно построить из простых с помощью

логических операций: отрицания, конъюнкции, дизъюнкции, импликации

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

логических операций. Рассмотрим их подробней.

Операцией отрицания А называют высказывание А (или -А,

говорят не А), которое истинно тогда, когда А ложно, и ложно тогда,

когда А истинно. Например, если событие А состоит в том, что

«завтра будет снег», то А «завтра НЕ будет снега», истинность одного

утверждения автоматически означает ложность второго.

Отрицание — унарная (т.е. для одного операнда) логическая операция. Ей

соответствует языковая конструкция, использующая частицу НЕ.

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

А

0

1

А

1

0

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В

является новое высказывание С, которое истинно только тогда,

когда истинны оба высказывания, записывается С = А л В или С = А & В

(при этом говорят С равно А и В). Примером такой операции может

быть следующая: пусть высказывание А состоит в том, что «высота

шкафа меньше высоты двери», событие В «ширина шкафа меньше

ширины двери», событие С «шкаф можно внести в дверь, если

ширина шкафа меньше ширины двери И высота шкафа меньше

высоты двери», т.е. данная операция применяется, если два

высказывания связываются союзом И.

Таблица истинности этой операции, как следует из определения,

имеет вид

А

0

0

1

1

В

0

1

0

1

А&В

0

0

0

1

50

Дизъюнкцией (логическим сложением) двух высказываний А и В

является новое высказывание С, которое истинно, если истинно хотя

бы одно высказывание. Записывается С = A v В (при этом говорят:

С равно А ИЛИ В). Пример такой операции следующий: пусть

высказывание А состоит в том, что «студент может добираться домой

на автобусе», событие В «студент может добираться домой на

троллейбусе», событие С «студент добрался домой на автобусе ИЛИ

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

связываются союзом ИЛИ.

Таблица истинности такой операции следующая:

А

0

0

1

1

В

0

1

0

1

AvB

0

1

1

1

Импликацией двух высказываний А (А называется посылкой) и В

(В называется заключением) является новое высказывание С,

которое ложно только тогда, когда посылка истинна, а заключение

ложно, записывается С = А —> В (при этом говорят: из А следует В).

Примером такой операции может быть любое рассуждение типа:

если произошло событие А, то произойдет событие В, «если идет

дождь, то на небе тучи». Очевидно, операция не симметрична, т.е.

из В —> А не всегда истинно, в нашем примере «если на небе тучи,

то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

А

0

0

1

1

В

0

1

0

1

А->В

1

1

0

1

Импликация имеет следующие свойства:

А-»В*В -> А

А->А= 1

51

0->А= 1

1 -» А = А

А-» 1 = 1

А-» 0 = А

Эквиваленцией двух высказываний А и В является новое

высказывание С, которое истинно только тогда, когда оба высказывания

имеют одинаковые значения истинности, записывается С = А <-» В

(.С = А = В). Примером такой операции может быть любое

высказывание типа: событие А равносильно событию В.

Таблица истинности:

А

0

0

1

1

В

0

1

0

1

А«->В

1

0

0

1

Эквиваленция имеет следующие свойства:

А <-» В = В <-» А

А<-> В = В <-> А

А*-» 1 =А

А<-»0 = А

Логические Выражения.

ПоряЭок логический операиий

С помощью логических операций из простых высказываний

(логических переменных и констант) можно построить логические

выражения, которые также называются булевскими функциями.

Например, С = (( A v В) -> В) v А.

Чтобы избежать большого количества скобок в булевских

функциях, принято следующее соглашение о старшинстве операций.

Первыми выполняются операции в скобках, затем операции в

следующем порядке: отрицание, конъюнкция и дизъюнкция слева

направо, импликация, эквиваленция.

52

Зависимости межЭу логическими опероииоми

Операции не являются независимыми; одни из них могут быть

выражены через другие. Можно доказать с помощью таблиц

истинности следующие равносильности:

1. А = А закон двойного отрицания

2. А&В = В&А коммутативный закон для конъюнкции

3. AvB = BvA коммутативный закон для дизъюнкции

4. (А & В) & С = А & (В & С) ассоциативный закон для

конъюнкции

5. (AvB)vC = Av(BvC) ассоциативный закон для

дизъюнкции

6. А & (В v С) = (А & В) v (А & С) дистрибутивные законы

7. A v (В & С) = (A v В) & (A v С)

8. А&В = A v В законы де Моргана

9. AvB = А & В

10. А & А = А закон идемпотенции для конъюнкции

11. A v A = А закон идемпотенции для дизъюнкции

12. А & 1 = А закон единицы для конъюнкции

13. А & 0 = 0 закон нуля для конъюнкции

14. A v 1 = 1 закон единицы для дизъюнкции

15. A v 0 = А закон нуля для дизъюнкции

16. A v А = 1 закон исключения третьего

17. А & А = 0 закон противоречия

18. А -> В = A v В

19. А <-» В = (А -> В) & (В -> А) = ( A v В) & ( A v В ) =

= (A&B)v(A & В)

20. A v (А & В) = А законы поглощения

21. А & (A v В) = А

53

22. А&(А vB) = A&B

23. Av (A & В) = Av В

Одну и ту же зависимость между логическими переменными

можно выразить различными формулами. Поэтому важно иметь

возможность приводить формулы с помощью эквивалентных

преобразований к некоторому стандартному виду. Существует несколько

стандартных форм, к которым приводятся логические выражения с

помощью эквивалентных преобразований (формул 1—23).

Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет

вид Al v A2 v ... v An, где каждое из составляющих высказываний

есть конъюнкция простых высказываний и их отрицаний, например:

В = ( А1 & А2 & A3) v (А4 & А5).

Вторая — конъюнктивная нормальная форма (КНФ), имеет вид

А1 л А2 а ... a An, где каждое из составляющих есть

дизъюнкция простых высказываний и их отрицаний, например:

В = ( Al v А2 v A3) & (А4 v А5) & А6.

Табличное и алгебраическое з^Эание

булеВскин срункиий

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

всех наборов значений аргументов. Каждый аргумент может иметь два

значения: 0 и 1, следовательно, п аргументов могут принимать 2П

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

аргумента: X,, Х2, Х3. Общее число наборов 23 = 8; зададим таблицу

истинности функции, указав для каждого набора значение функции.

№

1

2

3

4

5

6

7

8

X,

0

0

0

0

1

1

1

1

х?

0

0

1

1

0

0

1

1

Х3

0

1

0

1

0

1

0

1

F

0

1

0

1

0

1

0

1

54

Для составления алгебраической формы по результатам

таблицы сделаем следующее. В комбинациях, где функция принимает

значение 1, единицу заменим именем функции, а нуль — именем с

отрицанием (т.е. комбинации 0 0 1 поставим в соответствие выражение

Xj &Х2&Х3), все элементы соединим знаками дизъюнкции, для

рассматриваемого примера получим F(X,, Х^ Х3) = (XY &Х2 &X3) v

v (ХХ&Х2&Х3) v (X,&X2&X3) v (Х,&Х2&Х3).

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

заданной таблице истинности. Функция представляет дизъюнктивную

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

дизъюнкций входят все аргументы функции. Такая ДНФ называется

совершенной, а каждая группа дизъюнкций называется коституентой

единицы.

Аналогично, для комбинаций, где функция принимает значение

нуля, можно построить алгебраическую форму F(X,,X2,X3) =

= (X,vX2vX3) & (X,vX^vX3) & (X^vXjVXj) & (XjV^vXj),

которая также удовлетворяет заданной таблице истинности и

представляет собой конъюнктивную нормальную форму, в данном случае

совершенную. Каждая конъюнкция называется конституентой нуля.

В главе 2 будет показано, как, основываясь на булевой алгебре,

создаются цифровые устройства.