Инфоурок / Математика / Другие методич. материалы / УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ЕН.03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА (ТЕОРЕТИЧЕСКИЙ БЛОК0 ПО СПЕЦИАЛЬНОСТИ 09.02.03 Программирование в компьютерных системах
Обращаем Ваше внимание: Министерство образования и науки рекомендует в 2017/2018 учебном году включать в программы воспитания и социализации образовательные события, приуроченные к году экологии (2017 год объявлен годом экологии и особо охраняемых природных территорий в Российской Федерации).

Учителям 1-11 классов и воспитателям дошкольных ОУ вместе с ребятами рекомендуем принять участие в международном конкурсе «Я люблю природу», приуроченном к году экологии. Участники конкурса проверят свои знания правил поведения на природе, узнают интересные факты о животных и растениях, занесённых в Красную книгу России. Все ученики будут награждены красочными наградными материалами, а учителя получат бесплатные свидетельства о подготовке участников и призёров международного конкурса.

ПРИЁМ ЗАЯВОК ТОЛЬКО ДО 15 ДЕКАБРЯ!

Конкурс "Я люблю природу"

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ЕН.03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА (ТЕОРЕТИЧЕСКИЙ БЛОК0 ПО СПЕЦИАЛЬНОСТИ 09.02.03 Программирование в компьютерных системах

Напоминаем, что в соответствии с профстандартом педагога (утверждён Приказом Минтруда России), если у Вас нет соответствующего преподаваемому предмету образования, то Вам необходимо пройти профессиональную переподготовку по профилю педагогической деятельности. Сделать это Вы можете дистанционно на сайте проекта "Инфоурок" и получить диплом с присвоением квалификации уже через 2 месяца!

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ
библиотека
материалов

Дhello_html_6ff7e003.pngЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ

«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»







Евдокимова М.Д.




УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

ПО ДИСЦИПЛИНЕ

ЕН.03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА


(ТЕОРЕТИЧЕСКИЙ БЛОК0


ПО СПЕЦИАЛЬНОСТИ

09.02.03 Программирование в компьютерных системах


ДЛЯ СТУДЕНТОВ ОЧНОЙ ФОРМЫ ОБУЧЕНИЯ



hello_html_73bb3b20.jpg




Семилуки. 2014


Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»

Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»






Учебно-методический комплекс по дисциплине Теория вероятностей и математическая статистика составлен в соответствии с требованиями к минимуму результатов освоения дисциплины, изложенными в Федеральном государственном стандарте среднего профессионального образования по специальности 09.02.03 Программирование в компьютерных системах.










Учебно-методический комплекс по дисциплине Теория вероятностей и математическая статистика адресован студентам очной формы обучения.

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
















© Евдокимова М.Д., 2014

©ГОБУ СПО ВО «СГТЭК»




СОДЕРЖАНИЕ



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

стр

Введение

4

Образовательный маршрут

7

Содержание дисциплины

8

ТЕОРЕТИЧЕСКИЙ БЛОК

8

Раздел 1. Основные понятия комбинаторики

8

Тема 1.1. Основные понятия комбинаторики

8

Раздел 2. Основы теории вероятностей

15

Тема 2.1. Основные теоремы теории вероятностей

15

Тема 2.2. Дискретные случайные величины (ДСВ)

33

Тема 2.3. Непрерывные случайные величины (НСВ)

39

Раздел 3. Основы математической статистики

50

Тема 3.1. Выборочный метод. Статистические оценки параметров распределения

50

Тема 3.2. Моделирование случайных величин

59

Тема 3.3. Современные пакеты прикладных программ многомерного статистического анализа

62

Раздел 4. Основы теории графов

69

Тема 4.1.Основные понятия теории графов

69

Тема 4.2.Остовы графов, деревья

80

Тема 4.3.Виды графов

87

Контроль и оценка результатов освоения учебной дисциплины

98

Информационное обеспечение дисциплины

100


УВАЖАЕМЫЙ СТУДЕНТ!


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

УМК по дисциплине включает теоретический блок, примеры решения задач, задания для самостоятельного решения, перечень практических занятий, вопросы для самоконтроля.

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

По каждой теме в УМК перечислены основные понятия и термины, вопросы, необходимые для изучения (план изучения темы), а также информация по каждому вопросу из подлежащих изучению. Наличие теоретической информации по теме позволит Вам вспомнить ключевые моменты, рассмотренные преподавателем на занятии.


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


По итогам изучения дисциплины проводится экзамен.


В результате освоения учебной дисциплины обучающийся должен уметь:

  • Применять стандартные методы и модели к решению вероятностных и статистических задач

  • Пользоваться расчетными формулами, таблицами, графиками при решении статистических задач

  • Применять современные пакеты прикладных программ многомерного статистического анализа


В результате освоения учебной дисциплины обучающийся должен знать:

  • Основные понятия комбинаторики

  • Основы теории вероятностей и математической статистики

2. Результаты освоения учебной дисциплины, подлежащие проверке


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

Таблица 1.1

Результаты обучения

(освоенные умения, усвоенные знания)

Основные показатели оценки результатов

У 1. Применять стандартные методы и модели к решению вероятностных и статистических задач

-Вычисление элементов комбинаторики;

-Вычисление классической, геометрической и статистической вероятности;

-Вычисление вероятностей случайных событий;

- Вычисление вероятности сложных событий;

- Вычисление вероятности по формулам Байеса и полной вероятности;

- Вычисление вероятности при повторении испытаний по формуле Бернулли, Пуассона, теоремы Муавра-Лапласа;

-Cоставление закона распределения дискретной случайной величины;

-Вычисление числовых характеристик дискретной случайной величины;

-Вычисление числовых характеристик непрерывных случайных величин;

-Вычисление выборочной средней и дисперсии;

У 2. Пользоваться расчетными формулами, таблицами, графиками при решении статистических задач

-Построение полигона, гистограммы;

-Вычисление выборочной средней и дисперсии;

- Проверка значимости статистических гипотез;

-Моделирование случайных величин.

У 3. Применять современные пакеты прикладных программ многомерного статистического анализа

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

З 1. Основные понятия комбинаторики

-Формулировка определений сочетания, размещения, перестановки.

З 2. Основы теории вероятностей и математической статистики

-Формулировка классического определения вероятности;

-Формулировка теорем умножения и сложения вероятностей;

- Формулировка теоремы Байеса, полной вероятности;

- Определение алгоритма действий вычисления вероятности при повторении испытаний по формулам Бернулли, Муавра-Лапласа, Пуассона;

- Формулировка определения закона распределения дискретной случайной величины;

- Виды распределения дискретной случайной величины;

- Формулировка определения математического ожидания, дисперсии и среднего квадратического отклонения дискретной случайной величины;

- Формулировка определения функции распределения и плотности распределения непрерывной случайной величины;

-Формулировка определений числовых характеристик непрерывной случайной величины;

- Классификация законов распределения непрерывной случайной величины;

- Формулировка определения статистического распределения выборки, эмпирической функции распределения;

- Формулировка определения характеристик выборки;

- Формулировка определений основных понятий статистических гипотез;

- Формулировка определения основных понятий метода статистических испытаний



В таблице приведены профессиональные компетенции, к освоению которых готовит содержание дисциплины.


Название ПК

Результат, который Вы должны получить после изучения содержания дисциплины

ПК 1.1. Выполнять разработку спецификаций отдельных компонент.

Умение составлять математические модели решаемых задач


ПК 1.2. Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.

Умение использовать полученные знания при составлении программ.


ПК 2.4. Реализовывать методы и технологии защиты информации в базах данных.

Умение использовать полученные знания при составлении программ.

ПК 3.4. Осуществлять разработку тестовых наборов и тестовых сценариев.

Умение использовать полученные знания при составлении программ.


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

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

занятий.






ОБРАЗОВАТЕЛЬНЫЙ МАРШРУТ ПО ДИСЦИПЛИНЕ


Таблица 1

Формы отчетности, обязательные для сдачи

Количество


практические занятия

10

Итоговая аттестация (при наличии)

экзамен




Желаем Вам удачи!

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


ТЕОРЕТИЧЕСКИЙ БЛОК


Раздел 1. Основные понятия комбинаторики


Тема 1.1. Основные понятия комбинаторики


Введение



О теории вероятностей

Чhello_html_6781349f.jpgеловечество всегда стремилось к некоторого рода предсказаниям. Любая наука основана на этом. Однако предвидение фактов не может быть абсолютным, каким бы обоснованным оно не казалось. У нас не может быть абсолютной уверенности в том, что наше предвидение не будет опровергнуто опытом.

Допустим, что некоторый простой закон подтверждается для большого числа случаев. Является ли это просто случайным совпадением, или все-таки это - закономерность? Получается, что ученый часто находится в положении игрока; опираясь на метод индукции, он сознательно или не очень вычисляет вероятность.

История теории вероятности содержит очень много неожиданных парадоксов. По мнению Карла Пирсона, в математике нет другого такого раздела науки, в котором так же легко совершить ошибку. Даже само высказывание "вычислить вероятность" содержит парадокс. Ведь вероятность, в противоположность достоверности, есть то, чего не знают. Как же можно вычислять то, о чем нет никаких знаний?

Пользуясь классическим определением, можно сказать, что вероятность - это отношение числа случаев, благоприятствующих изучаемому событию, к полному числу возможных случаев. Однако это определение весьма неполно, что может подтвердить простой пример. Дhello_html_1d4dfc25.jpgавайте посчитаем вероятность того, что при бросании двух игральных костей по крайней мере на одной выпадет 6. Очевидно, что каждая кость может выпасть шестью различными способами. Число всех возможных случаев равно 6*6 = 36; число благоприятствующих случаев равно 11 (6-1, 6-2, 6-3, 6-4, 6-5, 6-6, 5-6, 4-6, 3-6, 2-6, 1-6). Таким образом, вероятность равна 11/36. Мы знаем, что это правильное решение.

Но ведь можно рассуждать и по-другому. Числа очков, выпавшие на обеих костях, могут образовать 6*7/2 = 21 различных комбинаций. 6 из них благоприятствующие (6-6, 6-5, 6-4, 6-3, 6-2, 6-1). Вероятность равна 6/21. Этот результат явно отличается от предыдущего. Однако пользуясь нашим определением, мы не сможем найти ошибку.

Таким образом, придется дополнить определение: вероятность - это отношение числа случаев, благоприятствующих изучаемому событию, к полному числу возможных случаев, при условии, что эти случаи равновероятны. И вот мы определили вероятное при помощи вероятного.

Но как узнать, равновероятны ли два возможных случая? Не является ли это результатом некоторого условного соглашения? Если мы явно укажем условное соглашение перед вычислениями, то все будет хорошо. Но как мы применим результат на практике? Ведь тогда придется доказать состоятельность данного соглашения.

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

Тем не менее без теории вероятности не сможет существовать наука как таковая, ведь без нее мы не сможем ни открыть какой-нибудь закон, ни применять его.


Исторические сведения


Возникновение теории вероятностей как науки относят к средним векам и первым попыткам математического анализа азартных игр (орлянка, кости, рулетка). Первоначально её основные понятия не имели строго математического вида, к ним можно было относиться как к некоторым эмпирическим фактам, как к свойствам реальных событий, и они формулировались в наглядных представлениях. Самые ранние работы учёных в области теории вероятностей относятся к XVII веку. Исследуя прогнозирование выигрыша в азартных играх, Блез Паскаль и Пьер Ферма открыли первые вероятностные закономерности, возникающие при бросании костей. [1]

Важный вклад в теорию вероятностей внёс Якоб Бернулли: он дал доказательство закона больших чисел в простейшем случае независимых испытаний. В первой половине XIX века теория вероятностей начинает применяться к анализу ошибок наблюдений; Лаплас и Пуассон доказали первые предельные теоремы. Во второй половине XIX века основной вклад внесли русские учёные П. Л. Чебышёв, А. А. Марков и А. М. Ляпунов. В это время были доказаны закон больших чисел, центральная предельная теорема, а также разработана теория цепей Маркова. Современный вид теория вероятностей получила благодаря аксиоматизации, предложенной Андреем Николаевичем Колмогоровым. В результате теория вероятностей приобрела строгий математический вид и окончательно стала восприниматься как один из разделов математики.

Тема лекции: Элементы комбинаторики



План:

1. Принцип умножения

2. Размещения (упорядоченные выборки).

3. Перестановки

4. Сочетания (неупорядоченные выборки)


  1. Принцип умножения


Пусть необходимо выполнить одно за другим одновременно r действий. Если первое действие можно вы­полнить n1 способами, после чего второе - n2 способами и т.д. до r - того действия, которое можно выполнить nr спосо­бами, то все r действий вместе можно выполнить n1, n2nr способами.


Пример: Сколько существует двузначных чисел?


Способ 1: (принцип умножения)

Выбирается две цифры, поэтому r= 2. Первая цифра может быть любой, кроме 0. Потому n1= 9. Вторая цифра может быть любой, т.е. n2=10. итак двузначных чисел: n1n2=9 . 10=90.


Способ 2. (перо6ора)

10 20 30 ………..90

11 21 31 …………91 прямоугольная таблица 10 . 9=90

12 22 32 …………92

………………………….

19 29 39 ………...99


Пример: Бросают три игральные кости и наблюдают за числом очков, появившихся на каждой кости. Сколько различных исходов опы­та возможно?


Решение: Бросают три игральные кости, поэтому по принципу умножения r= 3, На выпавшей грани "первой" игральной кости может появить­ся одно очко, два очка, ... шесть очков. Поэтому n1= 6. Анало­гично n2= 6, n3= 6. Итак, число всех исходов опыта n1n2n3= 6 .6 .6=216.


Пример: Сколько существует нечетных трехзначных чисел?


Решение: По принципу умножения r = 3 ; n1 = 9, т.к. первая цифра может быть любой, кроме 0; n2 = 10, т. к. вторая цифра может быть любой ; n3 = 5, т.к. третья цифра должна быть нечетной. Итак, всех возмож­ностей

n1n2n3 =9 . 10 . 5=450.


Замечания к принципу умножения. Если на выполнение какого-ли­бо из r действий наложено ограничение, то подсчет удобнее начи­нать с выполнения именно этого действия.


Пример: В машине 7 мест, одно место водителя. Сколькими спо­собами могут сесть в машину 7 человек, если место водителя могут занять только трое из них?


Решение: По принципу умножения r = 7. Начнем с места водителя n1 = 3, следующее место может занять любой из 6 оставшихся человек, т.е. n2 = 6, следующее место может занять любой из 5 оставшихся человек и т.д. Поэтому n3 = 5, n4= 4, n5 = 3, n6= 2, n7 = 1.

Итак, всех возможностей: n1 n2 n3n4n5n6n7=3∙6∙5∙4∙3∙2∙1 = 2160.


  1. Размещения (упорядоченные выборки).


Пусть А – множество, состоящее из элементов а1, а2,…, аn.

Определение: Упорядоченные наборы, состоящие из r элементов множество А, будем называть размещениями из n элементов множества А по r элементов.

hello_html_m38914009.gifчисло размещений из n элементов по r элементов(r n). Вычислим hello_html_m2308015f.gif по принципу умножения:

n1=n,

n2 =n-1, hello_html_m38914009.gif = n(n-1)(n-2)….(n-r+1).

n3 = n-2,

…………

nr= n-(r-1) = n-r+1.

Здесь n, n-1, n-2,…,n-r+1 есть число возможностей для выбора первого, второго, третьего,… r – того элементов.

hello_html_m13e61ad1.gif


  1. Перестановки


Определение: Размещения из n элементов по n элементов называются перестановки из n элементов.

Pn – число перестановок из n элементов.

hello_html_43a7785c.gif


Пример: Сколькими способами могут 4 человека разместиться в 4-х местном купе железнодорожного вагона?


Решение: А = {1, 2, 3, 4} (4 места в купе вагона);

P4 = 4! = 1∙2∙3∙4 = 24.


  1. Сочетания (неупорядоченные выборки)


А = {а1, а2, а3, …аn}


Определение: Неупорядоченные наборы, состоящие из r элементов множества А, называются сочетаниями из n элементов по r элементов. (rhello_html_m6391290f.gifn).

hello_html_m45cf0b43.gif


Пример: Студенту необходимо сдать 4 экзамена за 10 дней. Сколькими способами можно составить ему расписание, если в один день нельзя сдать более одного экзамена?

Решение: А = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (10 дней). Поскольку в расписании учитывается порядок экзаменов, то мы имеем дело с упорядоченными выборками, т.е. с размещениями.


Пример: Подрядчику нужны 4 плотника, к нему с предложениями своих услуг обратилось 10 человек. Сколькими способами можно набрать рабочую силу?

А = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (плотники).

hello_html_m5e198b70.gif


Пример. В розыгрыше первенства по футболу участвуют 10 команд. Известно, что те, кто займет первые 3 места, получают золотую, серебряную и бронзовую медали, а последние двое выбывают. Сколько различных результатов первенства может быть?


Решение: Нужно выполнить одно за другими два действия:

  1. Из десяти команд выбрать три на три первых места.

  2. После выполнения первого действия из оставшихся семи команд выбрать две на два последних места.

Итак, по принципу умножения r = 2 ;

n1=hello_html_2e38acae.gif=1098=720; n2=hello_html_m7ac1d041.gif=hello_html_m2696c764.gif=21.

Различных результатов первенства может быть:

n1n2= 720 . 21=15120.


Контрольные вопросы:


  1. Сформулируйте принцип умножения.

  2. Сформулируйте замечание к принципу умножения.

  3. Приведите пример задачи на принцип умножения.

  4. Размещения (упорядоченные выборки). Определение, формула.

  5. Перестановки. Определение, формула

  6. Сочетания (неупорядоченные выборки). Определение, формула.


Задачи на закрепление материала:


  1. hello_html_67df9160.gif

  2. hello_html_m4e6b26a4.gif

  3. Вычислить: hello_html_m4d0d24e9.gif.

  4. Вычислить: hello_html_m5721c4f0.gif.

  5. Упростить выражение:hello_html_m302445e7.gif

  6. Упростить выражение:hello_html_7b7e83cd.gif

  7. Упростить выражение:hello_html_m6df8b5a2.gif

  8. Решить уравнение: hello_html_409e009a.gif.


Решить комбинаторные уравнения:

  1. hello_html_m74e52cb5.gif

  2. hello_html_m1434d34f.gif

  3. hello_html_mee6767d.gif

  4. hello_html_370c4172.gif

  5. hello_html_5b55bb03.gif



Тема лекции: Задачи на расчет количества выборок


На использование формул для перестановок и размещений


  1. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять:

(а) из восьми букв, (б) из семи букв, (в) из трех букв?

Решение задачи:

В слове фрагмент 8 букв алфавита.

(а) Всевозможные перестановки 8 букв по восьми местам: Аhello_html_37bda243.gif = hello_html_m6405215e.gif=P8.

(б) Размещения 8 букв по 7 местам: Аhello_html_1e0fccf4.gif.

(в) Размещения 8 букв по 3 местам: Аhello_html_m2e6ad526.gif.

Ответ: P8, Аhello_html_1e0fccf4.gif, Аhello_html_m2e6ad526.gif.


  1. Сколькими способами можно расставить на полке 7 книг, если (а) две определенные книги должны всегда стоять рядом, (б) эти две книги не должны стоять рядом?


Решение задачи:

(а) Книги, которые должны стоять рядом, считаем за одну книгу. Тогда нужно расставить 6 книг по шести местам. Применяя формулу перестановок, получаем: P6 = 6!. Мы учли перестановки шести книг, не учитывая порядок внутри тех книг, которые мы посчитали за одну. А так как две книги по двум местам можно разместить только двумя способами (P2), то получаем окончательно следующее произведение: P2hello_html_41b1474e.gifP6 =2hello_html_41b1474e.gif6! = 1440.

(б) Способов переставить 7 книг существует P7= 7!. Из них   2hello_html_41b1474e.gif6! способов поставить определенные книги вместе. Следовательно, способов поставить книги так, чтобы 2 заданные книги не стояли вместе существует: 7!   2hello_html_41b1474e.gif6!.

Ответ: 1440; . 7!   2hello_html_41b1474e.gif6!


На использование формул для сочетаний


  1. Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?

Решение задачи:

Для решения этой задачи необходимо использовать формулу для сочетания элементов, т.к. здесь не имеет значения порядок элементов в выборке. Запишем формулу для сочетаний и произведем вычисления:

Сhello_html_7d79fa11.gif = hello_html_4839fce9.gif.

Ответ: 56.


  1. Компания из двадцати мужчин разделяется на три группы, в первую из которых входят три человека, во вторую — пять и в третью — двенадцать. Сколькими способами они могут это сделать? (Ответ записать в виде произведения сомножителей, не вычисляя его.)

Решение задачи:

Из 20-ти элементов необходимо сделать три выборки, причем порядок внутри выборок значения не имеет. Поэтому используем формулу для сочетаний. Чтобы выбрать из 20-ти элементов 3, существует Сhello_html_1c430509.gif способов. Остается 17 элементов, из которых выбирается 5 элементов - Сhello_html_72952700.gif способами. Остается 12 элементов, из которых выбирается 12 элементов. Это можно сделать Сhello_html_m1fceb366.gif= 1, т.е. одним способом. Используя принцип произведения, получаем: Сhello_html_1c430509.gifhello_html_41b1474e.gif Сhello_html_72952700.gifhello_html_41b1474e.gif Сhello_html_m1fceb366.gif.

Ответ: Сhello_html_1c430509.gifhello_html_41b1474e.gif Сhello_html_72952700.gifhello_html_41b1474e.gif Сhello_html_m1fceb366.gif.


На использование формул для перестановок и сочетаний


  1. Сколько четырехбуквенных слов можно образовать из букв слова сапфир? 2) Сколько среди них таких, которые не содержат буквы р? 3) Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?

Решение задачи:

1.  Из шести букв составляются четырехбуквенные слова, причем порядок букв важен для образования новых слов. Поэтому используется формула для размещений: Аhello_html_m6272a211.gif.

2.  Необходимо исключить букву р из рассмотрения. Количество слов, не содержащих эту букву: Аhello_html_m79f41fba.gif.

3.  На первое место поставить букву с можно только одним способом. На последнее место поставить букву р можно тоже только одним способом. Остаются 4 буквы, которые необходимо разместить по двум местам: Аhello_html_1dc8b0a7.gif.

Ответ: 360, 120, 12.


  1. Сколько пятибуквенных слов, каждое из которых состоит из трех согласных и двух гласных, можно. образовать из букв слова уравнение?

Решение задачи:

В слове уравнение 3 согласных и 4 гласных буквы русского алфавита. Чтобы посчитать количество требуемых пятибуквенных слов, необходимо посчитать количество сочетаний 3 согласных из 3-х заданных и двух гласных из четырех заданных: Сhello_html_mbb13407.gifи Сhello_html_m473cb096.gif. После того, как 5 букв выбраны, необходимо посчитать все возможные перестановки этих букв: Сhello_html_mbb13407.gifhello_html_41b1474e.gifСhello_html_m473cb096.gifhello_html_41b1474e.gifP5.

Ответ: Сhello_html_mbb13407.gifhello_html_41b1474e.gifСhello_html_m473cb096.gifhello_html_41b1474e.gifP5.



Задачи для закрепления материала


  1. Сколькими способами можно разложить 7 шаров по 4-м ящикам?

Ответ: hello_html_2054122e.gif .

  1. Сколькими способами можно разложить 5 разноцветных шаров по 3-м ящикам?

Ответ: 243.

  1. Директор фирмы составил список из 5-ти возможных кандидатов на вакантные должности своих 1-го, 2-го и 3-го заместителей, а также список из 4-х возможных кандидатов на 2 вакантные должности своих помощников. Сколько вариантов заполнения пяти вакантных должностей имеет директор?

Ответ: hello_html_m5dbdedb5.gif.

  1. У одного человека есть 7 книг, а у другого — 9 книг. Сколькими способами они могут обменять три книги одного на три книги другого?

Ответ: hello_html_4dff721.gif.

  1. Бригада строителей состоит из 16-ти штукатуров и 4-х маляров. Сколькими способами бригаду можно разделить на две бригады, чтобы в одной из них было 10 штукатуров и 2 маляра, а в другой 6 штукатуров и 2 маляра?

Ответ: hello_html_m6027bea4.gif.


Дополнительные задачи

  1. Из цифр 1, 2,3,4,5 составляются всевозможные числа, каждое из которых содержит три цифры. Сколько таких чисел можно составить, если повторение цифр в числах запрещено?

  2. Сколько существует пятизначных чисел, которые начинаются цифрой 2 и оканчиваются цифрой 4?

  3. На окружности выбрано 10 точек. Сколько существу­ет треугольников с вершинами в этих точках?

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

  5. В распоряжении агрохимика есть 6 различных типов минеральных удобрений. Ему необходимо провести несколько экспериментов по изучению влияния любой тройки минеральных удобрений. Сколько всего экспериментов ему придется произвести?

  6. Имеется три письма, каждое из которых можно послать по одному из шести адресов. Сколько есть способов рассылки писем, если нельзя послать более одного письма по одному адресу?

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

  8. Сколько различных комбинаций букв можно получить, переставляя буквы в слове «парабола»?



Практические занятия

  1. Практическое занятие №1 «Применение стандартных методов и моделей к решению вероятностных задач. Решение задач на расчет количества выборок»


Раздел 2. Основы теории вероятностей


Тема 2.1. Основные теоремы теории вероятностей


Тема лекции: Случайные события. Типы событий. Классическое определение вероятности

События


Событие в теории вероятностей – это множество, состоящее из элементарных событий.

События обычно имеют свои словесные описания. Например, при бросании двух игральных костей можно рассматривать событие A, состоящее в суммарном выпадении четного числа очков, а при вытаскивании игральной карты из колоды событием является выпадение карты бубновой масти. Все эти события состоят из элементарных событий. Так, при бросании игральных костей событие A состоит из элементарных событий {1,1}, {1,3}, {1,5}, {2,2}, {2,4}, {2,6}, {3,1} {3,3}, {3,5}, {4,2}, {4,4}, {4,6}, {5,1}, {5,3}, {5,5}, {6,2}, {6,4}, {6,6}.


Достоверным событием называется событие, состоящее из всех элементарных событий.

Достоверное событие происходит всегда, поскольку в результате случайного выбора какое-то элементарное событие всегда реализуется. Обозначим достоверное событие буквой Ώ.


Невозможным событием называется событие, которое не может произойти никогда.

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


Противоположным событию Аhello_html_246867f4.gif Ώ событием называется событие hello_html_m395c2482.gif, состоящее в том, что событие А не произошло.

hello_html_m395c2482.gifсостоит из элементарных событий, не входящих в А.


Суммой (или объединением) событий А и В называется событие А + В, состоящее в том, что из двух событий А и В происходит по крайней мере одно (либо А, либо В, либо А и В вместе).

Этому событию соответствует множество элементарных событий А hello_html_4969d799.gif В. Поэтому, иногда мы будем использовать знак объединения, вместо знака суммирования.


Пример. По мишени стреляют 3 раза. События А, В, С – попадание при 1-ом, 2-ом и 3 выстрелах соответственно. Сумма событий А, В и C означает хотя бы одно попадание.






Классическое определение вероятности


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

  1. образуют полную группу, т.е. в каждом испытании обязан появиться какой-нибудь из этих исходов;

  2. попарно несовместны, т.е. два различных элементарных исхода не могут появиться в одном испытании;

  3. равновозможные, т.е. шансы на появление у всех элементарных исходов одинаковы.


В этих условиях может использоваться классическое определение вероятности.


Определение: Элементарные исходы, в которых появляются интересующее нас событие, называются благоприятными этому событию.



Определение: Вероятностью события А называются число P(А), равное отношению числа исходов испытания, благоприятствующих событию А к общему числу исходов:

hello_html_1bff500a.gifгде n – общее число исходов испытания, m – число исходов, благоприятствующих событию А.


Пример: Бросается один раз игральная кость. Какова вероятность выпадения нечетного числа очков?

Решение: Опыт состоит в бросании игральной кости 1 раз и наблюдении за числом очков, появившихся на верхней грани.

Все исходы опыта: 1, 2, 3, 4, 5, 6.

Число всех исходов: n = 6.

Рассмотрим событие А – выпало нечетное число очков. Исходы благоприятствующие А: 1, 3, 5.

Число исходов, благоприятствующих А : m = 3

hello_html_m3ed18c3d.gif.


Пример: Ребенок играет с шестью буквами разрезной азбуки А, В, К, М, О, С. Какова вероятность того, что при случайном расположении букв в ряд получится слово «МОСКВА»?

Решение: Опыт состоит в случайном расположении шести букв в ряд. Все исходы опыта – множество перестановок из шести различных букв.

Число всех исходов: n = P6=6! = 1.2.3.4 .5.6=720.

Рассмотрим событие А – при случайном расположении шести букв в ряд получено слово «МОСКВА». Очевидно, что такое расположение букв единственно, т.е. m=1. Найдем вероятность события А: P(A)=hello_html_m720fcc22.gif.


Пример: В ящике находится 20 деталей, из них 8 бракованных. Из ящика наудачу извлекают 5 деталей. Найти вероятность того, что среди них окажутся две бракованные детали.

Решение: Опыт состоит в выборе наудачу 5 деталей из 20. Все исходы опыта – множество сочетаний из 20 деталей (находящихся в ящике) по 5.

Число всех исходов опыта n=hello_html_20cb380b.gif=hello_html_5fad6bd2.gif

Рассмотрим событие А – среди 5 деталей, извлеченных из ящика, две бракованные.

Если среди 5 деталей две бракованные, то остальные 3 небракованные. Тогда число исходов, благоприятствующих

событию А, можно найти по принципу умножения. Нужно выполнить одно за другим два действия: из 8 бракованных выбрать 2 детали и затем из 12 небракованных выбрать 3 детали. Первое действие можно выполнить n1=hello_html_2aeff68.gifвторое действие можно выполнить n2=hello_html_d43e95d.gif способами. Итак, m=n1.n2=hello_html_2aeff68.gifhello_html_d43e95d.gif.

Найдем вероятность события А:

hello_html_m2f4dbf7f.gif


Задачи на классическое определение вероятности



Буквой A обозначаем событие, фигурирующее в условии задачи.


Задача. Корреспонденция разносится в 5 адресов. Разносчик забыл дома очки и разнес корреспонденцию случайным образом. Какова вероятность того, что вся корреспонденция попала к своим адресатам?

Решение. Элементарным событием является перестановка из 5 адресов. Их число равно hello_html_m3826d3b3.gif По смыслу задачи все они равновероятны. Поэтому P(A)= 1/120.


Задача. Цифры 0,1,2,3 написаны на четырех карточках. Карточки расположили в случайном порядке. Какова вероятность того, что из них сложено 4-х-значное число?

Решение. Элементарным событием является перестановка из 4 карточек. Их всего 4!. Поскольку четырехзначное число не может начинаться с нуля, то событие A состоит из тех перестановок, которые начинаются с карточки с не равной нулю цифрой. Их всего 4!-3!=18. Поэтому P(A)= 18/4! =18/24=3/4.


Задача. В хоккейном турнире участвуют 6 равных по силе команд. Каждая команда должна сыграть с каждой одну игру. У Вас есть любимая команда. Вы пришли «поболеть» на турнир на одну из игр, выбранных случайно. Какова вероятность того, что в этой игре будет играть Ваша любимая команда?

Решение. Общее число проведенных игр равно C62=15. Любимая команда участвует в 5 играх из 15. Поэтому P(A)= 5/15 = 1/3.


Задача. В ящике разложено 20 деталей. Известно, что 5 из них являются стандартными. Рабочий случайным образом берет 3 детали. Какова вероятность того, что хотя бы одна деталь стандартная?

Решение. Элементарным событием является сочетание из 20 деталей по 3. Количество таких сочетаний равно C203. В соответствии с решением задачи 11, число сочетаний, содержащих хотя бы одну стандартную деталь равно C203- C153=685. Поэтому P(A)= hello_html_m266d79c.gif


Задача. Из 7 карточек разрезной азбуки составлено слово колокол. Эти карточки рассыпали и затем собрали в случайном порядке. Какова вероятность того, что снова получится слово колокол?

Решение. На карточках имеется 3 буквы о, 2 буквы к, 2 буквы л. Поэтому, первая буква слова колокол может быть выбрана двумя способами, вторая – 3 способами, третья – 2 способами. При уже выбранных первых трех буквах четвертая буква может быть выбрана еще 2 способами (поскольку одна буква о уже выбрана). Остальные буквы могут быть выбраны только одним способом. Таким образом (см. решение задачи 12), число перестановок карточек, реализующих слово колокол равно произведению чисел 3, 2, 2, 2 т.е. равен 24. Общее число перестановок карточек равно 7!.Поэтому P(A)= hello_html_4e1032ad.gif


Контрольные вопросы:


  1. Что такое случайное событие?.

  2. Какие виды событий вы знаете?

  3. Дайте классическое определение вероятности.



Тема лекции: Противоположное событие. Теоремы сложения, умножения вероятностей


План:

  1. Основные определения

  2. Теорема умножения вероятностей

  3. Теорема сложения вероятностей несовместимых событий

  4. Вероятность противоположного события


  1. Основные определения



Определение: Событие, которое в результате опыта должно произойти непременно, называется достоверным событием.


Определение: Событие, которое в данном опыте не может произойти, называется невозможным.

Вероятность достоверного события равна единице, вероятность невозможного события равна нулю.


Определение: Два события называют несовместными, если появление одного из них исключает появление другого в одном и том же испытании.


Определение: Суммой А+В двух событий А и В называется событие, состоящее в появлении хотя бы одного из них, т. е. или событие А или В или А и В вместе.


Определение: Произведением А.В двух событий А и В называется событие, состоящее в совместном появлении события А и события В.


Определение: Противоположным к А называется событие hello_html_m3b117811.gif, состоящее в том, что А не произошло.


Определение: Два события называются независимыми, если вероятность одного из них не зависит от появления или не появления другого.


Определение: Пусть А и В – зависимые события. Условной вероятностью Р(В|А) (или PA(B)) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.


  1. Теорема умножения вероятностей



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

P(A.B) = P(A).P(B).


Пример . Какова вероятность того, что при десятикратном бросании монеты герб выпадет 10 раз ?


Решение: Пусть событие Ai — появление герба при i-м бросании. Искомая вероятность есть вероятность совмещения всех событий Ai (i=1,2,3,...,10), а так как они, очевидно, независимы в совокупности, то применяя формулу (10), имеем 

hello_html_3efb21ee.png

Но P(Ai)=1/2 для любого i; поэтому

hello_html_72b9b634.png


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

P(A .B) = P(A).P(BA).

Для трех зависимых событий:

P(A .B) = P(A).P(BA).P(CA .B).


Пример. Из урны, содержащей 3 белых и 7 черных шаров, вынимают два шара. Какова вероятность того, что оба шара окажутся белыми ?


Решение: Эта задача уже была решена в п. 3 с помощью классического определения вероятности. Решим ее, применяя формулу (5). Извлечение двух шаров равносильно последовательному их извлечению. Обозначим через А появление белого шара при первом извлечении, а через В — при втором. Событие, состоящее в появлении двух белых шаров, является совмещением событий А и В. По формуле (5) имеем

hello_html_151de788.png

Но Р(А)=3/10; РA(В)=2/9, поскольку после того, как был вынут первый белый шар, в урне осталось 9 шаров, из которых 2 белых. Следовательно, 

hello_html_6f772ec1.png


  1. Теорема сложения вероятностей несовместимых событий



Теорема: Вероятность суммы несовместных событий равна сумме вероятностей этих событий:

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


Пример. В урне 2 зеленых, 7 красных, 5 коричневых и 10 белых шаров. Какова вероятность появления цветного шара?


Решение: Находим соответственно вероятности появления зеленого, красного и коричневого шаров: Р(зел.)=2/24; Р(кр.)=7/24; Р(кор.)=5/24. Так как рассматриваемые события, очевидно, несовместны, то, применяя аксиому сложения, найдем вероятность появления цветного шара:

hello_html_1c4c3963.png

Теорема:

Если A и B – совместные события, то

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

Для трех и более совместных событий эта формула значительно усложняется.

Например:

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


Пример: Произведен залп из двух орудий по мишени. Вероятность попадания из первого орудия равна 0,85, а из второго – 0,91. Найти вероятность поражения цели.


Решение: Пусть событие А – хотя бы одно попадание в мишень, событие А1 – попадание в мишень из первого орудия, событие А2 – попадание в мишень из второго орудия.

Тогда А = А12.

Поскольку события А1 и А2 совместны, то

P(A) = P1)+P2)-P1,А2).

Т.к. события А1 и А2 независимы, то P(A1,A2)=P(A1) ,P(A2),

где P(A1)=0,85, а P(A2)=0,91 по условию задачи.

Итак, P(A) =0,85+0,91-0,85, 0,91=0,9865.



  1. Вероятность противоположного события


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

Если события, образующие полную группу, попарно несовместны, то в результате опыта появится одно и только одно из этих событий.

Для суммы таких событий справедлива формула

P(A1+A2+….+An) = P(A1)+P(A2)+….+P(An) = 1.


Теорема: Два противоположных друг другу события образуют полную группу:

hello_html_3ccfa7a.gif


Пример: В партии содержится 20 деталей, среди которых 4 нестандартных. Для контроля взяли наудачу 3 детали. Найти вероятность того, что хотя бы одна из взятых деталей нестандартна.


Решение: Пусть событие А – хотя бы одна из взятых деталей окажется нестандартной. Рассмотрим событиеhello_html_m3b117811.gif, противоположное событию А:

hello_html_m3b117811.gif - среди взятых деталей нет нестандартных. Вычислим вероятность события hello_html_m3b117811.gif: hello_html_4332ba5b.gif

Теперь вычислим вероятность искомого события:

P(A) = 1-hello_html_m3f1efbe2.gif.


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


Решение: Пусть событие А – повреждение будет исправлено после замены третьей лампы.

Рассмотрим следующие три события:

А1 – первая замененная лампа оказалась перегоревшей;

А2 – вторая замененная лампа оказалась перегоревшей;

А3 – третья замененная лампа оказалась перегоревшей.

Тогда: А = hello_html_275a6c7b.gif

Поскольку события hello_html_m9ac9127.gifзависимы, то hello_html_m2344cfa.gif

Вероятность события hello_html_m8b707a9.gif есть вероятность того, что первая замененная лампа оказалась исправнойhello_html_m3af8e129.gif.

Условная вероятность hello_html_m7d137fb7.gif - вероятность того, что вторая замененная лампа оказалась исправной, если известно, что первая замененная лампа также исправна.

Поэтому hello_html_m7d137fb7.gif=hello_html_m5f7a4b39.gif.

Наконец, условная вероятность hello_html_m629647fe.gif есть вероятность того, что третья замененная лампа оказалась перегоревшей, если известно, что первая и вторая замененные лампы были исправными.

Откуда hello_html_4150032b.gif.

Теперь подсчитаем искомую вероятность: P(A)=hello_html_4c1168e7.gif


Пример: Вероятности того, что деталь нужного вида находится в первом, втором, третьем ящике соответственно равны 0,7; 0,8; 0,9. Найти вероятность того, что деталь содержится не менее, чем в двух ящиках.


Решение: Пусть событие А – деталь нужного вида находится не менее, чем в двух ящиках. Рассмотрим следующие три события:

А1 – деталь нужного вида имеется в 1-ом ящике;

А2 – деталь нужного вида имеется во 2-ом ящике;

А3 ­­- деталь нужного вида имеется в 3-ем ящике.

Событие B1=hello_html_2256a6e7.gif заключается в том, что нужного вида деталь имеется во 2-ом и 3-ем ящиках, но ее нет в 1-ом ящике. События имеется во 2-ом и 3-ем независимы, поэтому

hello_html_m7fcca1fb.gif

Событие hello_html_24260246.gif заключается в том, что нужного вида деталь имеется в 1-ом и в 3-ем ящиках, но ее нет во 2-ом ящике.

Событие B3=A1,A2,hello_html_m17a9b757.gifзаключается в том, что нужного вида деталь имеется в 1-ом и 2-ом ящиках, но ее нет в 3-ем ящике.

hello_html_m4d5e31c4.gif)=P(A1) ,P(A2) ,P(hello_html_3ac3e8b4.gif

Наконец, событие B4=A1 ,A2,A3 заключается в том, что нужного вида деталь имеется и в 1-ом, и во 2-ом, и в 3-ем ящиках.

hello_html_5c480abb.gif

Событие А произойдет тогда, когда произойдет одно из событий:

или В1, или В2, или В3, или В4. Поэтому А=В1234.

Поскольку события В1, В2, В3, В4 несовместны, то

P(A)=P(В1)+P(В2)+P(B3)+P(B4).

Вычисляем:

P(A)=0,216+0,126+0,056+0,504=0,902.


Контрольные вопросы:


  1. Что такое случайное событие?.

  2. Дайте классическое определение вероятности.

  3. Сформулируйте теорему умножения вероятностей.

  4. Сформулируйте теорему сложения вероятностей.

  5. Как найти вероятность противоположного события?


Задачи на закрепление материала


  1. Вероятность того, что электрическая лампочка, принадлежащая данной партии, проработает гарантийный срок, равна 0,7. Какова вероятность того, что из трех лампочек этой партии гарантийный срок проработает только одна?

  2. Система состоит из двух блоков. Первый из них выходит из строя с вероятностью 0,15, а второй – с вероятностью 0,1. Система выйдет из строя, когда откажут оба блока. Найти надежность безотказной работы системы

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

  4. Имеется 6 потребителей электрического тока, два из которых выходят из строя с вероятностью 0,2, а остальные с вероятностью 0,3. Определить вероятность того, что генератор тока будет отключен, если все 6 потребителей соединены последовательно.

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

  6. В телестудии имеется 3 телевизионные камеры. Для каждой камеры вероятность того. что она в данный момент включена, равна 0,4. Найти вероятность того, что в данный момент включена хотя бы одна из трех камер.

  7. ОТК проверяет изделия на стандартность. Вероятность того, что изделия данной партии нестандартно, равна 0,1. найти вероятность того, что из трех проверенных изделий только одно окажется нестандартным.

  8. Производится залп из трех орудий. Найти вероятность хотя бы одного попадания в цель, если вероятности попадания для первого, второго и третьего орудий равны соответственно 0,7; 0,8 и 0,9.

  9. Вероятность улучшить свой результат в одной попытке для данного спортсмена, равна 0,6. Найти вероятность того, что на соревнованиях спортсмен улучшит свой результат, если разрешается делать три попытки.

  10. Данное предприятие дает в среднем 21% продукции высшего сорта и 70 % продукции первого сорта. Найти вероятность того, что случайно взятые два изделия окажутся одного сорта.


Тема лекции: Формула полной вероятности



Пусть событие А происходит совместно с одним из событий (гипотез) Н1, Н2,… Нn, которые образуют полную группу событий. Тогда справедлива формула полной вероятности события А :

hello_html_mfefd3c4.gif,

где Р(Нк) – вероятность гипотезы Нк, Р(АНк) – условная вероятность А, т.е. вероятность появления события А при условии, что произошла гипотеза Нк .


Пример. Три автомата изготовляют одинаковые детали.

Известно, что первый автомат производит 30% всей продукции, второй – 25% и третий – 45%. Вероятность изготовления детали, соответствующей стандарту, на первом автомате равна 0,99, на втором – 0,988 и на третьем – 0,988. все изготовленные за смену детали складываются вместе. Определить вероятность того, что взятая наудачу деталь не соответствует стандарту.


Решение: Пусть событие А – взятая наудачу деталь не соответствует стандарту.

Гипотезы:

Н1- взятая деталь изготовлена первым автоматом;

Н2- взятая деталь изготовлена вторым автоматом;

Н3- взятая деталь изготовлена третьим автоматом.

Вычислим вероятность гипотез.

hello_html_33aaa239.gif

Вычислим условные вероятности:

Р(АН1) – вероятность того, что взятая наудачу деталь не соответствует стандарту, если она изготовлена первым автоматом.

hello_html_m8942dbe.gif

Вероятность события А подсчитываем по формуле полной вероятности :

Р(А)=0,3 .0,01+0,25 .0,012+0,45 .0,012=0,009.


Задачи на закрепление материала


Задачи с решениями.


Пример 1.В первой урне 7 белых и 3 черных шара, во второй – 8 белых и 2 черных. При перевозке из первой урны во вторую урну перекатились два шара. После того, как шары во второй урне перемешались, из неё выкатился шар. Найти вероятность того, что выкатившийся из второй урны шар белый.

Решение: Пусть событие Н1 состоит в том, что из первой урны во вторую перекатились два белых шара, событие Н2 состоит в том, что перекатились два чёрных шара, а событие Н3 состоит в том, что перекатились шары разного цвета. Можно вычислить вероятности Р(Н1) = hello_html_m22398ada.gif = 7/15, Р(Н2) = hello_html_m6489a386.gif = 1/15, Р(Н3) = hello_html_55abe8a3.gif = 7/15 (при решении задачи полезно проверить выполнение необходимого условия hello_html_626d646d.gif).

Если реализовалась гипотеза Н1, то во второй урне оказалось 10 белых и 2 черных шара. Обозначим через А событие, заключающееся в том, что из второй урны выкатился белый шар. Тогда Р(А/Н1) = hello_html_69e6fcd5.gif = 5/33. Если реализовалась гипотеза Н2, то во второй урне оказалось 8 белых и 4 чёрных шара, и Р(А/Н2) = hello_html_m3030933b.gif = 4/33. Легко показать, что Р(А/Н3) = hello_html_m45c11e83.gif = 3/22. Теперь можно воспользоваться формулой полной вероятности:

Р(А) = (5/33)(7/15) + (4/33) (1/15) + (3/22) (7/15) = 47/330


Пример 2. В ящике лежат 20 теннисных мячей, в том числе 15 новых и 5 играных. Для игры выбираются 2 мяча и после игры возвращаются обратно. Затем для второй игры также наудачу извлекаются ещё два мяча. Найти вероятность того, что вторая игра будет проводиться новыми мячами.

Решение Обозначим через А событие, заключающееся в том, что вторая игра будет проводиться новыми мячами. Пусть гипотеза Н1 состоит в том, что для первой игры были выбраны два новых мяча, гипотеза Н2 состоит в том, что для первой игры были выбраны новый и играный мячи, гипотеза Н3 состоит в том, что для первой игры были выбраны два играных мяча. Определим вероятности гипотез:

Р(Н1) = hello_html_m36a770b1.gif; Р(Н2) = hello_html_3a4ba56a.gif; Р(Н3) = hello_html_135f8937.gif.

Теперь вычислим условные вероятности события А.

Р(А/Н1) = hello_html_1a6df431.gif; Р(А/Н2) = hello_html_m7940724b.gif; Р(А/Н3) = hello_html_m36a770b1.gif.

Осталось подставить результаты вычислений в формулу полной вероятности

Р(А) = hello_html_422f9d32.gif.


Пример 3. На автозавод поступили двигатели от трех моторных заводов. От первого завода поступило 10 двигателей, от второго – 6 и от третьего – 4 двигателя. Вероятности безотказной работы этих двигателей в течение гарантийного срока соответственно равны 0,9; 0,8; 0,7. Какова вероятность того, что установленный на машине двигатель будет работать без дефектов в течение гарантийного срока?

Решение Событие A – установленный на машине двигатель будет работать без дефектов в течение гарантийного срока – может произойти, если произойдет одно из несовместных событий: hello_html_m508b9f69.gif – установленный на машине двигатель изготовлен на первом, втором или третьем заводе соответственно. Эти события образуют полную группу, их вероятности:

hello_html_m1012e9c2.gif, hello_html_m52f7d6a.gif, hello_html_47bc085a.gif,

(Контроль:hello_html_m3d94cec7.gif).

По условию hello_html_4c2d8525.gif, hello_html_369865ad.gif, hello_html_m3f78e501.gif.

По формуле полной вероятности

hello_html_9c798ba.gifhello_html_m1c5b65bf.gif.


Решить задачи:

  1. В партии саженцев имеются в одинаковых количествах березы, клены, липы. Вероятность того, что посаженное дерево приживется, равна для березы 0,7, для клена – 0,8, для липы – 0,9. Найти вероятность того, что наудачу взятое прижившееся дерево окажется березой.

  2. Половина всех арбузов поступает в магазин с 1-й базы, 1/3 – со 2-й базы, остальные – с 3-ей базы. Арбузы с повышенным содержанием нитратов составляют на 1-й базе 15 %, на 2-й базе – 10 %, на 3-ей – 20 %. Какова вероятность купить недоброкачественный арбуз?

  3. Имеются три одинаковых ящика. В первом ящике лежат 2 белых и 2 черных шара, во втором – ящике – 3 черных, в третьем – 1 черный и 5 белых. Некто, случайным образом выбирая ящик, наугад вынимает из него шар. Какова вероятность того, что шар будет белый?

  4. В лаборатории имеется 12 автоматических машин и 8 полуавтоматов. Вероятность того, что за время выполнения некоторого задания автомат не выйдет из строя, равна 0,94. Для полуавтоматов эта вероятность равна 0,85. Студент выполняет задание на машине, выбранной наудачу. Найти вероятность того, что до конца выполнения задания машина не выйдет из строя.


Тема лекции: Формула Байеса


Пусть вероятности гипотез до опыта были Р(Н1), Р(Н2),… Р(Нn). В результате опыта появилось событие А . Тогда условная вероятность Р(НкА) гипотезы Нк с учетом появления события А вычисляется по формуле Байеса:

hello_html_3a945eb5.gif.


Пример. На двух станках производят одинаковые детали, которые поступают на конвейер. Производительность первого станка в три раза больше производительности второго. Первый станок дает в среднем 80% деталей отличного качества, а второй –90%. Наудачу взятая с конвейера деталь оказалась отличного качества. Найти вероятность того , что она изготовлена на втором станке.


Решение Пусть событие А - взятая наудачу с конвейера деталь отличного качества.

Гипотезы:

Н1- деталь изготовлена на первом станке;

Н2- деталь изготовлена на втором станке.

Вероятность гипотез до появления события А:

Р(Н1)=3/4; Р(Н2)=1/4.

Условные вероятности

hello_html_m73e9628b.gif

Вероятности того, что взятая наудачу с конвейера деталь окажется отличного качества, т.е. вероятность события А, вычисляется по формуле полной вероятности:

hello_html_m1bec9bbd.gif

Искомая вероятность того, что взятая деталь отличного качества изготовлена на втором станке, вычисляется по формуле Байеса: hello_html_m8910f83.gif


Задачи на закрепление материала


Задачи с решениями.


Пример. В первой урне 7 белых и 3 черных шара, во второй – 8 белых и 2 черных. При перевозке из первой урны во вторую урну перекатились два шара и шары во второй урне перемешались, из неё выкатился белый шар. Найти вероятность того, что из первой урны во вторую перекатились разноцветные шары.

Решение

Пусть событие Н1 состоит в том, что из первой урны во вторую перекатились два белых шара, событие Н2 состоит в том, что перекатились два чёрных шара, а событие Н3 состоит в том, что перекатились шары разного цвета. Можно вычислить вероятности Р(Н1) = hello_html_m22398ada.gif = 7/15, Р(Н2) = hello_html_m6489a386.gif = 1/15, Р(Н3) = hello_html_55abe8a3.gif = 7/15 (при решении задачи полезно проверить выполнение необходимого условия hello_html_626d646d.gif).

Если реализовалась гипотеза Н1, то во второй урне оказалось 10 белых и 2 черных шара. Обозначим через А событие, заключающееся в том, что из второй урны выкатился белый шар. Тогда Р(А/Н1) = hello_html_69e6fcd5.gif = 5/33. Если реализовалась гипотеза Н2, то во второй урне оказалось 8 белых и 4 чёрных шара, и Р(А/Н2) = hello_html_m3030933b.gif = 4/33. Легко показать, что Р(А/Н3) = hello_html_m45c11e83.gif = 3/22. Теперь можно воспользоваться формулой полной вероятности:

Р(А) = (5/33)(7/15) + (4/33) (1/15) + (3/22) (7/15) = 47/330

Вычисления подставим в формулу Байеса

Р(Н3/А) = Р(А/Н3)Р(Н3)/ Р(А) = (3/22)(7/15)/( 47/33) = 7/47.


Пример Сообщение со спутника на землю передаётся в виде бинарного кода, то есть как упорядоченного набора нулей и единиц. Предположим, что послание на 70% состоит из нулей. Помехи приводят к тому, что только 80% нулей и единиц правильно распознаются приёмником. Если принят сигнал “1”, то какова вероятность того, что отправлен сигнал “0”?

Решение Пусть событие В0 состоит в том, что отправлен сигнал “0”, а событие В1 – в том, что отправлен сигнал “1”. Пусть событие А0 состоит в том, что принят сигнал “0”, с событие А1 – в том, что принят сигнал “1”. Нас интересует Р(В0/А1). По условию

Р(В0) = 0,7 Р(В1) = 0,3

Р(А0/ В0) = 0,8 Р(А1/ В0) = 0,2

Р(А1/В0) = 0,8 Р(А0/ В 1) = 0,2

По формуле Байеса получаем

Р(В0/А1) = 0,20,7/(0,20,7+0,803) = 0,37.


Пример По цели независимо сбросили две бомбы. Вероятность попадания для каждой бомбы равна 1/2. При попадании одной бомбы цель поражается с вероятность 1/2, а при попадании двух бомб она поражается с вероятностью 2/3. Найти вероятность поражения цели.

Решение. Пусть события H1, H2 и H3 состоят в попадании 0, 1 и 2 бомб соответственно. Событие A состоит в поражении цели. По формуле полной вероятности

P(A)=P(A|H1)P(H1)+ P(A|H2)P(H2)+ P(A|H3)P(H3).

P(A|H1)=0, P(A|H2)=1/2, P(A|H3)=2/3, P(H2)= ½, P(H3)=1/4.

Поэтому, P(A)= (1/2)(1/2)+(2/3)(1/4)=5/12.




Решить задачи: Полная вероятность. Формула Байеса


1.На трех станках различной марки изготовляется определенная деталь. Производительность первого станка за смену составляет 40 деталей, второго - 35 деталей, третьего – 25 деталей. Установлено, что 2, 3 и 5% продукции этих станков соответственно имеют скрытые дефекты. В конце смены на контроль взята одна деталь. Какова вероятность, что она нестандартная?

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

3. В ящике содержится 12 деталей, изготовленных на заводе №1, 20 деталей на заводе №2 и 18 деталей на заводе №3. Вероятность того, что деталь, изготовленная на заводе №1, отличного качества, равна 0,9; для деталей, изготовленных на заводах №2 и №3, эти вероятности соответственно равны 0,6 и 0,9. Найти вероятность того, что извлеченная наудачу деталь окажется отличного качества.

4. Два автомата производят одинаковые детали, которые поступают на общий конвейер. Производительность первого автомата вдвое больше производительности второго. Первый автомат производит в среднем 60% деталей отличного качества, а второй – 84%. Наудачу взятая с конвейера деталь оказалась отличного качества. Найти вероятность того, что эта деталь произведена первым автоматом.

5. В специализированную больницу поступают в среднем 50% больных с заболеванием К, 30% - с заболеванием L, 20% - с заболеванием М. Вероятность полного излечен6ия болезни К равна 0,7. Для болезней L и М эти вероятности соответственно равны 0,8 и 0,9. Больной, поступивший в больницу, был выписан здоровым. Найти вероятность того, что этот больной страдал заболеванием К.

6. Число грузовых автомашин, проезжающих по шоссе, на котором стоит бензоколонка, относится к числу легковых машин, проезжающих по тому же шоссе как 3:2. Вероятность того, что будет заправляться грузовая машина равна 0,1. для легковой машины эта вероятность равна 0,2. К бензоколонке подъехала для заправки машина. Найти вероятность того, что это грузовая машина.



Тема лекции: Схема Бернулли. Формула Бернулли


План:

  1. Схема Бернулли. Формула Бернулли

  2. Предельные теоремы для схемы Бернулли


  1. Схема Бернулли. Формула Бернулли


Пусть производится n независимых однотипных испытаний, в каждом из которых событие А может появиться с вероятностью Р. Тогда вероятность непоявления события А, т.е. Р(hello_html_68b47740.gif) равна q=1-p.

Вероятность того, что событие А произойдет в этих n независимых испытаниях ровно k раз, можно вычислить по формуле Бернулли

hello_html_1385830a.gif


Для определения вероятности появления события A менее m раз (< m), более m раз (> m), хотя бы один раз (hello_html_m26fb39d4.gif) и т. п. могут быть использованы формулы:

hello_html_m64bd4943.gif,

hello_html_5b170bc6.gif,

hello_html_m4959d2ea.gif.


Пример: Прибор состоит из пяти узлов. Надежность (вероят­ность безотказной работы в течение времени t ) для каждого узла равна 0,9. Узлы выходят из строя независимо один от друго­го. Найти вероятность того, что за время t откажут ровно два узла.


Решение: Рассмотрим событие А - выход узла из строя за время t. Число узлов n=5. Число отказавших узлов за время t: k=2.

Р(А) - вероятность выхода узла из строя: p =P(A)=0,1. Тогда q=1-p=1-0,1=0,9.

Теперь вычислим искомую вероятность по формуле Бернулли:

Р5(2) =hello_html_147fb795.gif(0,1)2.(0,9)3=10.0,01.0,729=0,0729.


Пример . Всхожесть семян данного растения равна 90 %. Найти вероятность того, что из четырех посеянных семян взойдут: а) три; б) не менее трех.


Решение

а) Искомую вероятность находим с помощью формулы Бернулли (14), учитывая что hello_html_e5397b.gif, hello_html_48437165.gif, hello_html_76364e8.gif, hello_html_m2de8dd9d.gif.

hello_html_5893116e.gif.

б) «Не менее трех» означает, что из четырех семян взойдут или три, или четыре. Так как эти события несовместны, то по теореме сложения искомая вероятность равна

hello_html_50025aba.gif.


  1. Предельные теоремы для схемы Бернулли


Теорема Пуассона. (Отметим, что на практике эта теорема применяется при hello_html_5379c8f1.gif Это означает, что p должно быть очень малым числом). Пусть имеется n независимых испытаний с вероятностью р успеха в одном испытании и q- вероятностью неудачи. Тогда для любого фиксированного m справедливо соотношение

hello_html_m4b5688ee.gif, где hello_html_m7008a69c.gif


Пример. Машинистка печатает текст, который содержит 20000 знаков. Каждый знак может быть напечатан неправильно с вероятностью 0.0004. Какова вероятность того, что в тексте не менее 3 опечаток?


Решение. Если опечатку считать успехом, то к этой задаче применима схема Бернулли при p=0.0004, n=20000. Поскольку λ=np=8, то можно использовать предельную теорему Пуассона. Поэтому, искомая вероятность равна 1-Pn0- Pn1- Pn2=1-e-8- 8 e-8-(64/2) e-8= 1-41 e-8=0.986.


Пример. Монета бросается 100 раз. Найти приближенно вероятность того, что герб выпадет 40 раз. (Воспользоваться таблицей )


Решение. Если считать успехом выпадение герба, то вероятность успеха равна 1/2. Поэтому используя предельную локальную теорему Муавра-Лапласа, получим

hello_html_m5bcd7cd3.gif, где hello_html_m35c249aa.gif

Таким образом, используя таблицы для плотности нормального распределения, получим P(A)=0.0108.


Интегральная теорема Муавра-Лапласа. Пусть имеется n независимых испытаний с вероятностью успеха p, hello_html_m185ef192.gif, в одном испытании и hello_html_55b2d5ea.gif - вероятностью неудачи. Величина hello_html_2489d00d.gifне зависит от n. Тогда .для любых вещественных чисел a<b при hello_html_10ae05b8.gif

P(a<hello_html_7413c59c.gif<b )=Φ(b)- Φ(a).

Здесь Φ(x)=hello_html_m2cdc3435.gif- функция Лапласа, значения которой заданы в таблицах, приведенных в большинстве задачников по вероятности и математической статистике.


Пример. При рождении ребенка вероятность рождения мальчика равна 0.512. Найти вероятность того, что среди 1000 новорожденных мальчиков родится больше, чем девочек.


Решение. Пусть A – это событие, соответствующее вопросу задачи, m это число рожденных мальчиков. Нетрудно видеть, что P(A) = P(m>500). Поскольку n=1000 можно считать достаточно большим, то применим интегральную теорему Муавра-Лапласа, согласно которой

P(A)=P(hello_html_67f436dd.gif

Задачи на закрепление материала


Пример. В урне 20 белых и 10 черных шаров. Вынули 4 шара, причем каждый вынутый шар возвращают в урну перед извлечением следующего и шары в урне перемешивают. Найти вероятность того, что из четырех вынутых шаров окажется 2 белых.

Решение: Событие А – достали белый шар. Тогда вероятности hello_html_5a67739d.gif, hello_html_5517656b.gif. По формуле Бернулли требуемая вероятностьhello_html_7ba61b04.gif.


Пример. Определить вероятность того, что в семье, имеющей 5 деталей, будет не больше трех девочек. Вероятности рождения мальчика и девочки предполагаются одинаковыми.

Решение: Вероятность рождения девочки hello_html_4415da96.gif, тогда hello_html_m6c784c98.gif.

Найдем вероятности того, что в семье нет девочек, родилась одна, две или три девочки:

hello_html_m787df2c5.gif, hello_html_m24ac3f3e.gif,

hello_html_m5c4761fb.gif, hello_html_m49fccd4c.gif.

Следовательно, искомая вероятность hello_html_5c249d19.gif.


Пример. Вероятность поражения цели при одном выстреле равна 0,8. Найти вероятность того, что при 100 выстрелах цель будет поражена 70 раз.


Решение: Из условия следует, что hello_html_54abead3.gif, hello_html_3811fe4c.gif, поэтому hello_html_263a4711.gif; hello_html_4882a2ba.gif. Поскольку hello_html_2a55efe5.gif, то можно воспользоваться формулой.

hello_html_m7d1e706d.gif.

По таблице приложения 1 находим hello_html_m494a5dda.gif. Поэтому hello_html_m5dbd76f3.gif.


Пример. Вероятность поражения цели при одном выстреле равна 0,8. Найти вероятность того, что при 100 выстрелах цель будет поражена от 75 до 90 раз.


Решение: Используем интегральную теорему Лапласа. В нашем случае hello_html_54abead3.gif, hello_html_3811fe4c.gif, hello_html_263a4711.gif, hello_html_50dbd00b.gif, hello_html_47b3ce82.gif.

hello_html_5506241a.gif, hello_html_m671c58de.gif.

По таблице приложения 1 находим

hello_html_5a910a72.gif, hello_html_m2240443c.gif.

Поэтому hello_html_f6c85ec.gif.


Пример. Устройство состоит из 1000 элементов, работающих независимо один от другого. Вероятность отказа любого элемента в течении времени Т равна 0,002. Найти вероятность того, что за время Т откажут ровно три элемента.

Решение N=1000, p=0,002, λ=np=2, k=3.

Искомая вероятность hello_html_13688d55.gif.


Пример. Завод отправил на базу 500 изделий. Вероятность повреждения изделия в пути 0,004. Найти вероятность того, что в пути повреждено меньше трех изделий.

Решение n=500, p=0,004, λ=2.

По теореме сложения вероятностей

hello_html_43bfca98.gif.


Пример. Магазин получил 1000 бутылок минеральной воды. Вероятность того, что при перевозке бутылка окажется разбитой, равна 0,003. Найти вероятность того, что магазин получит более двух разбитых бутылок.

Решение λ=np=1000·0,003=3

hello_html_160d010.gif

hello_html_59a3eaf.gif.



Тема 2.2. Дискретные случайные величины (ДСВ)



Тема лекции: Случайные величины. ДСВ. Распределение ДСВ


План:

  1. Случайные величины.

  2. Пример построения ряда распределения ДСВ

  3. Функция распределения ДСВ

  4. Пример построения функции от ДСВ.


  1. Случайные величины


Определение: Случайной величиной называется величина, которая в результате опыта примет одно и только одно возможное значение, при этом зара­нее неизвестно, какое именно.


Определение: Дискретной называют случайную величину, которая принимает от­дельные, изолированные значения.

Случайную величину в дальнейшем мы будем обозначать большой буквой Х, а ее возможные значения маленькой буквой х.

Например, Х- число попаданий при трех выстрелах. Возможные значения этой случайной величины: х1=0, х2=1, х3=2, х4=3. Рассмотрим случайную величину Х с возможными зна­чениями х1, х2,…хn . Каждое из этих значений случайная величина может принять с некоторой вероятностью:

Р(Х=х1)=р1, Р(Х=х2)=р2, … Р(Х=хn)=рn.

В результате опыта случайная величина Х примет только одно из этих значений, т.е. произойдет только одно из полной группы событий: Х=х1 ,Х=х2, … Х=хn.

Поскольку сумма вероятностей полной группы попарно несовмест­ных событий равна 1, то hello_html_m110419f4.gif


Определение: Законом распределения ДСВ называется соотношение между ее возможными значениями и их вероятностями (т. е. вероятностями, с которыми случайная величина принимает эти возможные значения).

Закон распределения может быть задан формулой (формулы Бернулли, Пуассона и др.), таблицей или графиком, а также функцией распределения.

хi

х1

х2

. . .

хn

Pi

р1

р2

. . .

рn

называется законом или рядом распределения дискретной случайной величины.


Пример ДСВ hello_html_2d589d49.gif – число точек на грани игрального кубика, выпадающее при его подбрасывании.


!Задание привести пример ДСВ из окружающей жизни

Закон распределения может быть задан формулой (формулы Бернулли, Пуассона и др.), таблицей или графиком, а также функцией распределения.


  1. Пример построения ряда распределения ДСВ


Пример: Два стрелка стреляют по мишени, делая по два выстре­ла каждый. Вероятность попадания в мишень при каждом выстреле для первого стрелка равна 0,7, а для второго - 0,6. Построить ряд распределения случайной величины Х – общего числа попаданий в мишень. Найти числовые характеристики этой случайной величины.


Решение: Случайная величина Х - общее число попаданий в мишень может принимать следующие значения: х1=0, х2=1, х3=2, х4=3, х5=4.

Случайная величина Х примет значение х1=0. когда прои­зойдет событие С - ни один из стрелков не попал в мишень. Со­бытие С произойдет в том случае, если одновременно произойдут следующие четыре события:

А1 - 1-й стрелок не попал в мишень при первом выстреле;

А2 - 1-й стрелок не попал в мишень при втором выстреле;

В1 - 2-й стрелок не попал в мишень при первом выстреле;

В2 - 2-й стрелок не попал в мишень при втором выстреле.

Отсюда следует: что событие С равно произведению независимых событий А1, А2, В1, В2. С= А1 .А2 .В1 .В2.

Откуда Р(С)=Р(А1).Р(А2).Р(В1).Р(В2).

По условию задачи 1-й стрелок попадает в мишень вероятностью 0,7, а 2-й - с вероятностью 0,6. Тогда вероятности непопадании в мишень для каждого стрелка будут следующими:

Р(А1) =Р(А2)=1-0,7=0,3; Р(В1 )=Р(В2)=1-0,6=0,4.

Вероятность того, что случайная величина Х примет значе­ние х1 = 0, равна вероятности события С :

Р(Х=0)=Р(С)=0,3 .0,3 .0,4 .0,4=0,0144.

Аналогично подсчитываем и другие вероятности:

Р(Х=1)=0,7.0,3.0,4 .0,4+0,3.0,7.0,4 .0,4+0,3.0,3.0,6.0,4+0,3.0,3.0,4 .

.0,6=0,1104.

Р(Х=2)=0,7.0,7.0,4 .0,4+0,3 .0,3 .0,4 .0,4+4 .(0,7 .0,3 .0,6 .0,4)=0,3124.

Р(Х=3)=0,3.0,7.0,6.0,6+0,7.0,3.0,6.0,6+0,7.0,7.0,4.0,6+0,7.0,7.0,6.0,4==0,3864.

Р(Х=4)=0,7 .0,7 .0,6 .0,6=0,1764.

Составим ряд распределения случайной величины Х.

хi

0

1

2

3

4

Pi

0,0144

0,1104

0,3124

0,3864

0,1764

Проверим тождество hello_html_m110419f4.gif.

0,0114+0,1104+0,З124+0,3864+0,1764 =1.


  1. Функция распределения ДСВ


Определение: Функцией распределения случайной величины hello_html_m11c65b7d.gif называется функция

hello_html_2a087742.gif,

определяющая вероятность того, что случайная величина hello_html_2d589d49.gif примет значение, меньшее hello_html_21f0f5da.gif.

Свойства функции распределения:

а) функция распределения принимает значения только из отрезка [0,1]:

0 ≤ F(x) ≤ 1;

б) F(x) – неубывающая функция, т.е. если x2 > x1, то F(x2) > F(x1) ;

в) F(- ∞ ) = 0; F(+ ∞) = 1;

г) вероятность того, что случайная величина примет значение из

интервала hello_html_m369e2252.gif (причем hello_html_1d2f9d3b.gif), равна:

hello_html_m6a9a667.gif;

Функция распределения содержит всю информацию об этой случайной величине и поэтому изучение случайной величины заключается в исследовании ее функции распределения, которую часто называют просто распределением.

У дискретной случайной величины функция распределения ступенчатая.


  1. Пример построения функции от ДСВ


Пример: Случайная величина X задана функцией распределения


x

1

2

3

4

p(x)

0,2

0,3

Р3

0,1

Найти вероятность р3. Построить функцию распределения. Найти числовые характеристики с.в.


Решение:

Проверим тождество hello_html_m325d424c.gif

0,2+0,3+р3+0,1=1.

р3=0,4.

Построим функцию распределения этой случайной величины.

Имеем:

hello_html_m408d796b.gif

Иhello_html_62d6c561.gifтак,

hello_html_cb0d588.png


Контрольные вопросы:


  1. С.в. ДСВ.

  2. Как построить ряд распределения ДСВ.

  3. Дайте определение функции распределения с.в.

  4. Как построить функцию распределения ДСВ


Задачи на закрепление материала


  1. Случайная величина X задана рядом распределения

x

4

6

8

10

12

p(x)

0,2

0,4

0,2

0,1

0,1

Построить функцию распределения

  1. Случайная величина X задана рядом распределения

x

2

4

10

6

8

p(x)

0,1

0,4

0,1

Р4

0,1

Найти р4. Построить функцию распределения.

  1. Пять однотипных приборов испытываются при пере­грузочных режимах. Вероятность пройти испытание для каждого при­бора равна 0,85. Испытания заканчиваются после выхода из строя первого же прибора. Построить ряд распределения случайной величи­ны- числа произведенных испытаний.

  2. Батарея состоит из трех орудий. Вероятности по­падания в цель при одном выстреле из 1-го, 2-го, 3-го орудия рав­ны соответственно 0,5; 0,6; 0,8. Каждое из орудий стреляет по некоторой цели один раз. Построить ряд распределения случайной ве­личины числа попаданий в цель.

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




Тема лекции: Числовые характеристики ДСВ


План:

  1. Математическое ожидание ДСВ.

  2. Дисперсия ДСВ.

  3. Среднее квадратическое отклонение ДСВ.


  1. Математическое ожидание ДСВ


Определение: Математическое ожидание ДСВ находится по формуле:

hello_html_m4991b756.gif


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


Механический смысл этого равенства заключается в следующем: математическое ожидание есть абсцисса центра тяжести системы материальных точек, абсцис­сы которых равны возможным значениям случайной величины, а массы - их вероятностям.


  1. Дисперсия ДСВ


Определение: Дисперсия случайной величины Х есть

hello_html_7c23bdc2.gif

Дисперсию случайной величины Х иногда удобнее вычислять по формуле

hello_html_2f5dcbf0.gif.


Вероятностный смысл Дисперсия случайной величины Х есть характеристика рассеива­ния разбросанности значений случайной величины около ее математи­ческого ожидания. Дисперсия случайной величины имеет размерность квадрата случайной величины.


  1. Среднее квадратическое отклонение


Для более наглядной характеристики рассеивания удобнее пользоваться величиной, имеющей размерность самой случайной величины. Поэтому вводится понятие среднего квадратического отклонения: hello_html_5345d9de.gif.


Пример: Случайная величина X задана функцией распределения


x

1

2

3

4

p(x)

0,2

0,3

Р3

0,1

Найти вероятность р3. Найти числовые характеристики с.в.


РЕШЕНИЕ:

Проверим тождество hello_html_m325d424c.gif

0,2+0,3+р3+0,1=1.

р3=0,4.

Найдем числовые характеристики случайной величины Х:

hello_html_m4991b756.gif

М(Х)=1.0,2+2.0,3+3.0,4+4.0,1=0,2+0,6+1,2+0,4=2,4.

Для вычисления дисперсии применим формулу: hello_html_579ad4ac.gif.

М(Х2 )=12. 0,2+22.0,3+32.0,4+42.0,1=0,2+1,2+3,6+1,6=6,6.

hello_html_3c6da1c4.gif.

hello_html_m52c2351d.gif


Контрольные вопросы:


  1. Дать определение дискретной случайной величины.

  2. Что такое математическое ожидание?

  3. Что такое дисперсия?

  4. Что такое среднее квадратичное отклонение?

  5. Дать определение закона распределения дискретной случайной величины.


Задачи на закрепление материала


1. Случайная величина X задана функцией распределения

x

4

6

8

10

12

p(x)

0,2

0,4

0,2

0,1

0,1

Найти числовые характеристики данной случайной величины.


2. Случайная величина X задана функцией распределения

x

2

4

10

6

8

p(x)

0,1

0,4

0,1

Р4

0,1

Найти р4. Найти числовые характеристики данной случайной величины.

3. Экзаменатор задает студенту не более четырех дополнительных вопросов. Вероятность того, что студент ответит на любой вопрос, равна 0,9. Преподаватель прекращает экзаменовать студента, как только студент обнаружит незнание заданного вопро­са. Составить ряд распределения случайной величины - числа допол­нительных вопросов, заданных студенту. Найти ее числовые характе­ристики.

4. В нашем распоряжении четыре лампочки, каждая из которых имеет дефект с вероятностью 0,08. Для отбора одной годной лампочки каждая: лампочка ввинчивается в патрон. При включении тока дефектная лампочка сразу же перегорает. Построить ряд распре­деления случайной величины - числа лампочек, которое будет испробовано. Найти ее числовые характеристики.


Тема 2.3. Непрерывные случайные величины (НСВ)



Тема лекции: Непрерывные случайные величины (НСВ)


  1. НСВ


Множество значений непрерывной случайной величины несчетно и обычно представляет собой некоторый промежуток конечный или бесконечный.


Пусть Х - некоторое действительное число. Вероятность события, состоящего в том, что с.в. Х примет значение, меньшее х, обозначим F(x), т.е. F(x)=Р(Х<х).


Определение: Функция F(x) называется функцией распределения с.в.Х или интегральной функцией.

Например, значение функции F(x) при х=2 равно вероятности того, что с.в. Х в результате испытания примет значение, меньшее двух, т.е. F(2)=Р(Х<2).


Определение: С. в. называется непрерывной (НСВ), если ее функция распределения F(x) является непрерывной функцией.

Свойства функции распределения:

  1. F(x)- неубывающая функция;

  2. hello_html_m7ce8203b.gif; hello_html_m4ffa2c4c.gif;

  3. Р(а≤Х<в)= F(в)-F(а).


Определение: Функция f(x)= F′(x) называется плотностью распределения вероятностей НСВ Х.

Функция f(x) существует во всех точках, где существует производная от функции распределения.


Определение: Плотность распределения называют также дифференциальной функцией распределения.


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


Свойства плотности распределения:

  1. f(x)≥0;

  2. hello_html_617965a.gif(характеристическое свойство)

3. Р(а<Х<в)= hello_html_289a5fc0.gif

Зная плотность распределения f(x), можно найти функцию распределения F(x) по формуле

F(x)= hello_html_m53e23cc3.gif.


Пример: Функция плотности непрерывной случайной величины имеет вид:

hello_html_67f579d1.gif

Определить константу C, построить функцию распределения F(x) и вычислить вероятность hello_html_4ac37505.gif.


Решение. Константа C находится из условия hello_html_m13a13ca0.gif Имеем:

hello_html_md209d29.gifоткуда C=3/8.

Чтобы построить функцию распределения F(x), отметим, что интервал [0,2] делит область значений аргумента x (числовую ось) на три части: hello_html_d414785.gif Рассмотрим каждый из этих интервалов. В первом случае (когда x<0) вероятность события {Х<x} вычисляется так:

hello_html_71735ae6.gif

так как плотность х на полуоси hello_html_m2d034d42.gifравна нулю.

Во втором случае

hello_html_36c41da2.gif

Наконец, в последнем случае, когда x>2,

hello_html_7d61f796.gifтак как плотность hello_html_278687bc.gif обращается в нуль на полуоси hello_html_35da2e4a.gif.

Итак, получена функция распределения

hello_html_5c61132f.gif

Вероятность hello_html_1a2d75e0.gif вычислим по формуле hello_html_m5a46a7ef.gif. Таким образом, hello_html_3e17bc15.gif


  1. Нахождение интегральной функция распределения НСВ


Пример: Дана плотность распределения случайной величины X: hello_html_425dc46b.gif

Требуется:

а) найти параметр A;

б) функцию распределения случайной величины X;

в) построить график функции распределения;

г) найти вероятность попадания случайной величины X в интервал hello_html_m66831106.gif.


Решение:

а) Параметр A подберем так, чтобы выполнялось свойство (2) плотности распределения: hello_html_1155039f.gif.

hello_html_m1a1bd2f4.gif, hello_html_m26d6e341.gif.

Отсюда hello_html_m548f85f6.gif.

б) Функцию распределения hello_html_61578d09.gif будем искать на каждом интервале отдельно.

Для значений hello_html_m5a034693.gif

hello_html_39c7a033.gif,

Для значений hello_html_m30ae5eb5.gif

hello_html_20d2d0ba.gif.

Для значений hello_html_m7c371c37.gif

hello_html_m709f9cca.gif.

Таким образом, hello_html_m7b3987bf.gif

hello_html_m3fde6883.gif
График этой функции изображен на рисунке

в) Вероятность попадания случайной величины X в интервал hello_html_m66831106.gif вычисляем по формуле hello_html_4a734416.gif:

hello_html_4a78adb.gif.

Контрольные вопросы:


  1. Дайте определение НСВ.

  2. Плотность и функция распределения.


Задачи на закрепление материала


Дана плотность распределения f(x) случайной величины X. Требуется:

а) найти параметр c;

б) функцию распределения случайной величины X;

в) построить графики функции распределения и плотности распределения;

г) вероятность попадания случайной величины X в интервал hello_html_m43456a0e.gif.

1.

hello_html_m53ac486c.gif

 = 0,1;  = 1,2.

2.

hello_html_69475490.gif

 = 2,5;  = 7,1.


3.Задан график плотности распределения с.в. Х

hello_html_5cde7c02.giff(x)



hello_html_12d0a5af.gifа


hello_html_m2aded293.gifhello_html_33fc9065.gifhello_html_m3ef944b9.gif

а х

1) Записать функцию f(x).

2)Найти F (x).

3)Построить графики функций F(x).

4)Вычислить Р(а/2<X<a).



Тема лекции: Числовые характеристики НСВ


Математическое ожидание с.в. Х находится по формул

М(Х)= hello_html_m10d15c93.gif,

если сходится несобственный интеграл.


Дисперсией с.в. Х называют несобственный интеграл

Д(Х)= hello_html_m239c73a4.gif,

если он сходится.

Для вычисления дисперсии более удобна следующая формула:

Д(Х)= hello_html_2e7f39f5.gif


Пример. Случайная величина Х задана плотностью распределения

hello_html_14523bb8.gif

Найти математическое ожидание, дисперсию и среднеквадратичное отклонение с.в. Х.

Воспользуемся определениями.

hello_html_533bbd44.gif.

hello_html_m3744aa6e.gif.

hello_html_346dcd3f.gif.

hello_html_m4aa5b60a.gif.


Пример: Плотность распределения с.в. задана функцией

hello_html_m6d35324d.gif

1) Найти а, F(x), М(Х), Д(Х).

2) Вычислить Р(-2<X<1/2).


Решение: Для нахождения параметра а воспользуемся свойством плотности распределения вероятностей: hello_html_m12081b16.gif

hello_html_2e09198c.gifОтсюда находим а=hello_html_m35ce15b3.gif.

Тогда функцию плотности распределения можно записать следующим образом:

hello_html_51282149.gif

Найдем функцию распределения вероятностей F(x):

Для х<-1 F(x)=hello_html_m46ae7549.gif

Для -1≤х<0 F(x)=hello_html_27edbbea.gif

Для 0≤х<1 hello_html_m5b1d829.gif

Для х≥1

hello_html_m4002651a.gif

Следовательно, функция распределения имеет вид:

hello_html_73db51a3.gif

Вычислим числовые характеристики с.в. Х .


Математическое ожидание

hello_html_2b9396b8.gif


Дисперсия

hello_html_m6fe939dc.gif


2) Вычислим Р(-2<X<1/2).

Вычислить эту вероятность можно двумя способами: с помощью функции плотности или с помощью функции распределения вероятностей.

hello_html_m4ff6c91e.gif

или

Р(-2<X<1/2)=F(1/2)-F(-2)=hello_html_1af94151.gif


Задачи на закрепление материала


Дана плотность распределения f(x) случайной величины X. Требуется:

а) найти параметр c;

б) функцию распределения случайной величины X;

в) найти числовые характеристики случайной величины X;

г) вероятность попадания случайной величины X в интервал hello_html_m43456a0e.gif.


10.

hello_html_262ff703.gif

 = 3,2;  = 6,4.

20.

hello_html_m66298fb6.gif

 = 1;  = 2.



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


  1. Равномерное распределение


Равномерным называют распределение вероятностей непрерывной случайной величины X, если на отрезке hello_html_m4e6c2a53.gif, которому принадлежат все возможные значения X, плотность распределения сохраняет постоянное значение, а именно:

hello_html_m78c61fe8.gif,

вне этого отрезка hello_html_m64f8424c.gif.

Математическое ожидание и дисперсия равномерно распределенной случайной величины определяются выражениями:

hello_html_f80be39.gif, hello_html_367f7524.gif.


  1. Показательное распределение


Непрерывная случайная величина X имеет показательное (или экспоненциальное) распределение, если ее плотность распределения имеет вид:

hello_html_m3ba90722.gif

где hello_html_m55f56e8e.gif, hello_html_m1d96a188.gif.

Числовые характеристики этого распределения определяются равенствами:

hello_html_me6e1425.gif, hello_html_m5d031d1d.gif.


  1. Нормальное распределение


Непрерывная случайная величина X имеет нормальное распределение (или распределение Гаусса), если ее плотность распределения имеет вид:

hello_html_m161e472e.gif.

Постоянные a и ( > 0) называются параметрами нормального распределения и представляют собой соответственно математическое ожидание и среднеквадратическое отклонение случайной величины X, т. е.

hello_html_m664eb9e8.gif, hello_html_112b2176.gif.

Отсюда hello_html_m28d0993e.gif.

hello_html_2e5b8e05.gifГрафик функции hello_html_m7c9787.gif называют нормальной кривой (или кривой Гаусса). Кривая имеет форму «колокола», симметричного относительно прямой hello_html_6549e1c6.gif (рис. 1).

Функция распределения нормальной случайной величины

hello_html_m4dab3aa6.gif

связана с функцией Лапласа соотношением

hello_html_m95e055f.gif.

где hello_html_m44db2e8f.gif - функция Лапласа, таблицу значений которой можно найти в приложениях.


Замечание: Ф(х) - функция нечетная, т.е. Ф(-х)=-Ф(х).

Поэтому для нормальной случайной величины справедлива формула

hello_html_53822256.gif.

Вероятность того, что абсолютная величина отклонения нормальной случайной величины меньше положительного числа , равна:

hello_html_m466b453b.gif.

В частности,

hello_html_31ac047c.gif.

Отсюда следует «правило трех сигм»: если случайная величина X имеет нормальное распределение, то отклонение этой случайной величины от ее математического ожидания по абсолютной величине не превышает утроенное среднее квадратическое отклонение (3).


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


Пример. Нормально распределенная случайная величина X задана плотностью вероятности hello_html_7541f97b.gif. Требуется найти:

а) математическое ожидание и дисперсию X;

б) вероятность того, что X примет значение, принадлежащее интервалу hello_html_m5bd47949.gif;

в) вероятность того, что абсолютная величина отклонения X от математического ожидания окажется меньше 5.


Решение.

а) Сравнив данную функцию с плотностью нормального распределения, заключаем, что hello_html_m3e9321e2.gif, hello_html_7358836.gif. Следовательно, hello_html_m30e2775d.gif, hello_html_m33c966e4.gif.

б) Воспользуемся формулой hello_html_53822256.gif.

В нашем случае hello_html_m3e9321e2.gif, hello_html_7358836.gif,  = 3;  = 10.

hello_html_6a2b1a14.gifЗначения hello_html_5b000573.gif и hello_html_5713d45d.gif определили по таблице значений функции Лапласа.

в) Воспользуемся формулой hello_html_m466b453b.gif, где hello_html_m3e9321e2.gif, hello_html_7358836.gif,  = 5.

hello_html_3701909d.gif.


Пример: Ошибка измерительного прибора - случайная величи­на, распределенная по нормальному закону, со средним квадратическим отклонением 3 мк. Систематическая ошибка прибора отсутствует. Какова вероятность того, что в независимом измерении ошибка окажется в интервале (0 ; 2,4)?


Решение: Вычислим вероятность того, что в результате измерения случайная, величина Х - ошибка измерительного прибора будет принадлежать интервалу (0 ; 2,4):

hello_html_m6c63677e.gif

Здесь математическое ожидание a=0 (так как систематическая ошибка отсутствует, то среднее значение ошибки при большом числе измерений будит равно нулю).

Ф(0)=0, Ф(0,8)=0,2881 находим по таблице Лапласа.

Теперь найдем вероятность события hello_html_m3b117811.gif, состоящего в том, что в результате трех измерений


Пример: Случайная величина Х распределена нормально с математическим ожиданием, равным 10. Вероятность того, что слу­чайная величина Х примет значение, принадлежащее интервалу (4 ; 16), равна 0,8664. Найти среднее квадратическое отклонение этой случайной величины.


Решение: По условию задачи случайная величина Х имеет мате­матическое ожидание а=10 и hello_html_m612c65aa.gif

Но, с другой стороны,

hello_html_70a9d7ed.gif

где σ - среднее квадратическое отклонение случайной величи­ны Х.

Итак, 2Ф(hello_html_a973276.gif)=0,8664 или Ф(hello_html_a973276.gif)=0,4332.

По таблице значений функции Лапласа находим hello_html_a973276.gif=1,5. Отку­да σ=4.


Задачи на закрепление материала


Нормально распределенная случайная величина X задана плотностью вероятности f(x). Требуется найти:

а) математическое ожидание и дисперсию X;

б) вероятность того, что X примет значение, принадлежащее интервалу hello_html_m43456a0e.gif;

в) вероятность того, что абсолютная величина отклонения hello_html_67e6bdfb.gif окажется меньше .

1.

hello_html_661dcd0b.gif,

 = 11;  = 21;  = 6.

3.

hello_html_4137a1ef.gif,

 = 6;  = 15;  = 8.

2.

hello_html_m7b32c07f.gif,

 = 9;  = 19;  = 4.

4.

hello_html_20e04dc5.gif,

 = 2;  = 15;  = 3.



Практические занятия


  1. Практическое занятие №2 «Применение стандартных методов и моделей к решению вероятностных задач. Вычисление вероятностей событий по классической формуле определения вероятности»

  2. Практическое занятие №3 «Вычисление вероятностей событий, используя теоремы сложения, умножения вероятностей»

  1. Практическое занятие №4 «Применение стандартных методов и моделей к решению вероятностных задач. Вычисление вероятностей сложных событий»Практическое занятие №5 «Решение задач на запись ДСВ»

  1. Практическое занятие №6 «Вычисление числовых характеристик ДСВ»Практическое занятие №7 «Нахождение интегральной функция распределения НСВ»

  2. Практическое занятие №8 «Вычисление характеристик НСВ с помощью функции плотности»

Практическое занятие №9 «Вычисление вероятностей для нормального распределения»


Раздел 3. Основы математической статистики


Тема 3.1. Выборочный метод. Статистические оценки параметров распределения



Тема лекции: Математическая статистика


План:

  1. Основные понятия математической статистики

  2. Графическое изображение выборки

  3. Точечные оценки параметров распределения


  1. Основные понятия математической статистики


На практике функция распределения случайной величины бывает неизвестна и ее определяют по результатам наблюдений или, как говорят, по выборке. Выборкой объема n для случайной величины называется последовательность независимых наблюдений этой величины, где hello_html_68500c12.gif – совокупность значений, принятых независимыми случайными величинами hello_html_meb6daac.gif, имеющими тот же закон распределения hello_html_26b980f2.gif, что и величина X. В этом случае говорят, что выборка hello_html_68500c12.gif взята из генеральной совокупности величины X, а под законом распределения генеральной совокупности понимают закон распределения случайной величины X. Значения hello_html_68500c12.gif называют выборочными значениями или вариантами. Последовательность вариант, записанных в возрастающем порядке, называется вариационным рядом. Число, указывающее, сколько раз наблюдается данная варианта, называется частотой варианты, а отношение частоты варианты к объему выборки – относительной частотой.


Если hello_html_68500c12.gif – вариационный ряд, а x – произвольное число, и nx – количество выборочных значений, меньших x, то hello_html_m63071de5.gif – частота попадания выборочных значений левее точки x в данной выбоке объема n, т. е. частота события hello_html_m474bf77d.gif.


Эта частота является функцией от x и называется эмпирической функцией распределения случайной величины X, полученной по данной выборке. Если обозначить эту функцию через hello_html_m1ed857d5.gif, то по определению

hello_html_631c298.gif.

Эмпирическая функция распределения hello_html_m1ed857d5.gif обладает всеми свойствами функции распределения hello_html_26b980f2.gif. Так как частота события в n независимых опытах является оценкой вероятности этого события, то значение эмпирической функции распределения в точке x есть оценка вероятности события hello_html_m474bf77d.gif, то есть оценка теоретической функции распределения hello_html_26b980f2.gif:

hello_html_2fda62a.gif.

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

hello_html_mf40e831.gif,

hello_html_53f61c9b.gif, hello_html_m3cea7577.gif.

Таблица 1 Таблица 2

x1

x2

...

xk


hello_html_m58047882.gif

hello_html_m1b02f8b2.gif

...

hello_html_2b713f75.gif

n1

n2

...

nk


n1

n2

...

nk

w1

w2

...

wk


w1

w2

...

wk

В случае непрерывного распределения величины X статистический ряд распределения представляет собой таблицу, в которой заданы интервалы значений величины X и соответствующие им частоты или относительные частоты, причем интервалы располагаются в порядке возрастания величины X (табл. 2).

Второй случай легко сводится к первому, если в качестве вариант брать середины интервалов:

hello_html_58e33c6.gif, hello_html_678918b2.gif.


  1. Графическое изображение выборки


Графически табл. 1 изображается полигоном частот, представляющим собой ломаную, отрезки которой соединяют на плоскости соседние точки hello_html_m5a62a6a4.gif и hello_html_1753e213.gif или hello_html_7f91596d.gif и hello_html_m2d12cadc.gif, если строится полигон относительных частот.

В случае табл. 2 исходный интервал, в котором заключены все наблюдаемые значения признака, разбивают на определенное количество равных интервалов длины hello_html_6b3b763b.gif. После этого строится гистограмма частот – ступенчатая фигура, состоящая из прямоугольников, основания которых равны h, а высоты равны отношению hello_html_3f998266.gif (или hello_html_b37c3c.gif для гистограммы относительных частот).

Гистограмма относительных частот является аналогом функции плотности, так как площадь под ней равна единице. Число интервалов разбиения находят по формуле hello_html_2eb3f7b0.gif, где n – объем выборки. Тогда длина каждого интервала hello_html_m45021880.gif, где hello_html_406f9c05.gif и hello_html_4ac9c548.gif– максимальное и минимальное значение выборки соответственно.


  1. Точечные оценки параметров распределения


По аналогии с такими числовыми характеристиками случайной величины, как математическое ожидание, дисперсия и среднее квадратическое отклонение, для выборки hello_html_68500c12.gif случайной величины X и для статистического ряда определяются следующие числовые характеристики:

выборочная средняя hello_html_m70006db5.gif,

где k – число вариант и hello_html_mecfa664.gif;

выборочная дисперсия hello_html_m22b4c097.gif

или hello_html_m2afd7cb1.gif, hello_html_m3c2fe3b8.gif;

выборочное среднее квадратическое отклонение hello_html_m1b7f03f9.gif


Во многих случаях бывает заранее известно, что функция распределения hello_html_26b980f2.gifпринадлежит к определенному классу функций распределения, зависящих от одного или нескольких параметров: hello_html_73bba943.gif. В этом случае определение неизвестной функции распределения сводится к оценке неизвестных параметров по результатам выборки. Следует заметить, что ни при каких n нельзя определить по выборке точное значение неизвестного параметра, а можно найти его приближенное значение, которое называется оценкой по выборке неизвестного параметра. Всякая оценка по выборке является функцией hello_html_m8c9136a.gif от выборочных значений hello_html_68500c12.gif, так как она меняется от выборки к выборке. Функцию hello_html_m19ae0542.gif подбирают так, чтобы случайная величина hello_html_m68b40337.gifпо возможности более точно аппроксимировала неслучайное неизвестное число a.


Для выполнения данного условия накладывают следующие требования на оценку: несмещенность оценки, ее эффективность и состоятельность. Наиболее часто применяемыми метода получения оценок являются метод моментов и метод максимального правдоподобия.


Несмещенной и состоятельной оценкой математического ожидания hello_html_1636616b.gif является выборочная средняя hello_html_6fd3bfb5.gif.


Несмещенная и состоятельная оценка hello_html_5f4df1f9.gif дисперсии hello_html_26465279.gif вычисляется по формуле:

hello_html_m23147a16.gif.

где hello_html_5f4df1f9.gif – исправленная дисперсия.


Для оценки среднего квадратического отклонения используется величина S, равная квадратному корню из исправленной дисперсии, которая называется исправленным средним квадратическим отклонением.


Рассмотренные оценки характеризуются одним числом и называются точечными.


Пример 1. По заданному статистическому ряду (табл. 1) требуется:

а) построить гистограмму относительных частот;

б) перейти к вариантам и построить полигон относительных частот;

в) построить эмпирическую функцию распределения.

Таблица 1

hello_html_262cb400.gif

12 –15

15 – 18

18 – 21

21 – 24

24 – 27

27 – 30

hello_html_5b76c0e0.gif

2

6

12

19

7

4


Решение

а) Объем выборки hello_html_m202eddc7.gif.

Определяем относительные частоты hello_html_53f61c9b.gif и составляем табл. 2 с относительными частотами:

Таблица 2

hello_html_262cb400.gif

12 –15

15 – 18

18 – 21

21 – 24

24 – 27

27 – 30

hello_html_m12365aca.gif

0,04

0,12

0,24

0,38

0,14

0,08

Для построения гистограммы относительных частот на оси абсцисс откладываются частичные интервалы длины hello_html_3239bea8.gif, а над ними проводятся горизонтальные отрезки на расстоянии hello_html_m66a6151d.gif (рис. 1).

hello_html_m62bfac31.gif

б) Перейдем к вариантам, положив их равными серединам частичных интервалов hello_html_m2bb7f6d6.gif, где hello_html_569c243.gif, hello_html_62e8887e.gif– концы интервалов. Тогда табл. 2 превратится в табл. 3:

Таблица 3

hello_html_569c243.gif

13,5

16,5

19,5

22,5

25,5

28,5

hello_html_m12365aca.gif

0,04

0,12

0,24

0,38

0,14

0,08

Отметим на плоскости точки hello_html_m44092c85.gif и, соединив соседние точки, получим полигон относительных частот (рис. 2).

hello_html_cb2dc68.gif

в) Эмпирическая функция распределения hello_html_m1ed857d5.gif строится по закону:

hello_html_1676650b.gif

В нашем случае получаем:

hello_html_f8c2d6c.gif

График функции hello_html_m1ed857d5.gif представлен на рис. 3.


hello_html_688df780.gif
Пример 2. В условиях примера 1 найти статистические оценки.

Решение Обратимся к табл. 3: hello_html_m46fcf303.gif; hello_html_4b1cbc36.gif;hello_html_3db397b9.gif.


Контрольные вопросы:


  1. Что такое выборка?

  2. Что такое варианта выборки и частота?

  3. Как графически изображается выборка?

  4. Точечные оценки выборки.


Задачи на закрепление материала


Статистический ряд задан таблицей. Требуется:

а) построить гистограмму относительных частот;

б) перейти к вариантам и построить полигон относительных частот;

в) записать эмпирическую функцию распределения и построить ее график;

г) найти точечные оценки hello_html_m726c2fb0.gif, hello_html_m72b2ff92.gif, hello_html_m6c04fa8e.gif;

1.

(–6; –4)

(–4; –2)

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

2

6

17

18

4

3


2.

(0; 2)

(2; 4)

(4; 6)

(6; 8)

(8; 10)

(10; 12)

1

3

19

21

4

2


3.

(–4; –2)

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

(6; 8)

3

8

14

15

9

1


4.

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

(6; 8)

(8; 10)

1

4

20

19

4

2




Тема лекции: Интервальные оценки параметров распределения


План:

  1. Интервальная оценка математического ожидания нормального распределения.

  2. Интервальная оценка среднего квадратического отклонения нормального распределения.

  3. Интервальная оценка вероятности события



Определение: Интервальной называют оценку, которая определяется двумя числами – концами интервала.

Так как любая оценка hello_html_m68b40337.gif есть некоторое приближение оцениваемой величины a, то возникает вопрос об оценке точности данного приближения, т. е. можно ли утверждать, что hello_html_225d1c7d.gif для некоторого hello_html_668200cc.gif.

Однако статистические методы не позволяют категорически утверждать, что оценка hello_html_m68b40337.gif удовлетворяет неравенству hello_html_225d1c7d.gif. Можно лишь говорить о вероятности наступления события, заключающегося в том, что мы получили оценку с точностью : hello_html_62cd7039.gif. Эта вероятность называется доверительной вероятностью (или надежностью), а интервал hello_html_m30b17e87.gifдоверительным интервалом. Вероятность того, что интервал hello_html_4d355254.gif заключает в себе неизвестный параметр a, равна . Обычно надежность выбирают близкой к единице (0,95; 0,99; 0,999).


  1. Интервальная оценка математического ожидания нормального распределения


Если случайная величина распределена нормально и среднее квадратическое отклонение известно, то доверительный интервал для оценки математического ожидания a

hello_html_m449f79ce.gif, (1)

где n – объем выборки, t находится из равенства hello_html_m2f58c1fd.gif по таблице значений функции Лапласа hello_html_27b2bd12.gif.


Если неизвестно, то в формуле (1) оно заменяется на исправленное среднее квадратическое отклонение S, t заменяется на hello_html_m406f0b2e.gif, которое находится по таблице (приложение )

hello_html_59f80ac6.gif. (2)


  1. Интервальная оценка среднего квадратического отклонения нормального распределения


Доверительный интервал для оценки среднего квадратического отклонения нормального распределения с заданной надежностью находится по формуле

hello_html_4e7d9cd1.gif, (3)

где hello_html_m777f535d.gif находится по таблице (приложение ).


Пример 1. Дано распределение частот выборки (табл. 1). Найти доверительные интервалы для математического ожидания a и среднего квадратического отклонения с доверительной вероятностью  = 0,95, если известно, что генеральная совокупность распределена по нормальному закону


Таблица 1

hello_html_262cb400.gif

12 –15

15 – 18

18 – 21

21 – 24

24 – 27

27 – 30

hello_html_5b76c0e0.gif

2

6

12

19

7

4


Решение

Имеем: hello_html_m6c4f00a9.gif, hello_html_m20dde10.gif, hello_html_m28e78005.gif. Так как объем выборки hello_html_301fe3ad.gif, то находим

hello_html_6f04c68f.gif.

По таблице приложения  находим

hello_html_260ae99d.gif.

Подставляя полученные значения S и t в формулу (2), получим

hello_html_m4a6addae.gif

или

hello_html_15e7ee85.gif.

По таблице приложения  найдем hello_html_m21f33b32.gif.

Подставляя значения S и q в формулу (3), получим

hello_html_m3750385e.gif

или

hello_html_m345e0bfa.gif.


3.Интервальная оценка вероятности события


Интервальной оценкой (с надежностью hello_html_368a497d.gif) неизвестной вероятности р биномиального распределения по относительной частоте hello_html_m40407ad2.gif служит доверительный интервал (с приближенными концами р1 и р2) hello_html_m4a718a49.gif,

где hello_html_6fdee659.gif

n- общее число испытаний;

m- число появления события;

hello_html_m40407ad2.gif- относительная частота, равная отношению m/n;

t- значение аргумента функции Лапласа, при котором hello_html_m2f58c1fd.gif. (hello_html_368a497d.gif - заданная надежность).


Замечание: При больших значениях n (порядка сотен) можно принять в качестве приближенных границ доверительного интервала

hello_html_6a2d1b84.gif


Пример: Производятся независимые испытания с одинаковой, но неизвестной вероятностью р появления события А в каждом испытании. Найти доверительный интервал для оценки вероятности р с надежностью 0,95, если в 60 испытаниях событие А появилось 15 раз.


Решение: По условию, n=60, m=15, hello_html_368a497d.gif=0.95. Найдем относительную частоту появления события А: hello_html_m310c373.gif.

Найдем t из соотношения hello_html_696afa8f.gif. По таблице функции Лапласа находим t=1,96.

Найдем границы искомого доверительного интервала:

hello_html_6fdee659.gif

Подставив в эти формулы n=60, hello_html_6e3d6392.gif, t=1,96, получим р1=0,16, р2=0,37.

Итак, искомый доверительный интервал hello_html_2ea55df9.gif.


Пример: Изготовлен экспериментальный игровой автомат, который должен обеспечить появление выигрыша в одном случае из 100 бросаний монеты в автомат. Для проверки пригодности автомата произведено 400 испытаний, причем выигрыш появился 5 раз. Найти доверительный интервал, покрывающий неизвестную вероятность появления выигрыша с надежностью hello_html_368a497d.gif=0.999.


Решение: Найдем относительную частоту появления выигрыша hello_html_m7d594566.gif.

Найдем t из соотношения hello_html_m66794583.gif. По таблице функции Лапласа находим t=3,3.

Учитывая, что n=400 велико, используем для отыскания границ доверительного интервала приближенные формулы: hello_html_m430f488.gif

Подставив в эти формулы n=400, hello_html_m677b60ff.gif, t=3,3,

получим р1= -0,0058, р2= 0,0308.

Итак, искомый доверительный интервал hello_html_m26d24832.gif.


Задачи на закрепление материала


Считая генеральную совокупность нормальной, найти интервальные оценки для и a с надежностью 0,95.

1.

(–6; –4)

(–4; –2)

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

2

6

17

18

4

3


2.

(0; 2)

(2; 4)

(4; 6)

(6; 8)

(8; 10)

(10; 12)

1

3

19

21

4

2


3.

(–4; –2)

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

(6; 8)

3

8

14

15

9

1


4.

(–2; 0)

(0; 2)

(2; 4)

(4; 6)

(6; 8)

(8; 10)

1

4

20

19

4

2


5.

(0; 2)

(2; 4)

(4; 6)

(6; 8)

(8; 10)

(10; 12)

1

5

18

19

4

3


6. Производятся независимые испытания с одинаковой, но неизвестной вероятностью р появления события А в каждом испытании. Найти доверительный интервал для оценки вероятности р с надежностью 0,99, если в 100 испытаниях событие А появилось 60 раз.

7. Производятся независимые испытания с одинаковой, но неизвестной вероятностью р появления события А в каждом испытании. Найти доверительный интервал для оценки вероятности р с надежностью 0,95, если в 300 испытаниях событие А появилось 250 раз.




Тема 3.2. Моделирование случайных величин



Тема лекции: Моделирование случайных величин. ДСВ. НСВ


План:

  1. Разыгрывание ДСВ.

  2. Разыгрывание полной группы событий.

  3. Разыгрывание НСВ.


Моделирование (разыгрывание) с.в. проводится методом Монте-Карло.


Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. С этой целью выбирают с.в.Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: вычисляют (разыгрывают) n возможных значений xi с.в.Х, находят их среднее арифметическое hello_html_m12e308bf.gif и принимают hello_html_40cc3bad.gif в качестве оценки (приближенного значения) hello_html_2feb4d4e.gif искомого числа а: hello_html_m2ca0f0ae.gif.


1.Разыгрывание ДСВ


ПРАВИЛО: Для того, чтобы разыграть ДСВ Х, заданную законом распределения

Х

х1

х2

хn

р

р1

р2

рn

надо:

  1. Разбить интервал (0,1) оси Or на частичных интервалов: hello_html_151dab76.gif

  2. Выбрать (например, из таблицы случайных чисел) случайное число rj.

Если rjпопало в частичный интервал hello_html_8a1d1e9.gif, то разыгрываемая величина приняла возможное значение xi.


ПРИМЕР: Разыграть шесть возможных значений ДСВ Х, закон распределения которой задан в виде таблицы:

Х

2

10

18

р

0,22

0,17

0,61


Решение:

  1. Разобьем интервал (0,1) оси Or точками с координатами 0,22: 0,22+0,17=0,39 на три частичных интервала: hello_html_5ce93e5.gif

  2. Выпишем из таблицы случайных чисел (приложение) шесть случайных чисел, например 0,32; 0,17; 0,90; 0,05; 0,97; 0,87 (пятая строка снизу).

Случайное число r1=0.32 принадлежит частичному интервалу hello_html_62b2b4a7.gif, поэтому разыгрываемая ДСВ приняла возможное значение х2=10; случайное число r2=0.17 принадлежит частичному интервалу hello_html_6be9e7bd.gif, поэтому разыгрываемая ДСВ приняла возможное значение х1=2.

Аналогично получим остальные возможные значения.

Итак, разыгранные возможные значения таковы: 10; 2; 18; 2; 18; 18.


2.Разыгрывание полной группы событий


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


ПРАВИЛО: Для того, чтобы разыграть испытания, в каждом из которых наступает одно из событий А1, А2,…,Аnполной группы, вероятности которых р1, р2, …, рn известны, достаточно разыграть (по правилу для ДСВ) ДСВ Х со следующим законом распределения:

Х

1

2

n

р

р1

р2

рn

Если в испытании величина Х приняла возможное значение xi=i., то наступило событие Аi.


ПРИМЕР: Заданы вероятности трех событий: А1, А2, А3, образующих полную группу: р1=Р(А1)=0,22, р2=Р(А2)=0,31, р3=Р(А3)=0,47. Разыграть пять испытаний, в каждом из которых появляется одно из трех рассматриваемых событий.


Решение:

В соответствии с правилом надо разыграть ДСВ Х с законом распределения

Х

1

2

3

р

0,22

0,31

0,47

По правилу для ДСВ разобьем интервал (0,1) на три частичных интервала: hello_html_m5b5b87e2.gif

Выпишем из таблицы случайных чисел (приложение) пять случайных чисел, например 0,61; 0,19; 0,69; 0,04; 0,46.

Случайное число r1=0.61 принадлежит частичному интервалу hello_html_6ea6da5d.gif, Х=3 и, следовательно, наступило событие А3.

Аналогично найдем остальные события.

Получим последовательность событий: А3, А1, А3, А1, А3.


3.Разыгрывание НСВ


Известна функция распределения F(x) НСВ Х. Требуется разыграть Х, т.е. вычислить последовательность возможных значений xi.


Метод обратных функций:


ПРАВИЛО 1: Для того, чтобы разыграть возможное значение xi НСВ Х, зная ее функцию распределения F(x), надо выбрать случайное число ri , приравнять его функции распределения и решить относительно xi полученное уравнение F(xi)=ri,

Если известна плотность вероятности f(x) , то используют правило 2.


ПРАВИЛО 2: Для того, чтобы разыграть возможное значение xi НСВ Х, зная ее плотность вероятности f(x), надо выбрать случайное число ri и решить относительно xi уравнение

hello_html_6e4ea22.gif, или уравнение hello_html_189b2ab9.gif,

где а – наименьшее конечное возможное значение Х.


ПРИМЕР: Найти явную формулу для разыгрывания равномерно распределенной с.в. Х, заданной плотностью вероятности f(x)=b/(1+ax)2 в интервале (0;1/(b-a)); вне этого интервала f(x)=0.

Решение:

Используем правило 2, напишем уравнение hello_html_43116a13.gif.

Решив это уравнение относительно xi , окончательно получим hello_html_m2bbd65b6.gif.


Контрольные вопросы:


  1. Разыгрывание ДСВ. Правило.

  2. Разыгрывание полной группы событий. Правило.

  3. Разыгрывание НСВ. Правило.


Задачи на закрепление материала


  1. Разыграть шесть возможных значений ДСВ Х, закон распределения которой задан в виде таблицы:

Х

3

5

8

р

0,2

0,3

0,5


  1. Заданы вероятности трех событий: А1, А2, А3, образующих полную группу: р1=Р(А1)=0,14, р2=Р(А2)=0,26, р3=Р(А3)=0,6. Разыграть пять испытаний, в каждом из которых появляется одно из трех рассматриваемых событий.

  2. Разыграть четыре возможных значения НСВ Х, распределенной равномерно в интервале(6;16).

  3. Найти явную формулу для разыгрывания равномерно распределенной с.в. Х, заданной плотностью вероятности f(x)=5 в интервале (0;0,2); вне этого интервала f(x)=0.




Тема 3.3. Современные пакеты прикладных программ многомерного статистического анализа



Тема лекции: Применение современные пакеты прикладных программ многомерного статистического анализа


1. Основные статистические характеристики.


Электронные таблицы Excel имеют огромный набор средств для анализа статистических данных. Наиболее часто используемые статистические функции встроены в основное ядро программы, то есть эти функции доступны с момента запуска программы. Другие более специализированные функции входят в дополнительную подпрограмму, называемую пакетом анализа. Команды и функции пакета анализа называют Инструментами анализа. Мы ограничимся изучением нескольких основных встроенных статистических функций и наиболее полезных инструментов анализа из пакета.


Среднее значение.

Функция СРЗНАЧ (или AVERAGE) вычисляет выборочное (или генеральное) среднее, то есть среднее арифметическое значение признака выборочной (или генеральной) совокупности. Аргументом функции СРЗНАЧ является набор чисел, как правило, задаваемый в виде интервала ячеек, например, =СРЗНАЧ (А3:А201).


Дисперсия и среднее квадратическое отклонение.

Для оценки разброса данных используются такие статистические характеристики, как дисперсия D и среднее квадратическое (или стандартное) отклонение hello_html_7691e7c8.gif. Стандартное отклонение есть квадратный корень из дисперсии: hello_html_1aa7bd4c.gif. Большое стандартное отклонение указывает на то, что значения измерения сильно разбросаны относительно среднего, а малое – на то, что значения сосредоточены около среднего.

В Excel имеются функции, отдельно вычисляющие выборочную дисперсию Dв и стандартное отклонение hello_html_7691e7c8.gifв и генеральные дисперсию Dг и стандартное отклонение hello_html_7691e7c8.gifг. Поэтому, прежде чем вычислять дисперсию и стандартное отклонение, следует четко определиться, являются ли ваши данные генеральной совокупностью или выборочной. В зависимости от этого нужно использовать для расчета Dг и hello_html_7691e7c8.gifг , Dв и hello_html_7691e7c8.gifв.

Для вычисления выборочной дисперсии Dв и выборочного стандартного отклонения hello_html_7691e7c8.gifв имеются функции ДИСП (или VAR) и СТАНДОТКЛОН (или STDEV). Аргументом этих функций является набор чисел, как правило, заданный диапазоном ячеек, например, =ДИСП (В1:В48).

Для вычисления генеральной дисперсии Dг и генерального стандартного отклонения hello_html_7691e7c8.gifг имеются функции ДИСПР (или VARP) и СТАНДОТКЛОНП (или STDEVP), соответственно.

Аргументы этих функций такие же как и для выборочной дисперсии.


Объем совокупности.

Объем совокупности выборочной или генеральной – это число элементов совокупности. Функция СЧЕТ (или COUNT) определяет количество ячеек в заданном диапазоне, которые содержат числовые данные. Пустые ячейки или ячейки, содержащие текст, функция СЧЕТ пропускает. Аргументом функции СЧЕТ является интервал ячеек, например: =СЧЕТ (С2:С16).

Для определения количества непустых ячеек, независимо от их содержимого, используется функция СЧЕТ3. Ее аргументом является интервал ячеек.


Мода и медиана.

Мода – это значение признака, которое чаще других встречается в совокупности данных. Она вычисляется функцией МОДА (или MODE). Ее аргументом является интервал ячеек с данными.

Медиана – это значение признака, которое разделяет совокупность на две равные по числу элементов части. Она вычисляется функцией МЕДИАНА (или MEDIAN). Ее аргументом является интервал ячеек.


Размах варьирования. Наибольшее и наименьшее значения.

Размах варьирования R – это разность между наибольшим xmax и наименьшим xmin значениями признака совокупности (генеральной или выборочной): R=xmaxxmin. Для нахождения наибольшего значения xmax имеется функция МАКС (или MAX), а для наименьшего xmin – функция МИН (или MIN). Их аргументом является интервал ячеек. Для того, чтобы вычислить размах варьирования данных в интервале ячеек, например, от А1 до А100, следует ввести формулу: =МАКС (А1:А100)-МИН (А1:А100).


Отклонение случайного распределения от нормального.

Нормально распределенные случайные величины широко распространены на практике, например, результаты измерения любой физической величины подчиняются нормальному закону распределения. Нормальным называется распределение вероятностей непрерывной случайной величины, которое описывается плотностью hello_html_m53d4ecad.gif

hello_html_m67d00d4b.gif,

где hello_html_6c54b47e.gif дисперсия, hello_html_edb72f2.gif - среднее значение случайной величины hello_html_35ea3983.gif.

Для оценки отклонения распределения данных эксперимента от нормального распределения используются такие характеристики как асимметрия А и эксцесс Е. Для нормального распределения А=0 и Е=0.

Асимметрия показывает, на сколько распределение данных несимметрично относительно нормального распределения: если А>0, то большая часть данных имеет значения, превышающие среднее hello_html_edb72f2.gif; если А<0, то большая часть данных имеет значения, меньшие среднего hello_html_edb72f2.gif. Асимметрия вычисляется функцией СКОС. Ее аргументом является интервал ячеек с данными, например, =СКОС (А1:А100).

Эксцесс оценивает «крутость», т.е. величину большего или меньшего подъема максимума распределения экспериментальных данных по сравнению с максимумом нормального распределения. Если Е>0, то максимум экспериментального распределения выше нормального; если Е<0, то максимум экспериментального распределения ниже нормального. Эксцесс вычисляется функцией ЭКСЦЕСС, аргументом которой являются числовые данные, заданные, как правило, в виде интервала ячеек, например: =ЭКСЦЕСС (А1:А100).hello_html_m53d4ecad.gif


Задачи на закрепление материала


Задание 1

Одним и тем же вольтметром было измерено 25 раз напряжение на участке цепи. В результате опытов получены следующие значения напряжения в вольтах: 32, 32, 35, 37, 35, 38, 32, 33, 34, 37, 32, 32, 35, 34, 32, 34, 35, 39, 34, 38, 36, 30, 37, 28, 30. Найдите выборочные среднюю, дисперсию, стандартное отклонение, размах варьирования, моду, медиану. Проверить отклонение от нормального распределения, вычислив асимметрию и эксцесс.

  1. Наберите результаты эксперимента в столбец А.

  2. В ячейку В1 наберите «Среднее», в В2 – «выборочная дисперсия», в В3 – «стандартное отклонение», в В4 – «Максимум», в В5 – «Минимум», в В6 – « Размах варьирования», в В7 – «Мода», в В8 – «Медиана», в В9 – «Асимметрия», в В10 – «Эксцесс». Выровняйте ширину этого столбца с помощью Автоподбора ширины.

  3. Выделите ячейку С1 и нажмите на знак «=» в строке формул. С помощью Мастера функций в категории Статистические найдите функцию СРЗНАЧ, затем выделите интервал ячеек с данными и нажмите Enter.

  4. Выделите ячейку С2 и нажмите на знак «=» в строке формул. С помощью помощью Мастера функций в категории Статистические найдите функцию ДИСП, затем выделите интервал ячеек с данными и нажмите Enter.

  5. Проделайте самостоятельно аналогичные действия для вычисления стандартного отклонения, максимума, минимума, моды, медианы, асимметрии и эксцесса.

  6. Для вычисления размаха варьирования в ячейку С6 следует ввести формулу: =МАКС (А1:А25)-МИН(А1:А25).


2. Инструменты статистического анализа: Генерация случайных чисел, Гистограмма, Описательная статистика.


Загрузка Пакета анализа.

Пакет анализа без дополнительных установок автоматически не загружается при запуске Excel. Он входит в так называемую Надстройку – набор дополнительных подпрограмм, к которым относятся, например, уже известные вам Мастер диаграмм и Мастер функций. Для загрузки Пакет анализа необходимо:

  1. в Основном меню выбрать пункт Сервис;

  2. выбрать пункт Надстройки;

  3. в появившемся списке Надстроек активизировать переключатель AnalysisToolPak-VBA и нажать ОК.

После этого в меню Сервис добавится пункт Анализ данных. К этому пункту следует обращаться для вызова Пакета анализа.


Инструмент: Генерация случайных чисел.

В Excel имеется встроенная функция СЛЧИСЛ (или RAND) для генерации равномерно распределенных случайных чисел в интервале [0,1].

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

  1. в меню Сервис выбрать команду Анализ данных;

  2. в появившемся диалоговом окне Анализ данных в группе Инструменты анализа выбрать пункт Генерация случайных величин и нажать ОК;

  3. в появившемся диалоговом окне Генерация случайных чисел следует заполнить поля ввода:

  • в полях Число переменных и Число случайных чисел указать нужное количество столбцов и сколько чисел вы хотите получить в каждом столбце;

  • в поле Распределение следует выбрать один из имеющихся типов распределения случайных чисел;

  • в группе Параметры следует указать диапазон чисел, т.е. min и max числа распределения для Равномерного распределения; или среднее значение и стандартное отклонение для Нормального распределения и т.д.

  • поле Случайное рассеивание заполняется только в том случае, если вам необходимо несколько раз воспроизводить одну и туже последовательность случайных чисел;

  • в поле Выходной интервал указывается место, куда следует поместить последовательность чисел, как правило, это интервал ячеек (или столбец целиком).


Инструмент: Гистограмма.

Графическое представление результатов обработки статистических данных обычно оформляется в виде гистограммы. Совокупность данных разбивается на частичные интервалы, называемые нормальными. Интервалы разбиения могут быть любой ширины, но обязательно они должны следовать в порядке возрастания. Интервалы разбиения откладываются по оси абсцисс гистограммы. На оси ординат гистограммы откладывается число значений, попавших в интервал разбиения. Это число значений признака совокупности называется частотой. Для построения гистограммы:

  1. в начале следует задать частичные интервалы разбиения;

  2. затем в меню Сервис выбрать команду Анализ данных и указать инструмент анализа –Гистограмма и нажать ОК;

  3. в диалоговом окне Гистограмма следует указать:

  • в группе Входные данные в поле Входной интервал – интервал ячеек с данными, а в поле Интервал карманов – интервал ячеек с частичными интервалами разбиения;

  • в группе Параметры вывода указывается интервал ячеек для вывода частот и отмечается галочкой переключатель Вывод графика.

После нажатия ОК инструмент Гистограмма выводит два столбца: карман и частота. Сама гистограмма выводится правее столбца частот. Форматирование гистограммы производится так же, как и любой диаграммы в Excel (см. лабораторную работу №6).


Инструмент: Описательная статистика.

В пакете анализа Excel содержится инструмент Описательная статистика, который создает таблицу основных статистических характеристик для совокупности данных. В этой таблице будут содержаться следующие характеристики: среднее, стандартная ошибка, дисперсия, стандартное отклонение, мода, медиана, размах варьирования интервала, максимальное и минимальное значения, асимметрия, эксцесс, объем совокупности, сумму всех элементов совокупности, доверительный интервал (уровень надежности). Инструмент Описательная статистика существенно упрощает статистический анализ тем, что нет необходимости вызывать каждую функцию для расчета статистических характеристик отдельно.

Для того, чтобы вызвать Описательную статистику, следует:

  1. в меню Сервис выбрать команду Анализ данных;

  2. в списке Инструменты анализа диалогового окна Анализ данных выбрать инструмент

Описательная статистика и нажать ОК;

  1. в появившемся диалоговом окне Описательная статистика необходимо:

  • в группе Входные данные в поле Входной интервал указать интервал ячеек, содержащих данные;

  • если первая строка во входном диапазоне содержит заголовок столбца, то в поле Метки в первой строке следует поставить галочку;

  • активизировать переключатель (поставить галочку) Итоговая статистика, если нужен полный список характеристик;

  • активизировать переключатель Уровень надежности и указать надежность в %, если необходимо вычислить доверительный интервал.


Задание 2.


Сгенерировать 500 случайных чисел, распределенных нормально. Построить гистограмму и полный список статистических характеристик с помощью инструмента Описательная статистика.

1. Выполните команду СервисАнализ данныхГенерация случайных чисел;

2..В диалоговом окне Генерация случайных чисел введите в поле число переменных: 1; в поле Число случайных чисел 500; выберите Распределение Нормальное; задайте любое среднее значение (желательно около 100) и небольшое стандартное отклонение (не больше 10); в поле Выходной интервал укажите абсолютный адрес столбца $A$2. Нажмите ОК.

  1. Теперь постройте гистограмму по совокупности случайных чисел. Сначала нужно задать интервалы решения. Пусть длины интервалов будут одинаковыми и равны 3. Для автоматического составления интервалов разбиения наберите в ячейку В2 начальное число, например, 75 для наших случайных чисел. Затем выполните команду ПравкаЗаполнитьПрогрессия. В появившемся диалоговом окне заполните данные:

  • в группе переключателей поле Расположение установите по столбцам;

  • в поле Шаг наберите 3;

  • в поле Предельное значение наберите 125;

  • в группе переключателей Тип установите арифметическая и нажмите ОК.

В результате столбец В будет содержать интервалы разбиения (карманы).

  1. Выполните команду СервисАнализ данныхГистограмма. В появившемся диалоговом окне Гистограмма заполните:

  • входной интервал появится, если щелкнуть мышью по столбцу А;

  • интервал карманов появится, если щелкнуть мышью по столбцу В;

  • поставьте галочку в поле метки;

  • укажите столбец С в поле Выходной интервал;

  • активизируйте переключатель Вывод графика; если это поле не содержит галочки, нажмите ОК.

  1. Построение гистограммы займет от 5 до 10 минут. За это время письменно ответьте на контрольные вопросы. В результате вычисления получатся столбец под названием Карман, который дублирует ваш столбец интервалов разбиения, и столбец под название Частота с рассчитанными частотами. После того, как появилась гистограмма, измените ее размеры с помощью мыши так, чтобы хорошо были видны все столбцы и подписи.

  2. Теперь осталось получить таблицу статистических характеристик с помощью Описательной статистики. Выполните команду СервисАнализ данныхОписательная статистика. В появившемся диалоговом окне Описательная статистика укажите:

  • в поле Входной интервал появится адрес, если выделить мышью интервал сданными или с клавиатуры набрать адрес $A$2: $A$501;

  • в поле Группирование активизировать переключатель по столбцам;

  • активизировать переключатель Метки в первой строке;

  • в группе Параметры вывода укажите Выходной интервал, щелкнув мышью по какой-либо пустой ячейке ниже столбца частот, например, по С 25;

  • активизируйте переключатель Итоговая статистика (если в этом поле нет галочки);

  • активизируйте переключатель Уровня надежности и установите 95%;

  • снимите галочки с полей наименьший и наибольший и нажмите ОК.

Результаты записать в отчет.


Контрольные вопросы:


  1. Для чего предназначена функция СРЗНАЧ?

  2. С помощью каких характеристик оценивают разброс статистических данных? Какие функции в Excel их вычисляют? В чем отличие функции оценки разброса данных для генеральной и выборочной совокупности?

  3. В чем отличие функций СЧЕТ и СЧЕТЗ?

  4. Что такое мода и какая функция ее вычисляет?

  5. Что такое медиана и какая функция ее вычисляет?

  6. Как вычислить размах варьирования?

  7. С помощью каких характеристик оценивают отклонение случайного распределения от нормального? Какой смысл этих характеристик и какие функции в Excel их вычисляют?

  8. Что такое Инструменты Анализа? Как загрузить Пакет Анализа?

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

  10. Как построить гистограмму?

  11. Для чего предназначен инструмент Описательная статистика?







Практические занятия


  1. Практическое занятие №10 «Использование расчетных формул, таблица, графиков при решении статистических задач. Построение по заданной выборке ее графической диаграммы, расчет числовых характеристик»

  2. Практическое занятие №11 «Использование расчетных формул при решении статистических задач. Интервальная оценка математического ожидания нормального распределения. Интервальная оценка вероятности события»

  3. Практическое занятие № 12 «Использование расчетных формул, таблица, графиков при решении статистических задач. Моделирование случайных величин, Моделирование сложных испытаний и их результатов»

  4. Практическое занятие № 13 «Применение современные пакеты прикладных программ многомерного статистического анализа»


Раздел 4. Основы теории графов


Тема 4.1.Основные понятия теории графов



Тема лекции: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

План:

  1. Введение

  2. Основные понятия и определения теории графов

  3. Некоторые типы графов


  1. Введение


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

Термин «граф» впервые появился в книге выдающе­гося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Одна из задач, положивших начало теории графов, – задача о кенигсбергских мостах ( рассказать, показать граф).


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

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

В последнее время теория графов принимает все более прикладной характер, являясь эффективным аппаратом для формализации множества задач, связанных с дискретным размещением объектов. К ним, в частности, относятся: проектирование и исследование сетей связи, анализ электрических цепей, графы потока сигналов и теория обратной связи, блок-схемы программы, исследование автоматов, анализ и синтез логических цепей, задачи календарного планирования, планирование и обеспечение материально-технического снабжения, поиск информации, стратегия инвестиций, анализ качества, исследование движения транспорта, размещение предприятий коммунального обслуживания, моделирование, экономические задачи, теория игр, головоломки, доказательство теорем.


  1. Основные понятия и определения теории графов


Определение: Пусть задано некоторое конечное множество X, элементы которого будем называть вершинами, и множество V, состоящее из пар элементов (xi, xj) множества X. Упорядоченная пара множеств G=(X,V) называется графом. Вершины изображаются точками, а пары элементов – линиями, соединяющими точки, соответствующие образующим пары вершинам.

Если в определении графа существенно в каком порядке выбираются вершины (то есть пара (xi, xj) отлична от пары (xj,xi)), то такой граф называют ориентированным или орграфом, а пару (xi, xj) дугой, при этом считается, что хi –начальная вершина, a xj – конечная. В геометрической интерпретации дуге соответствует направленный отрезок. Часто орграф задают парой G=(X,Г), где Х – множество вершин, а Г – неоднозначное отображение, ставящее в соответствие каждой вершине подмножество в X. Г(хi) – множество вершин хjХ, для которых в графе G существует дуга (хi, хj). hello_html_5b2f97fb.gif(хi) – множество вершин хjX, для которых в графе G существует дуга (xj, хi).


Если в определении графа не существенен порядок вершин при образовании пары (хi, xj), то граф называют неориентированным или неорграфом, а пару (xi, xj) – ребром.

Число вершин графа называется его порядком.


Пример. На рис.1 изображен ориентированный граф G=({x1, x2, x3, x4}, {(x1, x2), (x1, x4), (x2, x4), (x3, x1), (x3, x2), (x4, x3)}), а на рис.2 – неориентированный граф.

hello_html_2500b2a3.gif

Рис. 1 Рис. 2


Определение: Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Для неорграфа такая последовательность ребер называется цепью. Если путь (цепь) проходит через вершины х1, ..., хk то будем обозначать его (ее) символом [x1, …, xk].

Для графа на рис. 1 последовательность дуг (x1, x2), (x2, x4), (x4, x3) является путем и может быть обозначена следующим образом [x1, x2, x4, x3]. Для графа на рис.2 цепью является, например, следующая последовательность ребер (x2, x3), (x3, x5), (x5, x4), которую обозначим через [x2, x3, x5, x4].


Определение: Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом).

Для графа на рис. 2 циклом является, например, следующая цепь [x2, x3, x5, x1, x2].


Определение: Простым циклом графа называется цикл, в котором все вершины различны за исключением начальной и конечной вершины, которые совпадают.

Например, для графа на рис.2 цикл [x2, x3, x5, x1, x2] является простым, а цикл [x2, x3, x4, x5, x3, x1, x2] не является простым.


Определение: Петлей называется дуга, начальная и конечная вершины которой совпадают.


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


Пример. На рис.3.б изображен граф, который является основание графа, изображенного на рис.3.а.


Определение: Две вершины хi и хj называются смежными, если существует соединяющее их ребро (дуга) (хi, xj), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) – инцидентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину.

hello_html_m18d60b29.gif

Рис.3 а б


Вершины х1 и х4 смежны (рис. 1), дуга (х1, х4) инцидентна вершинам х1 и х4, а вершины х1 и х4 инцидентны дуге (х1, х4). Ребра (х1, х3) и (х3, х4) смежны (рис.2).


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


Определение: Множество всех вершин графа G, смежных с некоторой вершиной x, называется окружением вершины x и обозначается через NG(x) или просто N(x).


Определение: В неориентированном графе число ребер, инцидентных данной вершине хi, называется степенью (валентностью) вершины хiи обозначается d(хi). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень 1 – висячей. Для неорграфа на рис.2 d(х1)=3, d(х3)=4.


Утверждение (лемма о рукопожатиях). Сумма степеней вершин графа G равна 2m, где m – число ребер графа G.

Доказательство. Поскольку каждое ребро инцидентно двум вершинам, то оно добавляет двойку к сумме степеней графа G. Следовательно, все ребра дают вместе сумму степеней 2m.


Определение: Подграфом графа G=(X,V) называется граф G'=(X',V'), для которого X'X, V'V, причем ребро (xi, xj) содержится в V' только в том случае, если xi и xj содержатся в X'. Одним из подграфов графа на рис.1 является следующий (рис..4)


Определение: Если все вершины графа G=(X,V) присутствуют в подграфе G'=(X',V'), тогда G' называется остовным подграфом, т. е. X'=Х, V'V.


Определение: Пусть X' – подмножество вершин Х графа G=(X,V). Тогда граф G'=(X',V') называется порожденным подграфом графа G на множестве вершин X' (вершинно-порожденный подграф), если V' является таким подмножеством V, что ребро (xi,xj) входит в V' тогда и только тогда, когда xi и xj входят в X'.


Пример. На рис.5 представлен порожденный подграф на множестве вершин {х1, х3, x5} неориентированного графа, изображенного на рис2.

hello_html_10377d45.gif

Рис. 4 Рис.5


  1. Некоторые типы графов


Определение: Граф G называется полным, если любые две его вершины смежны. Полный граф порядка n обозначается символом Кn, число ребер в нем равно hello_html_m4b8555a8.gif. На рис.6 изображены графы Кn , n5.

hello_html_212fae18.gif

Рис.6


Определение: Граф называется пустым, если в нем нет ребер. Пустой граф порядка n обозначается через Оn.


Определение: Граф, не содержащий вершин и, следовательно, ребер, называется ноль-графом. Граф, состоящий из одной вершины, называется тривиальным.


Красивыми примерами являются графы пяти платоновых тел (т. е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра


Контрольные вопросы:


  1. Понятие графа.

  2. Применение графов.

  3. Основные определения теории графов.

  4. Типы графов.




Тема лекции: Представление информации в форме графа


План:

  1. Вводные понятия.

  2. История возникновения и развития теории графов.

  3. Представление графа в памяти компьютера.


  1. Вводные понятия


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

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

Если вы любите решать олимпиадные задачи, тогда, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии. То есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы открывали для себя начала теории графов.


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

Две вершины, соединенные ребром (дугой) называются смежными.

Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.

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


  1. История возникновения и развития теории графов


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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

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

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


  1. Представление графа в памяти компьютера



Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.

hello_html_391b2a63.gif



























рис.1


На рис.1 представлены различные изображения одного и того же графа.

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

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


Способы описания графа:

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


Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.

Пример:

hello_html_m2b45c718.gif


l1V1V3

l2V1V2

l3 V1V2

l4 V2V3



Матрица смежности – это двумерный массив А размерности N*N


hello_html_3b209fbf.gif1, если вершины i и j - смежные

A[i,j]=

0, если вершины i и j - несмежны

hello_html_12a6d043.gif
Пример: Данный граф можно представить в виде матрицы смежности:


V1 V2V3 V4 V5 V6 V7 V8

V1 0 0 0 0 0 0 0 0

V2 1 0 0 0 0 0 0 0

V3 0 1 0 1 1 0 0 0

A= V4 0 0 0 0 1 0 0 0

V5 0 1 0 0 0 0 0 0

V6 0 0 0 0 0 0 1 1

V7 0 0 0 0 0 0 0 1

V8 0 0 0 0 0 0 0 0

Матрица инцидентности графа, имеющего n вершин и m ребер– это двумерный массив А размерности N*M

hello_html_3b209fbf.gifhello_html_m6cbde1e8.gif1, если j-е ребро инцидентно i-й вершине

A[i,j]=

0, если j-е ребро неинцидентно i-й вершине



e1 e2 e3 e4 e5 e6

v1 1 0 0 0 0 0

v2 1 1 0 0 0 1

v3 0 1 1 0 1 0

v4 0 0 1 1 0 0

v5 0 0 0 1 1 1


Пример. На рис. 2 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:

шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К), информация от абонента-источника распространяется по каналу в обе стороны;

кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;

звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;

древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;

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


Рhello_html_5ca948c7.gifис. 2

Различные типы

конфигураций Шинная

локальных

вычислительных

сетей



hello_html_m2dc5656c.gif

Кольцевая







hello_html_7c1aa50c.gif



Звездообразная









hello_html_19b02666.gif



Полносвязная







hello_html_m5f771d1d.gif


Древовидная










Тема лекции: Метрические характеристики графов


В теории графов применяются:


  1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.


  1. Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.


  1. Пусть G=(X,U) - связный граф, а hello_html_fcf6c43.gif - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины hello_html_fcf6c43.gif (пути из hello_html_59204260.gif) называется расстоянием между вершинами hello_html_fcf6c43.gif и обозначается hello_html_m42455058.gif. Положим hello_html_7fdf5ab9.gif, если вершины hello_html_fcf6c43.gif не соединены маршрутом (путем). Расстояние hello_html_m42455058.gif удовлетворяет следующим аксиомам:

1) hello_html_4ed68fff.gif;

2) hello_html_m8f0df6.gif;

3) hello_html_m433fbb7f.gif тогда и только тогда, когда hello_html_m3edfdd0c.gif;

4) hello_html_m45683780.gif для симметрических графов;

5) hello_html_m68b33d09.gif (неравенство треугольника).


  1. Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:

hello_html_17d0e387.gif

Матрицу расстояний можно определить


  1. Для фиксированной вершины hello_html_780249fd.gif величина

hello_html_20ae01b.gif

называется эксцентриситетом (отклоненностью) вершины hello_html_780249fd.gif.


  1. Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):

hello_html_380b3b0d.gif

  1. Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):

hello_html_m3837382d.gif


  1. Вершина, имеющая минимальный эксцентриситет, называется центром графа.

  2. Для вершины hello_html_780249fd.gif число hello_html_114d1601.gif называется передаточным числом.

  3. Вершина графа, которой соответствует минимальное передаточное число

hello_html_f72500f.gif

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


hello_html_79164a42.gif

Рис. 1


Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:

hello_html_69688356.gif


Радиус графа равен 1, диаметр равен 2. Центр графа - вершина hello_html_m14a51d2a.gif; Медиана графа - вершина hello_html_m14a51d2a.gif.

Контрольные вопросы:


  1. Что такое граф?

  2. Приведите разновидности графов.

  3. Может ли пустой граф быть ориентированным?

  4. Нарисуйте полный граф.

  5. Что такое подграф?

  6. Каким образом понятие дерева активно используется в информатике и программировании?

  7. Метрические характеристики графов.




Тема 4.2.Остовы графов, деревья


Деревья


Оhello_html_2d68f0c1.pngпределение: Деревом называют связный граф без циклов. Пример: Название достаточно жизненно - взгляните на рисунок:


Теорема: В любом дереве вершин ровно на одну больше, чем ребер.

Док-во: Будем доказывать этот факт индукцией по количеству вершин.

Когда вершин - две ясно, что ребро ровно одно, так что база индукции очевидна.

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


Теорема: В любом связном графе с n вершинами хотя бы n-1 ребро, причем если количество ребер ровно n-1, то это дерево.

Док-во: Пусть это не дерево (иначе ребер ровно n-1 по предыдущей теореме), значит, в нем есть цикл. Сотрем любое из ребер этого цикла - граф останется связным. Если в нем остался еще цикл, то сотрем ребро и из него, и т.д. Ясно, что граф все время остается связным, так что в конце получится связный граф без циклов - дерево - у него ровно n-1 ребро, а значит у исходного графа хотя бы п.

.

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

1. Граф является деревом.

2. Граф связен и перестает быть таким при стирании любого ребра.

3. Граф связен и вершин в нем на одну больше, чем ребер.

4. В графе нет циклов и вершин на одну больше, чем ребер.


Док-во: 1<=>2: это ясно, т.к. если мы стираем ребро, а связность не нарушается, то значит между его концами есть какой-то другой путь, а значит, есть и цикл. И наоборот: если есть цикл, то можно стереть любое ребро из этого цикла, не нарушив связность графа.

1 =>3: В любом дереве вершин на одну больше; чем ребер. Это мы уже знаем.

3=>4: Пусть цикл все-таки есть. Уберем из него ребро - граф, естественно, останется связным, но это невозможно, т.к теперь ребер на два меньше, чем вершин (см. пред, теорему). Значит, цикла нет. 4=>1: Пусть граф несвязен. Тогда в каждой компоненте связности нет циклов, то есть каждая компонента - дерево, а значит в ней вершин на одну больше, чем ребер. Но тогда всего вершин более чем на одну больше, чем ребер, что невозможно. Значит, граф связен, а тогда это дерево.


hello_html_7b846106.png

Определение: пусть у нас есть произвольный связный граф. Максимальное дерево в нем - это подграф, который содержит все вершины исходного графа и некоторые из его ребер. Замечание: Таких максимальных деревьев может быть несколько.


Пример: На рисунке выделено одно из возможных максимальных деревьев.


Теорема: В любом связном графе можно выделить максимальное дерево.

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


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


Рассмотрим пример. Для классификации некоторого объекта предприятие. (варианты его названия — hello_html_1e3e55fa.gif) выберем в качестве корня дерева сам объект . Компоненты, составляющие этот объект, разместим на первом уровне (ярусе) графа: это будут hello_html_m550903ea.gif Второй уровень (ярус) графа содержит компоненты первого уровня (его подмножества: hello_html_m703acebd.gif). Аналогично на третьем уровне разместим подмножества компонентов второго уровня - hello_html_m4eb305b7.gif От нижнего уровня к высшему ведёт лишь одна дуга, поэтому граф является деревом.

hello_html_1d2fb2dc.jpg


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

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

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми есть маршрут, а вес ребра равен стоимости проезда по соответствующему маршруту.

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




Тема лекции: Построения остовного дерева


  1. Постановка задачи


Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c(e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX(G).


  1. Методы решения данной проблемы


Остовным деревом графа называется дерево, содержащее все вершмины V графа.

Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер.


Идея решения:

Для остовного дерева верно следующее свойство:

Пусть G=(V,E) - свызный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (u,v) - такое ребро наибольшей стоимости, что u из U и v из V\U, тогда для графа G существует остовное дерево максимальной стоимости, содержащее ребро (u,v)

На этом свойстве основан алгоритм Прима. В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. Пусть V={1,2,...n}. Сначала U={1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u,v) такое, что u из U и v из V\U, затем вершина v переносится из множества V\U в множество U. Процесс продолжается до тех пор, пока множество U не станет равным множеству V.

Детали реализации:

Удобно выбрать представление в виде списка дуг

Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса. В нашей работе длина проложенного кабеля должна быть максимальной.

Определим понятие каркаса более формально. Если дан связный неориентированный граф G=(V, E), то каркас (также называемый остовным или стягивающим деревом) T=(V, E’), где E’E – это связный граф без циклов. Иными словами, каркас неориентированного графа G – это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|–1 ребро.

Предположим, что для каждого ребра eE существует вес w(e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере – длину кабеля между зданиями). Во взвешенном графе вес подграфа – это сумма весов его ребер. Тогда каркас T максимального веса– это каркас G, в котором вес дерева максимален относительно всех остовных деревьев G .

Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес. Также можно изменить алгоритм нахождения остовного дерева максимального веса, чтобы на выходе получать минимальный остовный лес.

В алгоритме Краскала используется жадный подход к решению задачи, т. е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается «лучшее» ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу максимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т. е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.


  1. Описание алгоритма Краскала


Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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


Алгоритм состоит из следующей последовательности действий:


  1. Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i),номер конечной вершины ребра (j), признак включения данного ребра в дерево.

  2. Данный список упорядочивается в порядке возрастания длин ребер.

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

  4. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Или в терминах теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево максимальной длины.

В задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.

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

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u, v) – “добавлено” означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.


Теорема. Алгоритм Прима–Краскала получает максимальное остовное дерево.



Пример Для заданного графа произвольно пронумеровать вершины и построить кратчайшее остовное дерево, определить его длину.

hello_html_75b0713f.png


Решение:

Для построения кратчайшего остовного дерева воспользуемся алгоритмом Крускала.

В этом алгоритме мы начинаем с пустого дерева и добавляем к нему ребра в порядке возрастания их весов пока не получим набор ребер, объединяющий все вершины графа. Если ребра закончатся до того, как все вершины будут соединены между собой, то это означает, что исходный граф был несвязным, и полученный нами результат представляет собой объединение МОД всех его компонент связности.

Начнем с ребер наименьшего веса, равного 1, то есть с ребер AB, BE, ED, EL, LK.

Ребер веса 2 нет.

Следующими добавляем ребра веса 3, при этом следим, чтобы в графе не появлялись циклы. Добавляем ребра BC, CF.

К результирующему графу последовательно добавляются ребра веса 4- EG.

Добавление остальных ребер приведет к появлению цикла в уже построенной части МОД.

Таким образом, кратчайшее остовное дерево для заданного графа имеет вид:

hello_html_m3e263a8f.png


Длина построенного кратчайшего остовного дерева равна 15.



Тема 4.3.Виды графов


Двудольные графы


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

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

Полный двудольный граф, доли которого состоят из р и из q вершин, обозначается символом Kp,q . При р=1 получаем звезду K1,q. На рис.1 изображены звезда К1,5 и полный двудольный граф K3,3.

Аналогично двудольным графам определяются k-дольный и полный k-дольный графы для k=3, 4, ... На рис.2 приведен трехдольный граф.


hello_html_7814f6dc.png

Рис. 1 Рис. 2


Для решения примеров удобно применять теорему


Теорема: Граф является двудольным т. и т.т., к. все его простые циклы имеют четную длину.

Легко подсчитать число всех графов с фиксированным множеством вершин X. Эти графы различаются своими ребрами, и потому их число равно количеству подмножеств в X(2), т.е. 2hello_html_m4de6e249.gif , где п=|X|. Однако эти графы не всегда следует различать. Как в применениях теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Оформим эти соображения в виде следующего определения.


Изоморфные графы


Определение: Два графа G1 и G2 называются изоморфными, если существует взаимно-однозначное отображение между множествами их вершин, сохраняющее смежность. Такое отображение называется изоморфизмом.

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


Например, три графа, представленные на рис. 4, изоморфны, а графы на рис. 5 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.

hello_html_2d01cc0a.png

Рис. 4.

hello_html_20ccf76a.png

Рис. 5


Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы можно отождествлять, т. е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игно­рируется при введении понятия «граф».

В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помеченный граф». Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, ..., n. Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин с множеством чисел {1, 2, ..., n}), определим равенство помеченных графов G1=(X,V1) и G2=(X,V2) одного и того же порядка: G1=G2 тогда, когда V1=V2. На рис. 6 изо­бражены три разных помеченных графа.

При необходимости подчеркнуть, что рассматриваемые графы различаются лишь с точностью до изоморфизма, говорят: «абстрактный граф». Строго говоря, абстрактный (или непомеченный) граф – это класс изоморфных графов.

hello_html_m23bd11ab.png

Рис. 6

Контрольные вопросы:


  1. Двудольные графы.

  2. Изоморфные графы.

  3. Решить задачи:

1. Определите, является ли граф двудольным?

а) Граф К3,3 (задача о колодцах);

б) hello_html_49e1036a.png;

в) граф – додекаэдр (пятиугольник).

2. Определите, являются ли графы изоморфными?

а)hello_html_3be92d68.png б) hello_html_m609c94f7.png

3. Сколько можно построить графов с 3 вершинами с точностью до изоморфизма? (4)



Тема лекции: Эйлеровы и гамильтоновы циклы


Эйлеровы циклы и гамильтоновы циклы (контуры) часто встречаются в практических задачах и поэтому представляют особый интерес.

Одна из самых первых задач теории графов это известная задача о кенигсбергских мостах. Постановка и решение этой задачи Эйлером знаменует начало разработки теории графов. Расположение мостов через реку Прегель в г. Кенигсберге в его время приведено на рис.1.


hello_html_m229e356a.png

Рис.1


Возник вопрос: можно ли, выйдя из дома, вернутся обратно, пройдя по каждому мосту ровно один раз.

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

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


Эйлеровы циклы


Определение: Цикл, который проходит ровно один раз по каждому ребру неориентированного графа G, называется эйлеровым циклом.


Определение: Граф, в котором существует эйлеров цикл, называется эйлеровым графом.


Определение: Цепь, которая проходит ровно один раз по каждому ребру неориентированного графа G, называется эйлеровой цепью.


Определение: Граф, в котором существует эйлерова цепь, называется полуэйлеровым графом.

hello_html_948d464.png

Рис 2.

На рис 2 а) неэйлеров граф; б) полуэйлеров граф; в) эйлеров граф;


Теорема: Связный граф является эйлеровым тогда и только тогда, когда каждая вершина в графе имеет четную степень.

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


Утверждения.

1. Связный неориентированный граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0 (0 или 2).

2. Для связного графа G следующие утверждения эквивалентны:

а) G эйлеров граф;

б) каждая вершина графа G имеет четную степень;

в) множество ребер графа G можно разбить на простые циклы.


Метод Флёри построения эйлерова цикла


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

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

Замечание. Граф G=(X,V) задается множеством X своих вершин и набором реберных окрестностей всех его вершин S(x)={v | ребро v инцидентно вершине х}.

Шаг 1. Выбрать произвольную вершину х0X и положить х=x0, z=х0, С=x0, D=x0, где С чередующаяся последовательность вершин и ребер, представляющая строящийся эйлеров цикл; D чередующаяся последовательность, представляющая начальный отрезок цикла, который будет присоединен к текущему циклу С; х конечная вершина в последовательности D; z вершина на цикле С, которая служит началом D.

Шаг 2. В множестве S(x) \ [V(С) V(D)] выбрать произвольное ребро 1. Если S(x)=, то прейти к шагу 5. Здесь V(С) и V(D) обозначают множество ребер из С и D.

Шаг 3. К D дописать ребро 1 и его конец у, т.е. положить D = D, 1, у.

Шаг 4. Положить х=у и перейти к шагу 2.

Шаг 5. Присоединить к С в вершине z цикл D, т.е. положить C=C[x0,z),D,C(z,x0], где C[x0,z) начальный отрезок последовательности С до веpшины z, не включая z; C(z,x0] – отрезок последовательности С от z до x0, не включая z.

Шаг 6. Просматривая последовательность С слева направо, ищем первую такую вершину v, что S(v)\V(C)=. Если такой вершины нет, то перейти к шагу 8, иначе перейти к шагу 7.

Шаг 7. Положить x=v, z=v, D=v и перейти к шагу 2.

Шаг 8. Выдать последовательность С, которая является эйлеровым циклом.


Гамильтоновы циклы


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


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

hello_html_1a466a10.png

Рис. 3

На рис. 3 а) не гамильтонов граф; б) полугамильтонов граф; в) гамильтонов граф.


Утверждения: Пусть G данный неорграф, a L(G) его реберный граф, тогда:

1. а) если G имеет эйлеров цикл, то L(G) имеет как эйлеров так и гамильтонов циклы;

б) если G имеет гамильтонов цикл, то L(G) также имеет гамильтонов цикл.

2. Сильно связный полный граф гамильтонов.

3. Пусть G сильно связный граф на n вершинах без параллельных дуг и петель. Если для любой вершины х справедливо неравенство d-(х)+d+(х)n, то граф G имеет гамильтонов контур.

4. Если орграф G полный, то он имеет ориентированный гамильтонов путь.


Контрольные вопросы:


  1. Эйлеровы графы.

  2. Гамильтоновы графы.

  3. Решить задачи:


1. С помощью алгоритма Флери найдите эйлерову цепь в графе:

hello_html_179044b4.png

2. Можно ли ходом шахматного коня обойти шахматную доску размером 8*8 так, чтобы каждый ход встречался ровно один раз (при этом мы считаем, что ход встречался, если конь переместился с одной клетки на другую любым из двух возможных способом). Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.

3. Может ли ходом шахматный конь побывать на каждой клетке шахматной доски размером 8*8 ровно один раз и возвратиться в начальную клетку. Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.

4. Приведите пример графа, который является эйлеровым, но не гамильтоновым.

5. Приведите пример графа, который является гамильтоновым, но не. эйлеровым

6. Что можно сказать о графах, являющихся одновременно эйлеровыми и гамильтоновыми?


Плоские и планарные графы


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


Таким образом, возникает понятие плоского графа.


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

hello_html_m7cbf9068.gif
hello_html_m30e3d744.gif

а б

Рис. 1. Плоские графы.


Определение: hello_html_m5b290501.gif
Любой граф, изоморфный плоскому графу, будем называть планарным.

Рис.2.


Граф на рис.2 является планарным, так как он изоморфен графу на рис 1.б.


Очевидны следующие утверждения:

  1. всякий подграф планарного графа планарен;

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

О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).

Алгоритм укладки графа на плоскости



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

Одним из таких алгоритмов является следующий:

Рассмотрим граф G=(X,U). Алгоритм укладки графа представляет собой процесс последовательного присоединения к некоторому уложенному подграфу G' (G'=(X',U')) графа G новой цепи, оба конца которой принадлежат G'. Тем самым эта цепь разбивает одну из граней G' на две. При этом в качестве начального плоского графа G' выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В этом случае граф не является планарным.

Пошаговое описание алгоритма укладки графа на плоскости


  1. Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G'=С.

  2. Найдем грани графа G' и сегменты относительно G'. Если множество сегментов пусто, то перейдем к п. 7.

  3. Для каждого сегмента S определим множество Г(S).

  4. Если существует сегмент S, для которого Г(S)=, то граф G непланарен. Конец. Иначе перейти к п. 4.

  5. Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейти к п. 6. Иначе – к п. 5.

  6. Для некоторого сегмента S (Г(S)>1) выбираем произвольную допустимую грань Г.

  7. Поместить произвольную –цепь L S в грань Г; заменить G' на G'L и перейти к п. 1.

  8. Построена укладка G' графа G на плоскости. Конец.


Проиллюстрируем работу алгоритма на примерах.


Пример 1. Для графа G, изображенного на рис 3, построить его укладку на плоскости.


Решение. Уложим сначала цикл С =(1, 2, 3, 4, 1), который разбивает плоскость на две грани Г1 в Г2. На рис. 4 изображены граф G'=С и сегменты S1, S2, S3 относительно G' с контактными вершинами, обведенными кружками. Так как Г(Si)={Г1, Г2} (i=1, 2, 3), то любую -цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, -цепь L = (2, 5, 4) в Г1. Возникает новый граф G' и его сегменты (рис. 5). При этом Г(S1) = {Г3}, Г(S2) = {Г1, Г2}, Г(S3) = {Г1, Г2, Г3}. Укладываем цепь L = (1, 5) в Г3 (рис. 6). Тогда Г(S1) = {Г1, Г2}, Г(S2) = {Г1, Г2}. Далее, уложим -цепь L = (2, 6, 4) сегмента S1 в Г1 (рис. 7). В результате имеем Г(S1) = {Г5}, Г(S2) = {Г1, Г2, Г3}. Наконец, уложив ребро (6,3) в Г5, а ребро (2,4) - например, а Г1, получаем укладку графа G на плоскости (рис. 8).

hello_html_m514eb36.png

Рис. 3.

hello_html_m3f3dcfc8.png

Рис. 4.

hello_html_16173679.png

Рис. 5.

hello_html_m4dfbf240.png

Рис. 6.

hello_html_m6381795e.png

Рис. 7.

hello_html_40d5a68e.png

Рис. 8.


Пример 2. Для графа К3,3, изображенного на рис.9, построить, если это возможно, его укладку на плоскости.


Решение: цикл G' и сегменты относительно этого цикла изображены на рис. 10. При этом Г(Si) = {Г1, Г2} (i=1,2,3). Помещает S1 в грань Г2. Тогда S2 необходимо поместить в грань Г1 (рис. 11). Поскольку Г(S1)=, то К3,3 - непланарный граф.

hello_html_2b49d35c.png

Рис. 9.

hello_html_2a960df6.png

Рис. 10.

hello_html_m7af4a144.png

Рис. 11.


Контрольные вопросы:


  1. Плоские графы.

  2. Планарные графы.

  3. Решить задачи:

1. Для графа построить, если это возможно, его уклад­ку на плоскости.

а)hello_html_34832292.png

hello_html_1cde9227.png

б)

2. Для графа построить, если это возможно, его уклад­ку на плоскости.

а) б)

hello_html_62be00aa.gifhello_html_7e373e1f.gifhello_html_m105148d7.gifhello_html_m2823cef2.gifhello_html_m3a42497.gifhello_html_7afb48c.gifhello_html_40862967.gifhello_html_3d0a52bb.gifhello_html_40862967.gifhello_html_m74936d7e.gifhello_html_6db9e2a7.gifhello_html_24599752.gifhello_html_m411aaa44.gif

hello_html_59853bf0.gif




в) г)

hello_html_62be00aa.gifhello_html_7e373e1f.gifhello_html_m105148d7.gifhello_html_m2823cef2.gifhello_html_m3a42497.gifhello_html_7afb48c.gifhello_html_40862967.gifhello_html_59853bf0.gifhello_html_3d0a52bb.gifhello_html_40862967.gifhello_html_m74936d7e.gifhello_html_6db9e2a7.gifhello_html_62be00aa.gifhello_html_7e373e1f.gifhello_html_m105148d7.gifhello_html_m2823cef2.gifhello_html_m534256bc.gifhello_html_m5556e6ce.gifhello_html_40862967.gifhello_html_m19ce912e.gifhello_html_m74936d7e.gifhello_html_m74936d7e.gifhello_html_4cbb7abc.gifhello_html_m19ce912e.gifhello_html_59853bf0.gif











Практические занятия


Практическое занятие №14 «Метрические характеристики графов»

  1. Практическое занятие №15 «Построения остовного дерева»

КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ


Вопросы к экзамену


ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА»



Теоретическая часть:


Раздел 1. Основные понятия комбинаторики


Тема 1.1. Основные понятия комбинаторики


  1. Основные комбинаторные объекты. Размещения. Примеры

  2. Основные комбинаторные объекты. Сочетания. Примеры

  3. Основные комбинаторные объекты. Перестановки. Примеры.

  4. Два основных принципа комбинаторики


Раздел 2. Основы теории вероятностей


Тема 2.1. Основные теоремы теории вероятностей


  1. Случайные события. Типы событий.

  2. Классическое определение вероятности

  3. Противоположное событие.

  4. Теоремы сложения вероятностей

  5. Теоремы умножения вероятностей

  6. Формула полной вероятности

  7. Формула Байеса

  8. Схема Бернулли. Формула Бернулли


Тема 2.2. Дискретные случайные величины (ДСВ)


  1. Случайные величины.

  2. ДСВ. Распределение ДСВ.

  3. Методика записи распределения функции от одной ДСВ, от двух ДСВ.

  4. Числовые характеристики ДСВ и их свойства


Тема 2.3. Непрерывные случайные величины (НСВ)


  1. Функция плотности НСВ. Свойства

  2. Интегральная функция распределения НСВ. Свойства

  3. Методика вычисления характеристик НСВ по ее функции плотности.

  4. Виды распределений НСВ. Нормальное распределение с.в.



Раздел 3. Основы математической статистики


Тема 3.1. Выборочный метод. Статистические оценки параметров распределения.


  1. Генеральная совокупность и выборка.

  2. Полигон, гистограмма.

  3. Числовые характеристики выборки.

  4. Понятие интервальной оценки математического ожидания нормального распределения.

  5. Интервальная оценка вероятности события.


Тема 3.2. Моделирование случайных величин


  1. Моделирование случайных величин. ДСВ.

  2. Моделирование случайных величин. НСВ.


Тема 3.3. Современные пакеты прикладных программ многомерного статистического анализа


  1. Современные пакеты прикладных программ многомерного статистического анализа.


Раздел 4. Основы теории графов


Тема 4.1.Основные понятия теории графов


  1. Понятие графа. Способы задания графов.

  2. Операции над графами

  3. Метрические характеристики графов


Тема 4.2.Остовы графов, деревья


  1. Остов графа. Деревья.

  2. Построения остовного дерева. Алгоритм


Тема 4.3.Виды графов


  1. Эйлеровы графы

  2. Гамильтоновы графы

  3. Фундаментальные циклы




ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ



Основные источники


  1. М.С. Спирина, П.А. Спирин Теория вероятностей и математическая статистика.- М.: Издательский центр «Академия», 2012.


Дополнительные источники


  1. Н.В. Богомолов, П.И. Самойленко Математика.-М.: Дрофа, 2010.

  2. Статистика : учебник для учреждений среднего профессионального образования / ред. В. С. Мхитарян . - 11-е изд., стер . - М. : Академия , 2012

  3. Virtual Laboratory Wiki. Распределение вероятностей /Категория: Распределения_вероятностей. – М., 2010. / http://ru.vlab.wikia.com/wiki/

  4. Кочетков Е.С. Теория вероятностей и математическая статистика: учебник для СПО / Е.С. Кочетков, С.О. Смерчинская, В.В. Соколов. – М.: Форум, 2011



Периодические издания


  1. Журнал «Алгебра и анализ»

  2. Журнал «Математические заметки»


Интернет-ресурсы


  1. Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru

  2. Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru

  3. Информационно-справочная система. Форма доступа: http://dit.isuct.ru.

  4. Информационно-справочная система. Форма доступа: http://www.resolventa.ru




98


Краткое описание документа:

Учебно-методический комплекс по дисциплине Теория вероятностей и математическая статистика составлен в соответствии с требованиями к минимуму результатов освоения дисциплины, изложенными в Федеральном государственном стандарте среднего профессионального образования по специальности 09.02.03  Программирование в компьютерных системах.

Учебно-методический комплекс по дисциплине Теория вероятностей и математическая статистика адресован студентам очной формы обучения.

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

 

Общая информация

Номер материала: 346044

Похожие материалы