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

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

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

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

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

3. Информатика

3
Информация и информационные процессы, 10 класс (углублённый уровень)
Информатика
1957, К. Штейнбух:
Informatik (нем.)
1962, Ф. Дрейфус:
informatique = information + automatique
информатика
информация
автоматика
Английский язык:
computer science
компьютер
+
К.Ю. Поляков, Е.А. Ерёмин, 2018
наука
= наука о компьютерах
http://kpolyakov.spb.ru

4. Информатика

4
Информация и информационные процессы, 10 класс (углублённый уровень)
Информатика
• теоретическая информатика (теория
информации, теория кодирования, …)
• вычислительная техника (устройство
компьютеров и компьютерных сетей)
• алгоритмизация и программирование
• прикладная информатика (персональные
компьютеры, прикладные программы, …)
• искусственный интеллект (распознавание
образов, понимание речи, машинный перевод, …)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Информация

5
Информация и информационные процессы, 10 класс (углублённый уровень)
Информация
Латинский язык:
informatiо – разъяснение, сведения
• отражает реальный мир
• нематериальна
это содержание, которое человек с помощью сознания
«выделяет» из окружающей среды
• характеризует разнообразие
• уменьшает неопределённость знания
Н. Винер: «Информация есть информация, а не
материя и не энергия».
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Получение информации

6
Информация и информационные процессы, 10 класс (углублённый уровень)
Получение информации
• зрительная
(визуальная, 80-90 % информации)
• звуковая (аудиальная)
• вкусовая
• обонятельная (запахи)
• тактильная (осязание)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Формы представления информации

7
Информация и информационные процессы, 10 класс (углублённый уровень)
Формы представления информации
• текстовая
• числовая
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim
veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea
commodo consequat.
1 2 4 8 16 32 64 128 256 512 1024
• графическая
• звуковая
• мультимедийная
! Информация может быть
представлена в разных формах!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Информация и знания

8
Информация и информационные процессы, 10 класс (углублённый уровень)
Информация и знания
Знания — представления человека о природе,
обществе, самом себе («модель мира»).
? Всегда ли информация увеличивает знания?
I
Ю.А. Шрейдер
сведения
не новы
ничего
непонятно
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
100 Доля известной
информации, %
http://kpolyakov.spb.ru

9. Знания

9
Информация и информационные процессы, 10 класс (углублённый уровень)
Знания
• Декларативные — факты, законы, принципы.
«Я знаю, что …»
Волга впадает в Каспийское море.
F m a
• Процедурные — алгоритмы решения задач.
«Я знаю, как …»
25
×36
150
75
900
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Данные и информация

10
Информация и информационные процессы, 10 класс (углублённый уровень)
Данные и информация
Данные — это информация, закодированная в
некоторой форме.
данные
знания
информация
знания
знания
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Свойства (идеальной) информации

11
Информация и информационные процессы, 10 класс (углублённый уровень)
Свойства (идеальной) информации
• объективность
(независимость от чьего-либо мнения);
• понятность для получателя;
• полезность
(позволяет получателю решать свои задачи);
• достоверность
(получена из надёжного источника);
• актуальность
(значимость в данный момент);
• полнота
(достаточность для принятия решения).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

13
Информация и информационные процессы, 10 класс (углублённый уровень)
Информационные процессы
Материальный носитель — это объект или
среда, которые могут содержать информацию.
Информационные процессы — это изменение
свойств носителя (= изменение информации).
• передача информации
(перенос на другой носитель)
• обработка информации
(изменение содержания)
Хранение информации?
(нет изменений носителя не процесс)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Передача информации

14
Информация и информационные процессы, 10 класс (углублённый уровень)
Передача информации
канал связи помехи
источник
информации
101100100
К
носитель
Д
приемник
информации
сигналы
К — кодирующее устройство, Д – декодирующее
Сигнал — это изменение свойств носителя, которое
используется для передачи информации.
Сообщение — это последовательность сигналов
(оболочка для информации).
Для борьбы помехами – избыточность.
«Влг впдт в Кспск мр». «Борис, Инна, Тимур».
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

15. Обработка информации

15
Информация и информационные процессы, 10 класс (углублённый уровень)
Обработка информации
• создание новой информации
• кодирование – изменение формы, запись в
некоторой знаковой системе (в виде кода),
шифрование
• поиск
• структурирование – выделение важных
элементов в сообщениях и установление
связей между ними
• сортировка – расстановка элементов списка в
заданном порядке
? Зачем нужна сортировка?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

16. Хранение информации

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

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

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

18. Примеры

18
Информация и информационные процессы, 10 класс (углублённый уровень)
Примеры
Вариант 1
«Для того, чтобы добраться до села Васино, нужно
сначала долететь на самолете до Ивановска.
Затем на электричке доехать до Ореховска. Там
на пароме переправиться через реку Слоновую в
поселок Ольховка, и оттуда ехать в Васино на
попутной машине».
Вариант 2
Как ехать в Васино?
1) На самолете до Ивановска.
2) На электричке до Ореховска.
3) На пароме через р. Слоновую в пос. Ольховка.
4) На попутной машине до с. Васино.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. Примеры

19
Информация и информационные процессы, 10 класс (углублённый уровень)
Примеры
Вариант 3
Откуда
Москва
Ивановск
Ореховск
пос. Ольховка
Куда
Ивановск
Ореховск
пос. Ольховка
с. Васино
Транспорт
самолет
электричка
паром (р. Слоновая)
попутная машина
Вариант 4
Москва
Ивановск
самолёт
Ореховск
электричка
Ольховка
паром
р. Слоновая
Васино
попутная
машина
? Какой вариант лучше? Почему?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

20
Информация и информационные процессы, 10 класс (углублённый уровень)
Структурирование
Структурирование — это выделение важных
элементов в информационных сообщениях и
установление связей между ними.
Цель — облегчение восприятия и поиска
информации.
Оглавление:
1. Информация
1.1 Что такое информация?
1.2 Виды информации
1.3 Информация в природе
1.4 Информация в технике
2. Измерение информации
2.1 Что такое бит?
2.2 Байт и другие единицы
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
http://kpolyakov.spb.ru

21. Множество

21
Информация и информационные процессы, 10 класс (углублённый уровень)
Множество
• перечисление элементов
– Вася, Петя, Коля
– 1, 17, 22, 55
• по характерному признаку
– множество натуральных чисел
– множество драконов с тремя хвостами
!
Порядок перечисления не важен!
• процессор
• память
• устройства ввода
• устройства вывода
К.Ю. Поляков, Е.А. Ерёмин, 2018
маркированный
список
http://kpolyakov.spb.ru

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

22
Информация и информационные процессы, 10 класс (углублённый уровень)
Линейный список
Москва
!
Ивановск
Ореховск
Ольховка
Васино
Порядок следования элементов важен!
1) надеть носки
2) надеть ботинки
3) выйти из дома
К.Ю. Поляков, Е.А. Ерёмин, 2018
нумерованный
список
http://kpolyakov.spb.ru

23. Таблица

23
Информация и информационные процессы, 10 класс (углублённый уровень)
Таблица
свойства
Фамилия
Иванов
Петров
Сидоров
Имя
Иван
Петр
Сидор
Рост, см
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
объект
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

24. Таблица

24
Информация и информационные процессы, 10 класс (углублённый уровень)
Таблица
объект
Кубань
Кубань
Рубин
Зенит
0:3
2:1
Рубин
3:0
Зенит
1:2
2:0
0:2
объект
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

25
Информация и информационные процессы, 10 класс (углублённый уровень)
Иерархия (дерево)
директор
Уровень 1
главный инженер
Уровень 2
Уровень 3
Петров
Иванов
лист
главный бухгалтер
Фомин
лист
лист
Алексеева
Сидорова
лист
лист
дуга
узел
корень
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

26. Деревья

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

27. Деревья

27
Информация и информационные процессы, 10 класс (углублённый уровень)
Деревья
правое
поддерево
A
левое
поддерево
B
D
C
E
F
G
Поддерево – это часть дерева, которая тоже
представляет собой дерево.
Высота дерева – это число уровней (здесь = 3).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

30
Информация и информационные процессы, 10 класс (углублённый уровень)
Деревья и арифметические выражения
*
(a+3)*5-2*b
+
a
*
5
2
b
3
(корень(левое,правое))
(-(*(+(a,3),5),*(2,b)))
- * + a 3 5 * 2 b
Префиксная форма – операция
перед данными.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

31
Информация и информационные процессы, 10 класс (углублённый уровень)
Префиксная форма – вычисление с конца
- * + 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)
!
Скобки не нужны, вычисляется
однозначно!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

32
Информация и информационные процессы, 10 класс (углублённый уровень)
Постфиксная форма (левое-правое-корень)
*
(a+3)*5-2*b
+
a
a 3 + 5 * 2 b * (a+3) 5 * 2 b * (a+3)*5 2 b * -
*
5
2
b
3
!
Вычисляется
с начала!
(a+3)*5 (2*b) (a+3)*5 - (2*b)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Задачи

33
Информация и информационные процессы, 10 класс (углублённый уровень)
Задачи
Запишите выражения, соответствующие показанным
деревьям, в «нормальной» (инфиксной), в префиксной и
в постфиксной форме.
а)
б)
-
a
*
*
a
d
+
b
в)
c
К.Ю. Поляков, Е.А. Ерёмин, 2018
b
a
с
b
c
d
d
http://kpolyakov.spb.ru

34. Задачи

34
Информация и информационные процессы, 10 класс (углублённый уровень)
Задачи
Запишите выражения в префиксной и постфиксной
формах.
а)
(a+b)*(c+2*d)
б)
(2*a-3*d)*c+2*b
в)
(a+b+2*c)*d
г)
3*a-(2*b+c)*d
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

35. Задачи

35
Информация и информационные процессы, 10 класс (углублённый уровень)
Задачи
Вычислите выражения, записанные в постфиксной
форме.
а)
12 6 + 7 3 - 1 - * 12 +
б)
12 10 – 5 7 + * 7 – 2 *
в)
5 6 7 8 9 + - + -
г)
5 4 3 2 1 - - - -
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

36. Графы

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

37. Графы

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

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

38
Информация и информационные процессы, 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

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

39
Информация и информационные процессы, 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

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

40
Информация и информационные процессы, 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

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

41
Информация и информационные процессы, 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

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

42
Информация и информационные процессы, 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

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

43
Информация и информационные процессы, 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

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

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

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

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

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

46
Информация и информационные процессы, 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

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

47
Информация и информационные процессы, 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

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

48
Информация и информационные процессы, 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

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

49
Информация и информационные процессы, 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

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

50
Информация и информационные процессы, 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

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

51
Информация и информационные процессы, 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

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

52
Информация и информационные процессы, 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

61
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в Ж
Б
1
1
Д
1+1+1=3
1
А
Ж
Г
В
!
1
1+1+1+1+3=7
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

62
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в К
Д
Б
B
Е
А
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
Ж
К
И
http://kpolyakov.spb.ru

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

63
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в К
Д
Б
B
Е
А
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
Ж
К
И
http://kpolyakov.spb.ru

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

64
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru

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

65
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru

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

66
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в Л не через В
Сколько существует различных путей из
города А в город Л, не проходящих через B?
Д
Б
Ж
В
А
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
И
Е
Л
К
http://kpolyakov.spb.ru

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

67
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
Ж
В
А
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
И
Е
Л
К
http://kpolyakov.spb.ru

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

68
Информация и информационные процессы, 10 класс (углублённый уровень)
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
В
А
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
И
Ж
Е
Л
К
http://kpolyakov.spb.ru

69. Установить соответствие

69
Информация и информационные процессы, 10 класс (углублённый уровень)
Установить соответствие
Определить длину дороги между В и Е.
1
1
2
2
3
45
4
5
6
7
6
45
Д
2
55
3
15 60
2
40
10 40
15
Е
А
20 35
4
В
55
2
степень 5
55 60 20 55
35
Б
7
10
3
4
5
45
45
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
К
степень 4
2
Г
степени
вершин
Ответ: 20
http://kpolyakov.spb.ru

70. Установить соответствие

70
Информация и информационные процессы, 10 класс (углублённый уровень)
Установить соответствие
Определить длину дороги между A и Д.
степень 3 Б
1 2 3 4 5 6 7
1
30
2
17 12
3
30 17
4
5
23
12 23
18
34 15
5
46
3
34 46
18
15
3
2
25
6
7
25
37 18
37
2
18
3
А
4
степени
вершин
К.Ю. Поляков, Е.А. Ерёмин, 2018
Г
В
Д
Е
К
степень 3
Ответ: 46
http://kpolyakov.spb.ru

71. Конец фильма

71
Информация и информационные процессы, 10 класс (углублённый уровень)
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

72. Источники иллюстраций

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