10-1_Информация 2. Информатика и информация Что можно делать с информацией Измерение информации

• Название: Информатика и информация Что можно делать с информацией Измерение информации
• Дата: 26.10.2022
• Размер: 6.84 Mb.
• Имя файла: 10-1_Информация 2.ppt
• Тип: Документы; #755292
• страница: 10 из 10

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

	A	B	C	D	E
A		2	4		6
B	2		1
C	4	1		5	1
D			5		3
E	6		1	3

A


B


С


E


С


D


С


D


E


D


2


4


6


2


4


6


1


3


1


3


9


7


5


8


4


1


3


7


дерево возможных путей


Определите кратчайший путь между пунктами A и D.

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

	A	B	C	D	E
A		2	4
B	2		1		7
C	4	1		3	5
D			3		3
E		7	5	3

Определите кратчайший путь между пунктами A и E.

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

	A	B	C	D	E
A			3	1
B			4		2
C	3	4			2
D	1
E		2	2

Определите кратчайший путь между пунктами A и B.

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

	A	B	C	D	E
A			3	1	1
B			4
C	3	4			2
D	1
E	1		2

Определите кратчайший путь между пунктами A и B.

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

	A	B	C	D	E
A			3	1	4
B			4		2
C	3	4			2
D	1
E	4	2	2

Определите кратчайший путь между пунктами A и B.

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

	A	B	C	D	E
A				1
B			4		1
C		4		4	2
D	1		4
E		1	2

Определите кратчайший путь между пунктами A и B.

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

Рёбра имеют направление (начало и конец), рёбра называю дугами.


Васюки


Солнцево


Грибное


Ягодное


A


B


C


D


12


8


5


4


6


12


8


5


4


6

	A	B	C	D
A		12	8
B	12		5	6
C				4
D			4

Весовая матрица может быть несимметрична!


!

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

	A	B	C	D	E
A			3	1
B	2		4		2
C	3
D	1
E			2

	A	B	C	D	E
A			5	1
B			6	4
C	3	4			3
D		2
E			3

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

	A	B	C	D	E
A			3	1	4
B			4		2
C		4			2
D
E	4		2

	A	B	C	D	E
A				1
B			4		1
C	3	4		4	2
D	1	2	4
E	1	1	2

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

Ж


А


Б


В


Г


Д


Е


1


1


1


1+1+1=3


1


1+1+1+1+3=7


NЖ= NД + NБ + NГ + NВ + NЕ


!


1





А


Б


B


Г


Д


Е


Ж


З


И


К





А


Б


B


Г


Д


Е


Ж


З


И


К





А


Б


B


Е


И


К


Г


Д


Ж


З





А


Б


B


Е


И


К


Г


Д


Ж


З

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

А


Б


В


Г


Д


Е


Ж


И


К


Л


Сколько существует различных путей из города А в город Л, не проходящих через B?





А


Б


В


Г


Д


Е


Ж


И


К


Л


Сколько существует различных путей из города А в город Л, проходящих через Д?





Сколько существует различных путей из города А в город Л, проходящих через Д?


А


Б


В


Г


Д


Е


Ж


И


К


Л

Конец фильма

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

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

http://overhealth.ru
https://ufhealth.org
http://wmposters.com
http://ozon.ru
http://www.bikeshot.ru
http://ru.wikipedia.org
http://salestores.com
http://gimp-werkstatt.de
http://frontal-cortex.tumblr.com
http://www.intermedia.kg
http://pc-azbuka.ru
авторские материалы