Информационные модели на графах. Пути в графах

Разделы: Информатика, Конкурс «Презентация к уроку»


Презентация к уроку

Загрузить презентацию (2 МБ)


Обучающие цели: усвоение новых знаний учащихся о моделях; формирование представления о графах как наглядном средстве представления структуры и состава системы.

Воспитательные цели: воспитание уважения к мнению другого, умения вести диалог, находчивости, ответственности за свою работу в коллективе; создать условия для воспитания демократизации отношений между учителем и учащимися.

Развивающие цели: развитие приемов умственной деятельности, логического и пространственного мышления, внимания, навыков коммуникативной работы;

Тип урока: объяснение нового материала.

Организационная форма: беседа

Оборудование:мультимедийный проектор, экран.

План урока

1.Организационный момент

2. Изучение нового материала.

3. Применение полученныхзнаний.

4. Закрепление нового материала.

5. Подведение итого урока.Домашнее задание.

Этапы урока Деятельность учителя Деятельность учащегося
1. Орг. момент Здравствуйте. Садитесь.  
Проверьте, чтобы у вас на партах лежала рабочая тетрадь, ручка. Учащиеся проверяют готовность к уроку.
2. Изучение нового материала. Давайте вспомним, что мы называем схемой? Ответ:Схема – это представление некоторого объекта в общих, главных чертах с помощью условных обозначений.
Для чего мы используем схемы? Ответ:Схемы мы используем для представления внешнего вида объекта и его структуры.
Какие виды схем вы знаете? Ответ:генеалогическое дерево, электрическая схема,географическая карты, схема метро, схема движения автотранспорта, схема эвакуации и т.д.
Мы с вами повторили, что схемы нам  дают представление о некоторых объектах в виде условных обозначений и знаков.  
Но иногда нам необходимо представление систем некоторых объектов и ее структуры, например, в наглядном виде представленные дороги, которые соединяют населенные пункты. Для этого представления мы будем использовать графы.  
Тема нашего урока: "Информационные модели на графах. Пути в графах".(слайд 1) Учащиеся записывают тему в тетрадях.
Так что же такоеграф? Попробуем сформулировать определение сами? Учащиеся сами формулируют определение.
Запишем определение Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними.(слайд 2) Учащиеся записывают определение в тетрадь.
Также запишем:

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

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

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

(слайд 2)

Учащиеся записывают определение и понятия в тетрадь.
Граф может быть представлен в виде списка дуг, графически или с помощью таблицы смотри таблицу. (слайд 3) Учащиеся записывают таблицу в тетрадь.
Списки дуг Графическая форма Табличная форма
(АВ; 7),

(BC; 4)

(CD; 8)

  А В С
А     3
В     4
С 3 4  
 
Путь в графе - это конечная последовательность вершин графа, где каждая из вершин соединена со следующей в последовательности вершиной как минимум одним ребром (дугой).(слайд 4) Учащиеся записывают определение в тетрадь.
Ребята на уроках математики вы наверное изучали теорему"Неравенства треугольника". Давайте вспомни ее?  
Неравенство треугольника - если длина любой стороны треугольника не превосходит сумму длин двух его других сторон.(см. слайд ) Но эту теорему мы с вами начнем применять со следующего урока.(слайд 5) Учащиеся записывают определение в тетрадь.
3. Практические задания. А сейчас мы на практики отработаем тему. Давайте решим задачи.  
Задача 1. Домики трех поросят на полянесоединены несколькими тропинками.Сколько путей может быть?

Решение: 1*2=2 пути(слайд 6,7)

Решают письменно задачу.
Задача 2. Красная Шапочка пошла к бабушке пирожки отнести. Тропинок несколько. Сколько путей она может выбрать?

Решение: 3*2=6 пути(слайд 8,9)

Решают письменно задачу.
Задача 3. Графы помогут нам разгадать ребусы:

С “Ё” - колючий, с “У” - ползучий. Кто это?

Сколько всего путей может быть?

Решение: 2*1 = 2 пути (слайд 10)

Ответы: ёж, уж
Задача 4. Послушайте стихотворение.

С буквой “Н”, мои друзья,
Ничего не значу я,
“Н” на “С” перемените –
Смело в суп меня кладите.
Не берите с буквой “М” -
Я пальто у вас проем.

Сколько всего путей может быть?

Решение: 3*1=3 пути(слайд 11)

Ответы: ноль, соль, моль
Задача 5. В волшебном лесу на тропинках растут не грибы, а буквы. Какие слова получатся, если пройти по тропинкам и собрать буквы?

Сколько всего путей может быть?

Решение:2*2*2=8 путей (слайд 12)

Ответы: сок, сел, сек, рок, рол, рел, рек и т.д.;
Задача 6. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение:нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

(слайд 13)

Учащиеся рисуют графы на доске.

Ответ: нет

Задача №7. Четыре мышонка решили соединить свои норки подземными ходами. Для этого они обозначили каждую нору и дом Катуси числом букв в имени хозяина. Соедини все пары норок, у которых сумма номеров – нечетное число.

Решение: см.слайд (вершин 5, ребер 6) (слайд 14)

Решают письменно задачу.
Задача №8.Соединить все пары норок у которых произведение номеров не больше 20.

Решение: см.слайд (вершин 4, ребер 3) (слайд 15)

Решают письменно задачу.
Задача №9. Соединить все пары норок, у которых разность номеров равна 1 (из большего номера вычитается меньший)

Решение: см.слайд (вершин 5, ребер 4) (слайд 16)

Решают письменно задачу.
Задача №10.Соединить все пары норок, у которых сумма номеров меньше 9.

Решение: см.слайд (вершин 3, ребер 2) (слайд 17)

Решают письменно задачу.
4. Закрепление нового материала Давайте с вами решим задачи в виде самостоятельной работы. Каждую задачу вы решаете самостоятельно, а задания будем проверять все вместе.(слайд 18-27) Решают с.р. самостоятельно.
Ответы к самостоятельной работе:

1 вопрос: 6

2 вопрос: по желтой  линии

3 вопрос: 9

4 вопрос: 6

5 вопрос: 6

6 вопрос: 5

7 вопрос: 5

 
5. Подведение итога урока. Домашнее задание. Вот и подошел к концу наш урок.  
Что нового вы узнали? Учащиеся отвечают.
Что понравилось на уроке? Учащиеся отвечают.
Запишите домашнее задание. Выучить все определения и решить задачу: Соединить все пары норок, у которых произведение номеров делится на 7.(слайд 28) Ответ: (вершин 5, ребер 4)
Урок окончен.