Зачем структурировать информацию?
Давайте сравним четыре сообщения.
Первое:
«Для того чтобы добраться из Москвы до села Васино, нужно сначала долететь на самолёте до города Ивановска. Затем на электричке доехать до Ореховска. Там на пароме переправиться через реку Слоновую в посёлок Ольховка, и оттуда ехать в село Васино на попутной машине».
Второе:
«Как ехать в Васино:
1.На самолёте из Москвы до г. Ивановска.
2.На электричке из г. Ивановска до г. Ореховска.
3.На пароме из г. Ивановска через р. Слоновую в пос. Ольховка.
4.На попутной машине из пос. Ольховка до с. Васино».Информация и информационные процессы
Третье:
Откуда |
Куда |
Транспорт |
Москва |
г. Ивановск |
Самолёт |
г. Ивановск |
г. Ореховск |
Электричка |
г. Ореховск |
пос. Ольховка |
Паром (р. Слоновая) |
пос. Ольховка |
с. Васино |
Попутная машина |
Четвёртое (рис. 1.7):
Рис. 1.7
Можно считать, что все эти {такие разные по форме!) сообщения содержат одну и ту же информацию. Какие из них проще воспринимать? Очевидно, что человеку *вытащить» полезную информацию из сплошного текста (первое сообщение) сложнее всего. Во втором случае мы сразу видим все этапы поездки и понимаем, в каком порядке они следуют друг за другом. Третье сообщение (таблицу) и четвёртое (схему) можно понять сразу, с первого взгляда. Второй, третий и четвёртый варианты воспринимаются лучше и быстрее первого, потому что в них выделена структура информации, в которой самое главное — этапы поездки в Васино.
Зачем книгу разбивают на главы и разделы, а не пишут сплошной текст? Зачем в тексте выделяют абзацы? Прежде всего для того, чтобы подчеркнуть основные мысли, — каждая глава, раздел, абзац содержат определённую идею. Благодаря особенностям человеческого восприятия, при таком выделении структуры улучшается передача информации от автора к читателю.
При автоматической (компьютерной) обработке правильно выбранная структура данных облегчает доступ к ним, позволяет быстро найти нужные данные.
Средства, облегчающие поиск информации, знакомы вам по работе с книгами. Самый простой (но очень утомительный!) способ найти в книге то, что нужно, — перелистывать страницу за страницей. Однако в большинстве книг есть оглавление, котороепозволяет сразу найти нужный раздел, и это значительно ускоряет поиск.
В словарях слова всегда расставлены в алфавитном порядке (представьте себе, что было бы, если бы они были расположены произвольно!). Поэтому, открыв словарь в любом месте, мы можем сразу определить, куда дальше листать страницы для поиска нужного слова — вперёд или назад.В больших книгах использется указатели (индексы) (рис. 1.8) — основных терминов с указанием страниц, на которых они встречаются.Оглавление:
1. Информация
2.Виды информ
3.Информация
4.Измерение информаци
1.Что такое бит? . . . .
2.Байт и другие единицы
Словарь:
автомат — automaton |
Д |
|
автор — author |
аксиома 45 |
|
адрес — address |
ал |
Оритм 30, 78 |
алгебра — algebra |
архиватор 125 |
|
алгоритм — algorithm |
Б |
|
архив — archive |
би- |
5,15.25,43 |
архитектура — architecture |
бр |
андмауэр 112 |
асимметрия — asymmetry |
бр, |
эуэер 322 |
Процесс |
|
|
|
|
|
|
|
у |
зтроиства |
|
|
||
|
|
|
|
|||
|
ь |
|
|
|
||
Рис. 1.9
Линейный список состоит из конечного числа элементов, которые должны быть расположены в строго определённом порядке. В отличие от множества элементы в списке могут повторяться. Список обычно упорядочен (отсортирован) по какому-то правилу, например по алфавиту, по важности, по последовательности действий и т. д. В тексте он часто оформляется как нумерованный список, например:
3.надеть носки;
4.надеть ботинки;
5.выйти из дома.
Переставить местами элементы такого списка нельзя (это будет уже другой список). Список можно задать перечислением элементов, с первого до последнего:
(надеть носки, надеть ботинки, выйти из дома),
■"а также представить в виде цепочки связанных элементов (рис. 1.10).
Надеть |
— |
Надеть ботинки |
— |
Выйти |
Рис. 1.10
Ещё одна знакомая вам структура — таблица. С помощью таблиц устанавливается связь между несколькими элементами. Например, в табл. 1.2 элементы в каждой строке связаны между собой — это свойства некоторого объекта (человека).
Таблица 1.2
Фамилия |
Имя |
Рост, см |
Вес, кг |
Год рождения |
Иванов |
Иван |
175 |
67 |
1996 |
Петров |
Пётр |
164 |
70 |
1998 |
Сидоров |
Сидор |
168 |
63 |
2000 |
Именно так хранится информация в базах данных: строка таблицы, содержащая информацию об одном объекте, называется записью, а столбец {название свойства) — полем.
Возможен и другой вариант таблицы, когда роли строк и столбцов меняются. В первом столбце записываются названия свойств, а данные в каждом из следующих столбцов описывают свойства какого-то объекта. Например, табл. 1.3 содержит характеристики разных марок автомашин.
Таблица 1.3
Марка |
Лада Приора |
Лада Калина |
ВАЗ 2110 |
ВАЗ 21099 |
Мощность двигателя, л. с. |
98 |
89 |
79 |
70 |
скорость, км/ч |
183 |
165 |
165 |
156 |
Время разгона до 100 км/ч, с |
11,5 |
12,5 |
14 |
15 |
Иерархия (дерево)
Линейных списков и таблиц иногда недостаточно для того, чтобы представить все связи между элементами. Например, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 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
|
А |
в |
с |
D |
А |
0 |
1 |
1 |
0 |
В |
1 |
0 |
1 |
1 |
С |
1 |
1 |
1 |
1 |
D |
0 |
1 |
1 |
0 |
Рис. 1.17
Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (серые клетки в таблице).
На пересечении строки С и столбца С стоит единица, которая говорит о том, что в графе есть петля — ребро, которое начинается и заканчивается в одной и той же вершине.
Можно поступить иначе: для каждой вершины перечислить все вершины, с которыми связана данная вершила. В этом случае мы получим список смежности. Для рассмотренного графа список смежности выглядит так:
(А (В, С), В (А, С, О), С (А, В, С, D), D (В, С))
Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 1.16, б), но матрица смежности и список смежности не дают никакой информации о том, как именно следует располагать узлы друг относительно друга. Для таблицы на рис. 1.17 возможны, например, варианты, показанные на рис. 1.18.
Информация и информационные процессы
В рассмотренном примере все вершины связаны, т. е. между любой парой вершин существует путь — последовательность рёбер, по которым можно перейти из одного узла в другой. Такой граф называется Связный граф — это граф, между любыми вершинами которого существует путь.Теперь представьте себе, что дороги Васюки — Солнцево, Ва-сюки — Грибное и Грибное — Ягодное завалило снегом (или размыло дождём) так, что по ним не пройти и не проехать (рис. 1.19). ■* Ягодно!
Схему на рис. 1.19, а тоже можно считать графом (она подходит под определение), но в таком графе есть две несвязанные части, каждая из которых — связный граф. Такие части называют компонентами связности.
Вспоминая материал предыдущего пункта, можно сделать вывод, что дерево — это частный случай связного графа. Но у дерева есть одно важное свойство — в нём нет замкнутых путей (циклов). Граф на рис. 1.17 не является деревом, потому что в нём есть циклы: АВСА, BCDB, ABDCA.
Дерево — это связный граф, в котором нет циклов.
Если в первом примере с дорогами нас интересуют ещё и расстояния между поселками, каждой связи нужно сопоставить число (вес) (рис. 1.20).
Ягодный Рис. 1.20
Такой граф называется взвешенным, поскольку каждое ребро имеет свой вес. Весом может быть не только расстояние, но и, например, стоимость проезда или другая величина.
|
А |
В |
С |
D |
А |
|
12 |
8 |
|
В |
12 |
|
5 |
6 |
С |
8 |
5 |
2 |
4 |
D |
|
6 |
4 |
|
Рис. 1.21
Так же как и матрица смежности, весовая матрица симметрична относительно главной диагонали. Нижняя ячейка в столбце А и верхняя в столбце D говорят о том, что между вершинами А и D нет ребра.
Если в графе немного вершин, весовая матрица позволяет легко определить наилучший маршрут из одной вершины в другую простым перебором вариантов. Рассмотрим граф, заданный весовой матрицей на рис. 1.22 (числа определяют стоимость поездки между соседними пунктами).
|
А |
В |
С |
D |
Е |
,1 |
|
|
3 |
1 |
|
в |
|
|
4 |
5 |
1 |
с |
3 |
4 |
|
|
2 |
D |
1 |
5 |
|
|
1 |
Е |
|
1 |
2 |
1 |
|
Таким образом, оптимальный (наилучший) маршрут — ADEB, его стоимость — 3. Маршрут ADEC, не дошедший до вершины В, далее проверять не нужно, он не улучшит результат.
Конечно, для более сложных графов метод перебора работает очень долго, поэтому используются более совершенные (но более сложные) методы, о которых мы поговорим в 11 классе.
Наверное, вы заметили, что при изображении деревьев, которые описывают иерархию (подчинение), мы ставили стрелки от верхних уровней к нижним. Это означает, что для каждого ребра указывается направление, и двигаться можно только по стрелкам, но не наоборот. Такой граф называется ориентированным (или коротко орграфом). Он может служить, например, моделью системы дорог с односторонним движением. Матрица смежности и весовая матрица для орграфа уже не обязательно будут симметричными.
На схеме на рис. 1.27 всего две дороги с двусторонним движением, по остальным можно ехать только в одну сторону.
Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.
|
А |
В |
С |
D |
А |
|
12 |
8 |
|
В |
12 |
|
5 |
6 |
С |
|
|
|
4 |
D |
|
|
4 |
|
Рис. 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.Постройте графы,