Структура информации. Деревья. Графы

Содержание

Слайд 2

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

Для того чтобы добраться из Москвы до села Васино, нужно сначала

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

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

Слайд 3

1. Линейный список

Как доехать до села Васино:
На самолете из Москвы до г.

1. Линейный список Как доехать до села Васино: На самолете из Москвы
Ивановска.
На электричке из г. Ивановска до г. Ореховска.
На пароме через реку Слоновую в пос. Ольховка.
На попутной машине из пос. Ольховка до с. Васино.

2. Таблица

Слайд 4

3. Схема (рисунок)

3. Схема (рисунок)

Слайд 5

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

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

Цель — облегчение восприятия и поиска информации.

Слайд 6

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

Иерархия (дерево) - одни элементы подчиняются другим

Структуры данных. Иерархия (дерево) - одни элементы подчиняются другим

Слайд 7

Иерархия – файловая система

Иерархия – семейное дерево

Иерархия – файловая система Иерархия – семейное дерево

Слайд 8

Что такое дерево?

Дерево (tree) — это структура, отражающая иерархию (отношения подчинённости, многоуровневые

Что такое дерево? Дерево (tree) — это структура, отражающая иерархию (отношения подчинённости, многоуровневые связи).
связи).

Слайд 9

Дерево состоит из узлов и связей между ними (они называются дугами).
Самый первый узел,

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

узел

дуга

Слайд 10

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

Из двух связанных узлов тот, который находится на более высоком уровне, называется
родителем, а другой – сыном. 
Корень – это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия «предок» и «потомок».
Потомок какого-то узла – это узел, в который можно перейти по стрелкам от узла-предка
Соответственно, предок (parent) какого-то узла – это узел, из которого можно перейти по стрелкам в данный узел.

Слайд 11

«Сыновья» А: B, C.

«Родитель» B: A.

«Потомки» А: B, C, D, E, F,

«Сыновья» А: B, C. «Родитель» B: A. «Потомки» А: B, C, D,
G.

«Предки» F: A, C.

Корень (root) – узел, не имеющий предков (A).

Лист – узел, не имеющий потомков (D, E, F, G).

Высота дерева – это наибольшее расстояние (количество дуг) от корня до листа.
Высота дерева, приведённого на рисунке равна 2.

Слайд 12

Дерево – это такая структура данных, которая представляет собой древовидную структуру в

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

Слайд 13

Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит

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

A – корень дерева
В – корень левого поддерева
С – корень правого поддерева

Способ представления бинарного дерева:

Слайд 14

Деревья широко применяются в следующих задачах:

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

Деревья широко применяются в следующих задачах: поиск в большом массиве неменяющихся данных
арифметических выражений
оптимальное сжатие данных (метод Хаффмана)

Слайд 15

Перечислим важные свойства дерева, показанного на рисунке:
слева от узла – узлы с

Перечислим важные свойства дерева, показанного на рисунке: слева от узла – узлы
меньшими или равными ключами
справа от узла – узлы с большими или равными ключами

Дерево, обладающее такими свойствами, называется бинарным (двоичным) деревом поиска.

Слайд 16

6

1

3

4

7

9

8

Узел дерева

слева от узла значение меньше

справа от узла значение больше

значение больше

значение больше

значение

6 1 3 4 7 9 8 Узел дерева слева от узла
меньше

значение меньше

Слайд 17

Что такое граф?

Граф — это набор узлов (вершин) и связей между ними

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

Слайд 18

петля

Матрица смежности:

Список смежности:

( A(B, C), B(A, C, D), C(A, B, С, D),

петля Матрица смежности: Список смежности: ( A(B, C), B(A, C, D), C(A,
D(B, C) )

Слайд 19

Единица на пересечении строки А и столбца В означает, что между узлами

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

петля

Матрица смежности:

Слайд 20

Строго говоря, граф — это математический объект, а не рисунок.
Его можно нарисовать

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

Слайд 21

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

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

Слайд 22

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

Если для каждого ребра указано направление, то такой граф называют ориентированным. Его
рёбра называют дугами, а матрица смежности не всегда симметричная. Единица, стоящая на пересечении строки А и столбца В, говорит о том, что существует дуга из вершины А в вершину В

Матрица смежности:

Слайд 23

Часто с каждым ребром связывают некоторое число — вес ребра. Это может

Часто с каждым ребром связывают некоторое число — вес ребра. Это может
быть, например, расстояние между городами или стоимость проезда. Такой граф называется взвешенным.
Информация о взвешенном графе хранится в виде весовой матрицы, содержащей веса рёбер.

Весовая матрица :

вес ребра

Слайд 24

У взвешенного ориентированного графа весовая матрица может быть несимметрична относительно главной диагонали

Весовая

У взвешенного ориентированного графа весовая матрица может быть несимметрична относительно главной диагонали Весовая матрица :
матрица :

Слайд 25

Задание 1. Постройте матрицу смежности

Задание 1. Постройте матрицу смежности

Слайд 26

Задание 2. Постройте граф, как он и его матрица называются?

Задание 2. Постройте граф, как он и его матрица называются?

Слайд 27

Домашнее задание

Задание 1. Постройте матрицы смежности или весовые матрицы для каждого графа:

Домашнее задание Задание 1. Постройте матрицы смежности или весовые матрицы для каждого графа:

Слайд 28

Задание 2. Постройте граф, соответствующий матрице смежности

Задание 2. Постройте граф, соответствующий матрице смежности
Имя файла: Структура-информации.-Деревья.-Графы.pptx
Количество просмотров: 79
Количество скачиваний: 0