Конспект урока по информатике "Структуры данных: деревья, графы" (7класс)

МБОУ «Средняя общеобразовательная школа №9»

Конспект открытого урока информатики на тему: 

«Структуры данных: деревья, графы»

Класс: 7 (общеобразовательный)

Учитель: Воронина Елена Вальдемаровна

 Тип урока: комбинированный

Учебник: Информатика и ИКТ. 7класс. Л. Босова.

Тема:  Структуры данных: деревья, графы.

Цели урока:

    Образовательные:

•      Расширить представления учащихся о видах информационных моделей;

•      Познакомить с понятиями «дерево, граф»;

•      Научить решать некоторые задачи с помощью графа;

•      Развить умения построения графа  и дерева.

Развивающие:

Создать условия для развития умения выделять главное, сравнивать, анализировать, обобщать.

Воспитательные:

1.    Воспитывать внимательность, стремление довести дело до намеченного результата;

2.    Установление взаимных контактов и обмен опытом между учащимися и преподавателем.

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

План урока

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

2. Проверка домашнего задания – фронтальный опрос (5 мин)

3. Объяснение нового материала. (15 мин)

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

5. Физкультминутка (2)

5.Практическая работа  (10мин)

6. Подведение итогов (2 мин)

Ход урока

1. Проверка домашнего задания – фронтальный опрос.

На предыдущем уроке мы с вами рассматривали такие понятия, как «модель», «информационная модель».

Ответьте на следующие вопросы:

1.     Что такое модель?

2.     Назовите виды моделей (натурные и информационные)

3.     Приведите примеры моделей, не упомянутые в параграфе.

2. Объяснение нового материала.

Графы

В разговорной речи мы часто используем словесное (вербальное) представление информации. Например, словестное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы (Слайд 7) (на ней поселки обозначены первыми буквами своих названий)

рис.1

Это не карта местности. Здесь не выднржаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом.

Глядя на этот граф, легко понять структуру дорожной системы в данной местности. Построенный граф позволяет, апример, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути:

1)    Р-К-Б-М

2)    Р-К-Д-Б-М

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

Презентация

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

Р.Т. №59, стр.77.

5.Физкультминутка.

Обратите внимание на стены и найдите:

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

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

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

·       Деревья.

Сколько их?

6. Практическая работа  (по группам)

·       Задачник1, стр.90, №11 (2,1)

·       Интерактивный тест на доске

7. Подведение итогов

• 1 слайд

  Моделирование
  
  Исходный объект -
  Объект-заместитель -
  

• 2 слайд

  Примеры моделей
  Манекен
  Карта
  погоды
  Схема
  

• 3 слайд

  Модель создают, если:
  

• 4 слайд

  Модель создают, если:
  

• 5 слайд

  Модель создают, если:
  

• 6 слайд

  модели
  Натурные
  Информационные
  

• 7 слайд

  Р-К-Б-М
  Р-К-Д-Б-М
  

• 8 слайд

  Информационные модели.
  ГРАФЫ И ДЕРЕВЬЯ.
  

• 9 слайд

  ЦЕЛИ УРОКА:
  Расширить представления учащихся о видах информационных моделей;
  Познакомить с понятиями «дерево, граф»;
  Научить решать некоторые задачи с помощью графа;
  Развить умения построения графа и дерева.
  

• 10 слайд

  Графы
  Графы –это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.
  
  
  
  
  

• 11 слайд

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

• 12 слайд

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

• 13 слайд

  Неориентированный граф -
  граф, вершины которого соединены ребрами.
  Маша
  Юра
  Аня
  Витя
  Коля
  

• 14 слайд

  Ориентированный граф -
  граф, вершины которого соединены дугами
  Маша
  Юра
  Аня
  Витя
  Коля
  

• 15 слайд

  граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).
  Москва, 1147
  Переславль Залесский, 1152
  Владимир, 1108
  Взвешенный граф -
  182
  158
  127
  

• 16 слайд

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

• 17 слайд

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

• 18 слайд

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

• 19 слайд

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

• 20 слайд

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

• 21 слайд

  
  
  
  
  
  
  количество рукопожатий- 10.
  Примеры графов
  

• 22 слайд

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

• 23 слайд

  Задание для домашней работы
  Генеалогическое древо
  Оформить генеалогическое древо своей семьи. Написать заголовок – фамилию семьи. В окошки на дереве вписать фамилию, имя, отчество ваших родственников и себя, а так же кем они вам приходятся.
  П. 2.10, стр.101-108
  Р.Т. № 64,67, стр.80
  
  Васильева С.В.
  я
  Захарова Р.П.
  мать
  Захаров В.А.
  отец
  Захаров А.П.
  дедушка
  Захарова З.А.
  бабушка
  Бездельникова О.А.
  бабушка
  Бездельников П.И.
  дедушка
  Васильевой С.В.