XII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Решение задач по теории вероятностей с помощью графов
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Актуальность исследования заключается в том, что данная тема недостаточно еще изучена, использование метода решения задач с помощью графов не входит в школьную программу.
При использовании графов, решение задач упрощается. Задачи в виде графа дают возможность наглядно и достаточно просто представить данные.
Примерами графов служат схемы метрополитена, железных или шоссейных дорог, структурные формулы молекул, планы выставок и т. д., то есть схемы и планы (или карты) без указанных масштабов, показывающие связь между принадлежащими им объектами.
Целью исследования является ознакомление с понятием графа, с теорией вероятностей, решение задач по теории вероятностей с помощью графов, изучение литературы по данной теме и расширение математического кругозора.
Чтобы достичь цели, были поставлены следующие задачи:
Дать определение графов и его составляющих;
Рассмотреть некоторые виды графов и их свойства;
Рассмотреть основные положения теории графов, а также теоремы, лежащие в основе данной теории с доказательством;
Изучить подробно теорию вероятностей;
Решить задачи по теории вероятностей с помощью графов;
Определить области применения теории графов и теории вероятностей в окружающей действительности.
Объект исследования: теория вероятностей и графы.
Предмет исследования: задачи по теории вероятностей.
Гипотеза: с помощью графов можно решить задачи по теории вероятностей.
Для решения поставленных задач были использованы следующие методы исследования: сбор информации, анализ, решение задач.
В первой и второй главе представлены определение, основные понятия и формулы теории вероятностей и графов, а также историю возникновения теории вероятностей и графов.
Глава 1. Теория вероятностей
История
История теории вероятностей начинается с давних времен. Известно, что в древнейших государствах Египте, Греции, Китае и Индии уже использовались некоторые элементы рассуждений вероятности, которые использовались для переписи населения и для того, чтобы определить численность войска неприятеля.
Первые работы по теории вероятности, принадлежащие французским учёным Б. Паскалю и П. Ферма, голландскому учёному X. Гюйгенсу, появились в связи с подсчётом различных вероятностей в азартных играх. Успех теории вероятностей связан с именем швейцарского математика Я. Бернулли (1654-1705 гг.). Он открыл знаменитый закон больших чисел: дал возможность установить связь между вероятностью какого-либо случайного события и частотой его появления, наблюдаемой непосредственно из опыта. Следующий период истории теории вероятностей (XVIII в. и начало ХIХ в.) связан с именами А. Муавра, П. Лапласа, К. Гаусса и С. Пуассона. В этот период теория вероятностей находит ряд применений в естествознании и технике. Третий период истории теории вероятностей (вторая половина XIX в.) связан в основном с именами русских математиков П. Л. Чебышева, А. М. Ляпунова. Наиболее распространённая в настоящее время логическая схема построения основ теории вероятностей разработана в 1933 году математиком А. Н. Колмогоровым.
Определение и основные формулы
Основным понятием теории вероятностей является вероятность. Это слово часто применяется в повседневной жизни. Каждому знакомы фразы: «Завтра, вероятно, подует ветер», или «вероятнее всего завтра утром мы поедем на озеро». В словаре С.И.Ожегова дано толкование слова вероятность как «возможности осуществления чего-нибудь». И здесь же представлено определение понятию теории вероятностей как «разделу математики, изучающей закономерности, основанные на взаимодействии большого числа случайных явлений».
Теория вероятностей — раздел математики, который изучает закономерности в случайных явлениях.
Случайное явление – это явление с неопределенным исходом, происходящее при неоднократном воспроизведении определенного комплекса событий [4:7].
Событие называется достоверным, если в в результате испытания оно обязательно произойдет. Например, достоверным будет появление одного из шести чисел 1,2,3,4,5,6 при одном бросании игральной кости.
Случайным называют событие, которое при осуществлении некоторых испытаний может произойти или не произойти. Например, при однократном бросании игральной кости может выпасть число 1 или не выпасть, то есть событие является случайным, потому что оно может произойти, а может и не произойти.
Невозможным называют событие, которое в результате испытания произойти не может. Например, невозможным является выпадение числа 7 при бросании игрального кубика.
Равновозможные события – это события, которые при данных условиях имеют одинаковые шансы для наступления. Например, при подбрасывании монеты событие А (появление цифры) и событие В (появление герба) равновозможны, так как предполагается, что монета изготовлена из однородного материала, имеет правильную форму и наличие чеканки не влияет на то, какая сторона монеты (герб или цифра) окажется верхней.
Каждое событие, которое может наступить в итоге испытания, называется элементарным исходом. Элементарные исходы, при котором данное событие наступает, называется благоприятным этому событию [2:5]
Вероятностью события называется отношение числа элементарных исходов, благоприятствующих данному событию, к числу всех равновозможных исходов испытания, в котором может появиться это событие.
Вероятность события А обозначают Р(А) (здесь Р –первая буква французского слова probabilite - вероятность). В соответствии с определением
Р(А) = ,
где m – число элементарных исходов, благоприятствующих данному событию А; n - число всех равновозможных исходов испытания, образующих полную группу событий.
Это определение вероятности называют классическим определением вероятности. Оно применяется, когда теоретически удается выявить все равновозможные исходы испытания и определить благоприятствующие исследуемому испытанию исходы.
Вероятность события имеет следующие свойства:
Вероятность достоверного события равна единице. Обозначим досиоверное событие буквой В. Для достоверного события m = n, поэтому Р(В) = 1.
Вероятность невозможного события равна нулю. Обозначим невозможное событие буквой V. Для невозможного события m = 0, поэтому Р (V) = 0.
Вероятность случайного события выражается положительным числом, меньшим единицы. Поскольку для случайного события А выполняется неравенство 0<m<n, или , то 0 < P(A) < 1.
Вероятность любого события В удовлетворяет неравенствам [2:9].
Классическое определение вероятности предполагает, что все элементарные исходы равновозможны. Однако, на практике часто встречаются испытания, число равновозможных исходов которых очень велико. Например, без многократного подбрасывания кнопки трудно определить, равновозможны ли ее падения «на плоскость» или на «острие». Поэтому используется и статистическое определение вероятности. Статистической вероятностью называют число, около которого группируются значения частоты события W(A) в различных сериях большого числа испытаний. Частотой события называется отношение числа опытов, в которых появилось это событие, к числу всех произведенных опытов.
Статистическое определение обладает следующими свойствами:
Вероятность достоверного события равна 1.
Вероятность невозможного события равно нулю.
Вероятность случайного события заключена между нулем и единицей.
Вероятность суммы двух несовместимых событий равна сумме вероятностей этих событий [2:21].
Вероятность того, что в серии из n независимых испытаний событие А появилось ровно k раз (и не появлялось n-k раз), обозначим через
P(k)= , где .
Данная формула называется формулой Бернулли [2:173] — это формула в теории вероятностей, позволяющая находить вероятность появления события A при независимых испытаниях. Названа в честь выдающегося швейцарского математика Якоба Бернулли, который и вывел формулу.
Глава 2. Графы
История возникновения графов
Огромный вклад в развитие математики внес российский, немецкий и швейцарский ученый Леонард Эйлер. История появления графов связана с его именем. Задачу о Кенигсбергских мостах составил именно он.
В городе Кенигсберге (ныне Калининград) протекает река Прегель, через которую построены мосты, связывающие все районы города. Во время прогулки по городу Эйлер захотел пройти по всем мостам, причем по каждому только один раз. Однако ему это не удалось. Вернувшись домой, ученый составил схему, изобразил участки суши точками, а мосты отрезками, это и был первый граф.
2.2. Понятие графа
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов - обширный раздел математики, в котором системно изучают свойства графов.
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – ребрами. Примерами графов могут служить любая карта дорог, схема метро, как было упомянуто выше, электросхема, чертеж многоугольника и т.д. Графы строят для того, чтобы визуально представить сложные взаимодействия.
Два ребра называются смежными, если у них есть общая вершина.
Два ребра называются кратными, если они соединяют одну и ту же пару вершин.
Ребро называется петлей, если его концы совпадают.
Степенью вершины называют количество ребер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра.
Вершина называется висячей, если из неё выходит ровно одно ребро.
Граф без кратных ребер и петель называется обыкновенным. [1]
Графы бывают полными и неполными. Полный граф - это простой граф, каждая пара различных вершин которого смежна. Неполный граф – это граф, в котором хотя бы 2 вершины не смежны.
Г раф, являющийся неполным, можно преобразовать в полный с теми же вершинами, добавив недостающие рёбра. Проведя недостающие рёбра, получим полный граф. Вершины графа Г и рёбра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа Г и обозначают его Г.
Г : Г:
Д ополнением графа Г называется граф Г с теми же вершинами, что и граф Г, и с теми и только с теми рёбрами, которые необходимо добавить графу Г, чтобы получился полный граф. Вершина называется нечётной, если её степень – число нечётное. Вершина называется четной, если её степень – четное число [5:63].
2.3.Виды графов:
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированный (ребрам присвоено направление)
Неориентированный (у ребер нет направлений)
Смешанный (встречаются как ориентированные, так и неориентированные рёбра)
Связный (между любой парой вершин этого графа существует как минимум одно ребро)
- несвязный граф
Дерево (между любой парой вершин имеется только по одному пути)
Двудольный (множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.)
Эйлеров граф (в нём каждая вершина должна иметь только чётное число рёбер)
Взвешенный (каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра)
Глава 3. Решение задач по теории вероятностей
с помощью графов
В этой работе при решении задач по теории вероятности мы будем пользоваться только ориентированными графами
Правило вычисления вероятности по вероятностному графу
вероятность попадания в конечную вершину (вероятность исхода) можно вычислить, перемножая вероятности, встречаемые на ребрах соответствующего маршрута (рис. 1, жирный маршрут) [3:3];
2) если же нас интересует вероятность события, которому благоприятствуют несколько исходов, то вероятности соответствующих конечных вершин складываются (рис. 2, жирные маршруты) [3:3].
Задача 1: Павел Иванович совершает прогулку из точки А по дорожкам парка. На каждой развилке он наудачу выбирает следующую дорожку, не возвращаясь обратно. Схема дорожек показана на рисунке. Часть маршрутов приводит к поселку S, другие в поле F или в болото М. Найдите вероятность того, что Павел Иванович забредет в болото?
Решение:
Построим вероятностный граф:
Пусть событие М - Павел Иванович забредет в болото. Этому событию на графе благоприятствуют три маршрута. Воспользуемся формулой , получим
Ответ: 0,42
Задача 2: Ковбой Джон попал в муху на стене с вероятностью 0,9, если стрелял их пристрелянного револьвера. Если Джон стреляет из непристрелянного револьвера, то он попадает в муху с вероятностью 0,4. На столе лежат 10 револьверов, из них только 2 пристрелянных. Ковбой видит на стене муху, наудачу хватает первый попавшийся револьвер и стреляет в муху. Найдите вероятность того, что Джон промахнется.
Решение:
Пусть событие А – Джон промахнулся
Построит вероятностный граф, где П – пристрелянный пистолет, Н – непристрелянный пистолет, «+» - попал, «-» - не попал.
То, что Джон взял пристрелянный револьвер, равен 0,2, а непристрелянный – 1-0,2=0,8. Из условия задачи следует, что с пристрелянным револьвером Джон попадает с вероятность. 0,9, а непристрелянным 1-0,9=0,1. Также из условия задачи мы знаем, что Джон из непристрелянного револьвера Джон попадает в муху с вероятностью 0,4, следовательно, промахнется 1-0,4=0,6 вероятностью.
Воспользуемся формулой правила 2, получим Р(А) = 0,2*0,1+0,8*0,6 = 0,02+0,48 = 0,5
Ответ: 0,5
Задача 3: В волшебной стране бывает 2 типа погоды: хорошая и замечательная, причем погода держится неизменно весь день. Известно , что с вероятностью 0,8 погода завтра будет такая же, как и сегодня. Сегодня 1 марта, и погода в волшебной стране замечательная. Найдите вероятность того, что 3 марта погода в волшебной стране также будет замечательной.
Решение: Пусть событие А – погода 3 марта замечательная.
Построим вероятностный граф:
Р(А) = 0,8*0,8+0,2*0,2 = 0,68
Ответ: 0,68
Задача 4: Из урны, где находятся 3 белых и 4 черных шаров, наугад без возвращения один за другим извлекают два шара. Какова вероятность того, что извлекут разноцветные шары?
Решение:
Построим вероятностный граф
Где Ш –шар, Ч – черный шар, Б – белый шар.
Пусть событие A – извлекли разноцветные шары. Этому событию на графе благоприятствуют 2 маршрута. Пользуемся вторым правилом, поэтому
Ответ: 0,57
Задача 5: В первой урне находятся 7 белых и 9 черных шаров, во второй - 6 белых и 4 черных шаров. Из первой урны во вторую переложили два шара, а затем из второй урны извлекли один шар. Найти вероятность того, что этот шар белый
Решение:
Построим вероятностный граф:
Пусть событие A - извлеченный из второй урны шар оказался белым. Этому событию на графе благоприятствуют четыре маршрута. Поэтому
Ответ: 0,57
Заключение
В результате проделанной работы сделаны следующие выводы:
теория вероятностей и теория графов - это огромный раздел науки математики, требующий дальнейшего подробного изучения;
изучив теорию, действительно возможно решить задачи по теории вероятностей с помощью графов;
практическое применение необычного способа решения задачи с помощью графов можно использовать на школьных математических олимпиадах, конкурсах, а также при подготовке к государственной итоговой аттестации.
Теория графов имеет свои преимущества в наглядности, доступности конкретности.
При этом нужно отметить, что имеются и некоторые недостатки применения этого способа. Не каждую задачу можно решить с помощью графов.
Таким образом, задачи исследовательской работы решены, поставленная цель достигнута, выдвинутая гипотеза подтверждена.
Список использованной литературы
https://skysmart.ru.Теория графов. Основные понятия и виды графов
Гусак, А.А. Теория вероятностей. Справочное пособие к решению задач/ А.А. Гусач, Е.А. Бричикова. – Изд-е 4-е, стереотип. - Минск.: ТетарСистемс, 2003. – 288 с. ISBN 985-470-138-7
Корниенко В.С. Теория вероятностей. Решение задач с помощью графов. Методическая разработка/ В.С. Корниенко. – Волгоград.: ИПК «Нива», 2010г. – 12 с.
Трофимова Е.А. Теория вероятностей и математическая статистика. Учебное пособие / Е.А.Трофимова, Н.В.Киселев, Д.В. Гиле; под ред. Е.А.Трофимовой; Екатеринбург: Изд-во Уральского университета, 2018. – 160 с. – ISBN 978-5-7996-2317-3
Березина Л. Ю. Графы и их применение. Пособие для учителей / Л. Ю. Березина. – Москва: Просвещение, 1979. – 143 с.
Ожегов С.И. Толковый словарь русского языка: 72500 слов и 7500 фразеологических выражений / С. И. Ожегов, Н. Ю. Шведова; Российская АН, Ин-т рус. яз., Российский фонд культуры. - 2-е изд., испр. и доп. - Москва : Азъ, 1994. - 907с. – ISBN 5-85632-007-7.
И.В.Ященко. Математика. Базовый уровень. 30 вариантов. Типовые варианты экзаменационных заданий. – Волгоград: Экзамен, 2021. – 188 с.
И.В.Ященко. Математика. Профильный уровень. 36 вариантов. Типовые варианты экзаменационных заданий. – Волгоград: Экзамен, 2021. – 230 с.
https://oge.sdamgia.ru. Банк заданий.