Информация и информационные процессы
Информация и информационные процессы
Информатика
Информатика
Информация
Получение информации
Формы представления информации
Информация и знания
Знания
Данные и информация
Свойства (идеальной) информации
Информация и информационные процессы
Информационные процессы
Передача информации
Обработка информации
Хранение информации
Информация и информационные процессы
Как измерить информацию?
Какой код использовать?
Двоичный код
1 бит
1 бит
Сколько информации?
Сколько вариантов?
Если вариантов больше…
Если вариантов больше…
Единицы измерения
Перевод в другие единицы
Перевод в другие единицы
Перевод в другие единицы
Информация и информационные процессы
Примеры
Примеры
Структурирование
Множество
Линейный список
Таблица
Иерархия (дерево)
Деревья
Деревья – классификации
Иерархия – файловая система
Деревья и арифметические выражения
Префиксная форма – вычисление с конца
Постфиксная форма (левое-правое-корень)
Задачи
Задачи
Задачи
Графы
Графы
Матрица и список смежности
Матрица инцидентности
Постройте матрицу смежности
Постройте матрицу смежности
Нарисуйте граф
Нарисуйте граф
Нарисуйте граф
Связность графа
Дерево – это граф?
Взвешенные графы
Постройте весовую матрицу
Постройте весовую матрицу
Нарисуйте граф
Нарисуйте граф
Нарисуйте граф
Кратчайший путь (перебор)
Кратчайший путь
Кратчайший путь
Кратчайший путь
Кратчайший путь
Кратчайший путь
Кратчайший путь
Кратчайший путь
Ориентированные графы (орграфы)
Нарисуйте орграф
Нарисуйте орграф
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ ЕГЭ-1
ДЗ-ЕГЭ1
Количество путей из А в Ж
Количество путей из А в К
Количество путей из А в К
Количество путей из А в К
Количество путей из А в К
Количество путей из А в Л не через В
Количество путей из А в Л через Д
Количество путей из А в Л через Д
До/за
До/за
Доза
До/за
ДО/ЗА
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
До/за
Конец фильма
Источники иллюстраций
8.58M
Категория: ИнформатикаИнформатика

Информация и информационные процессы. Что можно делать с информацией?

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

§ 1. Информатика и информация
§ 2. Что можно делать с информацией?
§ 3. Измерение информации
§ 4. Структура информации

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

§ 1. Информатика и
информация

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

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

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

4
Информатика
• теоретическая информатика (теория
информации, теория кодирования, …)
• вычислительная техника (устройство
компьютеров и компьютерных сетей)
• алгоритмизация и программирование
• прикладная информатика (персональные
компьютеры, прикладные программы, …)
• искусственный интеллект (распознавание
образов, понимание речи, машинный перевод, …)

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

5
Информация
Латинский язык:
informatiо – разъяснение, сведения
• отражает реальный мир
• нематериальна
это содержание, которое человек с помощью сознания
«выделяет» из окружающей среды
• характеризует разнообразие
• уменьшает неопределённость знания
Н. Винер: «Информация есть информация, а не
материя и не энергия».

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

6
Получение информации
• зрительная
(визуальная, 80-90 % информации)
• звуковая (аудиальная)
• вкусовая
• обонятельная (запахи)
• тактильная (осязание)

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

7
Формы представления информации
• текстовая
• числовая
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
• графическая
• звуковая
• мультимедийная
! Информация может быть
представлена в разных формах!

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

8
Информация и знания
Знания — представления человека о природе,
обществе, самом себе («модель мира»).
? Всегда ли информация увеличивает знания?
I
Ю.А. Шрейдер
сведения
не новы
ничего
непонятно
0
100 Доля известной
информации, %

9. Знания

9
Знания
• Декларативные — факты, законы, принципы.
«Я знаю, что …»
Волга впадает в Каспийское море.
F m a
• Процедурные — алгоритмы решения задач.
«Я знаю, как …»
25
×36
150
75
900

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

10
Данные и информация
Данные — это информация, закодированная в
некоторой форме.
данные
знания
информация
знания
знания

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

11
Свойства (идеальной) информации
• объективность
(независимость от чьего-либо мнения);
• понятность для получателя;
• полезность
(позволяет получателю решать свои задачи);
• достоверность
(получена из надёжного источника);
• актуальность
(значимость в данный момент);
• полнота
(достаточность для принятия решения).

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

§ 2. Что можно делать с
информацией?

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

13
Информационные процессы
Материальный носитель — это объект или
среда, которые могут содержать информацию.
Информационные процессы — это изменение
свойств носителя (= изменение информации).
• передача информации
(перенос на другой носитель)
• обработка информации
(изменение содержания)
Хранение информации?
(нет изменений носителя не процесс)

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

14
Передача информации
помехи
источник
информации
сигналы
канал связи
носитель
приемник
информации
датчики
Сигнал — это изменение свойств носителя, которое
используется для передачи информации.
Сообщение — это последовательность сигналов
(оболочка для информации).
Для борьбы помехами – избыточность.
«Влг впдт в Кспск мр». «Борис, Инна, Тимур».

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

15
Обработка информации
• создание новой информации
• кодирование – изменение формы, запись в
некоторой знаковой системе (в виде кода),
шифрование
• поиск
• структурирование – выделение важных
элементов в сообщениях и установление
связей между ними
• сортировка – расстановка элементов списка в
заданном порядке
? Зачем нужна сортировка?

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

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

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

§ 3. Измерение информации

18. Как измерить информацию?

18
Как измерить информацию?
• Что такое «много информации» и «мало
информации»?
• Как определить, в каком сообщении больше
информации?
объёмный
подход
Идея:
количество информации определяется
временем ее передачи
количество информации определяется
длиной сообщения.
? Как именно закодировать?

19. Какой код использовать?

19
Какой код использовать?
Идея: использовать тот код, который
применяется в компьютерной технике
220 В
220 В
«0»
«1»

20. Двоичный код

20
Двоичный код
Код, в котором используются только два
знака, называется двоичным. Все виды
информации в компьютерах кодируются в
двоичном коде.
1 бит – это количество информации, которое
можно передать с помощью одного знака в
двоичном коде («0» или «1»).
К. Шеннон, 1948:
bit = binary digit, двоичная цифра

21. 1 бит

21
1 бит
0
или
1
? Что можно сообщить с помощью
1 знака (1 бита)?
выбрать один из двух вариантов, если
заранее договориться, что означают «0» и «1»

22. 1 бит

22
1 бит
1 бит – это количество информации, которое мы
получаем при выборе одного из двух
возможных вариантов (вопрос: «Да» или
«Нет»?)
Примеры:
Эта стена – зеленая? Да.
Дверь открыта? Нет.
Сегодня выходной? Нет.
Это новый автомобиль? Новый.
Ты будешь чай или кофе? Кофе.

23. Сколько информации?

23
Сколько информации?
Определите количество информации:
01
2 бита
10101
5 битов
1010111
7 битов
1010101001
10 битов

24. Сколько вариантов?

24
Сколько вариантов?
0
1
1 бит: 0
2 бита: 00 01
10 11
3 бита: 000 001
010 011
100 101
110 111
4 бита: 16 вариантов!

25. Если вариантов больше…

25
Если вариантов больше…
00
01
10
11
4 варианта – 2 бита
?8 вариантов – 3 бита
? вариантов – 4 бита
16
? варианта – 5 бит
32
64
? варианта – 6 бит
? вариантов – 7 бит
128

26. Если вариантов больше…

26
Если вариантов больше…
I, битов
информации
1
2
3
4
5
6
7
8
N, вариантов
2
4
8
16
32 64
128
256 512 1024
9
6 вариантов – между 4 (2 бита) и 8 (3 бита)
Ответ: количество информации между
2 и 3 битами
! Количество информации может быть
нецелым числом!
10

27. Единицы измерения

27
Единицы измерения
1 байт (bytе)
= 8 бит
10
2
КиБ (кибибайт)
1 Кбайт (килобайт) = 1024 байта
МиБ (мебибайт)
1 Мбайт (мегабайт) = 1024 Кбайт
ГиБ (гибибайт)
1 Гбайт (гигабайт) = 1024 Мбайт
ТиБ (тебибайт)
1 Тбайт (терабайт) = 1024 Гбайт
ПиБ (пебибайт)
1 Пбайт (петабайт) = 1024 Тбайт

28. Перевод в другие единицы

28
Перевод в другие единицы
5 Кбайт = 5 ·1024 байтов = 5120 байтов
15 байтов = 15 · 8 битов = 120 битов
2048 Кбайт = 2048:1024 Мбайт = 2 Mбайта
1024 Mбайт = 1024:1024 Гбайт = 1 Гбайт
3 Мбайта = 3 · 1024 Кбайт = 3072 Кбайта
умножение
крупные
единицы
мелкие
единицы
деление
1 байт = 8 битов

29. Перевод в другие единицы

29
Перевод в другие единицы
Сравните (поставьте знак <, > или =):
3 байта = 24 бита
1000 байтов < 1 Кбайт
250 байтов < 0,25 Кбайт
1 Мбайт > 1000 Кбайт
8192 бита = 1 Кбайт

30. Перевод в другие единицы

30
Перевод в другие единицы
Впишите недостающее число:
8 байтов = ? бита
1,5 Кбайт =
? байтов
512 битов =
? байта
2 Мбайта =
? Кбайт
4 бита =
? байта
3072 Кбайта =
? Мбайта

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

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

32. Примеры

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

33. Примеры

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

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

34
Структурирование
Структурирование — это выделение важных
элементов в информационных сообщениях и
установление связей между ними.
Цель — облегчение восприятия и поиска
информации.
Оглавление:
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

35. Множество

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

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

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

37. Таблица

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

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

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

39. Деревья

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

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

40
Деревья – классификации
Хищные
Псообразные
Псовые
Енотовые Медвежьи
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи

Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые

Кошкообразные
Кошачьи
Гиеновые Мангустовые
многоуровневый
список

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

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

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

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

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

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

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

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

45. Задачи

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

46. Задачи

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

47. Задачи

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

48. Графы

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

49. Графы

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

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

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

51. Матрица инцидентности

51
Матрица инцидентности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

71
Кратчайший путь

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

72
Кратчайший путь

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

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

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

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

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

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

76. ЕГЭ-1

76
ЕГЭ-1
1. На рисунке справа схема дорог Н-ского района изображена в виде графа, в
таблице содержатся сведения о длинах этих дорог (в километрах). Так как
таблицу и схему рисовали независимо друг от друга, то нумерация населённых
пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе
запишите целое число – так, как оно указано в таблице.
П1
П2
П3
П4
П1
9
П2
5
П5
Г
В
11
12
9
5
4
П5
4
П6
П7
П7
7
П3
П4
П6
11
7
12
13
10
15
8
13
15
10
8
А
Ж
Б
Е
Д

77. ЕГЭ-1

77
ЕГЭ-1
1) определим для каждой вершины её степень, то есть, количество ребёр, в
которыми она связана; в таблице степень вершины – это количество
заполненных клеток в строке (или в столбце)
степень
2
2
1
A
5
Ж
3
4
Б
3
1
2
3
4
5
6
7
А Ж
Б
1 2 3 4 5 6 7
9
7
5
11
12
9 5
4 13 15
4
10 8
11 12 13 10
7
15 8
В
Г
2
5
А
1
Б
4
Ж
2
3
Д
Е3
2) сопоставление степеней вершин в таблице и на рисунке позволяет сразу
обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и Б (№ 6)
3) нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г имеет степень 2
и связана, кроме вершины Ж, с вершиной Д степени 3;
4) степень 2 имеют вершины № 1 и 2, но только вершина № 1 связана, кроме Ж, с
вершиной степени 3 (№ 7), поэтому вершина № 1 – это Г
5) по таблице определяем протяжённость дороги из пункта Г в пункт Ж, она равна 9.
6) Ответ: 9.

78. ЕГЭ-1

78
ЕГЭ-1

79. ЕГЭ-1

79
ЕГЭ-1
2. На рисунке справа схема дорог Н-ского района изображена в
виде графа, в таблице содержатся сведения о длинах этих дорог (в
километрах). Так как таблицу и схему рисовали независимо друг от
друга, то нумерация населённых пунктов в таблице никак не
связана с буквенными обозначениями на графе. Известно, что
длина кратчайшего пути из пункта А в пункт Ж не больше 15.
Определите, какова длина кратчайшего пути из пункта Д в пункт В.
В ответе запишите целое число – так, как оно указано в таблице.
П1
П1
П2
11
П3
7
П4
5
П2
П3
П4
11
7
5
15
П6
8
12
14
П7
А
Б
8
Д
14
9
Е
Г
6
10
9
В
10
15
13
П6
12
13
П5
П7
П5
6
Ж

80. ЕГЭ-1

80
ЕГЭ-1
1)
сложность этой задачи в том, что схема симметрична; легко понять, что без дополнительных данных
(используя только степени вершин – количество связанных с ними рёбер) мы не сможем различить
П1 П2 П3 П4 П5 П6 П7
вершины А и В, Г и Е, Д и Ж
Г, Е П1
11 7
5
12 4
2) определим степени вершин:
Б
Д, Ж
Д, Ж
А, В
Г, Е
А, В
3)
4)
5)
6)
7)
П2
П3
П4
П5
П6
П7
11
7
5
12
13
15
15
13
8
14
10
9
6
8
10
9
6
14
4
3
3
2
4
2
как и видно из рисунка, у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины
степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с
двумя вершинами степени 2
для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ; мы не знаем,
где какой маршрут, но точно знаем, что эти четыре маршрута
П3 П1 П7 = 7 + 12 = 19
П3 П6 П5 = 10 + 6 = 16
П4 П1 П7 = 5 + 12 = 17
П4 П6 П5 = 9 + 6 = 15
из дополнительного условия (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше
15.) находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А; в итоге получается
кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ
длиной 19
Ответ: 19.

81. ЕГЭ-1

81
ЕГЭ-1

82. ЕГЭ-1

82
ЕГЭ-1
26

83. ЕГЭ-1

83
ЕГЭ-1
3. На рисунке изображена схема дорог Н-ского района, в таблице
звёздочкой обозначено наличие дороги из одного населённого
пункта в другой. Отсутствие звёздочки означает, что такой дороги
нет. Каждому населённому пункту на схеме соответствует его номер
в таблице, но неизвестно, какой именно номер. Определите, какие
номера населённых пунктов в таблице могут соответствовать
населённым пунктам A и G на схеме. В ответе запишите эти два
номера в возрастающем порядке без пробелов и знаков
препинания.

84. ЕГЭ-1

84
ЕГЭ-1
Сопоставим населённые пункты графа и населённые пункты в таблице. Необходимо
определить номера населенных пунктов A и G. Из F ведут шесть дорог. Таким образом F
— 3. Заметим, что из пунктов A и G нет дороги в населённые пункты C и E, из которых
идут 2 дороги. Следовательно, пункты 6 и 7 это либо A, либо G.
Ответ: 67.

85. ДЗ ЕГЭ-1

85
ДЗ ЕГЭ-1

86. ДЗ ЕГЭ-1

86
ДЗ ЕГЭ-1

87. ДЗ ЕГЭ-1

87
ДЗ ЕГЭ-1

88.

88

89. ДЗ ЕГЭ-1

89
ДЗ ЕГЭ-1

90.

90

91. ДЗ ЕГЭ-1

91
ДЗ ЕГЭ-1

92.

92

93. ДЗ ЕГЭ-1

93
ДЗ ЕГЭ-1
24

94.

94

95. ДЗ ЕГЭ-1

95
ДЗ ЕГЭ-1

96. ДЗ ЕГЭ-1

96
ДЗ ЕГЭ-1

97. ДЗ ЕГЭ-1

97
ДЗ ЕГЭ-1

98. ДЗ-ЕГЭ1

98
ДЗ-ЕГЭ1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

107. До/за

107
До/за

108. До/за

108
До/за
10

109. Доза

109
Доза

110. До/за

110
До/за
11

111. ДО/ЗА

111
ДО/ЗА

112. До/за

112
До/за
33

113. До/за

113
До/за

114. До/за

114
До/за
4

115. До/за

115
До/за

116. До/за

116
До/за
11

117. До/за

117
До/за

118. До/за

118
До/за
8

119. До/за

119
До/за

120. До/за

120
До/за
Ж

121. До/за

121
До/за

122.

122

123.

123

124.

124

125.

125

126.

126

127. До/за

127
До/за

128. До/за

128
До/за
9

129. До/за

129
До/за

130. До/за

130
До/за
24

131. До/за

131
До/за

132. До/за

132
До/за
9

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

133
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]

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

134
Источники иллюстраций
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. авторские материалы
English     Русский Правила