Урок информатики по теме "Графы и сети"

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


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

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


Цель:  сформировать у учащихся понятие «граф» и его структуры.

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

Тип урока: урок изучения нового материала.

Вид урока: комбинированный.

Межпредметные связи: математика.

Возраст учащихся: 10 класс.

Программное обеспечение: Информатика и ИКТ И.Г.Семакин, Е.К.Хеннер, учебник для 10-11 классов, базовый уровень; компьютер; презентация к уроку

Основное содержание учебного материала

Время

Деятельность учителя

Деятельность учащихся

Результат совместной деятельности

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

Приветствие 1 мин. Организация проверки готовности класса к уроку Подготовка к уроку Готовность к уроку

2. Подготовка к восприятию

Что такое модель?
Что такое информационная модель?
Какова роль информатики в информационном моделировании?
Какова характерная особенность компьютерных информационных моделей?
Этапы разработки компьютерной информационной модели
Тема нашего урока: графы и сети. (слайд 1). Она имеет много серьезных практических приложений (транспортные перевозки, проектирование сетей коммуникаций, маршрутизация в Интернете и пр.).
Мы познакомимся с понятием «граф», с видами графов, научимся строить графы.
2 мин. Фронтальный опрос.
Объявляет тему, цели и задачи, стимулирует интерес учащихся к изучению новой темы.
Отвечают на вопросы.
Записывают тему урока
Подготовка к изучению новой темы

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

Информация о некотором реальном объекте может быть представлена по-разному. В разговорной речи мы используем словесное (вербальное) представление информации. Вот, например, словесное описание нашей области: «Волгоградская область состоит из административно-территориальных единиц — 33 районов и 6 городов областного значения. Города: ВолгоградВолжскийКамышинФролово, МихайловкаУрюпинск. По такому описанию можно представить как проехать из одного города в другой?  (Вывод делают учащиеся.) Гораздо понятнее становится из следующей схемы (слайд 2), по которой, например, можно ответить на вопрос: через какие города надо проехать, чтобы добраться из Волгограда в Урюпинск.

Сформулировано понятие «граф» и сети. Выделены его составные части: вершины и ребра. (Слайд 3)

Граф — это набор узлов (вершин) и связей между ними (ребер).

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

Как представить информацию о графе в памяти компьютера? Хранить ее в виде рисунка (растрового или векторного) неэффективно, потому что рисунок предназначен для восприятия человеком, а не компьютером. Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности. На рисунке показаны схема дорог, соответствующий ей граф и его матрица смежности: (слайд 4)

Единица на главной диагонали (выделенной серым цветом) показывает, что в графе есть петля —ребро, которое начинается и заканчивается в одной и той же вершине.
Обратите внимание, что матрица смежности симметрична относительно главной диагонали, то есть если существует ребро из вершины A в вершину B, то существует и ребро из B в A. Такой граф называют неориентированным — ребра не имеют направления и каждое из них учтено в матрице смежности дважды. Матрица смежности не дает никакой информации о том, как именно расположены узлы друг относительно друга. Для таблицы, приведенной выше, возможны, например, такие варианты, как на рисунках. (слайд 5)

Если для каждого ребра указано направление, граф называют ориентированным (или орграфом). Ребра орграфа называют дугами. Его матрица смежности не всегда симметричная. Единица, стоящая на пересечении строки A и столбца B, говорит о том, что существует дуга из вершины A в вершину B: (слайд 6).

Часто с каждым ребром связывают некоторое число — вес ребра. Это может быть, например, расстояние между городами или стоимость проезда. Такой граф называется взвешенным. Информация о таком графе хранится в виде весовой матрицы, содержащей веса ребер: (слайд 7).

У взвешенного орграфа весовая матрица не всегда симметрична относительно главной диагонали: (слайд 8).

Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти компьютера записывать в нее условный код, например, 0, –1 или очень большое число (?), в зависимости от задачи.

Другим примером ориентированного графа являются блок-схемы алгоритмов. (слайд 9) Блок-схема алгоритма представляет собой граф процесса управления некоторым исполнителем. Блоки – вершины этого графа – обозначают отдельные команды, которые отдаются исполнителю, а дуги указывают на последовательность переходов от одной команды к другой.

20 мин. Организует беседу с учащимися и подводит их к построению информационной модели на схеме, дает понятие о «графе», его структуре, подводит учащихся к формулировке определения «граф». Использует компьютерную презентацию. Отвечают на вопросы, участвуют в беседе с учителем. Делают записи. Определено понятие «граф», его структуры, изучены виды графов.

4. Первичное закрепление знаний

Задачи для коллективного решения. (слайды 10-14) 8 мин. Организует деятельность  учащихся  по определению  способов решения  задачи. Побуждение  к принятию  наиболее рационального  способа действий. Ищут  способы  решения задачи. Разрабатывают планы  действий. Составленный учащимися вместе с учителем и принятый  ими как  собственный  план  действий. Мотивация на его выполнение, на успех, на  сотрудничество в достижении  учебной задачи.

5. Самостоятельная работа по изучению нового материала.

Задачи для самостоятельного решения (слайды 15-16) 10 мин. Организует  деятельность  учащихся  по  проверке  качества  усвоения  ими знаний. Побуждает  их  к  совершенствованию. Выполняют задание с последующей проверкой в парах (меняются тетрадями)
Проверяют  качество  собственных  знаний  и знаний  своих  товарищей.
Знание  уровня  собственных  достижений,  качества  знаний,  ошибок и их причин, путей  их устранения.

6. Итог урока и постановка домашнего задания

1) Подводится итог урока (слайд 17)

2) Выставление оценок.

§ 14 (1), вопросы и задания 5, 6, 7.
Семакин И.Г., Хеннер Е.К. Информатика и ИКТ. Базовый уровень. 10 – 11 класс.

3 мин. Проверяет качество знаний  учащихся по теме

Сообщает объем и содержание домашнего задания, дает инструктаж по его выполнению

 

Отвечают на вопросы
Записывают домашнее задание.
Определена домашняя работа

7. Рефлексия

Выводы учащихся по уроку (слайд 18)
  • Сегодня я узнал…
  • Я выполнял задания…
  • Я понял, что…
  • Теперь я могу…
  • Я научился…
1 мин. Устанавливает соответствие между поставленными задачами урока и результатами, вносит коррективы; анализирует учебную деятельность. Учащиеся обмениваются мнениями по теме. Подведены итоги урока. Дан анализ работы учащихся

Литература:

  1. Семакин И.Г., Хеннер Е.К. Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов, – М. : БИНОМ. Лаборатория знаний, 2009
  2. Поляков К.Ю. Просто графы / Информатика (учебно-методический журнал для учителей информатики). – 2012. – №3.
  3. Поляков К.Ю., Шестаков А.П., Еремин Е.А. Алгоритмизация и программирование / Информатика (учебно-методический журнал для учителей информатики). – 2012. – №3.
  4. Поляков К, 2009-2010 http://kpolyakov.narod.ru