МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОСТОВСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ РОСТОВСКОЙ ОБЛАСТИ
« ГУКОВСКИЙ СТРОИТЕЛЬНЫЙ ТЕХНИКУМ»
открытый урок по дисциплине:
«ТЕОРИЯ ВЕРОЯТНОСТЕЙ ИМАТЕМАТИЧЕСКАЯ СТАТИСТИКА»
специальность СПО: 090204 «Информационные системы по (отраслям)»
ТЕМА УРОКА:
«Основные понятия теории графов»
рАЗРАБОТАЛА ПРЕПОДАВАТЕЛЬ:
ПИНГИНА ТАТЬЯНА ПЕТРОВНА
2019
Тема урока: Основные понятия теории графов.
Цели:
Обучающая:
Изучить основные понятия теории графов.
Закрепить знания решением задач по теории вероятностей.
Развивающая:
Способствовать развитию пространственного воображения.
Способствовать расширению кругозора.
Воспитывающая:
Формирование интереса к предмету.
Воспитывать активность, самостоятельность.
Повышение общекультурного уровня студентов.
Тип: Комбинированный урок.
Вид: лекция + практикум по решению задач.
Методы: репродуктивный, информационный, проблемно-эвристический.
Материально-техническое оснащение:
Компьютер с проектором, презентация, несколько ноутбуков.
Ход урока:
Организационный момент. Постановка цели урока. Мотивация.
Мы с вами заканчиваем курс «Теория вероятностей и математическая статистика» и сегодня мы поговорим о графах. Надо сразу отметить, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши "графы" имеют корнем греческое слово "графо", что значит "пишу". Тот же корень в словах "график", "биография", география.
Как вы думаете, чем мы будем заниматься на уроке? (варианты ответов студентов)
Итак, тема нашего урока: Основные понятия теории графов.
Наша цель: Изучить основные понятия теории графов.
Закрепить знания решением задач по теории вероятностей.
Это первый урок по данной теме, поэтому в процессе работы мы узнаем об истории возникновения графов, посмотрим, где встречаются графы в окружающем нас мире, для лучшего запоминания применим различные интересные моменты.
А так как в недалеком будущем нас ждет экзамен, то задачи мы свяжем со студентами, теорией вероятностей и экзаменами.
На данном уроке можно обойтись без компьютеров, но так как ваша специальность «Информационные системы», то несколько человек будут работать на ноутбуках, а затем покажут нам, что у них получилось.
2. Актуализация опорных знаний.
Курс теории вероятностей мы начинали с комбинаторных задач, поэтому я предлагаю вспомнить одну из них: (кому то подобная попадется на экзамене)
Задача: Сколько различных трехзначных чисел можно записать с помощью цифр 0 и 1?
Эту задачу можно решить несколькими способами. Предложите свои варианты решения.
(варианты ответов студентов)
Давайте проиллюстрируем ход решения. На первое место мы можем поставить только одну цифру 1. Запишем 1.
На второе место мы можем поставить любую из 2 цифр. На третье место мы также можем поставить 01, 01.
Сами не подозревая, мы, решая данную задачу, создали граф. У графа есть вершины, это наши цифры и ребра - это стрелочки.
Если мы возьмем первую ветвь, то получится число 100, если вторую ветвь, то 101, третью 110, четвертую - 111. Таким образом, решением данной задачи являются 4 трехзначных числа.
1 1
111
1 0 
110
0 1
101
0
100
Встречали ли вы такие схемы где - нибудь в своей жизни? Давайте посмотрим на иллюстрации. (слайды). Даже на основе показанных примеров, мы видим, что область распространения графов очень велика. Я хочу показать вам свое роословное дерево. Составляли мы его около года, и без графов это было бы очень сложно.
Более того уже во 2 классе, вы решали задачи таким способом. (раб.терадь 2 класса) Представление фактов или решение задач с помощью графов придает им наглядность и простоту.
Наверное нет ни одной дисциплины, где бы вы не сталкивались с графами, а некоторые даже считают, что теория графов – это раздел информатики. Но на самом деле это не так.
Давайте послушаем небольшое сообщение о истории возникновения графов (сообщение студента)
В теории графов есть своя особенность: для того, чтобы решить задачу с помощью графа, необязательно знать много теории. Поэтому и мы сейчас изучим только те понятия, которые понадобятся нам при решении задач по теории вероятностей.
Как обычно, теоретический материал мы систематизируем в таблицу.
Объяснение нового материала.
| Понятие | Определение | Пример |
| Граф | Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки - вершины графа, соединяющие линии – ребра.
Запись G=(V, E) означает, что у графа V вершин и Е ребер. |
G=(5, 5) |
| Неориентированный граф | - это граф, для каждого ребра которого несущественен порядок двух его конечных вершин. |
|
| Ориентированный граф | – это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Пара вершин может соединяться двумя или более ребрами. |
|
| Вероятностный граф | Граф называется вероятностным, если около каждой ветви указывается вероятность соответствующего исхода.
|
|
|
Правила вычисления вероятности по графу: 1) Сумма вероятностей на ветвях, выходящих из одной точки равна единице.
2)Если нас интересует вероятность попадания в конечную вершину (вероятность исхода), то двигаемся по нужной ветви и перемножаем соответствующие вероятности.
3) Если нас интересует вероятность события, которому благоприятствует несколько исходов, то необходимо сложить вероятности соответствующих конечных вершин. | ||
Пока нам достаточно определений, чтобы мы могли решать задачи по теории вероятностей. Мы с вами выполнили первую цель урока.
Следующая цель нашего урока: закрепить знания решением задач
Закрепление нового материала.
Задача: Буквы в слове «математика» перемешали и произвольным образом выкладываются по порядку 4 буквы. Какова вероятность , что получится слова «мама»?
Решение. Построим вероятностный граф:
м а м а
Р(А)=
∙
=
=0,0024
(Мы использовали 1 и 2 правило)
Задача: Экзаменационный билет содержит 2 вопроса и задачу. Студент выучил 12 вопросов из 50 и разобрал 10 задач из нужных 25. Какова вероятность того, что студент сдаст экзамен, если для этого необходимо ответить хотя бы на 2 вопроса или решить задачу и ответить на 1 вопрос.
Демонстрация результатов работы на ноутбуках.
5. Диагностика прочности усвоения знаний.
Студент пришел на экзамен, зная 25 из 30 билетов. Какова
вероятность того, что он сдаст экзамен, если после отказа отвечать на билет ему предоставляется возможность вытянуть еще один?
Решение: Построим вероятностный граф:
Сдал экзамен
Вытаскиваем первый билет без возвращения
Сдал экзамен
Вытаскиваем второй билет
Не сдал экзамен
несчастливый
Событие А: студент сдал экзамен.
На графе вероятностей этому событию благоприятствуют 2 маршрута.
Следовательно, Р(А)=
+ ∙
=
=0,98
6. Подведение итогов и постановка домашнего задания
А наш урок подходит к концу и мы должны подвести итоги.
Какие цели мы ставили перед собой? (слайд)
Выполнили мы поставленные цели?
Какой бы вы сделали вывод об использовании графов при решении задач по теории вероятностей?
Граф – наглядная, удобная и доступная модель.
Применение графов значительно упрощает нахождение вероятностей в задачах различного уровня сложности
Какая задача вам понравилась больше всего? Предлагаю вам решить дома задачу:
Предположите, сколько вопросов вы выучите к экзамену из 60 предложенных. Предположите, сколько задач вы сможете разобрать из 25 предложенных.
Посчитайте, какова вероятность, что вы сдадите экзамен с первого раза?
Выставление оценок.
Закончите предложение:
Я знаю…, я могу…, я умею... Спасибо за урок!
История возникновения графов
Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Преголь. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз.
Во время прогулки по городу Эйлер захотел так же пройти по всем мостам, причем по каждому только один раз. Однако ему это не удалось. Вернувшись домой, ученый составил схему, изобразил участки суши точками, а мосты отрезками и доказал, что задача не имеет решения.(Нужно, чтобы число выходящих из вершины ребер было четно)
Это и был первый граф. Было это в 1766 году. Поэтому, датой рождения теории графов принято считать 1736 год
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа: 1. Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. 2. Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине. 3. Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.
.
