Информация и информационные процессы. § 3. Структура информации

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

§ 1. Информатика и информация
§ 2. Что можно делать с информацией?
§ 3. Структура информации
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

§ 3. Структура информации
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Графы

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

4. Графы

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

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

5
Информация и информационные процессы, 10 класс (углублённый уровень)
Матрица и список смежности
Матрица смежности
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
петля
A (B, C),
B (A, C, D),
C (A, B, С, D),
D (B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

6
Информация и информационные процессы, 10 класс (углублённый уровень)
Постройте матрицу смежности
A
A
D
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
B
D
D
C
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

7
Информация и информационные процессы, 10 класс (углублённый уровень)
Постройте матрицу смежности
A
A
D
D
B
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
D
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

8
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A
B
C
D
A
0
0
1
1
B
0
0
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
D
1
0
1
0
http://kpolyakov.spb.ru

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

9
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A
B
C
D
E
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
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

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

10
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A
B
C
D
E
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
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

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

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

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

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

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

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

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

14
Информация и информационные процессы, 10 класс (углублённый уровень)
Постройте весовую матрицу
A
A
4
1
3
B
3
1
A
C
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
2
C
D
D
1
2
B
C
4
A
B
D
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

15
Информация и информационные процессы, 10 класс (углублённый уровень)
Постройте весовую матрицу
2
A
D
1
3
A
4
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
1
D
2
1
B
1
B
A
A
D
C
4
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

16
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A
A
B
C
D
B
4
C
3
4
3
D
2
6
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
6
A
B
C
D
A
B
C
2
2
3
4
5
D
3
4
5
http://kpolyakov.spb.ru

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

17
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A
B
C
D
E
A B
4
4
3
2
7
C D E
3
7
2
6
6
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
2
2
5
3
6
C D E
5
6
3
1
1
http://kpolyakov.spb.ru

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

18
Информация и информационные процессы, 10 класс (углублённый уровень)
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
2
C D E
2 2 6
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
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

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

19
Информация и информационные процессы, 10 класс (углублённый уровень)
Кратчайший путь (перебор)
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
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
http://kpolyakov.spb.ru