Графы (2)

1. Информация и информационные процессы

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

2. Примеры

2
Примеры
Вариант 1
«Для того, чтобы добраться до села Васино, нужно
сначала долететь на самолете до Ивановска.
Затем на электричке доехать до Ореховска. Там
на пароме переправиться через реку Слоновую в
поселок Ольховка, и оттуда ехать в Васино на
попутной машине».
Вариант 2
Как ехать в Васино?
1) На самолете до Ивановска.
2) На электричке до Ореховска.
3) На пароме через р. Слоновую в пос. Ольховка.
4) На попутной машине до с. Васино.

3. Примеры

3
Примеры
Вариант 3
Откуда
Москва
Ивановск
Ореховск
пос. Ольховка
Куда
Ивановск
Ореховск
пос. Ольховка
с. Васино
Транспорт
самолет
электричка
паром (р. Слоновая)
попутная машина
Вариант 4
Москва
Ивановск
самолёт
Ореховск
электричка
Ольховка
паром
р. Слоновая
Васино
попутная
машина
? Какой вариант лучше? Почему?

4. Структурирование

4
Структурирование
Структурирование — это выделение важных
элементов в информационных сообщениях и
установление связей между ними.
Цель — облегчение восприятия и поиска
информации.
Оглавление:
1. Информация
1.1 Что такое информация?
1.2 Виды информации
1.3 Информация в природе
1.4 Информация в технике
2. Измерение информации
2.1 Что такое бит?
2.2 Байт и другие единицы
5
6
8
10
11
12
13
14
Словарь:
Индекс:
автомат – automaton
автор – author
адрес – address
алгебра – algebra
алгоритм – algorithm
архив – archive
архитектура – architecture
асимметрия – asymmetry
А
аксиома 45
алгоритм 30, 78
архиватор 125
Б
бит 5, 15, 25, 43
брандмауэр 112
браузер 322

5. Множество

5
Множество
• перечисление элементов
– Вася, Петя, Коля
– 1, 17, 22, 55
• по характерному признаку
– множество натуральных чисел
– множество драконов с тремя хвостами
!
Порядок перечисления не важен!
• процессор
• память
• устройства ввода
• устройства вывода
маркированный
список

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

6
Линейный список
Москва
!
Ивановск
Ореховск
Ольховка
Васино
Порядок следования элементов важен!
1) надеть носки
2) надеть ботинки
3) выйти из дома
нумерованный
список

7. Таблица

7
Таблица
свойства
Фамилия
Иванов
Петров
Сидоров
Имя
Иван
Петр
Сидор
Рост, см
175
164
168
Год рождения
1996
1998
2000
объект
свойства
Марка
Мощность двигателя, л.с.
Максимальная скорость, км/ч
Время разгона до 100 км/ч, с
Вес, кг
67
70
63
Лада Приора
98
183
11,5
Лада Калина
89
165
12,5
ВАЗ 2110
79
165
14
объект
ВАЗ 21099
70
156
15

8. Иерархия (дерево)

8
Иерархия (дерево)
директор
Уровень 1
главный инженер
Уровень 2
Уровень 3
Петров
Иванов
лист
главный бухгалтер
Фомин
лист
лист
Алексеева
лист
лист
дуга
узел
корень
Сидорова

9. Деревья

9
Деревья
A
B
D
C
E
«Сыновья» А: B, C.
F
G
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).

10. Деревья – классификации

10
Деревья – классификации
Хищные
Псообразные
Псовые
Енотовые Медвежьи
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
…
Кошкообразные
Кошачьи
Гиеновые Мангустовые
многоуровневый
список

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

11
Иерархия – файловая система
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
Папа.jpg
Мама.gif
Документы
Тексты
Доходы.doc
Расходы.odt
Фотографии
Отдых.txt
Папа.jpg
Мама.gif

12. Деревья и арифметические выражения

12
Деревья и арифметические выражения
*
(a+3)*5-2*b
+
a
*
5
3
(корень(левое,правое))
(-(*(+(a,3),5),*(2,b)))
- * + a 3 5 * 2 b
Префиксная форма – операция
перед данными.
2
b

13. Префиксная форма – вычисление с конца

13
Префиксная форма – вычисление с конца
- * + a 3 5 * 2 b
- * + a 3 5 (2*b)
- * (a+3) 5 (2*b)
Идём с конца,
встретили знак
операции –
выполнили её.
- (a+3)*5 (2*b)
(a+3)*5 – (2*b)
!
Скобки не нужны, вычисляется
однозначно!

14. Постфиксная форма (левое-правое-корень)

14
Постфиксная форма (левое-правое-корень)
*
(a+3)*5-2*b
+
a
a 3 + 5 * 2 b * (a+3) 5 * 2 b * (a+3)*5 2 b * (a+3)*5 (2*b) (a+3)*5 - (2*b)
*
5
2
b
3
!
Вычисляется
с начала!

15. Задачи

15
Задачи
Запишите выражения, соответствующие показанным
деревьям, в «нормальной» (инфиксной), в префиксной и
в постфиксной форме.
а)
б)
-
a
*
*
a
d
+
b
в)
c
b
a
с
d
b
c
d

16. Задачи

16
Задачи
Запишите выражения в префиксной и постфиксной
формах.
а)
(a+b)*(c+2*d)
б)
(2*a-3*d)*c+2*b
в)
(a+b+2*c)*d
г)
3*a-(2*b+c)*d

17. Задачи

17
Задачи
Вычислите выражения, записанные в постфиксной
форме.
а)
12 6 + 7 3 - 1 - * 12 +
б)
12 10 – 5 7 + * 7 – 2 *
в)
5 6 7 8 9 + - + -
г)
5 4 3 2 1 - - - -

18. Графы

18
Графы
«От посёлка Васюки три дороги идут в
посёлки Солнцево, Грибное и Ягодное.
Между Солнцевым и Грибным и между
Грибным и Ягодным также есть дороги.
Кроме того, есть дорога, которая идет
из Грибного в лес и возвращается
обратно в Грибное».
?
Как структурировать?

19. Графы

19
Графы
Солнцево
A
C
B
D
Грибное
Васюки
!
Ягодное
Граф – это набор вершин и связей
между ними (рёбер).

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

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

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

21
Постройте матрицу смежности
A
A
A
A
B
C
D
D
C
B
B
C
B
D
C
A
A
B
C
D
D
B
C
D

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

22
Постройте матрицу смежности
A
A
D
D
B
C
B
A
A
B
C
D
B
C
C
D
A
A
B
C
D
B
C
D

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

23
Нарисуйте граф
A
A
B
C
D
0
1
1
B
0
1
0
C
1
1
0
D
1
0
0
A
A
B
C
D
1
0
1
B
1
1
0
C
0
1
1
D
1
0
1

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

24
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
0 1
C D E
1 1 0
1 0 1
0 1
0
0
1 0
A
B
C
D
E
A B
0
0
1 1
1 0
1 0
C D E
1 1 1
1 0 0
0 1
0
0
1 0

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

25
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
1 1
C D E
1 1 1
1 0 1
0 1
0
0
1 0
A
B
C
D
E
A B
0
0
0 1
1 0
0 1
C D E
0 1 0
1 0 1
1 1
1
0
1 0

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

26
Связность графа
A
C
B
D
!
Связный граф – это
граф, между любыми
вершинами которого
существует путь.
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
компоненты связности

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

27
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
H
C
E
F
G
J
дерево

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

28
Взвешенные графы
2
Солнцево
12
8
A
Грибное
5
B
Ягодное
Васюки
2
C
5
12
4
8
6
4
D
6
вес ребра
Весовая матрица:
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4

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

29
Постройте весовую матрицу
A
A
4
1
3
B
1
A
A
B
C
D
3
C
B
2
C
D
D
1
2
B
C
4
A
A
B
C
D
B
D
C
D

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

30
Постройте весовую матрицу
2
A
D
1
A
A
B
C
D
3
4
B
C
C
1
D
A
A
B
C
D
2
1
B
1
B
A
D
C
4
B
C
D

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

31
Нарисуйте граф
A
A
B
C
D
B
4
C
3
4
3
D
2
6
2
6
A
B
C
D
A
B
C
2
2
3
4
5
D
3
4
5

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

32
Нарисуйте граф
A
B
C
D
E
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
1
1

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

33
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
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

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

34
Кратчайший путь (перебор)
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.
2
B
A
4
С
2
6
E
4
1
С
5
D
8
1
С
3
1
E
4
3
дерево возможных
путей
D
7
6
3
7
D
9

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

35
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
C D E
4
1
7
3 5
3
3
5 3
Определите кратчайший
путь между пунктами A и E.

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

36
Кратчайший путь
A B
A
B
C 3
D 1
E
4
C D E
3 1
4
2
2
2
2
Определите кратчайший
путь между пунктами A и B.

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

37
Кратчайший путь
A B
A
B
C 3
D 1
E 1
4
C D E
3 1 1
4
2
2
Определите кратчайший
путь между пунктами A и B.

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

38
Кратчайший путь
A B
A
B
C 3
D 1
E 4
4
C D E
3 1 4
4
2
2
2
2
Определите кратчайший
путь между пунктами A и B.

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

39
Кратчайший путь
A B
A
B
C
D 1
E
4
1
C D E
1
4
1
4 2
4
2
Определите кратчайший
путь между пунктами A и B.

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

40
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
A
Весовая матрица
может быть
несимметрична!
B
A
A
B
C
D
12
C
5
12
4
Васюки
8
4
D
6
B
12
C
8
5
4
D
6
4

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

41
Нарисуйте орграф
A B
A
B 2
C 3
D 1
E
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

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

42
Нарисуйте орграф
A B
A
B
C
D
E 4
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

43. Ответы на орграфы

43
Ответы на орграфы

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

44
Количество путей из А в Ж
Б
1
1
Д
1+1+1=3
1
А
Ж
Г
В
!
1
1+1+1+1+3=7
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ

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

45
Количество путей из А в К
Д
Б
B
Е
А
Г
З
Ж
К
И

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

46
Количество путей из А в К
Д
Б
B
Е
А
Г
З
Ж
К
И

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

47
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
З
И

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

48
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
З
И

49. Количество путей из А в Л не через В

49
Количество путей из А в Л не через В
Сколько существует различных путей из
города А в город Л, не проходящих через B?
Д
Б
Ж
В
А
Г
И
Е
Л
К

50. Количество путей из А в Л через Д

50
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
Ж
В
А
Г
И
Е
Л
К

51. Количество путей из А в Л через Д

51
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
В
А
Г
И
Ж
Е
Л
К