Давайте сравним четыре сообщения.

Первое:

«Для того чтобы добраться из Москвы до села Васино, нужно сначала долететь на самолёте до города Ивановска. Затем на элек­тричке доехать до Ореховска. Там на пароме переправиться через реку Слоновую в посёлок Ольховка, и оттуда ехать в село Васино на попутной машине».

Второе:

«Как ехать в Васино:

1.На самолёте из Москвы до г. Ивановска.

2.На электричке из г. Ивановска до г. Ореховска.

3.На пароме из г. Ивановска через р. Слоновую в пос. Ольховка.

4.На попутной машине из пос. Ольховка до с. Васино».Информация и информационные процессы

Третье:

Четвёртое (рис. 1.7):

Рис. 1.7

Можно считать, что все эти {такие разные по форме!) сообще­ния содержат одну и ту же информацию. Какие из них проще воспринимать? Очевидно, что человеку *вытащить» полезную ин­формацию из сплошного текста (первое сообщение) сложнее всего. Во втором случае мы сразу видим все этапы поездки и понимаем, в каком порядке они следуют друг за другом. Третье сообщение (таблицу) и четвёртое (схему) можно понять сразу, с первого взгляда. Второй, третий и четвёртый варианты воспринимаются лучше и быстрее первого, потому что в них выделена структура информации, в которой самое главное — этапы поездки в Васино.

Зачем книгу разбивают на главы и разделы, а не пишут сплошной текст? Зачем в тексте выделяют абзацы? Прежде всего для того, чтобы подчеркнуть основные мысли, — каждая глава, раздел, абзац содержат определённую идею. Благодаря особеннос­тям человеческого восприятия, при таком выделении структуры улучшается передача информации от автора к читателю.

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

Средства, облегчающие поиск информации, знакомы вам по работе с книгами. Самый простой (но очень утомительный!) спо­соб найти в книге то, что нужно, — перелистывать страницу за страницей. Однако в большинстве книг есть оглавление, котороепозволяет сразу найти нужный раздел, и это значительно ускоряет поиск.

В словарях слова всегда расставлены в алфавитном порядке (представьте себе, что было бы, если бы они были расположены произвольно!). Поэтому, открыв словарь в любом месте, мы мо­жем сразу определить, куда дальше листать страницы для поиска нужного слова — вперёд или назад.В больших книгах использется указатели (индексы) (рис. 1.8) — основных терминов с указанием страниц, на которых они встречаются.Оглавление:

1. Информация

2.Виды информ

3.Информация

4.Измерение информаци

1.Что такое бит? . . . .

2.Байт и другие единицы 

Словарь:

Рис. 1.9

Линейный список состоит из конечного числа элементов, ко­торые должны быть расположены в строго определённом порядке. В отличие от множества элементы в списке могут повторяться. Список обычно упорядочен (отсортирован) по какому-то правилу, например по алфавиту, по важности, по последовательности дей­ствий и т. д. В тексте он часто оформляется как нумерованный список, например:

3.надеть носки;

4.надеть ботинки;

5.выйти из дома.

Переставить местами элементы такого списка нельзя (это бу­дет уже другой список). Список можно задать перечислением эле­ментов, с первого до последнего:

(надеть носки, надеть ботинки, выйти из дома),

■"а   также   представить   в   виде   цепочки   связанных   элементов (рис. 1.10).

Рис. 1.10

Ещё одна знакомая вам структура — таблица. С помощью таблиц устанавливается связь между несколькими элементами. Например, в табл. 1.2 элементы в каждой строке связаны между собой — это свойства некоторого объекта (человека).

Таблица 1.2

Именно так хранится информация в базах данных: строка таблицы, содержащая информацию об одном объекте, называется записью, а столбец {название свойства) — полем.

Возможен и другой вариант таблицы, когда роли строк и столбцов меняются. В первом столбце записываются названия свойств, а данные в каждом из следующих столбцов описывают свойства какого-то объекта. Например, табл. 1.3 содержит харак­теристики разных марок автомашин.

Таблица 1.3

Иерархия (дерево)

Линейных списков и таблиц иногда недостаточно для того, чтобы представить все связи между элементами. Например, в не­которой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 1.11, а).

Такая структура, в которой одни элементы «подчиняются» другим, называется иерархией (от древнегреческого lEpap^va — священное правление). В информатике иерархическую структуру называют деревом.. Дело в том, что, если перевернуть схему на рис, 1.11 вверх ногами, она становится похожа на дерево (точнее, на куст, см. рис. 1.11, б).Уровень 3--[Петров] | Иванов]) Фомин] [Алексеева || Сидорова |   Корен:

б

Рис. 1.11Дерево состоит из узлов и связей между ними (они называют­ся дугами). Самый первый узел, расположенный на верхнем уров­не (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — проме­жуточные.

Из двух связанных узлов тот, который находится на более вы­соком уровне, называется родителем, а другой — сыном. Ко­рень — это единственный узел, у которого нет родителя; у листь­ев нет сыновей.

Используются также понятия предок и пото] кого-то узла — это узел, в который мож от  узла-предка.   Соответственно,   предок узел, из которого можно перейти по стрелка

В дереве на рис. 1.12 родитель узла Е — это узел В, а предки узла Е — это узлы А к В, для которых узел Е — потомок. Потом­ками узла А (корня) являются все остальные узлы.

Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). На­пример, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 1.13).

Конечно, на рис. 1.13 показаны не все семейства, остальные обозначены многоточиями.

В текстах иерархию часто представляют в виде многоуровне­вого списка. Например, оглавление книги о хищниках может выглядеть так:

Глава 1. Псообразные

7.Псовые

8.Енотовые

9.МедвежьиИнформация и информационные процессы

Глава 2. Кошкоообразные

11.Кошачьи

12.Гиеновые

13.Мангустовые

Работая с файлами и папками, мы тоже встречаемся с иерар­хией: классическая файловая система имеет древовидную струк­туру¹. Вход в папку — это переход на следующий (более низкий) уровень иерархии (рис. 1.14).

 Документы £3 Тексты

Доходы.doc Расход bi.odt Отдых, txt ^ Фотографии

IIana.jpg Мама-png

Алгоритм вычисления арифметического выражения тоже мо­жет быть представлен в виде дерева (рис. 1.15). (а + 3) * 5 - 2 * Ь

В современных файловых лежать* нескольким ката структура, строго говоря,

 мах (NTFS, ext3) файл  одновременно. При этом древовидная

Здесь листья — это числа и переменные, тогда как корень и промежуточные вершины — знаки операций. Вычисления идут «снизу вверх», от листьев — к корню. Показанное дерево можно записать так:

(-(*(+(а, 3), 5),* (2, ft)))

Самое интересное, что скобки здесь необязательны; если их убрать, то выражение всё равно может быть однозначно вычислено

Такая запись, которая называется префикс (операция за­писывается перед данными), просматривается с конца. Как толь­ко встретится знак операции, эта операция выполняется с двумя значениями, записанными справа. В рассмотренном выражении сначала выполняется умножение:

a Z Ъ  (2*Ь)

- *  (а+3) 5 <2

- (о + 3) * 5 (2 * Ь) и наконец, вычитание:

(а + 3) * 5 - (2 * Ь)

Для получения префиксной записи мы обходили все узлы де­рева в порядке «корень — левое поддерево — правое поддерево». Действительно, сначала записана метка корня («-»), затем все метки левого поддерева, а затем — все метки правого поддерева. Для поддеревьев используется тот же порядок обхода. Если же

Информация и информационные процессы

обойти дерево в порядке «левое поддерево — правое поддерево — корень», получается постфиксная форма (операция после дан­ных). Например, рассмотренное выше выражение может быть за­писано в виде

Для вычисления такого выражения скобки также не нужны,  ень удобно для автоматических расчётов. Когда програм­ рирования высокого уровня  переводится в  ваются в бесскобоч­ сляются. Постфикс-

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

Графы

Подумайте, как можно структурировать такую информацию:

«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным и между Гриб­ным и Ягодным также есть дороги. Кроме того, есть дорога, кото­рая идет из Грибного в лес и возвращается обратно в Грибное».Можно, например, нарисовать i рисунке 1.16, б населённые пункты тинскими буквами.

му дорог (рис. 1.16, а). На

я краткости обозначены на

Солнцевом

Ягодн.Рис. 1.16

Для исследования таких схем используют графы. Граф — это набор вершин и связей между ними (рёбер).

Для хранения информации о вершинах и связях графа, соот­ветствующего схеме на рис. 1.16, можно использовать таблицу (матрицу), показанную на рис. 1.1

Рис. 1.17

Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (серые клетки в таблице).

На пересечении строки С и столбца С стоит единица, которая говорит о том, что в графе есть петля — ребро, которое начинает­ся и заканчивается в одной и той же вершине.

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

(А (В, С), В (А, С, О), С (А, В, С, D), D (В, С))

Строго говоря, граф — это математический объект, а не рису­нок. Конечно, его можно нарисовать на плоскости (например, как на рис. 1.16, б), но матрица смежности и список смежности не дают никакой информации о том, как именно следует распола­гать узлы друг относительно друга. Для таблицы на рис. 1.17 воз­можны, например, варианты, показанные на рис. 1.18.

Информация и информационные процессы

В рассмотренном примере все вершины связаны, т. е. между любой парой вершин существует путь — последовательность рёбер, по которым можно перейти из одного узла в другой. Такой граф называется Связный граф — это граф, между любыми вершинами которого существует путь.Теперь представьте себе, что дороги Васюки — Солнцево, Ва-сюки — Грибное и Грибное — Ягодное завалило снегом (или раз­мыло дождём) так, что по ним не пройти и не проехать (рис. 1.19). ■*    Ягодно!
Схему на рис. 1.19, а тоже можно считать графом (она подхо­дит под определение), но в таком графе есть две несвязанные час­ти, каждая из которых — связный граф. Такие части называют компонентами связности.

Вспоминая материал предыдущего пункта, можно сделать вы­вод, что дерево — это частный случай связного графа. Но у дерева есть одно важное свойство — в нём нет замкнутых путей (цик­лов). Граф на рис. 1.17 не является деревом, потому что в нём есть циклы: АВСА, BCDB, ABDCA.

Дерево — это связный граф, в котором нет циклов.
Если в первом примере с дорогами нас интересуют ещё и рас­стояния между поселками, каждой связи нужно сопоставить чис­ло (вес) (рис. 1.20).

Ягодный Рис. 1.20

Такой граф называется взвешенным, поскольку каждое ребро имеет свой вес. Весом может быть не только расстояние, но и, на­пример, стоимость проезда или другая величина.

Рис. 1.21

Так же как и матрица смежности, весовая матрица симмет­рична относительно главной диагонали. Нижняя ячейка в столб­це А и верхняя в столбце D говорят о том, что между вершинами А и D нет ребра.

Если в графе немного вершин, весовая матрица позволяет лег­ко определить наилучший маршрут из одной вершины в другую простым перебором вариантов. Рассмотрим граф, заданный весо­вой матрицей на рис. 1.22 (числа определяют стоимость поездки между соседними пунктами).

Таким образом, оптимальный (наилучший) маршрут — ADEB, его стоимость — 3. Маршрут ADEC, не дошедший до вершины В, далее проверять не нужно, он не улучшит резуль­тат.

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

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

На схеме на рис. 1.27 всего две дороги с двусторонним движе­нием, по остальным можно ехать только в одну сторону.

Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.

Рис. 1.27

Рассмотрим следующую задачу: определить количество воз­можных путей из вершины А в вершину К для ориентированного графа, показанного на рис. 1.

Рис. 1.28

Так как граф ориентированный, переходить в другую верши­ну можно только по стрелкам.

Будем двигаться по стрелкам от начальной вершины А. Около каждой вершины запишем количество возможных путей из вер­шины А в эту вершину. Найдём все вершины, в которые можно попасть только из А: это вершины Б и Г, записываем около них количество путей 1 (рис. 1.29).

Теперь ищем вершины, в которые можно попасть только из уже отмеченных вершин. Например, в вершину В есть один путь из А напрямую, а также по одному пути через Б и Г (так как эти вершины отмечены числом 1). Общее количество путей из А в В

В вершину Д идёт один путь через Б и три пути через В, поэто­му общее число путей — четыре. Аналогично получаем четыре пути в вершину Е: три пути через В и один — через Ж (рис. 1.31).Далее находим один путь из А в И (только через Ж) и четыре пути из А в 3 (все через Д). В конечную вершину К можно по­пасть через вершины Д (четыре пути), 3 (четыре пути), Е (четыре пути) и И (один путь), таким образом, общее количество различ­ных путей   равно 13 (рис. 1.32).

Вопросы и задания

1)Что такое структурирование информации? Зачем оно нужно?

2)     Что  такое  алфавитный   порядок?   Как   поступают,  если  начЕной информации. Чем эти средства отличаютс. щать множество? Что такое пус

1)Приведите примеры множеств.

2)Чем отличаются множество и линейный список?

3)Что такое матрица?

8- Как можно записать табличные данные в виде списка? 9. Что такое иерархия? Приведите примеры.

3)Вспомните известные вам классификации, которые вы изучали на
других предметах.

4)Как называется иерархическая структура в информатике?

5)Что такое корень, лист, родитель, сын, предок, потомок в структуре
«дерево»?

6)В дереве 4 потомка, и все они являются листьями. Нарисуйте это де­
рево. Сколько в нём вершин?

7)В чём разница между понятиями «ребро» и «дуга»?

8)В чём различие понятий «дерево», *граф»?

9)Какой граф называется связным?

10)Что такое компонента связности?

11)Что такое петля?  Как по матрице смежности определить, есть ля
петли в графе?

12)Что такое орграф? Когда для представления данных используются
орграфы? Приведите примеры.

1.Выберите наиболее подходящий способ структурирования информа­
ции для хранения:

а) данных о крупнейших озерах мира;

в)  схемы железных дорог;

г)  схемы размещения файлов на флэш-диске.
Подготовьте сообщение

а)  «Как вычисляются арифметические выражения?»

б)   «Постфиксная и инфиксная формы записи выражений»

в)  «Графы в практических задачах»

г)   «Диаграммы связей (mind maps)»

д)  «Системы классификации книг (ДКД, УДК)»

Задачи

1.Определите выражения, соответствующие каждому из деревьев, в «нормальном» виде со скобками (эту форму называют инфиксной — операция записывается между данными). Постройте для каждого из них постфиксную форму.

а)(a+b)4c+2*d)

б)(2*a-3*d)*c+2*ft

соответствующие  следующим  арифметическим ите эти выражения в префиксной и постфик-

в)(a+b+2*c)*d

г)3*a-(2*b+c)*d
Информация и информационные процессы

. Вычислите выражения, записанные в постфиксной форме:
а)126+73-1-12

6)1210-57+*7-2

в)   56789+52-4+1-

г)   54321

Запишите каждое из них в инфиксной и в префиксной формах и по­стройте соответствующее дерево. Единственно ли такое дерево? В этом дереве назовите корень, листья и промежуточные вершины.

2.Нарисуйте граф, в котором 5 вершин и три компоненты связности.
Постройте его матрицу смежности.

3.Структурируйте    следующую    информацию    разными    способами:
«Между посёлками Верхний и Нижний есть просёлочная дорога дли­
ной 10 км. Село Сергееве соединяется двумя асфальтовыми шоссе с
Нижним (22 км) и Верхним (16 км). В село Солнечное можно до-
ехать только из Сергеева по грунтовой дороге (5 км)». Можно ли
сказать точно, как расположены эти пункты?

4.Для графа, полученного в предыдущей задаче, постройте матрицу

5.Постройте графы,

В главу