Презентация по теме: "Информационные модели на графах"

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

Урок 5. Информационное моделирование

Кенигсберг - город СЕМИ МОСТОВ

Загадка: как пройти по всем мостам, не проходя ни по одному из них дважды?

План г. Кенигсберга

Ядерный взрыв

1736 г. – решение задачи (Леонард Эйлер, математик)

Граф – средство для описания систем

Структура – определенный порядок объединения элементов, составляющих систему.

Граф – это средство для наглядного представления состава и структуры системы.

Граф состоит из вершин, связанных дугами или ребрами.

Вершины графа (точки) – элементы системы.

Линии (дуги или ребра) – связи между элементами.

линии со стрелкой (направленные);

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

линии без стрелки (ненаправленные);

связи – симметричные

Две вершины, соединенные дугой или ребром называются смежные.

Примеры графов

Дерево

– ориентированный граф с выделенной вершиной (корнем), в котором между корнем и любой вершиной существует единственный путь.

Иерархическая система – система, между частями которой установлены отношения подчиненности.

(Связь «один ко многим»).

Каждая вершина связана только с верхней и не связана больше ни с чем.

Сеть

– граф, в котором вершины связаны между собой по принципу «многие ко многим».

Пример: сетевая модель «учитель-класс».

Учитель физики

Учитель биологии

Учитель математики

11 - А

10 - А

9 - В

9 - Б

9 - А

Один учитель ведет свой предмет в разных классах, в одном классе уроки ведут разные учителя.

7 Да 7 + 10 3 + 10 Ответ конец " width="640"

Блок-схема

– это граф, отображающий последовательность выполнения действий.

Его вершины отображают отдельные действия и изображаются определенными геометрическими фигурами , а связи отображаются дугами.

начало

Числа 3 и 7

Нет

3 7

Да

7 + 10

3 + 10

Ответ

конец

Задания

1. Эйлер выяснил, что граф можно начертить одним росчерком, не отрывая карандаша от бумаги (обойти), если он имеет не более 2-х вершин, из которых выходит нечетное количество отрезков, иначе – нет. Проверим.

нельзя обойти

можно обойти

Задания

2. От Винни-Пуха до Кролика ведут 2 дороги, а от Кролика до Пятачка – три. Сколько различных путей от Винни к Пятачку, если надо зайти к кролику?

В

П

К

Решение: Число левых отрезков показывает, сколько раз нужно сложить количество правых отрезков:

3 + 3 = 6

или количество левых умножить на кол-во правых:

2*3=6

Ответ: 6 путей

Задания

3. Пять человек решили сыграть в шашки. Сколько всего партий будет сыграно, если каждый с каждым должен сыграть по одному разу? Постройте граф.

1

2

3

5

4

Решение: 4+3+2+1 = 10 игр

Задания

4. Постройте в виде графа множество геометрических фигур:

геометрический объект, линия, плоская фигура, объемное тело, прямая, круг, шар, квадрат, ломаная, трапеция, эллипс, прямоугольник, ромб, конус, кривая, призма, пирамида, параллелограмм.

9

Задания

4. Нарисуйте в виде графа систему, состоящую из одноклассников, между которыми существуют следующие взаимоотношения: дружат Андрей и Даша, Андрей и Маша, Даша и Коля, Коля и Андрей.

С кем Андрей может поделиться секретом, не рискуя, что он станет известен кому-то другому?

9

Домашнее задание

• Учебник: дополнение к Главе 2: 2.1. стр. 62.
• Постройте блок-схему какого-либо правила по русскому языку или по математике.
• Подготовиться к итоговому тесту по теме: «Информационное моделирование» (Глава 2 в учебнике, конспекты в тетради).

Источники

• Семакин И.Г. Информатика и ИКТ: учебник для 8 класса/ И.Г.Семакин, Л.А.Залогова, С.В.Русаков, Л.В.Шестакова. – 3-е изд. – М.: БИНОМ. Лаборатория знаний, 2015. – 176 с.: ил.
• Информатика. Задачник-практикум в 2 т. / Под ред. И.Г.Семакина, Е.К.Хеннера: Том 1. – М.: БИНОМ. Лаборатория знаний, 2004. – 304 с.: ил.
• Соколова О.Л. Универсальные поурочные разработки по информатике. 10 класс. М.: ВАКО, 2006. – 400 с. – (В помощь школьному учителю).
• ЦОРы к учебнику Семакина И.Г.
• tsyganskiy.professorjournal.ru
• http://offtop.ru/castles/v2_102583__.php
• http://www.kvadra.su/2009/04/26/sem-mostov-kenigsberga/
• http://ru.wikipedia.org/wiki/ Мосты_Кёнигсберга
• http://mashinku.ru/ язык-пространства-топология /
• http://ru.wikipedia.org/wiki/ Орграф
• http://www.ngfr.ru/ngd.html?neft22
• http://monar.ru/galereia/node/1191?size=_original
• www.klyaksa.net