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

Сегодня на уроке!

• Повторение пройденного материала
• Изучение новой темы
• Работа с учебником
• Работа с рабочей тетрадью на печатной основе
• Практическая работа

Тема урока:

• 14.03.12

Цели и задачи урока:

• * расширить представление о видах информационных моделей * сформировать представление о графах как наглядном средстве представления и состава системы * развивать умения построения схем.

Вспомним!

• Что такое модель?
• Что такое информационная модель?
• Какие виды информационных моделей нами уже изучены?
• Где применяются схемы, чертежи?
• Всякая ли схема может претендовать на полноту представления информации об объекте?

Модель – это упрощенное представление реального объекта Информационная модель - набор свойств, содержащий всю необходимую информацию об исследуемом объекте. Схема – это представление объекта в общих, главных чертах с помощью условных обозначений Смешанные модели Чертёж - условное графическое изображение Пример блок-схемы алгоритма

• Подъехал Иван Царевич к камню

• Направо пойдешь?

• Нет

• Да

• Голову сложишь

• Коня потеряешь

Учебник, стр. 112 №6

• Придумайте задачу, модель решения которой может быть представлена следующей блок-схемой:

Сказка «Колобок»

• начало

• катится

• спеть песенку

• встретил зверя

• зверь лиса?

• Прощай колобок

• конец

• Да

• Нет

Подумаем!

• С помощью каких информационных моделей можно отразить отношения между людьми?
• Как показать дороги и расстояния между городами?
• Способна ли информатика показать такие отношения?

Да! Это можно осуществить с помощью графов. ГРАФЫ

• Москва, 2007

Понятие «Граф»

• Что такое граф?
• Какие бывают графы?
• Где встречаются графы в повседневной жизни?

Понятие «Граф»

• Графы –это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых
• Научные графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу.

Понятие «Граф»

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

Состав графа

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

• А

• В

• С

• петля

• ребро

• дуга

Изображение вершин Неориентированный граф -

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

• Маша

• Юра

• Аня

• Витя

• Коля

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

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

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

• Маша

• Юра

• Аня

• Витя

• Коля

• Граф, отражающий отношение «пишет письма».

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

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

• Москва, 1147

• Переславль Залесский, 1152

• Владимир, 1108

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

• 1182

• 158

• 127

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

• С помощью графов часто упрощается решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др.
• Помогают графы в решении математических и экономических задач.

С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Примеры графов

• Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде графа.
• Система «Школьный урок», состоящая из следующих элементов: ученик, учитель, учебник, тетрадь, классный журнал, классная доска, мел, парта, учительский стол, классная комната.
• Круговорот воды в природе.

Познакомимся с основными понятиями теории графов при решении задачи.

• Познакомимся с основными понятиями теории графов при решении задачи.

• Задача:
• Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

• Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.

• 1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему

• 2. Ниже изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом

• Количество ребер графа соответствует количеству рукопожатий, совершенных молодыми людьми. Их - 10.

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

РТ №64 стр.80

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

• A

• B

• C

• D

• E

• 1)

• 2)

• A

• C

• E

• B

• D

• 1

• 3

• 4

• 1

• 1

• 1

• 1

• 2

• 3

• 4

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

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

• компьютер

• суперкомпьютер

• рабочая станция

• персональный компьютер

• настольный

• портативный

• карманный

• Всем хорошо известно понятие «родословное дерево» и вы можете изобразить в такой форме ваши родственные отношения.

Практическая работа

• Работа №10,
• задание 3, стр. 205

РТ №59 стр. 77

• Начертите граф, на котором были бы изображены высказывания:
• «8 кратно 2», «8 кратно 4», «8 кратно 1»,
• «4 кратно 2», «2 кратно 1», «4 кратно 4», «2 кратно 2».
• Каждая стрелка на графе должна означать «кратно»

«8 кратно 2», «8 кратно 4», «8 кратно 1», «4 кратно 2», «2 кратно 1», «4 кратно 4», «2 кратно 2».

• Как изобразим вершины графа?
• Сколько будет вершин?
• Как изобразим отношения между вершинами?
• Как изобразим вершину «4 кратно 4»?

РТ №59 стр. 77 РТ №65 стр.80

	A	B	C	D
A		4		5
B	4		3	6
C		3
D	5	6

• Постройте взвешенный граф,
• соответствующей таблице.
• Что называется взвешенным графом?
• Как обозначим вершины?
• Сколько будет вершин?
• Как обозначим отношения между
• вершинами?

Решение: РТ №65 стр.80

	A	B	C	D
A		4		5
B	4		3	6
C		3
D	5	6

Самое главное

• Граф - наглядное средство представления состава и структуры системы.
• Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная – ребром.

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

• § 2.10 (2),
• РТ № 60,61 (стр.78)

Проверь!

• Автобус

• Пассажир

• Контролер

• Билет

• Остановка

• Водитель

• управляет

• садится

• приходит

• покупает

• продаёт

Спасибо за урок!