Многообразие схем. Информационные модели на графах. Использование графов при решении задач

Содержание

Слайд 2

Ключевые слова

Схема
Граф
Сеть
Дерево

Ключевые слова Схема Граф Сеть Дерево

Слайд 3

Схема - это представление объекта в общих, главных чертах с помощью условных

Схема - это представление объекта в общих, главных чертах с помощью условных
обозначений.

Схема радиоприёмника

Многообразие схем

Слайд 4

Жидкокристаллический дисплей

Схема

Оригинал

Жидкокристаллический дисплей Схема Оригинал

Слайд 5

Схема зала театра им. Вахтангова

Схема зала театра им. Вахтангова

Слайд 6

Схема кабинета информатики

Что можно узнать из этой схемы?

Лекционные места

РМУ

РМП

?

Схема кабинета информатики Что можно узнать из этой схемы? Лекционные места РМУ РМП ?

Слайд 7

Схема типовой квартиры

ВХОД

Сколько комнат в квартире?
Какова площадь каждой из них?
Каковы длина и

Схема типовой квартиры ВХОД Сколько комнат в квартире? Какова площадь каждой из
ширина комнат?
Из какой комнаты есть выход на балкон?
Какова площадь коридора?
Где на кухне находятся плита и раковина?

Давайте обсудим

?

Слайд 8

Схема района Жулебино (г. Москва)

Схема района Жулебино (г. Москва)

Слайд 9

Схема движения электропоездов

Показывает:
последователь-ность станций
расположение станций по зонам удаления от Москвы
станции пересадок (узловые)

Схема движения электропоездов Показывает: последователь-ность станций расположение станций по зонам удаления от Москвы станции пересадок (узловые)

Слайд 10

Схема метро Санкт-Петербурга

Метро Санкт-Петербурга - самое глубокое в мире. Глубина многих станций

Схема метро Санкт-Петербурга Метро Санкт-Петербурга - самое глубокое в мире. Глубина многих
– свыше 70 метров, а спуск на эскалаторе может занимать больше трех минут!

Слайд 11

Карта центра Санкт-Петербурга

Покажите досто- примечательности, представленные на карте.

?

Карта центра Санкт-Петербурга Покажите досто- примечательности, представленные на карте. ?

Слайд 12

Пример блок-схемы алгоритма

Пример блок-схемы алгоритма

Слайд 13

Чертёж - условное графическое изображение предметов с точным соотношением размеров, получаемое методом

Чертёж - условное графическое изображение предметов с точным соотношением размеров, получаемое методом
проецирования. Он даёт представление о форме, величине, масштабе изображения предмета.

Болт и гайка из стали

Многообразие схем

Слайд 14

Информационные модели на графах

Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой)

Информационные модели на графах Граф состоит из вершин, связанных линиями. Направленная линия
называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

петля

ребро

дуга

Слайд 15

Изображение вершин графа

Изображение вершин графа

Слайд 16

Неориентированный граф

С помощью таких графов могут быть представлены схемы двухсторонних (симметричных)

Неориентированный граф С помощью таких графов могут быть представлены схемы двухсторонних (симметричных)
отношений.

Граф, отражающий отношение «переписываются» между объектами класса «дети»

Неориентированный граф - граф, вершины которого соединены ребрами.

Слайд 17

Граф отношения «переписываются»

Цепь – путь по вершинам и ребрам, включающий любое

Граф отношения «переписываются» Цепь – путь по вершинам и ребрам, включающий любое
ребро графа не более одного раза.
Цикл – цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью.

Приведите примеры цепи и цикла.

?

Слайд 18

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

Ориентированный граф - граф, вершины которого соединены дугами.

Граф,

Ориентированный граф Ориентированный граф - граф, вершины которого соединены дугами. Граф, отражающий
отражающий отношение «пишет письма».

Приведите примеры цепи и цикла.

?

С помощью таких графов могут быть представлены схемы односторонних отношений.

Слайд 19

Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную

Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную
информацию (вес).

Каким весом характеризуются вершины
и дуги данного графа?

?

Взвешенный граф

Слайд 20

Семантическая сеть

Семантическая сеть

Слайд 21

Информационные модели на графах

Иерархия - это расположение частей или элементов целого в

Информационные модели на графах Иерархия - это расположение частей или элементов целого
порядке от высшего к низшему.

Отношения подчиненности в школе

Слайд 22

Классификация компьютеров

Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует

Классификация компьютеров Дерево – граф иерархической структуры. Между любыми двумя его вершинами
единственный путь. Дерево не содержит циклов и петель.

Информационные модели на графах

Слайд 23

Чемпион

Финалисты

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Укажите перечисленные объекты у дерева

Корень – главная

Чемпион Финалисты Участники ½ финала Участники ¼ финала Первоначальные игроки Укажите перечисленные
вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.

Олимпийская система спортивных соревнований

?

Информационные модели на графах

Слайд 24

Файловая структура

Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней.

?

Файловая структура Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней. ?

Слайд 25

Графы при решении задач

Сколькими способами можно рассадить в ряд на три стула

Графы при решении задач Сколькими способами можно рассадить в ряд на три
трёх учеников? Выписать все возможные случаи.

Чтобы выписать все случаи, решение можно представить в виде дерева.

?

Слайд 26

Решение в виде дерева

О

На первый стул посадим любого ученика: А,В,С

Если на первом

Решение в виде дерева О На первый стул посадим любого ученика: А,В,С
стуле сидит ученик А, то на второй стул можно посадить В или С. Действуем аналогично и для других учеников.

Очевидно, что третий стул в каждом случае займёт оставшийся ученик

А

В

С

В

С

А

С

А

В

С

В

С

А

А

В

Выпишем все возможные случаи:
А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А.