Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Конспекты / Открытый урок по теории вероятностей

Открытый урок по теории вероятностей

  • Математика

Поделитесь материалом с коллегами:

Департамент образования города Москвы

Государственное бюджетное образовательное учреждение

среднего профессионального образования города Москвы

ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ № 42






Образовательная программа

среднего профессионального образования





Методическая разработка

«Основные понятия теории графов. Решение вероятностных задач с помощью графов»



по дисциплине « Теория вероятностей и математическая статистика»

для специальности


230113 «Компьютерные системы и комплексы»















Москва, 2015г





Одобрено:


цикловой комиссией

математических и общих

естественнонаучных

дисциплин

Утверждаю:


Зам. директора по УВР

________________/Мордвинова И.Н.

_______________________2015г.






Протокол №_______

от «___» __________ 2015г.



Председатель цикловой комиссии



_________________/Шмельков В.Ю.


































Составитель: Кирсанова Н.Ю., преподаватель математики ГБОУ СПО Политехнический колледж № 42, первая квалификационная категория





Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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

Приведем некоторые определения и теоремы, которые будем применять в дальнейшем:

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

Граф – это два непустых множестваэлементы первого называются вершинами (vertex)а второго – ребрами (edge)Каждое ребро соединяет не более двух вершин и любую пару вершин соединяет не более чем одно ребро.

hello_html_2aceccb5.png

Ребра и вершины графа.

gr4

Точки называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными. Длины отрезков и расположение точек произвольны. Вместо термина вершина часто употребляют термин узел(node), вместо термина ребро - дуга (arc), связь (link), ветвь(branch). Например, все три фигуры на рисунке изображают один и тот же граф.

Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:
предприятие А установило договорные отношения со всеми другими предприятиями;
Б установило с Г и Д;
В установило со всеми предприятиями, кроме предприятия Е.



Cтепень вершины - количество ребер графа, исходящих из этой вершины. Вершина называется нечетной- gr9

если степень этой вершины нечетная,

четной— если степень этой вершины четная.

На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

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

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Число нечетных вершин любого графа четно.

Граф связный, если из любой вершины в любую другую можно пройти по ребрам.

Циклом называется замкнутый путь из ребера деревом – связный граф без циклов.

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

Пусть в результате некоторого эксперимента возможны различные исходы. Будем предполагать, что ни один из исходов w1w2, ... , wn нельзя представить в виде комбинации остальных ( как говорят, w1w2, ... , wn неразложимы).

Неразложимые исходы w1w2,.., wn  некоторого   эксперимента  будем  называть элементарными событиями, а их совокупность 
={w1w2, ... , wn} (конечным) пространством элементарных событий или пространством исходов.

Обычно интересуются не тем, какой конкретно исход имеет место в результате испытания, а тем, принадлежит ли исход тому или иному подмножеству всех исходов. Все те подмножества А, для которых по условиям эксперимента возможен ответ одного из двух типов: «исход w   A» или «исход w   A», будем называть событиями.

Вероятностью P(Aсобытия A называется числоравное отношению числа | элементарных исходовсоставляющих Aк числу    | всех элементарных и равновозможных исходов:

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_3.gif

Свойства вероятностей

  1. 0    P(A   1;

  2. P(A) = 0 т  огда и только тогда, когда A =    – невозможное событие;

  3. P(A) = 1 тогда и только тогда, когда A = – достоверное событие;

  4. P(B) = P(A) + P(B), если AB =    (A– несовместные события);

  5. http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_4.gif – событие, противоположное A.

Пример 1 (задача Гюйгенса). В урне два белых и четыре черных шара. Один азартный человек держит пари с другим, что среди вынутых трех шаров будет ровно один белый. В каком отношении находятся шансы спорящих?

Решение 1 (традиционное). В данном случае испытание W = {вынимание трех шаров}, а событие A – благоприятствующее одному из спорящих:

A = {достать ровно один белый шар}.

Поскольку порядок вынимания трех шаров не важен, то число всех исходов |   | находим как число сочетаний из 6 по 3, т. е.

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_5.gif

Один белый шар можно достать в http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_6.gifслучаях, а два черных – в http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_7.gif, и тогда по основному правилу комбинаторики

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_8.gif

Отсюда http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_9.gif , а по свойству (5) вероятности

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_10.gif

Следовательно, http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_11.gif

Решение 2. Составим вероятностное дерево исходов:

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_12.gif

В этом решении мы использовали понятие вероятностного графа.

Теорема сложения. Вероятность суммы двух событий равна сумме вероятностей этих событий без вероятности их совместного наступления:

P(B) = P(A) + P(B) – P(AB).

Условной вероятностью http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_14.gif события A при условии, что событие B произошло (P(B0), назовем отношение http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_15.gif.

Это определение эквивалентно так называемой теореме умножения, согласно которой

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_16.gif

т. е. вероятность произведения двух событий равна вероятности одного из нихумноженной на условную вероятность другого при условиичто первое событие произошло.

Следствия теорем сложения и умножения имеют следующие интерпретации на вероятностных деревьях:

1.http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_17.gif – несовместные события (рис. 2).

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_18.gif

2. http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_19.gif

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_20.gif

Назовем произведение http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_21.gif

весом ветви, проходящей через корень дерева и вершины, соответствующие событиям A1A2, ..., An. Интерпретацией теорем сложения и умножения на вероятностных деревьях служит вес ветвей дерева исходов, соответствующих «благоприятному» событию.

Эффективность данных интерпретаций покажем на следующих примерах.

Пример 2. Слово «МАТЕМАТИКА» разделено на отдельные буквы, из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «МАМА»?

Решение (рис. 4).

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_22.gif

Пример 3. Является ли выбор с помощью «считалки» справедливым?

Решение. Пусть два брата считают до числа, которое оказалось суммой «выброшенных» пальцев одной руки каждого. Тот на котором остановился счет выходит, а оставшийся убирает квартиру. Играет ли роль с кого начинать счет? Обратим внимание на то, что первый, с кого начинается счет, не убирает квартиру, если сумма «выброшенных» пальцев окажется нечетной, а второй – если четной. Составим вероятностное дерево исходов http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_23.gif

P2 > P1 и, следовательно, выгодней при игре «считалки» стоять вторым.

Пример 4. Учащийся подготовил к экзамену 20 билетов из 25. В каком случае шансы взять известный билет больше, когда учащийся приходит на экзамен первым или вторым?

Решениеhttp://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_24.gif. Найдем вероятность P2 взять известный билет, придя на экзамен вторым (рис. 7).

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_26.gif и шансы равные.

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_5F25.gif

При традиционном подходе эта задача на формулу полной вероятности. Если событие A может наступить только при появлении одного из несовместных событий (гипотез) H1H2, ..., Hn, образующих полную группу событий, то вероятность события A вычисляется по формуле полной вероятности:

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_27.gif

где P(Hi) – вероятность гипотезы http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_28.gif  – условная вероятность события A при выполнении гипотезы 
Hi (i = 1, 2, ..., n). Полная вероятность события A равна весу всего вероятностного графа с гипотезами (и с выбранной вершиной) (рис. 8):

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_29.gif

Если до опыта вероятности гипотез были P(H1), P(H2), ..., P(Hn), а в результате опыта появилось событие A, то с учетом этого события «новые», то есть условные вероятности гипотез, вычисляются по формуле Байеса:

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_30.gifhttp://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_31.gif

Формула Байеса дает возможность «пересмотреть» вероятности гипотез с учетом наблюдающегося результата опыта.

Условная вероятность http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_32.gif находится как отношение веса ветви, проходящей через вершину, соответствующую гипотезе Hk, к весу всего вероятностного графа. Формулировка формулы Байеса на графе «похожа» на определение вероятности.

Пример 5. Сборщик получил три коробки деталей, изготовленных заводом № 1, и две коробки деталей, изготовленных заводом № 2. Вероятность того, что деталь завода № 1 стандартна, равна 0,8, а завода № 2 – 0,9. Сборщик извлек из наудачу взятой коробки деталь, которая оказалась дефектной. Какова вероятность того, что она изготовлена заводом № 1?

Решение 1. Пусть событие A = {извлечь дефектную деталь}. Выдвигаем две гипотезы:

H1 = {деталь изготовлена заводом № 1},

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_33.gif

H2 = {деталь изготовлена заводом № 2},

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_34.gif

По формуле Байеса находим

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_35.gif

Решение 2. Построим вероятностный граф с гипотезами (рис. 9):

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_36.gif



http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_37.gif











19. В первой урне содержатся один белый и один черный шар, а во второй – один белый и два черных шара. Найдите вероятность извлечения белого шара, если:

а) урна выбирается случайно, а из нее извлекается шар;
б) из каждой урны извлекли по одному шару, а из них выбирается шар;
в) из первой урны переложили во вторую один шар, а затем из нее извлекли шар.

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_61.gif

20. Одна кость из полного набора домино утеряна. Какова вероятность того, что:

а) она «дупль»;
б) она содержит нечетную сумму очков?
в) извлеченная из оставшихся кость «подходит» к утерянной?

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_62.gif

21. Имеются три урны: в первой 2 белых шара и 1 черный, во второй – 1 белый и 2 черных, в третьей – 3 белых шара. Наугад выбирается урна и из нее извлекается один шар. Этот шар оказался белым. Найдите вероятность того, что шар вынут из первой, второй, третьей урн.

http://www.distedu.ru/mirror/_fiz/archive.1september.ru/mat/1999/no35_63.gif

22. Является ли выбор дежурного по классу при помощи «считалки» из троих учащихся случайным и справедливым?

23. Четыре брата определяют дежурного по квартире при помощи четырех спичек, одна из которых короче остальных. В равных ли условиях находятся братья?

24. При последовательном извлечении с возвратом кости из полного набора домино первый игрок поставил на нечетную сумму (кратную трем), а второй – на четную. В каком соотношении находятся их шансы на победу?

Ответ: 21 : 16(35 : 36).



Автор
Дата добавления 14.10.2015
Раздел Математика
Подраздел Конспекты
Просмотров459
Номер материала ДВ-060452
Получить свидетельство о публикации
Похожие материалы

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