Структура информации

Зачем структурировать информацию?

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

Первое:

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

Второе:

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

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

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

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

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

Третье:

 

​

 

 

 

 

 

 

 

 

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

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

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

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

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

Оглавление:

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

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

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

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

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

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

Словарь:

 

 

​

​

​

​

​

​

​

​

 

Структурирование – это выделение важных элементов в информационных сообщениях и установление связей между ними.

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

 

 

 

 

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

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

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

Потомок ка-

перейти по стрелкам iKoro-то узла — это [й узел.

 

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

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

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

 

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

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

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

7.Псовые

8.Енотовые

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

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

11.Кошачьи

12.Гиеновые

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

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

| Доходы.doc | ]Расходы.(хН|     Отдых.txt   11    IIana.jpg Мама.р

 Документы £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 или 0, а в ра. Если связи между двумя вершинами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти ком­пьютера записывать в неё условный код, например —1. Такая таб­лица называется весовой матрицей, потому что содержит веса рёбер. В данном случае она выглядит, как показано на рис. 1.21.

 

​

 

​

​

​

 

Рис. 1.21

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

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

 

​

​

​

​

​

​

​

 

 

Найдём наилучший путь из А в В — такой, при котором об­щая стоимость поездки мини­мальная. Сначала видим, что из пункта А напрямую в В ехать нельзя, а можно ехать только в С и D. Изобразим это на схеме (рис. 1.23).Числа около рёбер показы­вают стоимость поездки по это­му участку, а индексы у назва­ний вершин показывают общую стоимость проезда в данную вершину из вершины А.Теперь разберём варианты дальнейшего движения из вер­шины С (вершину А уже не нужно рассматривать, так как мы из неё пришли) (рис. 1.24).Видим, что из С сразу мож­но попасть в В, стоимость про­езда в этом случае равна 7. Но, возможно, это не самый луч­ший вариант, и нужно прове­рить ещё путь через вершину Е. Действительно, оказывается, что можно сократить стоимость до 6 (рис. 1.25).Исследовать дальше маршрут, содержащий цепочку ACED, нет смысла, потому что его стоимость явно будет больше 6. Аналогично строим вторую часть схемы (вы догадались, что схе­ма представляет собой дерево!) (рис. 1.26).

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

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

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

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

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

 

 

 

 

​

 

Рис. 1.27

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

Рис. 1.28

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

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

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

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

​