В последние годы в школьный курс информатики вошла тема “Графы”, что связано прежде всего с включением соответствующих задач в варианты ЕГЭ и ГИА. Тема эта глубокая и интересная, имеет много практических приложений (транспортные перевозки, проектирование сетей коммуникаций, маршрутизация в Интернете и другие). В школьном курсе информатики (на базовом уровне) “математическое” понятие графа не требуется, но изучается в профильных классах.
Задача нашего урока — представить минимальный материал, необходимый для решения задач ЕГЭ и ГИА на графы (задачи А2, B9 , В13 и С2 ), для освоения которого достаточно 2–3 уроков. Приводятся несколько способов решения этих задач, так что каждый может выбрать то, что ему по душе. Кроме того, рассмотрение объекта с разных сторон способствует пониманию его сущности.
Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Просмотр содержимого документа
«Решение задач из материалов ЕГЭ по теме «Графы» »
Урок на тему:
Решение задач из материалов ЕГЭ по теме «Графы» (2 урока)
Цель: подготовка к ЕГЭ по информатике и ИКТ.
Задачи:
повторить основные понятия теории графов;
разобрать задачи, встречающиеся в ЕГЭ по информатике и ИКТ.
Тип урока-практикума: Комбинированный.
Метод обучения: объяснительно-иллюстративный.
Оборудование: компьютер, проектор, Презентация1.ppt, дидактический материал "Задачи" (Приложение1).
Время проведения 1 урока: 45 минут.
Структура урока:
Орг. момент (2 мин).
Повторение изученного материала (10 мин).
Разбор задач (15 мин).
Решение задач у доски (15 мин.)
Заключение урока (3 мин.)
Ход урока.
1. Оргмомент.
2. Повторение материала.
Графы - это отличный инструмент для наглядного решения широкого круга задач. Этот урок наглядно демонстрирует, что владея таким надежным инструментом, как теория графов, можно решить множество задач из материалов ЕГЭ, даже создать выигрышную стратегию игры, т.е. решить задачу ЕГЭ из части С3.
Основные понятия теории графов. (Слайд №1.)
Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек.
Степень вершины называется число ребер графа, которым принадлежит эта вершина.
Путем графа от А до E называется такая последовательность ребер, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Циклом в графе называется путь, в котором совпадают его начальная и конечная вершины.
Граф называется несвязным, если существуют хотя бы две вершины несвязные путем
Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь
Закрепление основных понятий теории графов. Выполнить задания. (Слайд №2.)
Область применения графов. (Слайд №3.)
Для организации данных
Классификация объектов
Описания структуры
Для решения задач, в которых надо найти
Все существующие решения
Самое короткое решение или длинное решение
Разработать стратегию игры
И так далее.
Отыскание пути в графе. (Слайд №4-5.)
Дерево - одно из наиболее часто встречающихся понятий в теории графов. С помощью дерева можно подсчитать число изомеров химического соединения, решать комбинаторные задачи, использовать для наглядного описания вероятностей, находить кратчайший путь.
Разбор задачи с решением.
Матрицы графов. (Слайд №7.)
При большом числе вершин и ребер рисунок графа теряет свою наглядность. В этом случае удобнее представить граф в виде матрицы.
Задачи из ЕГЭ.
Слайд №8 - A10 (базовый уровень)
Тема: "Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку".
Слайд №9 – В9
Слайд №10 – В13
Слайд №11 - C3 (высокий уровень, время - 30 мин)
Тема: "Дерево игры. Поиск выигрышной стратегии".
3. Дискуссия по результатам выполняемых заданий.
Используемая литература.
Л. Ю. Березина Графы и их применение: Пособие для учителей.- Москва: Просвещение, 1979 г.
Учебник Н.Д.Угринович Информатика и ИКТ, 11 класс. Профильный уровень.
