Конспект урока «Графы» по информатике

Урок на тему:

Решение задач из материалов ЕГЭ по теме «Графы» (2 урока)

Цель: подготовка к ЕГЭ по информатике и ИКТ.

Задачи:

• повторить основные понятия теории графов;

• разобрать задачи, встречающиеся в ЕГЭ по информатике и ИКТ.

Тип урока-практикума: Комбинированный.

Метод обучения: объяснительно-иллюстративный.

Оборудование: компьютер, проектор, Презентация1.ppt, дидактический материал "Задачи" (Приложение1).

Время проведения 1 урока: 45 минут.

Структура урока:

1. Орг. момент (2 мин).

2. Повторение изученного материала (10 мин).

3. Разбор задач (15 мин).

4. Решение задач у доски (15 мин.)

5. Заключение урока (3 мин.)

Ход урока.

1. Оргмомент.

2. Повторение материала.

Графы - это отличный инструмент для наглядного решения широкого круга задач. Этот урок наглядно демонстрирует, что владея таким надежным инструментом, как теория графов, можно решить множество задач из материалов ЕГЭ, даже создать выигрышную стратегию игры, т.е. решить задачу ЕГЭ из части С3.

Основные понятия теории графов. (Слайд №1.)

• Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек.

• Степень вершины называется число ребер графа, которым принадлежит эта вершина.

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

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

• Граф называется несвязным, если существуют хотя бы две вершины несвязные путем

• Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь

Закрепление основных понятий теории графов. Выполнить задания. (Слайд №2.)

Область применения графов. (Слайд №3.)

• Для организации данных

• Классификация объектов

• Описания структуры

• Для решения задач, в которых надо найти

  • Все существующие решения

  • Самое короткое решение или длинное решение

  • Разработать стратегию игры

• И так далее.

Отыскание пути в графе. (Слайд №4-5.)

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

Разбор задачи с решением.

Матрицы графов. (Слайд №7.)

При большом числе вершин и ребер рисунок графа теряет свою наглядность. В этом случае удобнее представить граф в виде матрицы.

Задачи из ЕГЭ.

Слайд №8 - A10 (базовый уровень)

Тема: "Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку".

Слайд №9 – В9

Слайд №10 – В13

Слайд №11 - C3 (высокий уровень, время - 30 мин)

Тема: "Дерево игры. Поиск выигрышной стратегии".

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

Используемая литература.

1. Л. Ю. Березина Графы и их применение: Пособие для учителей.- Москва: Просвещение, 1979 г.

2. Учебник Н.Д.Угринович Информатика и ИКТ, 11 класс. Профильный уровень.