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

Раздел Математика
Класс -
Тип Конспекты
Автор
Дата
Формат docx
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

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

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

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

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


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

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

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

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



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

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


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





Москва, 2015г



Одобрено:

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

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

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

дисциплин

Утверждаю:

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

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

_______________________2015г.


Протокол №_______

от «___» __________ 2015г.

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

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




















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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. 0  P(A)  1;

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

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

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

  5. Открытый урок по теории вероятностей - событие, противоположное A.

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

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

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

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

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

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

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

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

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

Следовательно, Открытый урок по теории вероятностей

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

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

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

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

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

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

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

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

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

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

1.Открытый урок по теории вероятностей - несовместные события (рис. 2).

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

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

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

Назовем произведение Открытый урок по теории вероятностей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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











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

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

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

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

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

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

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

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

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

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

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

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



© 2010-2022