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

1.

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

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
Таблица
свойства
Фамилия
Иванов
Петров
Сидоров
Имя
Иван
Петр
Сидор
Рост, см
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

6.

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

7.

7
Таблицы
Связи между объектами:
Лада
УАЗ
Тойота
Форд
Москва
Санкт-Петербург
Пермь
210
350
200
805
260
150
370
410
230
Вася
Маша
Даша
520
430
120
Петя
Барнаул
Хабаровск
Владивосток
Магадан

8.

8
Таблицы
Изменение свойств:
День
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

9.

9
Оптимальный маршрут
Из
Березовое
Березовое
Лесное
Полевое
Осиновое
Лесное
Осиновое
Березовое
Лесное
Полевое
В
Лесное
Осиновое
Березовое
Лесное
Полевое
Осиновое
Лесное
Полевое
Полевое
Осиновое
Отправл.
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
17:15 П
15:50 Л 16:10
17:30 П

10.

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

11.

11
Что такое список?
Список – последовательность элементов, в которой
важен порядок их расположения.
П
О
Л
И
предыдущий
Г
Л
О
следующий
Список как модель:
слово = список букв, текст = список абзацев
Запись:
['Amicus', 'Socrates', 'sed', 'magis', 'amica',
'veritas']
Что это значит?
?
Т

12.

12
Операции со списком
• замена элемента
• удаление элемента
• вставка нового элемента
? Какие операции на
каждом шаге?
КРАН КОАН КОРН КОРО КОРОН КОРОНА
? Более короткие варианты?
Операция
Замена гласной буквы на гласную или
согласной на согласную.
Замена гласной на согласную или согласной
на гласную.
Вставка или удаление буквы.
Цена
1
2
5
? СКАНЕР ПРИНТЕР с наименьшей стоимостью?

13.

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

14.

Деревья. Ключевые слова
Дерево
Лес
Узел
Вершина
Дуга
Корень
Ветви
Листья
Путь
Поддерево
Высота дерева
Родитель
Сын
Потомок
Предок
Двоичное дерево
Инфиксная запись
Префиксная запись
Постфиксная запись
14

15.

15
Что такое дерево?
директор
Уровень 1
Уровень 2
Уровень 3
главный инженер
Петров
Иванов
главный бухгалтер
Фомин
Дерево – это структура
данных, которая служит
моделью многоуровневой
структуры (иерархии).
Алексеева
Сидорова
лист лист
лист
лист
лист
Лес – это несколько деревьев.
корень

16.

16
Из чего состоит дерево?
A – корень
D, E, F, G –листья
A
рёбра
B
D
E
C
F
B, C – промежуточные
узлы
G
Путь — это последовательность узлов, где
каждый следующий связан с предыдущим.
Высота дерева — это наибольшая длина пути
от корня дерева к листу.
Поддерево — это часть дерева, которая тоже
представляет собой дерево.
? Какие есть поддеревья?

17.

17
Родители и дети
Родитель – сын: между ними есть ребро.
B – родитель для D и E
D и E – сыновья для B
A
B
D
C
E
F
G
? Если нет родителей?
? Если нет сыновей?
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A

18.

18
Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
внуки
Иванов К.А.
Иванов C.К.
Семёнова М.А.
Семёнов C.C.
дети
Семёнов А.C.

19.

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

20.

20
Файловая система
Документы
Тексты
Доходы.d
oc
Фотографии
Расходы.o Отдых.tx Папа.jp
dt
t
g
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографи
иПапа.jpg
Мама.gif
Мама.gif

21.

21
Арифметические выражения
-
(a+3)*5-2*b*c
*
+
a
*
5
3
2
*
b
c
Двоичное (бинарное) дерево – это дерево, в котором
каждый узел может иметь не более двух сыновей.

22.

22
Перебор вариантов
Составить все двухбуквенные слова, которые можно
записать с помощью алфавита {A, Б, В}.
пустое дерево
Б
A
В
БВ
A
Б
В
A
Б
В
A
Б
В

23.

23
Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа
состоит из трёх символов, причём могут
использоваться буквы из алфавита {A, B, C, D}.
Две одинаковые буквы не могут стоять рядом.
Рядом с буквой D обязательно должна стоять
буква A. Если в ключе есть буква B, то там не
может быть буквы C.
14
Сколько возможных ключей?
?

24.

24
Дерево для двоичного кода
А
0
Б
11
В
Г
Д
101 110 111
? Можно однозначно
0
А
1
0
1
декодировать?
0
Условие Фано: ни одно из
кодовых слов не совпадет
с началом другого
кодового слова.
Б
1
0
1
В
Г
Д
тогда однозначно
декодируется!
! Все буквы должны быть в листьях!

25.

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

26.

26
Деревья
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).

27.

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

28.

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

29.

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

30.

30
Префиксная форма – вычисление с конца
- * + 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)
!
Скобки не нужны, вычисляется
однозначно!

31.

31
Постфиксная форма (левое-правое-корень)
*
(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
!
Вычисляется
с начала!

32.

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

33.

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

34.

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

35.

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

36.

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

37.

37
Матрица и список смежности
Матрица смежности
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
петля

38.

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

39.

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

40.

40
Нарисуйте граф
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

41.

41
Нарисуйте граф
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

42.

42
Нарисуйте граф
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

43.

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

44.

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

45.

45
Взвешенные графы
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

46.

46
Постройте весовую матрицу
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

47.

47
Постройте весовую матрицу
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

48.

48
Нарисуйте граф
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

49.

49
Нарисуйте граф
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

50.

50
Нарисуйте граф
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

51.

51
Кратчайший путь (перебор)
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

52.

52
Кратчайший путь
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.

53.

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

54.

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

55.

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

56.

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

57.

57
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
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

58.

58
Нарисуйте орграф
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

59.

59
Нарисуйте орграф
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

60.

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

61.

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

62.

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

63.

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

64.

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

65.

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

66.

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

67.

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

68.

68
Источники иллюстраций
1. http://overhealth.ru
2. https://ufhealth.org
3. http://wmposters.com
4. http://ozon.ru
5. http://www.bikeshot.ru
6. http://ru.wikipedia.org
7. http://salestores.com
8. http://gimp-werkstatt.de
9. http://frontal-cortex.tumblr.com
10. http://www.intermedia.kg
11. http://pc-azbuka.ru
12. авторские материалы