3.02M

Category:

informatics

https_education_admoblkaluga_ru_ej_attachments_files_003_098_439

1. Что такое дерево?

1
Моделирование, 11 класс
Что такое дерево?
1
A
B
D
C
E
F
«Сыновья» А: B, C.
2
Высота дерева —
наибольшее
расстояние от
корня до листа
G
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

2. Рекурсивные определения

2
Моделирование, 11 класс
Рекурсивные определения
1) пустая структура – это дерево
2) дерево – это корень и несколько связанных с ним
отдельных (не связанных между собой) деревьев
Двоичное (бинарное) дерево:
1) пустая структура – это двоичное дерево
2) двоичное дерево – это корень и два связанных с ним
отдельных двоичных дерева («левое» и «правое»
поддеревья)
Применение:
• поиск в большом массиве неменяющихся данных
• сортировка данных
• вычисление арифметических выражений
• оптимальное сжатие данных (метод Хаффмана)
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

3. Дерево для двоичного кода

3
Моделирование, 11 класс
Дерево для двоичного кода
А
0
Б
11
В
Г
Д
101 110 111
? Можно однозначно
0
А
1
0
1
декодировать?
0
Условие Фано: ни одно из
кодовых слов не совпадет
с началом другого
кодового слова.
1
0
В
Г
Б
1
Д
тогда однозначно
декодируется!
! Все буквы должны быть в листьях!
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

4. Построение неравномерных кодов

4
Моделирование, 11 класс
Построение неравномерных кодов
По каналу связи передаются сообщения, содержащие
только шесть букв: А, И, К, Л, Н, Т. Для передачи
используется двоичный код, удовлетворяющий условию
Фано. Буквы Л и Н имеют коды 0 и 11 соответственно.
Укажите наименьшую возможную длину закодированной
последовательности для слова КАЛИТКА.
1
0
Л
1
0
0
Н
1
К
0
1
А
0
1
И
© К.Ю. Поляков, Е.А. Ерёмин, 2025
Т
К А Л И Т К А
К – 2 100
2·3 = 6
А – 2 1010 2·4 = 8
Л–1 0
1
И – 1 10110 5
Т – 1 10111 5
25
http://kpolyakov.spb.ru

5. Деревья поиска

5
Моделирование, 11 класс
Деревья поиска
Ключ – это значение, связанное с узлом дерева, по
которому выполняется поиск.
• слева от узла – узлы с
меньшими ключами
• справа от узла – узлы с
большими или равными
ключами
6
3
1
8
4
7
9
O(log N)
? Сложность поиска?
© К.Ю. Поляков, Е.А. Ерёмин, 2025
Двоичный поиск O(log N)
Линейный поиск O(N)
http://kpolyakov.spb.ru

6. Обход дерева

6
Моделирование, 11 класс
Обход дерева
Обойти дерево «посетить» все узлы по одному разу.
список узлов
КЛП – «корень-левый-правый» (в прямом порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛКП – «левый-корень-правый» (симметричный):
обойти левое поддерево
посетить корень
обойти правое поддерево
ЛПК – «левый-правый-корень» (в обратном порядке):
обойти левое поддерево
обойти правое поддерево
посетить корень
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

7. Обход дерева

7
Моделирование, 11 класс
Обход дерева
(1+4)*(9-5)
*
+
«в глубину»
1
-
4
9
5
КЛП: * + 1 4 – 9 5
префиксная форма
ЛКП: 1 + 4 * 9 - 5
инфиксная форма
ЛПК: 1 4 + 9 5 - *
постфиксная форма
Обход «в ширину»: «сыновья», потом «внуки», …
* + - 1 4 9 5
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

8. Моделирование

8
Моделирование
Игровые стратегии
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

9. Игровые стратегии

9
Моделирование, 11 класс
Игровые стратегии
Задача: найти стратегию (алгоритм игры), который
позволит получить лучший результат, если соперники
играют безошибочно.
Игры с полной информацией: можно определить, кто
должен выиграть, по начальной позиции.
Позиции:
• проигрышные – все возможные ходы ведут в
выигрышные позиции
• выигрышные – хотя бы один ход ведёт в
проигрышную позицию
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

10. Задача с кучей камней

10
Моделирование, 11 класс
Задача с кучей камней
В начале игры S камней. Ходы: «+1» (добавить 1) и «*2»
(удвоить). Выигрыш: получить 14 камней.
выигрыш за 1 ход
S
1
2
3
4
5
6
П3
В3
В2
П2
В2
П1
7
В1
8
В1
9
В1
10
В1
11
В1
12
В1
13
В1
Дерево игры:
+1
игрок 1:
+1
игрок 2:
© К.Ю. Поляков, Е.А. Ерёмин, 2025
6
5
4
*2
*2
+1
10
9
8
*2
16
http://kpolyakov.spb.ru

11. Неполное дерево игры

11
Моделирование, 11 класс
Неполное дерево игры
Задача: доказать выигрыш какого-то игрока.
Для победителя – только 1 верный ход, для
проигравшего – все возможные ответы.
S
1
П3
?
2
B3
3
B2
4
П2
5
B2
6
П1
Какая стратегия
у игрока 2?
7
В1
8
В1
9
В1
10
В1
12
В1
13
В1
игрок 1:
4
+1
5
*2
8
+1
игрок 2:
переводить игру в
проигрышную (для
игрок 1:
соперника) позицию
игрок 2:
© К.Ю. Поляков, Е.А. Ерёмин, 2025
11
В1
+1
7
*2
6
16
*2
12
*2
*2
14
24
http://kpolyakov.spb.ru

12. Задачи

12
Моделирование, 11 класс
Задачи
1. В начале игры S камней. Ходы: «+2» (добавить 2) и
«*2» (удвоить). Выигрыш: получить 25 камней.
Построить дерево игры для S = 7.
2. В начале игры S камней. Ходы: «+1» (добавить 1) и
«*3» (утроить). Выигрыш: получить 55 камней.
Построить дерево игры для S = 16.
3. В начале игры S камней. Ходы: «+2» (добавить 2),
«+3» (добавить 3) и «*2» (удвоить). Выигрыш:
получить 30 камней.
Построить дерево игры для S = 9.
4. Игра Баше. В начале игры S (S 15) камней. Ходы:
«-1» (взять 1), «-2» (взять 2) и «-3» (взять 3).
Проигрыш: взять последний камень.
Построить дерево игры для S = 12.
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

13. Ещё одна задача

13
Моделирование, 11 класс
Ещё одна задача
За один ход игрок может добавить в кучу один фантик или
увеличить количество фантиков в куче в два раза.
Игра завершается в тот момент, когда количество фантиков в
куче становится не менее 129. Победителем считается игрок,
сделавший последний ход, т. е. первым получивший кучу, в
которой 129 или больше фантиков. В начальный момент в
кучке S фантиков, 1 ≤ S ≤ 128.
Вопрос 1. Укажите такое значение S, при котором Петя не
может выиграть за один ход, но при любом ходе Пети Ваня
может выиграть своим первым ходом.
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

14. Решение

14
Моделирование, 11 класс
Решение
Вопрос 1. Укажите такое значение S, при котором Петя не
может выиграть за один ход, но при любом ходе Пети своим
первым ходом.
? Как обозначали
такую позицию?
S
Ответ:
П1
61 62 63 64 65 66 67
П1 В1 В1 В1
65·2 = 130
64
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

15. Решение

15
Моделирование, 11 класс
Решение
Вопрос 2. Найдите все значения S, при которых у Пети есть
выигрышная стратегия, причём одновременно выполняются
два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом
независимо от того, как будет ходить Ваня.
? Как обозначали
такую позицию?
S
Ответ:
31 32 33
В2
В2
П1
62 63 64 65 66 67
В2 П1 В1 В1 В1
32, 63
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

16. Решение

16
Моделирование, 11 класс
Решение
Вопрос 2. Найдите минимальное значение S, при котором
одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая
ему выиграть первым или вторым ходом при любой
игре Пети;
— у Вани нет стратегии, которая позволит ему
гарантированно выиграть первым ходом.
? Как обозначали
такую позицию?
S
Ответ:
31 32 33
В2
П2
В1
В2
62 63 64 65 66 67
П2 В2 П1 В1 В1 В1
62
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

17. Решение программой

17
Моделирование, 11 класс
Решение программой
def moves( x ):
return x+1, x*2
TARGET = 129
def gameOver( x ):
return x >= TARGET
def win1( x ): # В1 выигрыш на 1-ом ходу
return not gameOver(x) and \
any( gameOver(y) for y in moves(x) )
def lose1( x ): # П1
return all( win1(y) for y in moves(x) )
for S in range(64,0,-1):
if lose1(S): print(S) # вопрос 1
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

18. Решение программой

18
Моделирование, 11 класс
Решение программой
def win2( x ):
return any( lose1(y) for y in moves(x) )
def lose2( x ):
return all( win2(y) or win1(y)
for y in moves(x) ) and \
any( win2(y) for y in moves(x) )
for S in range(64,0,-1):
if win2(S): print(S)
# вопрос 2
for S in range(64,0,-1):
if lose2(S): print(S) # вопрос 3
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

19. Задача с двумя кучами камней

19
Моделирование, 11 класс
Задача с двумя кучами камней
В начале игры в одной куче 5 камней, во второй – S
камней. Ходы: «+1» (добавить 1) и «*2» (удвоить) для
одной из куч. Выигрыш: получить 15 камней в двух
кучах.
во второй куче
(5, 7)
во первой
куче
1 2 3 4 5 6 7 8 9
?1 B1 В1 В1 В1 В1
5 П2 В2 В2 П
6 В2 П?1 B1 В1 B1 В1 В1 В1
15+
7 B1 В1 B1 В1 B1 B1 В1
8 B1 В1 B1 В1 B1 В1
(5, 4) П1
(6, 2) П1
(6, 4) (5, 5) (10, 4) (5, 8)
(7, 2) (6, 3) (12, 2) (6, 4)
B1
B1
B1
B1
© К.Ю. Поляков, Е.А. Ерёмин, 2025
B1
B1
B1
B1
http://kpolyakov.spb.ru

20. Неполное дерево игры

20
Моделирование, 11 класс
Неполное дерево игры
выигрывает
игрок 2
5
6
7
8
1 2 3 4 5 6 7 8 9
П2 B2 B2 П1 В1 B1 В1 В1 В1
B2 П1 B1 В1 B1 В1 В1 В1
B1 В1 B1 В1 B1 B1 В1
B1 В1 B1 В1 B1 В1
все ходы
В виде таблицы:
игрок 1
игрок 2
(6, 1)
(5, 1)
(6, 2)
(5, 2)
(10, 1)
игрок 1
(7, 2)
(6, 3)
(12, 2)
(6, 4)
игрок 2
(14, 2)
(12, 3)
(12, 4)
(20, 1)
только
выигрышный ход
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

21. Моделирование

22. Что такое граф?

22
Моделирование, 11 класс
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
A
B
C
D
Список смежности:
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
© К.Ю. Поляков, Е.А. Ерёмин, 2025
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
петля
http://kpolyakov.spb.ru

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

23
Моделирование, 11 класс
Связность графа
Связный граф – это граф, между любыми вершинами
которого существует путь.
A
B
C
A
C
B
D
D
компоненты связности
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

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

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

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

25
Моделирование, 11 класс
Взвешенные графы
A
12
B
8
2
C
5
6
Весовая матрица:
A
4
D
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
вес ребра
© К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru

26. Задачи

26
Моделирование, 11 класс
Задачи
Построить матрицы смежности и весовые матрицы.
5
4
A
D
A
E
1
1
3
1
3
C
B
D
C
B
2
3
1
2
E
3
5
A
E
2
4
3
B
C
D
1
2
© К.Ю. Поляков, Е.А. Ерёмин, 2025
B
A
5
1
C
2
D
4
E
http://kpolyakov.spb.ru

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

27
Информация и информационные процессы, 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.
A
2
B
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

English Русский Rules