Выбранный для просмотра документ Подготовка_к_ЕГЭ_2015_(избранные задачи)1.ppt
Скачать материал "План урока по информатике "Введение в теорию графов" (11 класс)"
Рабочие листы
к вашим урокам
Скачать
1 слайд
Избранные задания к ЕГЭ по информатике 2015 года
Книга книгой,
а мозгами двигай!
Графы, деревья
2 слайд
5. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Б
3 слайд
A
4 слайд
A
B
5
D
G
12
25
5 слайд
A
B
5
D
8
D
G
12
25
6 слайд
A
B
5
2
C
D
8
D
G
12
25
7 слайд
A
B
E
F
G
5
2
C
10
5
4
D
8
D
G
12
25
8 слайд
A
B
E
F
G
5
2
C
10
5
4
D
8
G
D
G
12
5
25
9 слайд
A
B
E
F
G
5
2
C
10
5
4
D
8
G
24
D
G
12
5
25
10 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
D
8
G
24
D
G
12
5
25
11 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
D
G
12
5
25
12 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
G
12
5
25
13 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
G
12
8
2
5
25
14 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
G
12
8
2
5
25
15 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
12
8
2
5
25
16 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
23
G
12
8
2
5
5
25
17 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
5
24
G
23
G
12
8
2
5
5
25
18 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
5
24
G
23
24
G
12
8
2
5
5
25
19 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
5
24
G
23
24
G
12
8
2
5
5
25
25
20 слайд
A
B
E
F
G
5
2
C
10
5
4
G
5
25
D
8
G
24
25
D
B
C
E
F
G
10
5
4
G
5
24
G
23
24
G
25
12
8
2
5
5
25
21 слайд
Для решения задачи мы применили поиск решения путем построения всех возможных путей (полный перебор, теория игр).
22 слайд
15. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
А
Б
В
Г
Д
Е
Ж
И
К
Л
П
23 слайд
Для нашего графа можно записать:
П(А)=1 – из пункта в пункт А можно попасть единственным путем – оставаться на своем месте.
П(Б)=П(А)
П(В)=П(А)+П(Б)+П(Г)
П(Г)=П(А)
П(Д)=П(Б)+П(В)
П(Е)=П(Г)
П(Ж)=П(В)+П(Е)
П(И)=П(Д)
П(К)=П(Е)
П(Л)=П(И)+П(Д)+П(Ж)+П(К)
А
Б
В
Г
Д
Е
Ж
И
К
Л
24 слайд
П(А)=1
П(Б)=П(А)
П(Г)=П(А)
П(В)=П(А)+П(Б)+П(Г)
П(Д)=П(Б)+П(В)
П(Е)=П(Г)
П(Ж)=П(В)+П(Е)
П(И)=П(Д)
П(К)=П(Е)
П(Л)=П(И)+П(Д)+П(Ж)+П(К)
Выбирая подходящий порядок вычислений получим
П(А)=1
П(Б)=П(А)=1
П(Г)=П(А)=1
П(В)=П(А)+П(Б)+П(Г)=1+1+1=3
П(Д)=П(Б)+П(В)=1+3=4
П(Е)=П(Г)=1
П(Ж)=П(В)+П(Е)=3+1=4
П(И)=П(Д)=4
П(К)=П(Е)=1
П(Л)=П(И)+П(Д)+П(Ж)+П(К)=4+4+4+1=13
А
Б
В
Г
Д
Е
Ж
И
К
Л
Рабочие листы
к вашим урокам
Скачать
Выбранный для просмотра документ Урок Введение в теорию графов 11 класс.docx
Скачать материал "План урока по информатике "Введение в теорию графов" (11 класс)"
Рабочие листы
к вашим урокам
Скачать
Рабочие листы
к вашим урокам
Скачать
6 661 833 материала в базе
Настоящий материал опубликован пользователем Гайдыш Лариса Васильевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
8 ч.
Мини-курс
5 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.