Модели и моделирование

1. МОДЕЛИ И МОДЕЛИРОВАНИЕ

ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ

2. Списки, графы, деревья и таблицы

МК
Списки, графы, деревья и таблицы
Структуры данных
Линейные
Односвязный список
Стек
Очередь
Нелинейные
Дерево
Граф
Таблица

3. Списки, графы, деревья и таблицы

МК
Списки, графы, деревья и таблицы
Неориентированный Ориентированный
Таблица
Вершина
Ребро
Дуга
Невзвешенный
Вес вершины
19
Вес ребра
Таблица
Граф
Взвешенный
10
8
3
40
17
8
10
3
40
17

4. Списки, графы, деревья и таблицы

МК
Списки, графы, деревья и таблицы
Дерево – совокупность элементов (вершин), в которой выделен один
элемент, а остальные элементы разбиты на непересекающиеся множества
(поддеревья). Каждое поддерево является деревом, а его корень является
потомком корня дерева. Все элементы связаны между собой отношением
«предок — потомок». В результате образуется иерархическая структура
вершин.
Частным случаем дерева является
бинарное дерево, в котором каждая
вершина может иметь не более двух
потомков.
Корень
Дерево
Таблица
Граф

5. Списки, графы, деревья и таблицы

МК
Списки, графы, деревья и таблицы
A
A
B
B
C
15
8
D
3
C
E
G
7
10
D
F
12
5
6
Такую таблицу называют матрицей
смежности. Матрица смежности неориентированного графа симметрична
относительно главной диагонали. У
ориентированного
графа
такая
симметрия отсутствует.
E
15
A
F
11
G
B
8
3
C
10
7
E
5
D
Дерево
Таблица
Граф
6
12
F
11
G

6. Задача о количестве дорог

МК
ЗадачаЗадача
о количестве
дорог дорог
о количестве
Задание 1. Сколько существует различных маршрутов от A до H?
B1
D
С
1
G3
1
E
2
H9
А1
F
6

7. Задача о количестве дорог

МК
ЗадачаЗадача
о количестве
дорог дорог
о количестве
Задание 1. Сколько существует различных маршрутов от A до H?
B1
Решение
K(X) – количество
маршрутов от
С
начала до X.
1
K(A)=1
K(B)=K(A)=1
K(C)=K(B)=1
K(D)=K(B)=1
А1
K(E)=K(C)+K(D)=1+1=2
K(G)=K(D)+K(E)=1+2=3
K(F)=K(C)+K(E)+K(G)=1+2+3=6
K(H)=K(G)+K(F)=3+6=9
Ответ: 9
D
G3
1
E
2
H9
F
6

8. Списки, графы, деревья и таблицы

МК
Списки, графы, деревья и таблицы
Задание 2. На рисунке представлена схема дорог, связывающих
населённые пункты A, B, C, D, E, F. В таблице содержатся сведения о
стоимости проезда. На схеме информация об этих же дорогах. Отсутствие
значения означает, что прямого рейса нет. Определить минимальную
стоимость проезда из пункта E в пункт C.
2 3 4 2 1 2
CE B4
B B2
D B3
A B5
B1
F B6
E
5
4
2
2
D
10
5 6
E
3
B
B1
10
A
B
D
B2
9 4
5
D
10
9
4
6
2
B3
C 6 9
B 2
9 2 13С
6
A
B4
4 2
A2
C
C
16
В5
13
F C
4
F 1
14
13
E 1110 5
В6
Ответ:
Выясним
Степени
Каждая
Найдем
По
Осталась
Все
данным
таблице
способы
11из
вершин
вершину
единственная
степень
ввершин
видно,
передвижения
таблице
отметим
A,что
со
каждой
ее
подпишем
вершина
степенями
неустановленная
от
наот
всех
графе
вершины
пункта
вес
Cостальных
иявляется
1,определенных
вE3,
таблице.
до4–вершина
пункта
встречается
число
смежной
отличает
C –можно
ребер,
ребер.
E.вершиной
то,
Вес
один
что
рассмотреть
ребра
соединяющих
раз.
вершина
четырем
BE-10,
Значит,
на
Aа
некоторую
можно
является
вершинам
ребра
дереве
DE-5.
установить
решений.
смежной
–вершину
D, A, FМинимальная
взаимно-однозначное
и
вершиной
сB1.
другими
Вес ребра
для
вершинами.
стоимость
двух
CB –уже
6. соответствие
определенных
при перемещении
между
вершин
ними.
E-D-A-C.
– D и C.

9. Самое главное

МК
Самое главное
Линейный односвязный список – последовательность линейно связанных
элементов. В списке разрешены операции добавления и удаления любого
элемента. Частными случаями линейного односвязного списка являются
стек и очередь.
Графы и деревья являются нелинейными структурами. Граф – множество
элементов вместе с набором отношений между ними, называемых
рёбрами (дугами) графа. Дерево – совокупность элементов, в которой
выделен корень, а остальные элементы разбиты на непересекающиеся
множества (поддеревья). Все элементы дерева связаны между собой
отношением «предок – потомок». В бинарном дереве каждая вершина
имеет не более двух потомков. Таблица – структура данных, состоящая из
строк и граф (столбцов, колонок), пересечение которых образуют ячейки.
Табличный способ представления данных является универсальным –
любую структуру данных, в том числе и представленную в форме графа,
можно свести к табличной форме.