Табличные модели, диаграммы

1. Моделирование

§ 15. Табличные модели. Диаграммы
1

2. Таблицы

Моделирование, 9 класс
2
Таблицы
Свойства объектов:
Фамилия
Иванов
Кузьмин
Сидоров
Имя
Год рождения
Кузьма
Сидор
Иван
1955
1978
1990
Место отдыха
о. Валаам
о. Ольхон
о. Кипр
Лада
Приора
Лада
Калина
ВАЗ 2110
ВАЗ 21099
Мощность
двигателя, л.с.
98
89
79
70
Максимальная
скорость, км/ч
183
165
165
156
Время разгона до
100 км/ч, с
11,5
12,5
14
15
Марка
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Таблицы

Моделирование, 9 класс
3
Таблицы
Связи между объектами:
Лада
Москва
Санкт-Петербург
Пермь
520
430
120
Петя
Барнаул
Хабаровск
Владивосток
Магадан
К.Ю. Поляков, Е.А. Ерёмин, 2018
УАЗ
Тойота
Форд
210
350
200
805
260
150
370
410
230
Вася
Маша
http://kpolyakov.spb.ru
Даша

4. Таблицы

Моделирование, 9 класс
4
Таблицы
Изменение свойств:
День
1
2
3
4
5
6
7
Температура, C
15
18
20
17
23
16
19
Давление, мм. рт. ст.
750
748
760
755
770
743
756
Скорость ветра, м/с
5
7
2
9
3
6
4
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Оптимальный маршрут

Моделирование, 9 класс
5
Оптимальный маршрут
Из
Березовое
Березовое
Лесное
Полевое
Осиновое
Лесное
Осиновое
Березовое
Лесное
Полевое
В
Лесное
Осиновое
Березовое
Лесное
Полевое
Осиновое
Лесное
Полевое
Полевое
Осиновое
Отправл.
07:30
11:50
12:50
13:20
14:00
14:20
14:40
16:00
16:10
17:40
Прибытие
10:00
14:10
15:20
14:40
17:15
15:30
15:50
17:50
17:30
19:55
Березовое: 8:00
Полевое
17:50 П
16:00
Б 07:30
11:50
10:00 Л
14:00
14:10 О
14:40
К.Ю. Поляков, Е.А. Ерёмин, 2018
17:15 П
15:50 Л 16:10
http://kpolyakov.spb.ru
17:30 П

6. Анализ диаграмм

Моделирование, 9 класс
6
Анализ диаграмм
а)
30
25
лоси
белки
зайцы
20
15
лоси
белки
10
5
0
зайцы
б) зайцы
I участок II участок III участок
лоси
лоси
белки
зайцы
всего
I участок
15
30
10
II участок
30
20
15
III участок
15
10
15
всего
60
60
40
160
белки
в)
зайцы
лоси
белки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Анализ диаграмм

Моделирование, 9 класс
7
Анализ диаграмм
1)
10 + 40 + 30 + 20 = 100
2)
25
40
менеджеры
30
рабочие
20
10
0
охрана
«Лада» «Форд» «Тойота» «Ауди»
25
а) все «Форды» могут принадлежать менеджерам
б) все охранники могут ездить на «Ауди»
в) все «Тойоты» могут принадлежать рабочим
г) все рабочие могут ездить на «Фордах»
К.Ю. Поляков, Е.А. Ерёмин, 2018
50
http://kpolyakov.spb.ru

8. Моделирование. Деревья

8

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

Моделирование, 9 класс
9
Что такое дерево?
директор
Уровень 1
Уровень 2
Уровень 3
главный инженер
Петров
Иванов
Фомин
Дерево – это структура данных,
которая служит моделью
многоуровневой структуры
(иерархии).
главный бухгалтер
Алексеева
Сидорова
лист лист
лист
лист
Лес – это несколько деревьев.
корень
К.Ю. Поляков, Е.А. Ерёмин, 2018
лист
http://kpolyakov.spb.ru

10. Из чего состоит дерево?

Моделирование, 9 класс
10
Из чего состоит дерево?
левое
поддерево
A
B
D
правое
поддерево
C
рёбра
E
F
A – корень
D, E, F, G – листья
B, C – промежуточные
узлы
G
Путь — это последовательность узлов, где каждый
следующий связан с предыдущим.
Высота дерева — это количество уровней.
Поддерево — это часть дерева, которая тоже
представляет собой дерево.
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Какие есть поддеревья?
http://kpolyakov.spb.ru

11. Родители и дети

Моделирование, 9 класс
11
Родители и дети
Родитель – сын: между ними есть ребро.
B – родитель для D и E
D и E – сыновья для B
A
B
D
C
E
F
G
? Если нет родителей?
? Если нет сыновей?
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Генеалогическое дерево

Моделирование, 9 класс
12
Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
внуки
К.Ю. Поляков, Е.А. Ерёмин, 2018
Иванов К.А.
Иванов C.К.
Семёнова М.А.
Семёнов C.C.
дети
Семёнов А.C.
http://kpolyakov.spb.ru

13. Классификации

Моделирование, 9 класс
13
Классификации
Хищные
Псообразные
Псовые
Енотовые
Медвежьи
Кошкообразные
Кошачьи
Гиеновые
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
Мангустовые

14. Файловая система

Моделирование, 9 класс
14
Файловая система
Документы
Фотографии
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Папа.jpg
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
Мама.gif

15. Моделирование. Графы

15

16. Графы

Моделирование, 9 класс
16
Графы
«От посёлка Васюки три дороги идут в
посёлки Солнцево, Грибное и Ягодное. Между
Солнцевым и Грибным и между Грибным и
Ягодным также есть дороги. Кроме того,
есть дорога, которая идет из Грибного в лес
и возвращается обратно в Грибное».
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Как структурировать?
http://kpolyakov.spb.ru

17. Графы

Моделирование, 9 класс
17
Графы
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
Граф – это набор вершин (узлов) и связей между ними
(рёбер).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

18. Матрица и список смежности

Моделирование, 9 класс
18
Матрица и список смежности
Матрица смежности
A
B
C
D
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
2
3
5
2
петля
Степень вершины – это количество связанных с ней
рёбер (петля считается дважды!).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. Постройте матрицу смежности

Моделирование, 9 класс
19
Постройте матрицу смежности
A
A
A
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
C
B
B
C
B
D
D
C
A
B
C
A
B
C
D
http://kpolyakov.spb.ru
D

20. Постройте матрицу смежности

Моделирование, 9 класс
20
Постройте матрицу смежности
A
A
D
D
B
C
B
A
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
B
C
C
D
A
B
C
A
B
C
D
http://kpolyakov.spb.ru
D

21. Нарисуйте граф

Моделирование, 9 класс
21
Нарисуйте граф
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
0
0
1
1
B
0
0
1
0
C
1
1
0
0
D
1
0
0
0
A
B
C
D
A
0
1
0
1
B
1
0
1
0
C
0
1
0
1
http://kpolyakov.spb.ru
D
1
0
1
0

22. Нарисуйте граф

Моделирование, 9 класс
22
Нарисуйте граф
A
B
C
D
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
0
0
1
1
0
B
0
0
1
0
1
C D E
1 1 0
1 0 1
0 0 1
0 0 0
1 0 0
A
B
C
D
E
A
0
0
1
1
1
B
0
0
1
0
0
C D E
1 1 1
1 0 0
0 0 1
0 0 0
1 0 0
http://kpolyakov.spb.ru

23. Нарисуйте граф

Моделирование, 9 класс
23
Нарисуйте граф
A
B
C
D
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
0
0
1
1
1
B
0
0
1
0
1
C D E
1 1 1
1 0 1
0 0 1
0 0 0
1 0 0
A
B
C
D
E
A
0
0
0
1
0
B
0
0
1
0
1
C D E
0 1 0
1 0 1
0 1 1
1 0 0
1 0 0
http://kpolyakov.spb.ru

24. Связность графа

Моделирование, 9 класс
24
Связность графа
A
C
B
D
!
Связный граф – это
граф, между любыми
вершинами которого
существует путь.
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Дерево – это граф?

Моделирование, 9 класс
25
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
ABDC
CCC…
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru

26. Взвешенные графы

Моделирование, 9 класс
26
Взвешенные графы
2
Солнцево
8
A
Грибное
12
5
B
Ягодное
Васюки
2
C
5
12
4
8
6
4
D
6
вес ребра
Весовая матрица:
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
A
B
C
D
B
12
12
8
5
6
C
8
5
2
4
http://kpolyakov.spb.ru
D
6
4

27. Постройте весовую матрицу

Моделирование, 9 класс
27
Постройте весовую матрицу
A
1
A
1
A
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
3
B
3
C
B
2
C
D
D
1
2
B
C
4
A
B
D
C
A
B
C
D
http://kpolyakov.spb.ru
D

28. Постройте весовую матрицу

Моделирование, 9 класс
28
Постройте весовую матрицу
2
A
D
1
A
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
B
1
C
C
D
2
1
B
1
B
A
3
C
A
B
D
4
C
A
B
C
D
http://kpolyakov.spb.ru
D

29. Нарисуйте граф

Моделирование, 9 класс
29
Нарисуйте граф
A
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
B
4
C
3
4
3
D
2
6
2
6
A
B
C
D
A
B
C
2
2
3
4
5
http://kpolyakov.spb.ru
D
3
4
5

30. Нарисуйте граф

Моделирование, 9 класс
30
Нарисуйте граф
A
B
C
D
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
4
4
3
2
7
C D E
3
7
2
6
6
1
1
A
B
C
D
E
A B
2
2
5
3
6
C D E
5
6
3
http://kpolyakov.spb.ru
1
1

31. Нарисуйте граф

Моделирование, 9 класс
31
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
К.Ю. Поляков, Е.А. Ерёмин, 2018
2
C D E
2 2 6
2
2
2
A
B
C
D
E
A B
5
5
2
5
6
C D E
2
6
5
2
2
3
3
http://kpolyakov.spb.ru

32. Кратчайший путь (перебор)

Моделирование, 9 класс
32
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
http://kpolyakov.spb.ru
6
3
7
D
9

33. Кратчайший путь

Моделирование, 9 класс
33
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
C D E
4
1
7
3 5
3
3
5 3
Определите кратчайший путь
между пунктами A и E.
http://kpolyakov.spb.ru

34. Кратчайший путь

Моделирование, 9 класс
34
Кратчайший путь
A B
A
B
C 3
D 1
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
C D E
3 1
4
2
2
2
2
Определите кратчайший путь
между пунктами A и B.
http://kpolyakov.spb.ru

35. Кратчайший путь

Моделирование, 9 класс
35
Кратчайший путь
A B
A
B
C 3
D 1
E 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
C D E
3 1 1
4
2
Определите кратчайший путь
между пунктами A и B.
2
http://kpolyakov.spb.ru

36. Кратчайший путь

Моделирование, 9 класс
36
Кратчайший путь
A B
A
B
C 3
D 1
E 4
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
C D E
3 1 4
4
2
2
2
2
Определите кратчайший путь
между пунктами A и B.
http://kpolyakov.spb.ru

37. Кратчайший путь

Моделирование, 9 класс
37
Кратчайший путь
A B
A
B
C
D 1
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
1
C D E
1
4
1
4 2
4
2
Определите кратчайший путь
между пунктами A и B.
http://kpolyakov.spb.ru

38. Ориентированные графы (орграфы)

Моделирование, 9 класс
38
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
Весовая матрица
может быть
несимметрична!
B
A
A
B
C
D
C
5
12
4
Васюки
8
4
D
6
B
12
12
C
8
5
4
http://kpolyakov.spb.ru
D
6
4

39. Нарисуйте орграф

Моделирование, 9 класс
39
Нарисуйте орграф
A B
A
B 2
C 3
D 1
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
C D E
3 1
4
2
2
A B
A
B
C 3
D
E
4
2
C D E
5 1
6 4
3
3
http://kpolyakov.spb.ru

40. Нарисуйте орграф

Моделирование, 9 класс
40
Нарисуйте орграф
A B
A
B
C
D
E 4
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
C D E
3 1 4
4
2
2
2
A B
A
B
C 3
D 1
E 1
4
2
1
C D E
1
4
1
4 2
4
2
http://kpolyakov.spb.ru

41. Количество путей из А в Ж

Моделирование, 9 класс
41
Количество путей из А в Ж
Б
Д
1
1+1+1+1+3=7
Ж
Г
В
К.Ю. Поляков, Е.А. Ерёмин, 2018
1
1+1+1=3
1
А
!
1
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ
http://kpolyakov.spb.ru

42. Количество путей из А в К

Моделирование, 9 класс
42
Количество путей из А в К
Д
Б
B
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
Ж
И
http://kpolyakov.spb.ru

43. Количество путей из А в К

Моделирование, 9 класс
43
Количество путей из А в К
Д
Б
B
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
Ж
И
http://kpolyakov.spb.ru

44. Количество путей из А в К

Моделирование, 9 класс
44
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru