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

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

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

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

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

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

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

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

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

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

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

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

Москва, 2015г

Одобрено: цикловой  комиссией математических и общих естественнонаучных дисциплин

Утверждаю: Зам. директора по УВР ________________/Мордвинова И.Н.

                                                                             _______________________2015г.

Протокол №_______ от «___» __________ 2015г.
Председатель цикловой комиссии _________________/Шмельков В.Ю.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.     0   £ P(A)  £  1;

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

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

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

5.      – событие, противоположное A.

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

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

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

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

Один белый шар можно достать в случаях, а два черных – в , и тогда по основному правилу комбинаторики

Отсюда  , а по свойству (5)  вероятности

Следовательно, 

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

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

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

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

Условной вероятностью  события A при условии, что событие B произошло (P(B) ¹0), назовем отношение .

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

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

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

1. – несовместные события (рис. 2).

2. 

Назовем произведение

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

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

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

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

                              

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

Решение. Пусть два брата считают до числа, которое оказалось суммой «выброшенных» пальцев одной руки каждого. Тот на котором остановился счет выходит, а оставшийся убирает квартиру. Играет ли роль с кого начинать счет? Обратим внимание на то, что первый, с кого начинается счет, не убирает квартиру, если сумма «выброшенных» пальцев окажется нечетной, а второй – если четной. Составим вероятностное дерево исходов

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

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

Решение. . Найдем вероятность P₂ взять известный билет, придя на экзамен вторым (рис. 7).

 и шансы равные.

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

где P(H_i) – вероятность гипотезы   – условная вероятность события A при выполнении гипотезы 
H_i (i = 1, 2, ..., n). Полная вероятность события A равна весу всего вероятностного графа с гипотезами (и с выбранной вершиной) (рис. 8):

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

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

Условная вероятность  находится как отношение веса ветви, проходящей через вершину, соответствующую гипотезе H_k, к весу всего вероятностного графа. Формулировка формулы Байеса на графе «похожа» на определение вероятности.

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

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

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

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

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

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

             

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

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

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

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

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

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

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

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

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