Информатика 9 класс графы конспект
Обновлено: 06.07.2024
Загрузить презентацию (915 кБ)
- компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
- компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
- оборудование доски (тема урока, новые термины). Раздаточный материал.
I. Организационный момент. Актуализация знаний.
II. Изложение нового материала. (10 мин. )
III. Закрепление материала. Практическая работа. (15-20 мин.)
IV. Подведение итога урока.(2 мин)
V. Домашнее задание.
I. Организационный момент. Актуализация знаний.
Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.
II Изложение нового материала.
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Граф – это некоторая информационная модель
Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.
Примеры графов (Слайд 4, 5, 6)
Задание 1 (Слайд 7):
Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.
Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?
Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?
Представление графов (Слайд 12)
Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.
III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.
Задание 2 (Слайд 13)
Задание 3 (Слайд14)
Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)
- Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
ПЛАН-КОНСПЕКТ УРОКА
Номер урока
Планируемые результаты
Предметные УУД: представления о понятии управления, объекте управления, управляющей системе, обратной связи;
Метапредметные УДД: умение соотносить свои действия с планируемыми результатами, осуществлять контроль своей деятельности, определять способы действий в рамках предложенных условий, корректировать свои действия в соответствии с изменяющейся ситуацией; умение оценивать правильность выполнения учебной задачи; владение основами самоконтроля, самооценки, принятия решений и осуществления осознанного выбора в учебной и познавательной деятельности;
Личностные УДД: алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе.
Оборудование
тетради, ноутбуки, интерактивная доска, материалы на печатной основе
Основные термины
Деятельность учителя
Деятельность учащихся
I . Организационный момент
Проверяет готовность к уроку
Приветствуют учителя. Организуют своё рабочее место
II. Актуализация знаний
Проверка знаний по пройденному материалу
Вспоминают предыдущие темы изучения
III . Мотивационно-целевой этап
Показ графических изображений для определения темы
Определяют тему урока
Чтение цитаты и размышлений по этому поводу:
Слушают информацию и отвечают на вопросы
— Что должны изучить?
— Чему должны научиться?
Выявить: представления о понятии управления, объекте управления, управляющей системе, обратной связи
IV . Изучение нового материала
Запись темы урока, объяснение особенности изучения данной темы
Запись темы урока
Изучение плана урока
Внимательно слушают поставленные задачи на урок и задания
Подготовка ноутбуков для дальнейшей работы
Определяют план работы в зависимости от типа задания
Проверка выполнения заданий
Отчитываются о выполненной работе
V . Физкультминутка
Проведение небольших физических упражнений
Выполнение небольших физических упражнений
VI . Рефлексия
— Что узнали на уроке?
— Было ли интересно?
— Что было трудного в изучении?
— Всё ли получилось усвоить?
— Над чем необходимо ещё поработать?
Ответы на вопросы
VII . Подведение итогов
Оценка работы учащихся, выставление отметок
Определение уровня освоения темы
VII I . Домашнее задание
Объяснение домашнего задания
Запись домашнего задания
выполнить задания на печатной основе
Выполнение необходимых заданий дома
Дополнение к плану-конспекта урока по информатике
В данном случае объектом моделирования является процесс запоминания стихотворения учеником; цель моделирования состоит в том, чтобы получить формулу для расчёта времени, необходимого ученику для заучивания стихотворения.
С точки зрения цели моделирования, существенной является следующая информация: время запоминания первой строки (5 секунд); разница во времени запоминания очередной и предыдущей строк (2 секунды); количество строк, подлежащих запоминанию (42 строки). Это исходные данные. Результатом должно стать время, необходимое для заучивания всех 42 строк фрагмента романа.
- подготовка к ЕГЭ/ОГЭ и ВПР
- по всем предметам 1-11 классов
Курс повышения квалификации
Дистанционное обучение как современный формат преподавания
Курс повышения квалификации
Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam
- Курс добавлен 31.01.2022
- Сейчас обучается 24 человека из 17 регионов
Курс повышения квалификации
Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС
- ЗП до 91 000 руб.
- Гибкий график
- Удаленная работа
Дистанционные курсы для педагогов
Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:
5 611 087 материалов в базе
Материал подходит для УМК
Самые массовые международные дистанционные
Школьные Инфоконкурсы 2022
Свидетельство и скидка на обучение каждому участнику
Другие материалы
Вам будут интересны эти курсы:
Оставьте свой комментарий
- 19.12.2021 155
- DOCX 80.5 кбайт
- 3 скачивания
- Оцените материал:
Настоящий материал опубликован пользователем Легенза Дмитрий Васильевич. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Автор материала
40%
- Подготовка к ЕГЭ/ОГЭ и ВПР
- Для учеников 1-11 классов
Московский институт профессиональной
переподготовки и повышения
квалификации педагогов
Дистанционные курсы
для педагогов
663 курса от 690 рублей
Выбрать курс со скидкой
Выдаём документы
установленного образца!
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Время чтения: 2 минуты
Отчисленные за рубежом студенты смогут бесплатно учиться в России
Время чтения: 1 минута
Время чтения: 2 минуты
Рособрнадзор предложил дать возможность детям из ДНР и ЛНР поступать в вузы без сдачи ЕГЭ
Время чтения: 1 минута
Минобрнауки и Минпросвещения запустили горячие линии по оказанию психологической помощи
Время чтения: 1 минута
Минтруд предложил упростить направление маткапитала на образование
Время чтения: 1 минута
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.
Получите невероятные возможности
Конспект урока "Графические информационные модели. Графы"
Граф – это совокупность объектов со связями между ними. Графически это будет выглядеть следующим образом:
Вершины (точки) – это объекты, а ребра (линии между ними) – это связи. Помимо точек вершины графа могут изображаться овалами, кругами, прямоугольниками и так далее. Связи между вершинами могут быть различными: дуги, рёбра, петли.
На данном уроке мы с вами познакомимся с ориентированными и неориентированными графами. В ориентированном графе связями между вершинами будут дуги, а в неориентированном – рёбра.
Решим задачу: В соревнованиях по шахматам участвовало 6 учащихся с 9 по 11 класс. При встрече они все обменялись рукопожатиями. Вопрос: сколько всего было сделано рукопожатий?
Для решения данной задачи будем использовать граф. Вершинами графов будут являться шесть учащихся, которые участвовали в турнире. Пронумеруем их от одного до шести. Проведем от каждой вершины линии (ребра) к оставшимся пяти вершинам.
Для ответа на вопрос остается сосчитать, сколько линий изображено на графе. Ответ: на турнире было сделано 15 рукопожатий.
Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
Давайте сами нарисуем взвешенный граф на основе задачи со следующим условием: Между городами A, B, C, D, Е построены дороги. Необходимо найти кратчайший путь из города А в город Е, если известно, что из города А в город В расстояние 100 километров, из А в С – 260 километров, из В в С – 140 километров, из В в Е – 400 километров, из С в D – 50 километров, из С в Е – 100 километров и из D в Е – 40 километров.
Итак, для решения данной задачи необходимо нарисовать взвешенный граф, так как нам дано расстояние, то есть вес рёбер. Для начала нарисуем вершину А. Из неё будут выходить два ребра в вершины В и С. Ребро из А в В будет короче, чем из А в С, так как расстояние из пункта А в пункт В 100 километров, а из пункта А в пункт С – 260 километров.
Далее нарисуем ребро из В в С и его вес будет равен 140.
Теперь нарисуем ребро из вершины С в вершину D и укажем вес 50
У нас получился взвешенный граф.
Нам осталось найти кратчайший путь. Для этого из вершины А будем идти в вершину В – это 100 километров, затем сразу в вершину Е. Слаживаем 100 и 400, получим 500 километров.
Аналогичным образом проходим по остальным рёбрам и получим, что путь через вершины A, B, C, E равен 340 километров. Через вершины A, C, E 360 километров. A, B, C, D, E - 330, A, C, B, E 800 километров и через вершины A, C, D, E равен 350 километров. Нам необходимо выбрать кратчайший – это путь через города A, B, C, D, E и равен он 330 километров.
Следующее понятие, с которым мы должны познакомится - Цепь. Итак, цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза. То есть при построении пути по одному и тому же ребру можно пройти только один раз. Например, всем известная детская задача, где необходимо нарисовать домик не отрывая ручки от бумаги и в то же время нельзя дважды проходить по одной и той же линии.
В свою очередь, цикл – это цепь, в которой начальная и конечная вершины совпадают. В детстве, наверное, каждый из вас рисовал звезду, не отрывая ручки от бумаги и не проходя дважды по одной и той же линии или ребру. При изображении такой звезды начальная и конечная вершины совпадают. Сеть – это граф с циклом.
Разберём ещё один пример. У Антона в семье есть мама Татьяна, папа Юрий и сестра Маша. Изобразим каждого члена семьи как вершину нашего графа и обозначим первыми буквами имён. От каждого из них проведём рёбра к оставшимся троим. Над каждым из рёбер укажем, кто кем и кому приходится. Например, если идти от вершины Антона к Юрию, то Антон является сыном. А если идти наоборот, от Юрия к Антону, то Юрий является отцом. Аналогичным образом можно провести отношения между всеми членами семьи. Данный граф является примером семантической, или же смысловой сети.
Таким образом, Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними. Все связи данного графа различны, поэтому их необходимо подписывать.
Графы широко распространены как информационные модели. Их можно применять, например, при планировании жилого района, где вершинами будут являться дома, а рёбрами – дороги или дорожки, которые их связывают. Ещё одним примером будет являться карта проезда по городу на любом из видов транспорта, где остановки – это вершины, а путь движения транспорта – это рёбра и так далее.
Следующее определение в данной теме: дерево. Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину. Отличительная особенность дерева: между любыми двумя его вершинами существует единственный путь. Корень дерева – это одна и единственная главная его вершина.
Разберёмся более подробно на примере:
Ученик Антон решил составить генеалогическое дерево своей семьи. Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он является сыном своего отца Юрия и мамы Татьяны. В свою очередь Татьяна является дочерью Леонида (дедушки Антона) и Елены (бабушки Антона). Юрий является сыном Григория (дедушки Антона) и Марии (бабушки Антона). У Антона есть сестра Маша. Так как словесное описание трудно для восприятия, давайте поможем Антону представить это все в виде дерева и построим генеалогическое дерево.
Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху. У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок. У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.
Таким образом, мы построили родословное дерево.
Важно запомнить:
· Граф – это совокупность объектов со связями между ними.
· Вершины – это объекты, а ребра – это связи.
· Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
· Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
· Цикл – это цепь, в которой начальная и конечная вершины совпадают.
· Сеть – это граф с циклом.
· Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
· Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.
На прошлом уроке мы уже говорили о том, что одним из методов познания является моделирование, рассматривали различные классификации моделей и выделили в качестве предмета нашего рассмотрения информационные модели. Среди них можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.
Если рассматривать группу объектов вместе с имеющимися между ними связями как единое целое, то можно говорить о системе. Мы можем графически изобразить объекты системы вершинами, а связи между ними линиями (рёбрами). В этом случае мы получим информационную модель системы в форме графа.
Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).
Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.
Если вершины или ребра графа характеризуются некоторой дополнительной информацией — весом вершины или ребра, то такой граф называют взвешенным.
С помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяжённость дорог в километрах.
Проведём путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза. Такой путь называется цепью. Цепь, у которой совпадают начальная и конечная вершины, называется циклом.
Граф с циклом называется сетью . Если персонажей некоторого литературного произведения, мультфильма или сериала представить вершинами графа, а связи между ними изобразить рёбрами, то получится граф, который называют семантической сетью.
Информационные модели в виде графов широко используются в повседневной жизни.
Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т.д. — ребрами графа. По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.
Граф, в котором отсутствуют циклы, называется деревом.
В этом случае между любыми двумя вершинами существует только один путь.
С помощью дерева удобно представлять иерархическую систему.
У дерева выделяется одна главная вершина, которую называют корнем.
Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня), но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня. Вершины, у которых отсутствуют порожденные вершины, называются листьями.
Одним из известных применений графов является генеалогическое или родословное дерево, на котором отображаются родственные связи.
Существуют задачи, которые удобно решать с помощью графов.
Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.
С помощью графов удобно решать задачи на определение выигрышной стратегии игроков.
Задача на анализ информации, представленной в виде графа, является одной из предлагаемых на государственной итоговой аттестации по информатике.
Итак, сегодня вы узнали о том, какие бывают графы и из каких элементов они состоят, для каких целей создаются. Получили представление об ориентированных и неориентированных графах, деревьях. Научились решать задачи на определение количества путей в графе, используемые при государственной итоговой аттестации. Закрепите полученные знания на практике, выполнив упражнения.
Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.
2. Определяется необходимость рассмотрения группы объектов вместе с существующими между ними связями, т.е. системы. Затем — возможность получения информационной модели системы в форме графа. Рассматриваются различные варианты отображения графов;
3. Определение понятий — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.
4. Исследование различных возможных путей, проходящих по вершинам и ребрам графа. Цепь. Цикл.
5. Реализация интерактивного элемента с целью проверки первичного усвоения нового материала;
6. Определение сети. Исследование возможных вариантов применения информационных моделей в форме графов в повседневной жизни;
7. Определение Дерева. Корень, Предки, Потомки, Листья. Исследование возможностей, предоставляемых различными сервисами для построения генеалогического дерева;
8. Использование графов для графического представления решения различных задач. Задача о построении дерева возможных трёхзначных чисел.
Разбор задачи демонстрационного варианта ФИПИ-2017 на анализ информации, представленной в виде схем
Читайте также: