Что такое графы в теории вероятности
Применение графов в теории вероятностей
Описание презентации по отдельным слайдам:
Описание слайда:
Применение графов
в теории вероятностей
Кабанова Екатерина, Карташова Юлия.
г. Елец, Липецкой области, МОУ лицей №5,
8 «Б» класс.
Описание слайда:
Вероятностно – статистическая линия становится сегодня неотъемлемой частью школьного курса математики. Не исключено, что задачи, связанные с вычислением вероятности, войдут в материалы ЕГЭ. Но способы их решения обычно специфичны и требуют прочного знания специальной теории.
Описание слайда:
Цель данной работы:
Показать возможность использования графов для вычисления вероятностей в различных случаях и упрощения решения
Задачи работы:
Познакомиться с необходимой теорией, связывающей графы и вероятность;
Рассматривая различные примеры, убедиться в возможности нахождения вероятностей с помощью графов.
Описание слайда:
ГИПОТЕЗА:
Графы помогают легко находить вероятность в задачах различного уровня сложности.
Описание слайда:
Назовем произведение весом ветви, проходящей через корень дерева и вершины, соответствующие событиям
Сумма веса ветвей дерева исходов, соответствующих «благоприятному» событию, равна вероятности данного события.
Описание слайда:
Пример
В урне 3 чёрных и 4 белых шара. Вынимают один из них, возвращают обратно, перемешивают и вынимают другой. Какова вероятность достать 2 белых шара,2 чёрных, шары разных цветов?
Составим вероятностное дерево исходов:
Описание слайда:
Описание слайда:
Описание слайда:
Пример 2
В урне 3 чёрных и 4 белых шара. Последовательно вынимают два шара, но не возвращают их. Какова вероятность достать два белых шара, два чёрных, шары разных цветов?
Описание слайда:
Решение
1-й шар
2-й шар
исход
Вероятность
Описание слайда:
Описание слайда:
Задача 3
Слово «МАТЕМАТИКА» разделено на отдельные буквы, из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «МАМА»?
Описание слайда:
Описание слайда:
Описание слайда:
Задача 4
В цехе работают 6 мужчин и 4 женщины. По табельным номерам отобраны 3 человека. Найдите вероятность того, что все отобранные лица окажутся:
а) мужчинами;
б) женщинами.
Описание слайда:
Решение:
Заменим условие задачи урновой схемой. Всего 10 шаров: 6 чёрных(мужчины) и 4 белых (женщины).
Описание слайда:
1-ый шар
2-ой шар
3-ий шар
Исход
Вероятность
Описание слайда:
Описание слайда:
Задача 5
Один властелин, которому наскучил его звездочёт со своими ложными предсказаниями, решил казнить его. Однако, будучи добрым повелителем, он решил дать ему последний шанс. Звездочёту велено распределить по двум урнам четыре шара, два чёрных и два белых. Палач выберет наугад одну из урн и вытащит из неё шар: если шар будет чёрный, то звездочёта казнят, а в противном случае его жизнь будет спасена.
Каким образом звездочёт должен разместить шары в урнах, чтобы обеспечить себе максимальную возможность уцелеть?
Описание слайда:
Решение
Существует 2 способа размещения шаров по урнам.
1 способ: по два шара;
2 способ: 1 шар и 3 шара.
Описание слайда:
Описание слайда:
Описание слайда:
Ответ
Звездочёту надо в одну урну положить один белый шар, а все остальные во вторую. Тогда вероятность выжить составит
Описание слайда:
ВЫВОД:
применение графов значительно упрощает нахождение вероятности в задачах различного уровня сложности.
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Курс повышения квалификации
Охрана труда
Курс профессиональной переподготовки
Библиотечно-библиографические и информационные знания в педагогическом процессе
Курс профессиональной переподготовки
Охрана труда
Ищем педагогов в команду «Инфоурок»
Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Общая информация
Похожие материалы
Презентация Тренажёр для подготовки к ЕГЭ по обществознанию «Безработица иеё виды»
Памятка :» Антитеррористическая безопасность»
Статья «Концепция развития общего и профессионального образования в рамках стратегии социально- экономического развития Республики Татарстан»
Трудовые резервы 26А
Заводская 21
Заводская 23
«Варианты сервировки стола» 1-я младшая группа
Митоз
Не нашли то что искали?
Воспользуйтесь поиском по нашей базе из
5418200 материалов.
Вам будут интересны эти курсы:
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Минздрав включил вакцинацию подростков от ковида в календарь прививок
Время чтения: 1 минута
Путин поручил не считать выплаты за классное руководство в средней зарплате
Время чтения: 1 минута
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Ученые изучили проблемы родителей, чьи дети учатся в госпитальных школах
Время чтения: 5 минут
Итоговое сочинение успешно написали более 97% выпускников школ
Время чтения: 2 минуты
Путин призвал повышать уровень общей подготовки в колледжах
Время чтения: 1 минута
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
ScienceHub #04: Теория случайных графов
Съемочная группа ПостНауки во главе с главным редактором отправилась не абы куда, а в Яндекс, чтобы посмотреть, какое прикладное значение имеет в мире современных технологий фундаментальная наука. Мы встретились с Андреем Райгородским, доктором физико-математических наук, руководителем отдела теоретических и прикладных исследований компании «Яндекс», и профессором МГУ и МФТИ.
Введение
Есть подозрение, что пытаться рассказать своими словами речь Райгородского здесь, на Хабре, неслыханная наглость и нелепица. Хаброчитатели, наверняка, разбираются в этом и не нуждаются в повторении. Поэтому, чтобы не переливать из пустого в порожнее, я приведу цитаты Андрея, а вы можете их дополнить в комментариях.
Андрей Райгородский: «Для человека, который совсем не знает, что такое граф, правильно рассказывать в совершенно конкретных терминах. Представьте себе, что у вас есть большая пространственная молекула, которая состоит из жестких шариков, неважно, из чего сделанных (из картона, из металла). И эти шарики между собой перелинкованы, то есть соединены проволочками, прямолинейными отрезками. Получается жесткая конструкция, которую в математике принято называть графом. Это чисто наглядная интерпретация – в виде молекулы. Хотя мне думается, она кажется удобной всякому, кто пытается представить, что такое граф.
Абстрактно же граф устроен таким образом – у него есть множество вершин и множество ребер. Собственно, те шарики, которые мы видим в пространстве – это вершины графа. А проволочки, которые их соединяют – это ребра графа. Если говорить в абстрактных терминах, вершины – это просто некоторые конечные множества каких-то элементов.
Неважно, какой природы эти элементы. Это могут быть люди, например, между которыми есть какие-то отношения. Это могут быть натуральные числа, сайты в интернете, биологические объекты, например, белки. Могут быть совершенно абстрактные элементы какого-то множества.
Ребра, которые соединяют некоторые пары, – это суть пары этих элементов. То есть, мы говорим, что два элемента соединены ребром. И всё. Про каждые два элемента мы можем сказать, они соединены ребром или нет. Но это зависит от того, как мы определим.
В абстрактной ситуации мы можем определить как угодно, просто взяв конечное множество элементов, и какие-то пары этих элементов, соединив ребрами. Получится конструкция в пространстве, например, расположенная или на плоскости. Как вы ее нарисуете, так и будет».
«Еще в XIX веке была классически поставленная задача, которая касалась раскраски карт. Вот у вас есть карта мира. На ней нарисованы какие-то страны. Естественно, вам нужно каждую страну покрасить в определенный цвет таким образом, чтобы страны, которые граничат между собой, были разных цветов. Если они будут одинакового цвета, они просто сольются воедино. И вы не сможете их отличить. Спрашивается, как много цветов потребовалось для произвольной карты, чтобы осуществить такую покраску?
Гипотеза была, что четырех красок всегда хватит, если выполнены какие-то естественные ограничения относительно свойств границ этих стран, их взаимного расположения. Если нет анклавов типа Калининграда, то карта считается правильной, грубо говоря. И хочется ее покрасить каким-то образом в четыре цвета. Это естественным образом связывается с теорией графов. Мы просто каждой стране присваиваем абстрактную вершину (если угодно, ее столицу). И получаются вершины графа – столицы этих стран.
Дальше мы соединяем ребром (если хотите дорогой) две столицы, которые являются главными городами тех стран, которые между собой граничат. У нас получается граф. Его вершины отвечают странам. Ребра – это пары вершин, которые отвечают столицам граничащих между собой стран. И мы хотим покрасить вершины этого графа (то есть, страны) в минимальное количество цветов таким образом, чтобы вершины, соединенные ребром, были покрашены в разные цвета. Задача четырех красок – это великая классическая проблема, которая до сих пор полностью не решена. Она решена с помощью компьютерного перебора, но ручного, чисто аналитического доказательства того, что четырех красок всегда хватит, до сих пор нет».
Случайность
Направление случайных графов — одно из самых интересных в математике сейчас. Оно связано с теорией Эрдеша – Реньи, эти венгерские математики предложили ввести случайность на множестве графов.
А.Р.: «Они сказали так: «Давайте рассмотрим какое-нибудь фиксированное множество из n. вершин, неважно, из чего состоящее. Пусть это будет абстрактное n. объектов. Например, натуральные числа 1, 2…n. Мы хотим ребра проводить между ними случайно».
Понятно, какое количество есть ребер. Но каждые две вершины потенциально могли бы быть соединены ребром. Давайте возьмем какие-нибудь две вершины – бросим монету. Монетка, правда, со смещенным центром тяжести. Она теоретически или практически (я не знаю, как лучше сказать, но правильней всего сказать – статистически) падает «орлом» чаще, чем решкой. Когда вы ее бросаете на стол, вероятность того, что она упадет «орлом» кверху не такая же, как вероятность того, что она упадет кверху решкой. То есть, если бы монетка была сделана из идеально однородного материала, тогда такого бы, конечно, не произошло. В среднем в половине раз она бы выпадала решкой кверху, в половине раз орлом. Этого довольно естественно ожидать. Но у нас смещенная нехорошая монетка. Вероятность того, что она упадет решкой кверху – это какое-нибудь число Р. из отрезка 0 – 1. А вероятность того, что она упадет кверху «орлом» – это, соответственно, 1 – Р, потому что, конечно, мы предполагаем, что монетка не падает на бок – на ребро не становится и в воздухе не зависает. То есть, есть только две возможности: или она падает «орлом» кверху или она падает кверху решкой.
Давайте считать, что если она решкой падает кверху с вероятностью Р., то при выпадении решкой мы проводим, соответственно, ребро между фиксированными нами вершинами. А если нам не посчастливилось, она упала орлом, то ребра не появится. И так делаем с каждой парой вершин, которая есть в нашем распоряжении. У нас n. вершин. И каждую пару мы испытываем с помощью такой монетки. Это называется в науке (в теории вероятности) схема испытания бернулли. Мы просто много раз бросаем монетку и каждый раз фиксируем – выпала она кверху решкой или «орлом». В зависимости от этого, либо мы принимаем решение провести очередное ребро – эту связь между вершинами, либо принимаем решение его не проводить. В итоге у нас, конечно, получается случайный граф – то есть граф, у которого ребра возникли в результате бросания монеты, по воле случая. Такие графы называются классическими или графами Эрдеша – Реньи».
«Задач в теории случайных графов великое множество. Можно говорить о том же хроматическом числе случайного графа. Есть очень красивая интересная наука о том, как ведет себя хроматическое число случайного графа по модели Эрдеша – Реньи. Задачи практического характера, которые очень интересны с точки зрения случайных графов, это задачи построения адекватных моделей случайных графов, которые описывают поведение каких-то реальных сетей.
Под реальными сетями можно понимать, например, интернет, у которого вершины – это (в зависимости от интерпретации) либо сайты, либо страницы, либо еще какие-то структурные единицы. А ребра – это, как правило, гиперссылки. Получается здоровенный объект, который изменяется со временем. Граф как-то эволюционирует. Новые сайты появляются, появляются новые связи между ними.
Если вернуться к пространственной интерпретации, то у нас получается молекула, которая с течением времени прирастает, что-то у нее, наоборот, исчезает, схлопывается. Связи пропадают, появляются новые.
Оказывается, что молекула, которая описывает, например, интернет или описывает какие-то биологические сети, транспортные сети, сети, возникающие в социологии, не совершенно хаотически изменяется, а подчиняется некоторым интересным статистическим закономерностям. Можно, с одной стороны, наблюдать на практике как устроены эти закономерности, а с другой стороны, пытаться придумать адекватные модели случайных графов, отличные от классической модели (потому что классическая модель этого все таки не описывает), которые бы с высокой вероятностью обладали бы теми же самыми свойствами, что мы и пронаблюдали на практике.
Например, известно. Что распределение степеней вершин в интернете, то есть, грубо говоря, вероятность того, что случайно выбранная вершина в графе интернета имеет заданную наперед степень количества ребер, которые с ней соединены. Это распределение себя ведет очень специфическим образом. Это называется степенной закон».
Что делать со спамом
«Представьте себе, что у вас есть какая-то модель случайного графа, которая действительно очень адекватно и хорошо описывает интернет в том смысле, что по своим вероятностным характеристикам она великолепно ложится на эмпирически данные, полученные нами из интернета. То есть, мы знаем, что веб-граф развивается по определенным закономерностям. И, о чудо, мы придумали такую модель случайного графа, в которой с высокой вероятностью все эти закономерности выполнены. Это сложная задача, но частично она решена. Мы уже имеем некоторое первое приближение к тому, как правильно смоделировать поведение интернета. Представим себе, что она полностью решена.
У нас, допустим, есть идеальная модель, которая предсказывает нам, как должен вести себя интернет, если в нем нет внешних неправильных воздействий. Теперь давайте представим себе, что нам надо поймать какой-нибудь спам, который имеет, что называется, ссылочный характер. Ссылочный характер спама устроен следующим образом – есть какая-нибудь структура, построенная зловредными оптимизаторами.
Структура рассчитана, естественно на то, чтобы те сайты, которые находятся внутри этой структуры, легче находились в процессе поиска. То есть, вы задаете какой-то поисковый запрос. Вы хотите получить на него адекватный ответ. А спамеры стараются сделать так, чтобы вы на него получили ответ, состоящий из тех сайтов, которые интересны спамерам. И они эти сайты искусственно накручивают в выдаче. В частности, важным фактором выдачи является, конечно, количество ссылок на этот сайт или количество каких-то цитирований тех ребят, которые цитируют тебя и так далее.
Важно смотреть на локальную структуру графа вокруг той конструкции, которую, возможно, построили спамеры. Как правило, они строят такие конструкции, которые действительно достаточно плотно перелинкованы для того, чтобы обмануть поисковую систему. Поисковая система подумает «О, это крутой участок. Тут действительно находятся сайты, которые высоко цитируемы. Поэтому их стоит выдавать наверх в топ выдачи». И таким образом спамеры победят.
Что мы можем сделать? Мы можем с помощь какого-то алгоритма (естественно, не собираюсь говорить, какого) изловить много-много структур, которые потенциально могли бы оказаться плохими, то есть, достаточно плотно, густо перелинкованными. А потом посмотреть: в этой идеальной модели мира, которую мы придумали с помощью теории графов и теории вероятности, появление каждой конкретной структуры (из найденных с помощью алгоритма), имеет высокую вероятность или низкую?
Если с точки зрения модели случайного графа, которая призвана описывать поведение разумного интернета, вероятность такой структуры высока, то спамерская конструкция, наверное, ее не может никак понижать в выдаче. Не нужно ей присваивать утяжеляющие места, чтобы она все-таки улетала. А если у нее вероятность крайне низкая в рамках нашей идеальной модели, тут уже надо как-то ее заподозрить. Может быть, поставить ей какой-то флажок в рамках ранжирования, чтобы она появлялась, возможно, не на самой высокой позиции. А может быть, забанить. Надо уже глазами посмотреть. Если она действительно плохая, давайте забаним. Таких структур не очень много. Почему бы и нет. Но это все можно делать в автоматическом режиме, пользуясь ожиданием, которое мы имеем в рамках хорошей модели, и реальностью. То есть, действительно, количеством ребер (ссылок) и так далее. Тут я никаких секретов не открываю. Это очень естественные вещи».
Будущие ловцы спама: кто это?
Чтобы решить задачи, лежащие в области теории графов, и проблемы, связанные с интернетом и новыми технологиями, нужны ученые, которые занимаются комбинаторикой и теорией графов, теорией вероятности и случайными процессами. Во всем мире сейчас открываются лаборатории, а в университетах делают на эту область большой акцент. Кроме того, с этим связана и биоинформатика. О задаче хранения и обработки данных, получаемых биологами, мы уже говорили, точнее, рассказывал микробиолог Константин Северинов.
Такие специалисты нужны не только в интернете, не только в связи с контролем и распространением информации, но и в банковских структурах, в исследовании вопросов о финансовых кризисах, которые также связаны с теорией случайных графов.
Андрей Райгородский: «Я скажу вкратце, чем конкретно занимается мой отдел в «Яндекс». Это довольно большой отдел, в котором сейчас работает больше тридцати исследователей и разработчиков. Он построен по такой схеме, что есть довольно значительный кусок отдела, который встроен в продуктовую часть «Яндекса», и он получает часть своих заданий от непосредственных разработчиков – от тех, кто занимается поиском, задачами, в первую очередь интересными «Яндексу» как поисковой системе, строит какие-то сервисы. Эти люди занимаются исследованиями не чисто математического характера, а скорее, наоборот – попытками прилагать какие-то математические идеи к реализации содержательных проектов.
А есть кусок отдела, который, собственно, генерирует такие идеи. То есть, все построено достаточно естественным образом. Есть кусок, который непосредственно в продаже. Есть кусок, который занимается генерацией идей, производством научных публикаций как на индустриальных конференциях, так и в журналах чисто математического содержания. И здесь какие основные направления исследований, которые мы ведем? Конечно, нам очень интересны графы. И мы строим модели различных графов, которые адекватно описывают веб. Наверное, мы пока еще не успели построить идеальную модель. Но у нас есть довольно неплохие продвижения в этом направления. У нас получаются модели, действительно достаточно адекватно описывающие поведение веба. Их тоже удается применять на практике, как я уже говорил.
Есть направление, связанное с исследованием машинного обучения. Есть направление, связанное с задачами абстрактной теории случайных графов».
Послушать Андрея и посмотреть на интерьеры Яндекса можно по ссылке.
Презентация на тему: Применение графов в теории вероятностей
Применение графов в теории вероятностей Кабанова Екатерина, Карташова Юлия.г. Елец, Липецкой области, МОУ лицей №5,8 «Б» класс.
Вероятностно – статистическая линия становится сегодня неотъемлемой частью школьного курса математики. Не исключено, что задачи, связанные с вычислением вероятности, войдут в материалы ЕГЭ. Но способы их решения обычно специфичны и требуют прочного знания специальной теории.
Показать возможность использования графов для вычисления вероятностей в различных случаях и упрощения решения Цель данной работы: Задачи работы:Познакомиться с необходимой теорией, связывающей графы и вероятность;Рассматривая различные примеры, убедиться в возможности нахождения вероятностей с помощью графов.
ГИПОТЕЗА:Графы помогают легко находить вероятность в задачах различного уровня сложности.
В урне 3 чёрных и 4 белых шара. Вынимают один из них, возвращают обратно, перемешивают и вынимают другой. Какова вероятность достать 2 белых шара,2 чёрных, шары разных цветов?Составим вероятностное дерево исходов:
Пример 2 В урне 3 чёрных и 4 белых шара. Последовательно вынимают два шара, но не возвращают их. Какова вероятность достать два белых шара, два чёрных, шары разных цветов?
Задача 3 Слово «МАТЕМАТИКА» разделено на отдельные буквы, из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «МАМА»?
Задача 4 В цехе работают 6 мужчин и 4 женщины. По табельным номерам отобраны 3 человека. Найдите вероятность того, что все отобранные лица окажутся: а) мужчинами; б) женщинами.
Решение: Заменим условие задачи урновой схемой. Всего 10 шаров: 6 чёрных(мужчины) и 4 белых (женщины).
Один властелин, которому наскучил его звездочёт со своими ложными предсказаниями, решил казнить его. Однако, будучи добрым повелителем, он решил дать ему последний шанс. Звездочёту велено распределить по двум урнам четыре шара, два чёрных и два белых. Палач выберет наугад одну из урн и вытащит из неё шар: если шар будет чёрный, то звездочёта казнят, а в противном случае его жизнь будет спасена. Каким образом звездочёт должен разместить шары в урнах, чтобы обеспечить себе максимальную возможность уцелеть?
Решение Существует 2 способа размещения шаров по урнам. 1 способ: по два шара; 2 способ: 1 шар и 3 шара.