7.11_Derevya

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

9 класс

2. Повторение:

Как называется этот рисунок?
Назовите элементы графа?
Он взвешенный или нет?
Что нужно сделать, что бы он стал взвешенным?
Как называется эта таблица?

3. Повторение

В чем особенность этого графа?
Что можно изображать с помощью таких схем?
Сформулируйте тему урока

4. Тема: Деревья. Перебор вариантов с помощью дерева.

5. Цели урока:

Научиться • отличаются деревья графы от графов?
• отличать основные элементы графа дерева
• решать задачи на перебор вариантов с помощью
дерева

6. Задача: Собраться в путешествие, чтобы ничего не забыть.

7. Дерево — граф, в котором вершины расположены на разных уровнях, есть строгая иерархия и нет циклов.

Дерево — граф, в котором вершины
расположены на разных уровнях,
есть строгая иерархия и нет циклов.
Узлы, из которых не выходят рёбра,
называют листьями
Вершины дерева называют узлами.
Главный узел – корень дерева.
Его обычно изображают наверху.

8. Путь из корня в узлы называют ветвью.

Путь из корня в узлы называют ветвью.

9.

Распредели элементы дерева по группам.

10.

Чему равна высота дерева,
которое Никита увидел в
учебнике биологии?

11. Что будет, если убрать корень дерева?

У нас получится одно или
несколько новых деревьев.
Какие ещё поддеревья есть в этом графе?

12.

13. Какие узлы — потомки узла Верх?

Какие узлы — потомки узла Верх?
Какой узел — предок
узла Верх? Одежда
Футболки, рубашки

14. Решение задачи: Собраться в путешествие, чтобы ничего не забыть.

15. Самостоятельно построить дерево

Никита делал задание по географии. Ему необходимо
заполнить дерево нужными узлами.

16. Самопроверка

Никита делал задание по географии. Ему необходимо
заполнить дерево нужными узлами.

17. С помощью дерева перебора найдите все трёхзначные числа, меньшие 300, сумма цифр которых равна 6.

Моделирование, 9 класс
17
С помощью дерева перебора найдите
все трёхзначные числа, меньшие 300,
сумма цифр которых равна 6.
Сколько чисел вы нашли?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
11

18.

Моделирование, 9 класс
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

20. Домашняя работа

1. Выполнить задания из Яндекс Учебника
2. Решить задачи на слайде 21, 22, 23

21. Перебор вариантов (ПОСТРОИТЬ ДЕРЕВО)

Моделирование, 9 класс
21
Задача №1
Перебор вариантов (ПОСТРОИТЬ ДЕРЕВО)
Разведчик выяснил, что ключ к замку от сейфа состоит из
трёх символов, причём могут использоваться буквы из
алфавита {A, B, C, D}. Две одинаковые буквы не могут
стоять рядом. Рядом с буквой D обязательно должна
стоять буква A. Если в ключе есть буква B, то там не
может быть буквы C.
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Сколько возможных ключей?
http://kpolyakov.spb.ru

22. Перебор вариантов (ПОСТРОИТЬ ДЕРЕВО)

Моделирование, 9 класс
22
Задача №2
Перебор вариантов (ПОСТРОИТЬ ДЕРЕВО)
Запишите все возможные варианты расписания
пяти уроков на день из предметов:
математика(М), русский язык(Р), история(И),
английский язык(А), физкультура(Ф), причем
математика(М) должна быть вторым уроком.
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

23. Задача №3 из ГИА по информатике

24.

Моделирование, 9 класс
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Для подготовки презентации использовались материалы Яндекс Учебника

https://education.yandex.ru/