УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ЕН.03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА (ТЕОРЕТИЧЕСКИЙ БЛОК0 ПО СПЕЦИАЛЬНОСТИ 09.02.03 Программирование в компьютерных системах
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ
«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»
Евдокимова М.Д.
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
ПО ДИСЦИПЛИНЕ
ЕН.03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА
(ТЕОРЕТИЧЕСКИЙ БЛОК0
ПО СПЕЦИАЛЬНОСТИ
09.02.03 Программирование в компьютерных системах
ДЛЯ СТУДЕНТОВ ОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
Семилуки. 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. Основные понятия комбинаторики
Введение
О теории вероятностей
Человечество всегда стремилось к некоторого рода предсказаниям. Любая наука основана на этом. Однако предвидение фактов не может быть абсолютным, каким бы обоснованным оно не казалось. У нас не может быть абсолютной уверенности в том, что наше предвидение не будет опровергнуто опытом.
Допустим, что некоторый простой закон подтверждается для большого числа случаев. Является ли это просто случайным совпадением, или все-таки это - закономерность? Получается, что ученый часто находится в положении игрока; опираясь на метод индукции, он сознательно или не очень вычисляет вероятность.
История теории вероятности содержит очень много неожиданных парадоксов. По мнению Карла Пирсона, в математике нет другого такого раздела науки, в котором так же легко совершить ошибку. Даже само высказывание "вычислить вероятность" содержит парадокс. Ведь вероятность, в противоположность достоверности, есть то, чего не знают. Как же можно вычислять то, о чем нет никаких знаний?
Пользуясь классическим определением, можно сказать, что вероятность - это отношение числа случаев, благоприятствующих изучаемому событию, к полному числу возможных случаев. Однако это определение весьма неполно, что может подтвердить простой пример. Давайте посчитаем вероятность того, что при бросании двух игральных костей по крайней мере на одной выпадет 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. Этот результат явно отличается от предыдущего. Однако пользуясь нашим определением, мы не сможем найти ошибку.
Таким образом, придется дополнить определение: вероятность - это отношение числа случаев, благоприятствующих изучаемому событию, к полному числу возможных случаев, при условии, что эти случаи равновероятны. И вот мы определили вероятное при помощи вероятного.
Но как узнать, равновероятны ли два возможных случая? Не является ли это результатом некоторого условного соглашения? Если мы явно укажем условное соглашение перед вычислениями, то все будет хорошо. Но как мы применим результат на практике? Ведь тогда придется доказать состоятельность данного соглашения.
Некоторые могут предположить, что простого здравого смысла достаточно, чтобы указать верное соглашение. Но описанные далее парадоксы противоречат, казалось бы, всякому здравому смыслу.
Тем не менее без теории вероятности не сможет существовать наука как таковая, ведь без нее мы не сможем ни открыть какой-нибудь закон, ни применять его.
Исторические сведения
Возникновение теории вероятностей как [ Cкачайте файл, чтобы посмотреть ссылку ] относят к [ Cкачайте файл, чтобы посмотреть ссылку ] и первым попыткам [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] ([ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]). Первоначально её основные понятия не имели строго математического вида, к ним можно было относиться как к некоторым [ Cкачайте файл, чтобы посмотреть ссылку ], как к свойствам реальных событий, и они формулировались в наглядных представлениях. Самые ранние работы учёных в области теории вероятностей относятся к XVII веку. Исследуя прогнозирование выигрыша в азартных играх, [ Cкачайте файл, чтобы посмотреть ссылку ] и [ Cкачайте файл, чтобы посмотреть ссылку ] открыли первые вероятностные закономерности, возникающие при бросании [ Cкачайте файл, чтобы посмотреть ссылку ]. [ Cкачайте файл, чтобы посмотреть ссылку ]
Важный вклад в теорию вероятностей внёс [ Cкачайте файл, чтобы посмотреть ссылку ]: он дал доказательство [ Cкачайте файл, чтобы посмотреть ссылку ] в простейшем случае независимых испытаний. В первой половине 13 LINK "http://ru.wikipedia.org/wiki/XIX_%D0%B2%D0%B5%D0%BA" \o "XIX
век" 14XIX века15 теория вероятностей начинает применяться к анализу ошибок наблюдений; [ Cкачайте файл, чтобы посмотреть ссылку ] и [ Cкачайте файл, чтобы посмотреть ссылку ] доказали первые предельные теоремы. Во второй половине 13 LINK "http://ru.wikipedia.org/wiki/XIX_%D0%B2%D0%B5%D0%BA" \o "XIX
век" 14XIX века15 основной вклад внесли русские учёные [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ] и [ Cкачайте файл, чтобы посмотреть ссылку ]. В это время были доказаны [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], а также разработана теория [ Cкачайте файл, чтобы посмотреть ссылку ]. Современный вид теория вероятностей получила благодаря [ Cкачайте файл, чтобы посмотреть ссылку ], предложенной [ Cкачайте файл, чтобы посмотреть ссылку ]. В результате теория вероятностей приобрела строгий математический вид и окончательно стала восприниматься как один из [ Cкачайте файл, чтобы посмотреть ссылку ].
Тема лекции: Элементы комбинаторики
План:
1. Принцип умножения
2. Размещения (упорядоченные выборки).
3. Перестановки
4. Сочетания (неупорядоченные выборки)
Принцип умножения
Пусть необходимо выполнить одно за другим одновременно 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
·n3
· n4
· n5
·n6
·n7 =3
·6
·5
·4
·3
·2
·1 = 2160.
Размещения (упорядоченные выборки).
Пусть А – множество, состоящее из элементов а1, а2,, аn.
Определение: Упорядоченные наборы, состоящие из r элементов множество А, будем называть размещениями из n элементов множества А по r элементов.
13 EMBED Equation.3 1415 – число размещений из n элементов по r элементов(r (n). Вычислим 13 EMBED Equation.3 1415 по принципу умножения:
n1= n,
n2 =n-1, 13 EMBED Equation.3 1415 = 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 – того элементов.
13 EMBED Equation.3 1415
Перестановки
Определение: Размещения из n элементов по n элементов называются перестановки из n элементов.
Pn – число перестановок из n элементов.
13 EMBED Equation.3 1415
Пример: Сколькими способами могут 4 человека разместиться в 4-х местном купе железнодорожного вагона?
Решение: А = {1, 2, 3, 4} (4 места в купе вагона);
P4 = 4! = 1
·2
·3
·4 = 24.
Сочетания (неупорядоченные выборки)
А = {а1, а2, а3, аn}
Определение: Неупорядоченные наборы, состоящие из r элементов множества А, называются сочетаниями из n элементов по r элементов. (r13 EMBED Equation.3 1415 n).
13 EMBED Equation.3 1415
Пример: Студенту необходимо сдать 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} (плотники).
13 EMBED Equation.3 1415
Пример. В розыгрыше первенства по футболу участвуют 10 команд. Известно, что те, кто займет первые 3 места, получают золотую, серебряную и бронзовую медали, а последние двое выбывают. Сколько различных результатов первенства может быть?
Решение: Нужно выполнить одно за другими два действия:
Из десяти команд выбрать три на три первых места.
После выполнения первого действия из оставшихся семи команд выбрать две на два последних места.
Итак, по принципу умножения r = 2 ;
n1=13 EMBED Equation.3 1415=10(9(8=720; n2=13 EMBED Equation.3 1415=13 EMBED Equation.3 1415=21.
Различных результатов первенства может быть:
n1n2= 720 . 21=15120.
Контрольные вопросы:
Сформулируйте принцип умножения.
Сформулируйте замечание к принципу умножения.
Приведите пример задачи на принцип умножения.
Размещения (упорядоченные выборки). Определение, формула.
Перестановки. Определение, формула
Сочетания (неупорядоченные выборки). Определение, формула.
Задачи на закрепление материала:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Вычислить: 13 EMBED Equation.3 1415.
Вычислить: 13 EMBED Equation.3 1415.
Упростить выражение:13 EMBED Equation.3 1415
Упростить выражение:13 EMBED Equation.3 1415
Упростить выражение:13 EMBED Equation.3 1415
Решить уравнение: 13 EMBED Equation.3 1415.
Решить комбинаторные уравнения:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Тема лекции: Задачи на расчет количества выборок
На использование формул для перестановок и размещений
Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять:
(а) из восьми букв, (б) из семи букв, (в) из трех букв?
Решение задачи:
В слове фрагмент 8 букв алфавита.
(а) Всевозможные перестановки 8 букв по восьми местам: А13 EMBED Equation.3 1415 = 13 EMBED Equation.3 1415=P8.
(б) Размещения 8 букв по 7 местам: А13 EMBED Equation.3 1415.
(в) Размещения 8 букв по 3 местам: А13 EMBED Equation.3 1415.
Ответ: P8, А13 EMBED Equation.3 1415, А13 EMBED Equation.3 1415.
Сколькими способами можно расставить на полке 7 книг, если (а) две определенные книги должны всегда стоять рядом, (б) эти две книги не должны стоять рядом?
Решение задачи:
(а) Книги, которые должны стоять рядом, считаем за одну книгу. Тогда нужно расставить 6 книг по шести местам. Применяя формулу перестановок, получаем: P6 = 6!. Мы учли перестановки шести книг, не учитывая порядок внутри тех книг, которые мы посчитали за одну. А так как две книги по двум местам можно разместить только двумя способами (P2), то получаем окончательно следующее произведение: P213 EMBED Equation.3 1415P6 =2 13 EMBED Equation.3 14156! = 1440.
(б) Способов переставить 7 книг существует P7= 7!. Из них 213 EMBED Equation.3 14156! способов поставить определенные книги вместе. Следовательно, способов поставить книги так, чтобы 2 заданные книги не стояли вместе существует: 7! 213 EMBED Equation.3 14156!.
Ответ: 1440; . 7! 213 EMBED Equation.3 14156!
На использование формул для сочетаний
Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?
Решение задачи:
Для решения этой задачи необходимо использовать формулу для сочетания элементов, т.к. здесь не имеет значения порядок элементов в выборке. Запишем формулу для сочетаний и произведем вычисления:
С13 EMBED Equation.3 1415 = 13 EMBED Equation.3 1415.
Ответ: 56.
Компания из двадцати мужчин разделяется на три группы, в первую из которых входят три человека, во вторую пять и в третью двенадцать. Сколькими способами они могут это сделать? (Ответ записать в виде произведения сомножителей, не вычисляя его.)
Решение задачи:
Из 20-ти элементов необходимо сделать три выборки, причем порядок внутри выборок значения не имеет. Поэтому используем формулу для сочетаний. Чтобы выбрать из 20-ти элементов 3, существует С13 EMBED Equation.3 1415 способов. Остается 17 элементов, из которых выбирается 5 элементов - С13 EMBED Equation.3 1415 способами. Остается 12 элементов, из которых выбирается 12 элементов. Это можно сделать С13 EMBED Equation.3 1415= 1, т.е. одним способом. Используя принцип произведения, получаем: С13 EMBED Equation.3 141513 EMBED Equation.3 1415 С13 EMBED Equation.3 141513 EMBED Equation.3 1415 С13 EMBED Equation.3 1415.
Ответ: С13 EMBED Equation.3 141513 EMBED Equation.3 1415 С13 EMBED Equation.3 141513 EMBED Equation.3 1415 С13 EMBED Equation.3 1415.
На использование формул для перестановок и сочетаний
Сколько четырехбуквенных слов можно образовать из букв слова сапфир? 2) Сколько среди них таких, которые не содержат буквы р? 3) Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?
Решение задачи:
1. Из шести букв составляются четырехбуквенные слова, причем порядок букв важен для образования новых слов. Поэтому используется формула для размещений: А13 EMBED Equation.3 1415.
2. Необходимо исключить букву р из рассмотрения. Количество слов, не содержащих эту букву: А13 EMBED Equation.3 1415.
3. На первое место поставить букву с можно только одним способом. На последнее место поставить букву р можно тоже только одним способом. Остаются 4 буквы, которые необходимо разместить по двум местам: А13 EMBED Equation.3 1415.
Ответ: 360, 120, 12.
Сколько пятибуквенных слов, каждое из которых состоит из трех согласных и двух гласных, можно. образовать из букв слова уравнение?
Решение задачи:
В слове уравнение 3 согласных и 4 гласных буквы русского алфавита. Чтобы посчитать количество требуемых пятибуквенных слов, необходимо посчитать количество сочетаний 3 согласных из 3-х заданных и двух гласных из четырех заданных: С13 EMBED Equation.3 1415 и С13 EMBED Equation.3 1415. После того, как 5 букв выбраны, необходимо посчитать все возможные перестановки этих букв: С13 EMBED Equation.3 141513 EMBED Equation.3 1415С13 EMBED Equation.3 141513 EMBED Equation.3 1415P5.
Ответ: С13 EMBED Equation.3 141513 EMBED Equation.3 1415С13 EMBED Equation.3 141513 EMBED Equation.3 1415P5.
Задачи для закрепления материала
Сколькими способами можно разложить 7 шаров по 4-м ящикам?
Ответ: 13 EMBED Equation.3 1415 .
Сколькими способами можно разложить 5 разноцветных шаров по 3-м ящикам?
Ответ: 243.
Директор фирмы составил список из 5-ти возможных кандидатов на вакантные должности своих 1-го, 2-го и 3-го заместителей, а также список из 4-х возможных кандидатов на 2 вакантные должности своих помощников. Сколько вариантов заполнения пяти вакантных должностей имеет директор?
Ответ: 13 EMBED Equation.3 1415.
У одного человека есть 7 книг, а у другого 9 книг. Сколькими способами они могут обменять три книги одного на три книги другого?
Ответ: 13 EMBED Equation.3 1415.
Бригада строителей состоит из 16-ти штукатуров и 4-х маляров. Сколькими способами бригаду можно разделить на две бригады, чтобы в одной из них было 10 штукатуров и 2 маляра, а в другой 6 штукатуров и 2 маляра?
Ответ: 13 EMBED Equation.3 1415.
Дополнительные задачи
Из цифр 1, 2,3,4,5 составляются всевозможные числа, каждое из которых содержит три цифры. Сколько таких чисел можно составить, если повторение цифр в числах запрещено?
Сколько существует пятизначных чисел, которые начинаются цифрой 2 и оканчиваются цифрой 4?
На окружности выбрано 10 точек. Сколько существу ет треугольников с вершинами в этих точках?
На железной дороге 50 станций. На каждой билете печатаются названия станций отправления и прибытия. Сколько различных билетов можно напечатать? (Небезразлично, с какой из двух обозначенных в билете станций вы отправляетесь).
В распоряжении агрохимика есть 6 различных типов минеральных удобрений. Ему необходимо провести несколько экспериментов по изучению влияния любой тройки минеральных удобрений. Сколько всего экспериментов ему придется произвести?
Имеется три письма, каждое из которых можно послать по одному из шести адресов. Сколько есть способов рассылки писем, если нельзя послать более одного письма по одному адресу?
Сколько разных сигналов можно поднять на мачте, имея четыре вымпела разных цветов, если каждый сигнал должен состоять не менее, чем из двух вымпелов?
Сколько различных комбинаций букв можно получить, переставляя буквы в слове «парабола»?
Практические занятия
Практическое занятие №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. Оно представляет собой пустое множество элементарных событий.
Противоположным событию А13 EMBED Equation.3 1415
· событием называется событие 13 EMBED Equation.3 1415, состоящее в том, что событие А не произошло.
13 EMBED Equation.3 1415состоит из элементарных событий, не входящих в А.
Суммой (или объединением) событий А и В называется событие А + В, состоящее в том, что из двух событий А и В происходит по крайней мере одно (либо А, либо В, либо А и В вместе).
Этому событию соответствует множество элементарных событий А 13 EMBED Equation.3 1415 В. Поэтому, иногда мы будем использовать знак объединения, вместо знака суммирования.
Пример. По мишени стреляют 3 раза. События А, В, С – попадание при 1-ом, 2-ом и 3 выстрелах соответственно. Сумма событий А, В и C означает хотя бы одно попадание.
Классическое определение вероятности
Пусть некоторый опыт может приводить лишь к одному из конечного множества результатов. Эти результаты будем называть элементарными исходами. Предположим, что элементарные исходы удовлетворяют следующим условиям:
образуют полную группу, т.е. в каждом испытании обязан появиться какой-нибудь из этих исходов;
попарно несовместны, т.е. два различных элементарных исхода не могут появиться в одном испытании;
равновозможные, т.е. шансы на появление у всех элементарных исходов одинаковы.
В этих условиях может использоваться классическое определение вероятности.
Определение: Элементарные исходы, в которых появляются интересующее нас событие, называются благоприятными этому событию.
Определение: Вероятностью события А называются число P(А), равное отношению числа исходов испытания, благоприятствующих событию А к общему числу исходов:
13 EMBED Equation.3 1415где n – общее число исходов испытания, m – число исходов, благоприятствующих событию А.
Пример: Бросается один раз игральная кость. Какова вероятность выпадения нечетного числа очков?
Решение: Опыт состоит в бросании игральной кости 1 раз и наблюдении за числом очков, появившихся на верхней грани.
Все исходы опыта: 1, 2, 3, 4, 5, 6.
Число всех исходов: n = 6.
Рассмотрим событие А – выпало нечетное число очков. Исходы благоприятствующие А: 1, 3, 5.
Число исходов, благоприятствующих А : m = 3
13 EMBED Equation.3 1415.
Пример: Ребенок играет с шестью буквами разрезной азбуки А, В, К, М, О, С. Какова вероятность того, что при случайном расположении букв в ряд получится слово «МОСКВА»?
Решение: Опыт состоит в случайном расположении шести букв в ряд. Все исходы опыта – множество перестановок из шести различных букв.
Число всех исходов: n = P6=6! = 1.2.3.4 .5.6=720.
Рассмотрим событие А – при случайном расположении шести букв в ряд получено слово «МОСКВА». Очевидно, что такое расположение букв единственно, т.е. m=1. Найдем вероятность события А: P(A)=13 EMBED Equation.3 1415.
Пример: В ящике находится 20 деталей, из них 8 бракованных. Из ящика наудачу извлекают 5 деталей. Найти вероятность того, что среди них окажутся две бракованные детали.
Решение: Опыт состоит в выборе наудачу 5 деталей из 20. Все исходы опыта – множество сочетаний из 20 деталей (находящихся в ящике) по 5.
Число всех исходов опыта n=13 EMBED Equation.3 1415=13 EMBED Equation.3 1415
Рассмотрим событие А – среди 5 деталей, извлеченных из ящика, две бракованные.
Если среди 5 деталей две бракованные, то остальные 3 небракованные. Тогда число исходов, благоприятствующих
событию А, можно найти по принципу умножения. Нужно выполнить одно за другим два действия: из 8 бракованных выбрать 2 детали и затем из 12 небракованных выбрать 3 детали. Первое действие можно выполнить n1=13 EMBED Equation.3 1415второе действие можно выполнить n2=13 EMBED Equation.3 1415 способами. Итак, m=n1.n2=13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
Найдем вероятность события А:
13 EMBED Equation.3 1415
Задачи на классическое определение вероятности
Буквой A обозначаем событие, фигурирующее в условии задачи.
Задача. Корреспонденция разносится в 5 адресов. Разносчик забыл дома очки и разнес корреспонденцию случайным образом. Какова вероятность того, что вся корреспонденция попала к своим адресатам?
Решение. Элементарным событием является перестановка из 5 адресов. Их число равно 13 EMBED Equation.3 1415 По смыслу задачи все они равновероятны. Поэтому 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)= 13 EMBED Equation.3 1415
Задача. Из 7 карточек разрезной азбуки составлено слово колокол. Эти карточки рассыпали и затем собрали в случайном порядке. Какова вероятность того, что снова получится слово колокол?
Решение. На карточках имеется 3 буквы о, 2 буквы к, 2 буквы л. Поэтому, первая буква слова колокол может быть выбрана двумя способами, вторая – 3 способами, третья – 2 способами. При уже выбранных первых трех буквах четвертая буква может быть выбрана еще 2 способами (поскольку одна буква о уже выбрана). Остальные буквы могут быть выбраны только одним способом. Таким образом (см. решение задачи 12), число перестановок карточек, реализующих слово колокол равно произведению чисел 3, 2, 2, 2 т.е. равен 24. Общее число перестановок карточек равно 7!.Поэтому P(A)= 13 EMBED Equation.3 1415
Контрольные вопросы:
Что такое случайное событие?.
Какие виды событий вы знаете?
Дайте классическое определение вероятности.
Тема лекции: Противоположное событие. Теоремы сложения, умножения вероятностей
План:
Основные определения
Теорема умножения вероятностей
Теорема сложения вероятностей несовместимых событий
Вероятность противоположного события
Основные определения
Определение: Событие, которое в результате опыта должно произойти непременно, называется достоверным событием.
Определение: Событие, которое в данном опыте не может произойти, называется невозможным.
Вероятность достоверного события равна единице, вероятность невозможного события равна нулю.
Определение: Два события называют несовместными, если появление одного из них исключает появление другого в одном и том же испытании.
Определение: Суммой А+В двух событий А и В называется событие, состоящее в появлении хотя бы одного из них, т. е. или событие А или В или А и В вместе.
Определение: Произведением А.В двух событий А и В называется событие, состоящее в совместном появлении события А и события В.
Определение: Противоположным к А называется событие 13 EMBED Equation.3 1415, состоящее в том, что А не произошло.
Определение: Два события называются независимыми, если вероятность одного из них не зависит от появления или не появления другого.
Определение: Пусть А и В – зависимые события. Условной вероятностью Р(В|А) (или PA(B)) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.
Теорема умножения вероятностей
Теорема: Вероятность произведения двух независимых событий равна произведению вероятностей этих событий
P(A.B) = P(A).P(B).
Пример . Какова вероятность того, что при десятикратном бросании монеты герб выпадет 10 раз ?
Решение: Пусть событие Ai появление герба при i-м бросании. Искомая вероятность есть вероятность совмещения всех событий Ai (i=1,2,3,...,10), а так как они, очевидно, независимы в совокупности, то применяя формулу (10), имеем
[ Cкачайте файл, чтобы посмотреть картинку ]
Но P(Ai)=1/2 для любого i; поэтому
[ Cкачайте файл, чтобы посмотреть картинку ]
Теорема: Вероятность произведения двух зависимых событий равна произведению вероятностей одного из них на условную вероятность другого, вычисленную в предложении, что первое уже наступило.
P(A .B) = P(A).P(B(A).
Для трех зависимых событий:
P(A .B) = P(A).P(B(A).P(C(A .B).
Пример. Из урны, содержащей 3 белых и 7 черных шаров, вынимают два шара. Какова вероятность того, что оба шара окажутся белыми ?
Решение: Эта задача уже была решена в п. 3 с помощью классического определения вероятности. Решим ее, применяя формулу (5). Извлечение двух шаров равносильно последовательному их извлечению. Обозначим через А появление белого шара при первом извлечении, а через В при втором. Событие, состоящее в появлении двух белых шаров, является совмещением событий А и В. По формуле (5) имеем
[ Cкачайте файл, чтобы посмотреть картинку ]
Но Р(А)=3/10; РA(В)=2/9, поскольку после того, как был вынут первый белый шар, в урне осталось 9 шаров, из которых 2 белых. Следовательно,
[ Cкачайте файл, чтобы посмотреть картинку ]
Теорема сложения вероятностей несовместимых событий
Теорема: Вероятность суммы несовместных событий равна сумме вероятностей этих событий:
P(A+B) = P(A)+P(B).
Пример. В урне 2 зеленых, 7 красных, 5 коричневых и 10 белых шаров. Какова вероятность появления цветного шара?
Решение: Находим соответственно вероятности появления зеленого, красного и коричневого шаров: Р(зел.)=2/24; Р(кр.)=7/24; Р(кор.)=5/24. Так как рассматриваемые события, очевидно, несовместны, то, применяя аксиому сложения, найдем вероятность появления цветного шара:
[ Cкачайте файл, чтобы посмотреть картинку ]
Теорема:
Если 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 – попадание в мишень из второго орудия.
Тогда А = А1+А2.
Поскольку события А1 и А2 совместны, то
P(A) = P(А1)+P(А2)-P(А1 ,А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.
Вероятность противоположного события
Несколько событий в данном опыте образуют полную группу, если в результате опыта обязательно должно появиться хотя бы одно из этих событий, Отсюда следует, что сумма событий полной группы есть достоверное событие, вероятность которого равна единице.
Если события, образующие полную группу, попарно несовместны, то в результате опыта появится одно и только одно из этих событий.
Для суммы таких событий справедлива формула
P(A1+A2+.+An) = P(A1)+P(A2)+.+P(An) = 1.
Теорема: Два противоположных друг другу события образуют полную группу:
13 EMBED Equation.3 1415
Пример: В партии содержится 20 деталей, среди которых 4 нестандартных. Для контроля взяли наудачу 3 детали. Найти вероятность того, что хотя бы одна из взятых деталей нестандартна.
Решение: Пусть событие А – хотя бы одна из взятых деталей окажется нестандартной. Рассмотрим событие13 EMBED Equation.3 1415, противоположное событию А:
13 EMBED Equation.3 1415 - среди взятых деталей нет нестандартных. Вычислим вероятность события 13 EMBED Equation.3 1415: 13 EMBED Equation.3 1415
Теперь вычислим вероятность искомого события:
P(A) = 1-13 EMBED Equation.3 1415.
Пример: Перегорела одна из пяти электроламп, включенных в сеть последовательно. С целью устранения повреждения наудачу выбранную лампочку заменяют годной, после чего сразу проверяется исправность линии. Если повреждение не устранено, то заменяется другая лампочка. Найти вероятность того, что повреждение будет устранено только после замены третьей лампочки.
Решение: Пусть событие А – повреждение будет исправлено после замены третьей лампы.
Рассмотрим следующие три события:
А1 – первая замененная лампа оказалась перегоревшей;
А2 – вторая замененная лампа оказалась перегоревшей;
А3 – третья замененная лампа оказалась перегоревшей.
Тогда: А = 13 EMBED Equation.3 1415
Поскольку события 13 EMBED Equation.3 1415зависимы, то 13 EMBED Equation.3 1415
Вероятность события 13 EMBED Equation.3 1415 есть вероятность того, что первая замененная лампа оказалась исправной13 EMBED Equation.3 1415.
Условная вероятность 13 EMBED Equation.3 1415 - вероятность того, что вторая замененная лампа оказалась исправной, если известно, что первая замененная лампа также исправна.
Поэтому 13 EMBED Equation.3 1415=13 EMBED Equation.3 1415.
Наконец, условная вероятность 13 EMBED Equation.3 1415 есть вероятность того, что третья замененная лампа оказалась перегоревшей, если известно, что первая и вторая замененные лампы были исправными.
Откуда 13 EMBED Equation.3 1415.
Теперь подсчитаем искомую вероятность: P(A)=13 EMBED Equation.3 1415
Пример: Вероятности того, что деталь нужного вида находится в первом, втором, третьем ящике соответственно равны 0,7; 0,8; 0,9. Найти вероятность того, что деталь содержится не менее, чем в двух ящиках.
Решение: Пусть событие А – деталь нужного вида находится не менее, чем в двух ящиках. Рассмотрим следующие три события:
А1 – деталь нужного вида имеется в 1-ом ящике;
А2 – деталь нужного вида имеется во 2-ом ящике;
А3 - деталь нужного вида имеется в 3-ем ящике.
Событие B1=13 EMBED Equation.3 1415 заключается в том, что нужного вида деталь имеется во 2-ом и 3-ем ящиках, но ее нет в 1-ом ящике. События имеется во 2-ом и 3-ем независимы, поэтому
13 EMBED Equation.3 1415
Событие 13 EMBED Equation.3 1415 заключается в том, что нужного вида деталь имеется в 1-ом и в 3-ем ящиках, но ее нет во 2-ом ящике.
Событие B3=A1 ,A2 ,13 EMBED Equation.3 1415заключается в том, что нужного вида деталь имеется в 1-ом и 2-ом ящиках, но ее нет в 3-ем ящике.
13 EMBED Equation.3 1415)=P(A1) ,P(A2) ,P(13 EMBED Equation.3 1415
Наконец, событие B4=A1 ,A2 ,A3 заключается в том, что нужного вида деталь имеется и в 1-ом, и во 2-ом, и в 3-ем ящиках.
13 EMBED Equation.3 1415
Событие А произойдет тогда, когда произойдет одно из событий:
или В1, или В2, или В3, или В4. Поэтому А=В1+В2+В3+В4.
Поскольку события В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.
Контрольные вопросы:
Что такое случайное событие?.
Дайте классическое определение вероятности.
Сформулируйте теорему умножения вероятностей.
Сформулируйте теорему сложения вероятностей.
Как найти вероятность противоположного события?
Задачи на закрепление материала
Вероятность того, что электрическая лампочка, принадлежащая данной партии, проработает гарантийный срок, равна 0,7. Какова вероятность того, что из трех лампочек этой партии гарантийный срок проработает только одна?
Система состоит из двух блоков. Первый из них выходит из строя с вероятностью 0,15, а второй – с вероятностью 0,1. Система выйдет из строя, когда откажут оба блока. Найти надежность безотказной работы системы
В партии из 20 деталей имеется 2 бракованные. Сборщик взял из партии 3 детали. Найти вероятность того, что среди них не белее одной бракованной.
Имеется 6 потребителей электрического тока, два из которых выходят из строя с вероятностью 0,2, а остальные с вероятностью 0,3. Определить вероятность того, что генератор тока будет отключен, если все 6 потребителей соединены последовательно.
В одном ящике находятся 3 конусных и 7 эллиптических валиков. Сборщик взял наудачу один валик, а затем второй. Найти вероятность того, что первый из взятых валиков конусный, а второй эллиптический.
В телестудии имеется 3 телевизионные камеры. Для каждой камеры вероятность того. что она в данный момент включена, равна 0,4. Найти вероятность того, что в данный момент включена хотя бы одна из трех камер.
ОТК проверяет изделия на стандартность. Вероятность того, что изделия данной партии нестандартно, равна 0,1. найти вероятность того, что из трех проверенных изделий только одно окажется нестандартным.
Производится залп из трех орудий. Найти вероятность хотя бы одного попадания в цель, если вероятности попадания для первого, второго и третьего орудий равны соответственно 0,7; 0,8 и 0,9.
Вероятность улучшить свой результат в одной попытке для данного спортсмена, равна 0,6. Найти вероятность того, что на соревнованиях спортсмен улучшит свой результат, если разрешается делать три попытки.
Данное предприятие дает в среднем 21% продукции высшего сорта и 70 % продукции первого сорта. Найти вероятность того, что случайно взятые два изделия окажутся одного сорта.
Тема лекции: Формула полной вероятности
Пусть событие А происходит совместно с одним из событий (гипотез) Н1, Н2, Нn, которые образуют полную группу событий. Тогда справедлива формула полной вероятности события А :
13 EMBED Equation.3 1415,
где Р(Нк) – вероятность гипотезы Нк, Р(А(Нк) – условная вероятность А, т.е. вероятность появления события А при условии, что произошла гипотеза Нк .
Пример. Три автомата изготовляют одинаковые детали.
Известно, что первый автомат производит 30% всей продукции, второй – 25% и третий – 45%. Вероятность изготовления детали, соответствующей стандарту, на первом автомате равна 0,99, на втором – 0,988 и на третьем – 0,988. все изготовленные за смену детали складываются вместе. Определить вероятность того, что взятая наудачу деталь не соответствует стандарту.
Решение: Пусть событие А – взятая наудачу деталь не соответствует стандарту.
Гипотезы:
Н1- взятая деталь изготовлена первым автоматом;
Н2- взятая деталь изготовлена вторым автоматом;
Н3- взятая деталь изготовлена третьим автоматом.
Вычислим вероятность гипотез.
13 EMBED Equation.3 1415
Вычислим условные вероятности:
Р(А(Н1) – вероятность того, что взятая наудачу деталь не соответствует стандарту, если она изготовлена первым автоматом.
13 EMBED Equation.3 1415
Вероятность события А подсчитываем по формуле полной вероятности :
Р(А)=0,3 .0,01+0,25 .0,012+0,45 .0,012=0,009.
Задачи на закрепление материала
Задачи с решениями.
Пример 1.В первой урне 7 белых и 3 черных шара, во второй – 8 белых и 2 черных. При перевозке из первой урны во вторую урну перекатились два шара. После того, как шары во второй урне перемешались, из неё выкатился шар. Найти вероятность того, что выкатившийся из второй урны шар белый.
Решение: Пусть событие Н1 состоит в том, что из первой урны во вторую перекатились два белых шара, событие Н2 состоит в том, что перекатились два чёрных шара, а событие Н3 состоит в том, что перекатились шары разного цвета. Можно вычислить вероятности Р(Н1) = 13 EMBED Equation.3 1415 = 7/15, Р(Н2) = 13 EMBED Equation.3 1415 = 1/15, Р(Н3) = 13 EMBED Equation.3 1415 = 7/15 (при решении задачи полезно проверить выполнение необходимого условия 13 EMBED Equation.3 1415).
Если реализовалась гипотеза Н1, то во второй урне оказалось 10 белых и 2 черных шара. Обозначим через А событие, заключающееся в том, что из второй урны выкатился белый шар. Тогда Р(А/Н1) = 13 EMBED Equation.3 1415 = 5/33. Если реализовалась гипотеза Н2, то во второй урне оказалось 8 белых и 4 чёрных шара, и Р(А/Н2) = 13 EMBED Equation.3 1415 = 4/33. Легко показать, что Р(А/Н3) = 13 EMBED Equation.3 1415 = 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) = 13 EMBED Equation.3 1415; Р(Н2) = 13 EMBED Equation.3 1415; Р(Н3) = 13 EMBED Equation.3 1415.
Теперь вычислим условные вероятности события А.
Р(А/Н1) = 13 EMBED Equation.3 1415; Р(А/Н2) = 13 EMBED Equation.3 1415; Р(А/Н3) = 13 EMBED Equation.3 1415.
Осталось подставить результаты вычислений в формулу полной вероятности
Р(А) = 13 EMBED Equation.3 1415.
Пример 3. На автозавод поступили двигатели от трех моторных заводов. От первого завода поступило 10 двигателей, от второго – 6 и от третьего – 4 двигателя. Вероятности безотказной работы этих двигателей в течение гарантийного срока соответственно равны 0,9; 0,8; 0,7. Какова вероятность того, что установленный на машине двигатель будет работать без дефектов в течение гарантийного срока?
Решение Событие A – установленный на машине двигатель будет работать без дефектов в течение гарантийного срока – может произойти, если произойдет одно из несовместных событий: 13 EMBED Equation.3 1415 – установленный на машине двигатель изготовлен на первом, втором или третьем заводе соответственно. Эти события образуют полную группу, их вероятности:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,
(Контроль:13 EMBED Equation.3 1415).
По условию 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
По формуле полной вероятности
13 EMBED Equation.3 141513 EMBED Equation.3 1415.
Решить задачи:
В партии саженцев имеются в одинаковых количествах березы, клены, липы. Вероятность того, что посаженное дерево приживется, равна для березы 0,7, для клена – 0,8, для липы – 0,9. Найти вероятность того, что наудачу взятое прижившееся дерево окажется березой.
Половина всех арбузов поступает в магазин с 1-й базы, 1/3 – со 2-й базы, остальные – с 3-ей базы. Арбузы с повышенным содержанием нитратов составляют на 1-й базе 15 %, на 2-й базе – 10 %, на 3-ей – 20 %. Какова вероятность купить недоброкачественный арбуз?
Имеются три одинаковых ящика. В первом ящике лежат 2 белых и 2 черных шара, во втором – ящике – 3 черных, в третьем – 1 черный и 5 белых. Некто, случайным образом выбирая ящик, наугад вынимает из него шар. Какова вероятность того, что шар будет белый?
В лаборатории имеется 12 автоматических машин и 8 полуавтоматов. Вероятность того, что за время выполнения некоторого задания автомат не выйдет из строя, равна 0,94. Для полуавтоматов эта вероятность равна 0,85. Студент выполняет задание на машине, выбранной наудачу. Найти вероятность того, что до конца выполнения задания машина не выйдет из строя.
Тема лекции: Формула Байеса
Пусть вероятности гипотез до опыта были Р(Н1), Р(Н2), Р(Нn). В результате опыта появилось событие А . Тогда условная вероятность Р(Нк(А) гипотезы Нк с учетом появления события А вычисляется по формуле Байеса:
13 EMBED Equation.3 1415.
Пример. На двух станках производят одинаковые детали, которые поступают на конвейер. Производительность первого станка в три раза больше производительности второго. Первый станок дает в среднем 80% деталей отличного качества, а второй –90%. Наудачу взятая с конвейера деталь оказалась отличного качества. Найти вероятность того , что она изготовлена на втором станке.
Решение Пусть событие А - взятая наудачу с конвейера деталь отличного качества.
Гипотезы:
Н1- деталь изготовлена на первом станке;
Н2- деталь изготовлена на втором станке.
Вероятность гипотез до появления события А:
Р(Н1)=3/4; Р(Н2)=1/4.
Условные вероятности
13 EMBED Equation.3 1415
Вероятности того, что взятая наудачу с конвейера деталь окажется отличного качества, т.е. вероятность события А, вычисляется по формуле полной вероятности:
13 EMBED Equation.3 1415
Искомая вероятность того, что взятая деталь отличного качества изготовлена на втором станке, вычисляется по формуле Байеса: 13 EMBED Equation.3 1415
Задачи на закрепление материала
Задачи с решениями.
Пример. В первой урне 7 белых и 3 черных шара, во второй – 8 белых и 2 черных. При перевозке из первой урны во вторую урну перекатились два шара и шары во второй урне перемешались, из неё выкатился белый шар. Найти вероятность того, что из первой урны во вторую перекатились разноцветные шары.
Решение
Пусть событие Н1 состоит в том, что из первой урны во вторую перекатились два белых шара, событие Н2 состоит в том, что перекатились два чёрных шара, а событие Н3 состоит в том, что перекатились шары разного цвета. Можно вычислить вероятности Р(Н1) = 13 EMBED Equation.3 1415 = 7/15, Р(Н2) = 13 EMBED Equation.3 1415 = 1/15, Р(Н3) = 13 EMBED Equation.3 1415 = 7/15 (при решении задачи полезно проверить выполнение необходимого условия 13 EMBED Equation.3 1415).
Если реализовалась гипотеза Н1, то во второй урне оказалось 10 белых и 2 черных шара. Обозначим через А событие, заключающееся в том, что из второй урны выкатился белый шар. Тогда Р(А/Н1) = 13 EMBED Equation.3 1415 = 5/33. Если реализовалась гипотеза Н2, то во второй урне оказалось 8 белых и 4 чёрных шара, и Р(А/Н2) = 13 EMBED Equation.3 1415 = 4/33. Легко показать, что Р(А/Н3) = 13 EMBED Equation.3 1415 = 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,2(0,7/(0,2(0,7+0,8(03) = 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. К бензоколонке подъехала для заправки машина. Найти вероятность того, что это грузовая машина.
Тема лекции: Схема Бернулли. Формула Бернулли
План:
Схема Бернулли. Формула Бернулли
Предельные теоремы для схемы Бернулли
Схема Бернулли. Формула Бернулли
Пусть производится n независимых однотипных испытаний, в каждом из которых событие А может появиться с вероятностью Р. Тогда вероятность непоявления события А, т.е. Р(13 EMBED Equation.3 1415) равна q=1-p.
Вероятность того, что событие А произойдет в этих n независимых испытаниях ровно k раз, можно вычислить по формуле Бернулли
13 EMBED Equation.3 1415
Для определения вероятности появления события A менее m раз (k < m), более m раз (k > m), хотя бы один раз (13 EMBED Equation.3 1415) и т. п. могут быть использованы формулы:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
Пример: Прибор состоит из пяти узлов. Надежность (вероят ность безотказной работы в течение времени 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) =13 EMBED Equation.3 1415(0,1)2 .(0,9)3=10.0,01.0,729=0,0729.
Пример . Всхожесть семян данного растения равна 90 %. Найти вероятность того, что из четырех посеянных семян взойдут: а) три; б) не менее трех.
Решение
а) Искомую вероятность находим с помощью формулы Бернулли (14), учитывая что 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415.
б) «Не менее трех» означает, что из четырех семян взойдут или три, или четыре. Так как эти события несовместны, то по теореме сложения искомая вероятность равна
13 EMBED Equation.3 1415.
Предельные теоремы для схемы Бернулли
Теорема Пуассона. (Отметим, что на практике эта теорема применяется при 13 EMBED Equation.3 1415 Это означает, что p должно быть очень малым числом). Пусть имеется n независимых испытаний с вероятностью р успеха в одном испытании и q- вероятностью неудачи. Тогда для любого фиксированного m справедливо соотношение
13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415
Пример. Машинистка печатает текст, который содержит 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. Поэтому используя предельную локальную теорему Муавра-Лапласа, получим
13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415
Таким образом, используя таблицы для плотности нормального распределения, получим P(A)=0.0108.
Интегральная теорема Муавра-Лапласа. Пусть имеется n независимых испытаний с вероятностью успеха p, 13 EMBED Equation.3 1415, в одном испытании и 13 EMBED Equation.3 1415 - вероятностью неудачи. Величина 13 EMBED Equation.3 1415не зависит от n. Тогда .для любых вещественных чисел a
P(a<13 EMBED Equation.3 1415
·(b)-
·(a).
Здесь
·(x)=13 EMBED Equation.3 1415- функция Лапласа, значения которой заданы в таблицах, приведенных в большинстве задачников по вероятности и математической статистике.
Пример. При рождении ребенка вероятность рождения мальчика равна 0.512. Найти вероятность того, что среди 1000 новорожденных мальчиков родится больше, чем девочек.
Решение. Пусть A – это событие, соответствующее вопросу задачи, m – это число рожденных мальчиков. Нетрудно видеть, что P(A) = P(m>500). Поскольку n=1000 можно считать достаточно большим, то применим интегральную теорему Муавра-Лапласа, согласно которой
P(A)=P(13 EMBED Equation.3 1415
Задачи на закрепление материала
Пример. В урне 20 белых и 10 черных шаров. Вынули 4 шара, причем каждый вынутый шар возвращают в урну перед извлечением следующего и шары в урне перемешивают. Найти вероятность того, что из четырех вынутых шаров окажется 2 белых.
Решение: Событие А – достали белый шар. Тогда вероятности 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. По формуле Бернулли требуемая вероятность13 EMBED Equation.3 1415.
Пример. Определить вероятность того, что в семье, имеющей 5 деталей, будет не больше трех девочек. Вероятности рождения мальчика и девочки предполагаются одинаковыми.
Решение: Вероятность рождения девочки 13 EMBED Equation.3 1415, тогда 13 EMBED Equation.3 1415.
Найдем вероятности того, что в семье нет девочек, родилась одна, две или три девочки:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Следовательно, искомая вероятность 13 EMBED Equation.3 1415.
Пример. Вероятность поражения цели при одном выстреле равна 0,8. Найти вероятность того, что при 100 выстрелах цель будет поражена 70 раз.
Решение: Из условия следует, что 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, поэтому 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415. Поскольку 13 EMBED Equation.3 1415, то можно воспользоваться формулой.
13 EMBED Equation.3 1415.
По таблице приложения 1 находим 13 EMBED Equation.3 1415. Поэтому 13 EMBED Equation.3 1415.
Пример. Вероятность поражения цели при одном выстреле равна 0,8. Найти вероятность того, что при 100 выстрелах цель будет поражена от 75 до 90 раз.
Решение: Используем интегральную теорему Лапласа. В нашем случае 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
По таблице приложения 1 находим
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Поэтому 13 EMBED Equation.3 1415.
Пример. Устройство состоит из 1000 элементов, работающих независимо один от другого. Вероятность отказа любого элемента в течении времени Т равна 0,002. Найти вероятность того, что за время Т откажут ровно три элемента.
Решение N=1000, p=0,002,
·=np=2, k=3.
Искомая вероятность 13 EMBED Equation.3 1415.
Пример. Завод отправил на базу 500 изделий. Вероятность повреждения изделия в пути 0,004. Найти вероятность того, что в пути повреждено меньше трех изделий.
Решение n=500, p=0,004,
·=2.
По теореме сложения вероятностей
13 EMBED Equation.3 1415.
Пример. Магазин получил 1000 бутылок минеральной воды. Вероятность того, что при перевозке бутылка окажется разбитой, равна 0,003. Найти вероятность того, что магазин получит более двух разбитых бутылок.
Решение
·=np=1000·0,003=3
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Тема 2.2. Дискретные случайные величины (ДСВ)
Тема лекции: Случайные величины. ДСВ. Распределение ДСВ
План:
Случайные величины.
Пример построения ряда распределения ДСВ
Функция распределения ДСВ
Пример построения функции от ДСВ.
Случайные величины
Определение: Случайной величиной называется величина, которая в результате опыта примет одно и только одно возможное значение, при этом зара нее неизвестно, какое именно.
Определение: Дискретной называют случайную величину, которая принимает от дельные, изолированные значения.
Случайную величину в дальнейшем мы будем обозначать большой буквой Х, а ее возможные значения маленькой буквой х.
Например, Х- число попаданий при трех выстрелах. Возможные значения этой случайной величины: х1=0, х2=1, х3=2, х4=3. Рассмотрим случайную величину Х с возможными зна чениями х1, х2,хn . Каждое из этих значений случайная величина может принять с некоторой вероятностью:
Р(Х=х1)=р1, Р(Х=х2)=р2, Р(Х=хn)=рn.
В результате опыта случайная величина Х примет только одно из этих значений, т.е. произойдет только одно из полной группы событий: Х=х1 ,Х=х2, Х=хn.
Поскольку сумма вероятностей полной группы попарно несовмест ных событий равна 1, то 13 EMBED Equation.3 1415
Определение: Законом распределения ДСВ называется соотношение между ее возможными значениями и их вероятностями (т. е. вероятностями, с которыми случайная величина принимает эти возможные значения).
Закон распределения может быть задан формулой (формулы Бернулли, Пуассона и др.), таблицей или графиком, а также функцией распределения.
хi
х1
х2
. . .
хn
Pi
р1
р2
. . .
рn
называется законом или рядом распределения дискретной случайной величины.
Пример ДСВ – число точек на грани игрального кубика, выпадающее при его подбрасывании.
!Задание привести пример ДСВ из окружающей жизни
Закон распределения может быть задан формулой (формулы Бернулли, Пуассона и др.), таблицей или графиком, а также функцией распределения.
Пример построения ряда распределения ДСВ
Пример: Два стрелка стреляют по мишени, делая по два выстре ла каждый. Вероятность попадания в мишень при каждом выстреле для первого стрелка равна 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
Проверим тождество 13 EMBED Equation.3 1415.
0,0114+0,1104+0,З124+0,3864+0,1764 =1.
Функция распределения ДСВ
Определение: Функцией распределения случайной величины называется функция
,
определяющая вероятность того, что случайная величина примет значение, меньшее .
Свойства функции распределения:
а) функция распределения принимает значения только из отрезка [0,1]:
0
· F(x)
· 1;
б) F(x) – неубывающая функция, т.е. если x2 > x1, то F(x2) > F(x1) ;
в) F(-
· ) = 0; F(+
·) = 1;
г) вероятность того, что случайная величина примет значение из
интервала (причем ), равна:
;
Функция распределения содержит всю информацию об этой случайной величине и поэтому изучение случайной величины заключается в исследовании ее функции распределения, которую часто называют просто распределением.
У дискретной случайной величины функция распределения ступенчатая.
Пример построения функции от ДСВ
Пример: Случайная величина X задана функцией распределения
x
1
2
3
4
p(x)
0,2
0,3
Р3
0,1
Найти вероятность р3. Построить функцию распределения. Найти числовые характеристики с.в.
Решение:
Проверим тождество 13 EMBED Equation.3 1415
0,2+0,3+р3+0,1=1.
р3=0,4.
Построим функцию распределения этой случайной величины.
Имеем:
13 EMBED Equation.3 1415
Итак,
13 EMBED PBrush 1415
Контрольные вопросы:
С.в. ДСВ.
Как построить ряд распределения ДСВ.
Дайте определение функции распределения с.в.
Как построить функцию распределения ДСВ
Задачи на закрепление материала
Случайная величина X задана рядом распределения
x
4
6
8
10
12
p(x)
0,2
0,4
0,2
0,1
0,1
Построить функцию распределения
Случайная величина X задана рядом распределения
x
2
4
10
6
8
p(x)
0,1
0,4
0,1
Р4
0,1
Найти р4. Построить функцию распределения.
Пять однотипных приборов испытываются при пере грузочных режимах. Вероятность пройти испытание для каждого при бора равна 0,85. Испытания заканчиваются после выхода из строя первого же прибора. Построить ряд распределения случайной величи ны- числа произведенных испытаний.
Батарея состоит из трех орудий. Вероятности по падания в цель при одном выстреле из 1-го, 2-го, 3-го орудия рав ны соответственно 0,5; 0,6; 0,8. Каждое из орудий стреляет по некоторой цели один раз. Построить ряд распределения случайной ве личины числа попаданий в цель.
В ящике семь изделий, одно из которых бракован ное. Из ящика извлекают одно изделие за другим, пока не обнаружат брак. Составить ряд распределения случайной величины - числа вы нутых изделий.
Тема лекции: Числовые характеристики ДСВ
План:
Математическое ожидание ДСВ.
Дисперсия ДСВ.
Среднее квадратическое отклонение ДСВ.
Математическое ожидание ДСВ
Определение: Математическое ожидание ДСВ находится по формуле:
13 EMBED Equation.3 1415
Вероятностный смысл этого выражения таков: при большом числе измерений среднее значение наблюдаемых значений величины Х приближается к ее математическому ожиданию.
Механический смысл этого равенства заключается в следующем: математическое ожидание есть абсцисса центра тяжести системы материальных точек, абсцис сы которых равны возможным значениям случайной величины, а массы - их вероятностям.
Дисперсия ДСВ
Определение: Дисперсия случайной величины Х есть
13 EMBED Equation.3 1415
Дисперсию случайной величины Х иногда удобнее вычислять по формуле
13 EMBED Equation.3 1415.
Вероятностный смысл Дисперсия случайной величины Х есть характеристика рассеива ния разбросанности значений случайной величины около ее математи ческого ожидания. Дисперсия случайной величины имеет размерность квадрата случайной величины.
Среднее квадратическое отклонение
Для более наглядной характеристики рассеивания удобнее пользоваться величиной, имеющей размерность самой случайной величины. Поэтому вводится понятие среднего квадратического отклонения: 13 EMBED Equation.3 1415.
Пример: Случайная величина X задана функцией распределения
x
1
2
3
4
p(x)
0,2
0,3
Р3
0,1
Найти вероятность р3. Найти числовые характеристики с.в.
РЕШЕНИЕ:
Проверим тождество 13 EMBED Equation.3 1415
0,2+0,3+р3+0,1=1.
р3=0,4.
Найдем числовые характеристики случайной величины Х:
13 EMBED Equation.3 1415
М(Х)=1.0,2+2.0,3+3.0,4+4.0,1=0,2+0,6+1,2+0,4=2,4.
Для вычисления дисперсии применим формулу: 13 EMBED Equation.3 1415.
М(Х2 )=12. 0,2+22.0,3+32.0,4+42.0,1=0,2+1,2+3,6+1,6=6,6.
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415
Контрольные вопросы:
Дать определение дискретной случайной величины.
Что такое математическое ожидание?
Что такое дисперсия?
Что такое среднее квадратичное отклонение?
Дать определение закона распределения дискретной случайной величины.
Задачи на закрепление материала
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. Непрерывные случайные величины (НСВ)
Тема лекции: Непрерывные случайные величины (НСВ)
НСВ
Множество значений непрерывной случайной величины несчетно и обычно представляет собой некоторый промежуток конечный или бесконечный.
Пусть Х - некоторое действительное число. Вероятность события, состоящего в том, что с.в. Х примет значение, меньшее х, обозначим F(x), т.е. F(x)=Р(Х<х).
Определение: Функция F(x) называется функцией распределения с.в.Х или интегральной функцией.
Например, значение функции F(x) при х=2 равно вероятности того, что с.в. Х в результате испытания примет значение, меньшее двух, т.е. F(2)=Р(Х<2).
Определение: С. в. называется непрерывной (НСВ), если ее функция распределения F(x) является непрерывной функцией.
Свойства функции распределения:
F(x)- неубывающая функция;
13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415;
Р(а
·Х<в)= F(в)-F(а).
Определение: Функция f(x)= F(x) называется плотностью распределения вероятностей НСВ Х.
Функция f(x) существует во всех точках, где существует производная от функции распределения.
Определение: Плотность распределения называют также дифференциальной функцией распределения.
График функции плотности распределения называется кривой распределения, и площадь, ограниченная кривой распределения и осью абсцисс, равна единице. Тогда геометрически значение функции распределения F(x) в точке х0 есть площадь, ограниченная кривой распределения и осью абсцисс и лежащая левее точки х0.
Свойства плотности распределения:
f(x)
·0;
13 EMBED Equation.3 1415(характеристическое свойство)
3. Р(а<Х<в)= 13 EMBED Equation.3 1415
Зная плотность распределения f(x), можно найти функцию распределения F(x) по формуле
F(x)= 13 EMBED Equation.3 1415.
Пример: Функция плотности непрерывной случайной величины имеет вид:
13 EMBED Equation.3 1415
Определить константу C, построить функцию распределения F(x) и вычислить вероятность 13 EMBED Equation.3 1415.
Решение. Константа C находится из условия 13EMBED Equation.31415 Имеем:
13EMBED Equation.31415 откуда C=3/8.
Чтобы построить функцию распределения F(x), отметим, что интервал [0,2] делит область значений аргумента x (числовую ось) на три части: 13 EMBED Equation.3 1415 Рассмотрим каждый из этих интервалов. В первом случае (когда x<0) вероятность события {Х13 EMBED Equation.3 1415
так как плотность х на полуоси 13 EMBED Equation.3 1415равна нулю.
Во втором случае
13 EMBED Equation.3 1415
Наконец, в последнем случае, когда x>2,
13 EMBED Equation.3 1415 так как плотность 13 EMBED Equation.3 1415 обращается в нуль на полуоси 13 EMBED Equation.3 1415.
Итак, получена функция распределения
13 EMBED Equation.3 1415
Вероятность 13 EMBED Equation.3 1415 вычислим по формуле 13EMBED Equation.31415. Таким образом, 13 EMBED Equation.3 1415
Нахождение интегральной функция распределения НСВ
Пример: Дана плотность распределения случайной величины X: 13 EMBED Equation.3 1415
Требуется:
а) найти параметр A;
б) функцию распределения случайной величины X;
в) построить график функции распределения;
г) найти вероятность попадания случайной величины X в интервал 13 EMBED Equation.3 1415.
Решение:
а) Параметр A подберем так, чтобы выполнялось свойство (2) плотности распределения: 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Отсюда 13 EMBED Equation.3 1415.
б) Функцию распределения 13 EMBED Equation.3 1415 будем искать на каждом интервале отдельно.
Для значений 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415,
Для значений 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Для значений 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Таким образом, 13 EMBED Equation.3 1415
График этой функции изображен на рисунке
в) Вероятность попадания случайной величины X в интервал 13 EMBED Equation.3 1415 вычисляем по формуле 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415.
Контрольные вопросы:
Дайте определение НСВ.
Плотность и функция распределения.
Задачи на закрепление материала
Дана плотность распределения f(x) случайной величины X. Требуется:
а) найти параметр c;
б) функцию распределения случайной величины X;
в) построить графики функции распределения и плотности распределения;
г) вероятность попадания случайной величины X в интервал 13 EMBED Equation.3 1415.
1.
13 EMBED Equation.3 1415
( = 0,1; ( = 1,2.
2.
13 EMBED Equation.3 1415
( = 2,5; ( = 7,1.
3.Задан график плотности распределения с.в. Х
f(x)
а
а х
1) Записать функцию f(x).
2)Найти F (x).
3)Построить графики функций F(x).
4)Вычислить Р(а/2
Тема лекции: Числовые характеристики НСВ
Математическое ожидание с.в. Х находится по формул
М(Х)= 13 EMBED Equation.3 1415,
если сходится несобственный интеграл.
Дисперсией с.в. Х называют несобственный интеграл
Д(Х)= 13 EMBED Equation.3 1415,
если он сходится.
Для вычисления дисперсии более удобна следующая формула:
Д(Х)= 13 EMBED Equation.3 1415
Пример. Случайная величина Х задана плотностью распределения
13 EMBED Equation.3 1415
Найти математическое ожидание, дисперсию и среднеквадратичное отклонение с.в. Х.
Воспользуемся определениями.
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415.
Пример: Плотность распределения с.в. задана функцией
13 EMBED Equation.3 1415
1) Найти а, F(x), М(Х), Д(Х).
2) Вычислить Р(-2
Решение: Для нахождения параметра а воспользуемся свойством плотности распределения вероятностей: 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 Отсюда находим а=13 EMBED Equation.3 1415.
Тогда функцию плотности распределения можно записать следующим образом:
13 EMBED Equation.3 1415
Найдем функцию распределения вероятностей F(x):
Для х<-1 F(x)=13 EMBED Equation.3 1415
Для -1
·х<0 F(x)=13 EMBED Equation.3 1415
Для 0
·х<1 13 EMBED Equation.3 1415
Для х
·1
13 EMBED Equation.3 1415
Следовательно, функция распределения имеет вид:
13 EMBED Equation.3 1415
Вычислим числовые характеристики с.в. Х .
Математическое ожидание
13 EMBED Equation.3 1415
Дисперсия
13 EMBED Equation.3 1415
2) Вычислим Р(-2Вычислить эту вероятность можно двумя способами: с помощью функции плотности или с помощью функции распределения вероятностей.
13 EMBED Equation.3 1415
или
Р(-2
Задачи на закрепление материала
Дана плотность распределения f(x) случайной величины X. Требуется:
а) найти параметр c;
б) функцию распределения случайной величины X;
в) найти числовые характеристики случайной величины X;
г) вероятность попадания случайной величины X в интервал 13 EMBED Equation.3 1415.
10.
13 EMBED Equation.3 1415
( = 3,2; ( = 6,4.
20.
13 EMBED Equation.3 1415
( = 1; ( = 2.
Тема лекции: Основные распределения непрерывных случайных величин
Равномерное распределение
Равномерным называют распределение вероятностей непрерывной случайной величины X, если на отрезке 13 EMBED Equation.3 1415, которому принадлежат все возможные значения X, плотность распределения сохраняет постоянное значение, а именно:
13 EMBED Equation.3 1415,
вне этого отрезка 13 EMBED Equation.3 1415.
Математическое ожидание и дисперсия равномерно распределенной случайной величины определяются выражениями:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Показательное распределение
Непрерывная случайная величина X имеет показательное (или экспоненциальное) распределение, если ее плотность распределения имеет вид:
13 EMBED Equation.3 1415
где 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Числовые характеристики этого распределения определяются равенствами:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Нормальное распределение
Непрерывная случайная величина X имеет нормальное распределение (или распределение Гаусса), если ее плотность распределения имеет вид:
13 EMBED Equation.3 1415.
Постоянные a и ( (( > 0) называются параметрами нормального распределения и представляют собой соответственно математическое ожидание и среднеквадратическое отклонение случайной величины X, т. е.
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Отсюда 13 EMBED Equation.3 1415.
График функции 13 EMBED Equation.3 1415 называют нормальной кривой (или кривой Гаусса). Кривая имеет форму «колокола», симметричного относительно прямой 13 EMBED Equation.3 1415 (рис. 1).
Функция распределения нормальной случайной величины
13 EMBED Equation.3 1415
связана с функцией Лапласа соотношением
13 EMBED Equation.3 1415.
где 13 EMBED Equation.3 1415 - функция Лапласа, таблицу значений которой можно найти в приложениях.
Замечание: Ф(х) - функция нечетная, т.е. Ф(-х)=-Ф(х).
Поэтому для нормальной случайной величины справедлива формула
13 EMBED Equation.3 1415.
Вероятность того, что абсолютная величина отклонения нормальной случайной величины меньше положительного числа (, равна:
13 EMBED Equation.3 1415.
В частности,
13 EMBED Equation.3 1415.
Отсюда следует «правило трех сигм»: если случайная величина X имеет нормальное распределение, то отклонение этой случайной величины от ее математического ожидания по абсолютной величине не превышает утроенное среднее квадратическое отклонение (3().
Нормальный закон – наиболее часто встречающийся закон распределения, он является предельным законом, к которому, при определенных условиях, приближаются другие законы распределения.
Пример. Нормально распределенная случайная величина X задана плотностью вероятности 13 EMBED Equation.3 1415. Требуется найти:
а) математическое ожидание и дисперсию X;
б) вероятность того, что X примет значение, принадлежащее интервалу 13 EMBED Equation.3 1415;
в) вероятность того, что абсолютная величина отклонения X от математического ожидания окажется меньше 5.
Решение.
а) Сравнив данную функцию с плотностью нормального распределения, заключаем, что 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. Следовательно, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
б) Воспользуемся формулой 13 EMBED Equation.3 1415.
В нашем случае 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, ( = 3; ( = 10.
13 EMBED Equation.3 1415Значения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 определили по таблице значений функции Лапласа.
в) Воспользуемся формулой 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, ( = 5.
13 EMBED Equation.3 1415.
Пример: Ошибка измерительного прибора - случайная величи на, распределенная по нормальному закону, со средним квадратическим отклонением 3 мк. Систематическая ошибка прибора отсутствует. Какова вероятность того, что в независимом измерении ошибка окажется в интервале (0 ; 2,4)?
Решение: Вычислим вероятность того, что в результате измерения случайная, величина Х - ошибка измерительного прибора будет принадлежать интервалу (0 ; 2,4):
13 EMBED Equation.3 1415
Здесь математическое ожидание a=0 (так как систематическая ошибка отсутствует, то среднее значение ошибки при большом числе измерений будит равно нулю).
Ф(0)=0, Ф(0,8)=0,2881 находим по таблице Лапласа.
Теперь найдем вероятность события 13 EMBED Equation.3 1415, состоящего в том, что в результате трех измерений
Пример: Случайная величина Х распределена нормально с математическим ожиданием, равным 10. Вероятность того, что слу чайная величина Х примет значение, принадлежащее интервалу (4 ; 16), равна 0,8664. Найти среднее квадратическое отклонение этой случайной величины.
Решение: По условию задачи случайная величина Х имеет мате матическое ожидание а=10 и 13 EMBED Equation.3 1415
Но, с другой стороны,
13 EMBED Equation.3 1415
где
· - среднее квадратическое отклонение случайной величи ны Х.
Итак, 2Ф(13 EMBED Equation.3 1415)=0,8664 или Ф(13 EMBED Equation.3 1415)=0,4332.
По таблице значений функции Лапласа находим 13 EMBED Equation.3 1415=1,5. Отку да
·=4.
Задачи на закрепление материала
Нормально распределенная случайная величина X задана плотностью вероятности f(x). Требуется найти:
а) математическое ожидание и дисперсию X;
б) вероятность того, что X примет значение, принадлежащее интервалу 13 EMBED Equation.3 1415;
в) вероятность того, что абсолютная величина отклонения 13 EMBED Equation.3 1415 окажется меньше (.
1.
13 EMBED Equation.3 1415,
( = 11; ( = 21; ( = 6.
3.
13 EMBED Equation.3 1415,
( = 6; ( = 15; ( = 8.
2.
13 EMBED Equation.3 1415,
( = 9; ( = 19; ( = 4.
4.
13 EMBED Equation.3 1415,
( = 2; ( = 15; ( = 3.
Практические занятия
Практическое занятие №2 «Применение стандартных методов и моделей к решению вероятностных задач. Вычисление вероятностей событий по классической формуле определения вероятности»
Практическое занятие №3 «Вычисление вероятностей событий, используя теоремы сложения, умножения вероятностей»
Практическое занятие №4 «Применение стандартных методов и моделей к решению вероятностных задач. Вычисление вероятностей сложных событий»
Практическое занятие №5 «Решение задач на запись ДСВ»
Практическое занятие №6 «Вычисление числовых характеристик ДСВ»
Практическое занятие №7 «Нахождение интегральной функция распределения НСВ»
Практическое занятие №8 «Вычисление характеристик НСВ с помощью функции плотности»
Практическое занятие №9 «Вычисление вероятностей для нормального распределения»
Раздел 3. Основы математической статистики
Тема 3.1. Выборочный метод. Статистические оценки параметров распределения
Тема лекции: Математическая статистика
План:
Основные понятия математической статистики
Графическое изображение выборки
Точечные оценки параметров распределения
Основные понятия математической статистики
На практике функция распределения случайной величины бывает неизвестна и ее определяют по результатам наблюдений или, как говорят, по выборке. Выборкой объема n для случайной величины называется последовательность независимых наблюдений этой величины, где 13 EMBED Equation.3 1415 – совокупность значений, принятых независимыми случайными величинами 13 EMBED Equation.3 1415, имеющими тот же закон распределения 13 EMBED Equation.3 1415, что и величина X. В этом случае говорят, что выборка 13 EMBED Equation.3 1415 взята из генеральной совокупности величины X, а под законом распределения генеральной совокупности понимают закон распределения случайной величины X. Значения 13 EMBED Equation.3 1415 называют выборочными значениями или вариантами. Последовательность вариант, записанных в возрастающем порядке, называется вариационным рядом. Число, указывающее, сколько раз наблюдается данная варианта, называется частотой варианты, а отношение частоты варианты к объему выборки – относительной частотой.
Если 13 EMBED Equation.3 1415 – вариационный ряд, а x произвольное число, и nx – количество выборочных значений, меньших x, то 13 EMBED Equation.3 1415 – частота попадания выборочных значений левее точки x в данной выбоке объема n, т. е. частота события 13 EMBED Equation.3 1415.
Эта частота является функцией от x и называется эмпирической функцией распределения случайной величины X, полученной по данной выборке. Если обозначить эту функцию через 13 EMBED Equation.3 1415, то по определению
13 EMBED Equation.3 1415.
Эмпирическая функция распределения 13 EMBED Equation.3 1415 обладает всеми свойствами функции распределения 13 EMBED Equation.3 1415. Так как частота события в n независимых опытах является оценкой вероятности этого события, то значение эмпирической функции распределения в точке x есть оценка вероятности события 13 EMBED Equation.3 1415, то есть оценка теоретической функции распределения 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415.
Статистическим рядом распределения называется таблица, которая содержит вариационный ряд и соответствующие частоты или относительные частоты членов этого ряда (табл. 1).
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Таблица 1 Таблица 2
x1
x2
...
xk
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
...
13 EMBED Equation.3 1415
n1
n2
...
nk
n1
n2
...
nk
w1
w2
...
wk
w1
w2
...
wk
В случае непрерывного распределения величины X статистический ряд распределения представляет собой таблицу, в которой заданы интервалы значений величины X и соответствующие им частоты или относительные частоты, причем интервалы располагаются в порядке возрастания величины X (табл. 2).
Второй случай легко сводится к первому, если в качестве вариант брать середины интервалов:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Графическое изображение выборки
Графически табл. 1 изображается полигоном частот, представляющим собой ломаную, отрезки которой соединяют на плоскости соседние точки 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, если строится полигон относительных частот.
В случае табл. 2 исходный интервал, в котором заключены все наблюдаемые значения признака, разбивают на определенное количество равных интервалов длины 13 EMBED Equation.3 1415. После этого строится гистограмма частот – ступенчатая фигура, состоящая из прямоугольников, основания которых равны h, а высоты равны отношению 13 EMBED Equation.3 1415 (или 13 EMBED Equation.3 1415 для гистограммы относительных частот).
Гистограмма относительных частот является аналогом функции плотности, так как площадь под ней равна единице. Число интервалов разбиения находят по формуле 13 EMBED Equation.3 1415, где n – объем выборки. Тогда длина каждого интервала 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415– максимальное и минимальное значение выборки соответственно.
Точечные оценки параметров распределения
По аналогии с такими числовыми характеристиками случайной величины, как математическое ожидание, дисперсия и среднее квадратическое отклонение, для выборки 13 EMBED Equation.3 1415 случайной величины X и для статистического ряда определяются следующие числовые характеристики:
выборочная средняя 13 EMBED Equation.3 1415,
где k – число вариант и 13 EMBED Equation.3 1415;
выборочная дисперсия 13 EMBED Equation.3 1415
или 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415;
выборочное среднее квадратическое отклонение 13 EMBED Equation.3 1415
Во многих случаях бывает заранее известно, что функция распределения 13 EMBED Equation.3 1415принадлежит к определенному классу функций распределения, зависящих от одного или нескольких параметров: 13 EMBED Equation.3 1415. В этом случае определение неизвестной функции распределения сводится к оценке неизвестных параметров по результатам выборки. Следует заметить, что ни при каких n нельзя определить по выборке точное значение неизвестного параметра, а можно найти его приближенное значение, которое называется оценкой по выборке неизвестного параметра. Всякая оценка по выборке является функцией 13 EMBED Equation.3 1415 от выборочных значений 13 EMBED Equation.3 1415, так как она меняется от выборки к выборке. Функцию 13 EMBED Equation.3 1415 подбирают так, чтобы случайная величина 13 EMBED Equation.3 1415по возможности более точно аппроксимировала неслучайное неизвестное число a.
Для выполнения данного условия накладывают следующие требования на оценку: несмещенность оценки, ее эффективность и состоятельность. Наиболее часто применяемыми метода получения оценок являются метод моментов и метод максимального правдоподобия.
Несмещенной и состоятельной оценкой математического ожидания 13 EMBED Equation.3 1415 является выборочная средняя 13 EMBED Equation.3 1415.
Несмещенная и состоятельная оценка 13 EMBED Equation.3 1415 дисперсии 13 EMBED Equation.3 1415 вычисляется по формуле:
13 EMBED Equation.3 1415.
где 13 EMBED Equation.3 1415 – исправленная дисперсия.
Для оценки среднего квадратического отклонения ( используется величина S, равная квадратному корню из исправленной дисперсии, которая называется исправленным средним квадратическим отклонением.
Рассмотренные оценки характеризуются одним числом и называются точечными.
Пример 1. По заданному статистическому ряду (табл. 1) требуется:
а) построить гистограмму относительных частот;
б) перейти к вариантам и построить полигон относительных частот;
в) построить эмпирическую функцию распределения.
Таблица 1
13 EMBED Equation.3 1415
12 –15
15 – 18
18 – 21
21 – 24
24 – 27
27 – 30
13 EMBED Equation.3 1415
2
6
12
19
7
4
Решение
а) Объем выборки 13 EMBED Equation.3 1415.
Определяем относительные частоты 13 EMBED Equation.3 1415 и составляем табл. 2 с относительными частотами:
Таблица 2
13 EMBED Equation.3 1415
12 –15
15 – 18
18 – 21
21 – 24
24 – 27
27 – 30
13 EMBED Equation.3 1415
0,04
0,12
0,24
0,38
0,14
0,08
Для построения гистограммы относительных частот на оси абсцисс откладываются частичные интервалы длины 13 EMBED Equation.3 1415, а над ними проводятся горизонтальные отрезки на расстоянии 13 EMBED Equation.3 1415 (рис. 1).
13 SHAPE \* MERGEFORMAT 1415
б) Перейдем к вариантам, положив их равными серединам частичных интервалов 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415– концы интервалов. Тогда табл. 2 превратится в табл. 3:
Таблица 3
13 EMBED Equation.3 1415
13,5
16,5
19,5
22,5
25,5
28,5
13 EMBED Equation.3 1415
0,04
0,12
0,24
0,38
0,14
0,08
Отметим на плоскости точки 13 EMBED Equation.3 1415 и, соединив соседние точки, получим полигон относительных частот (рис. 2).
13 SHAPE \* MERGEFORMAT 1415
в) Эмпирическая функция распределения 13 EMBED Equation.3 1415 строится по закону:
13 EMBED Equation.3 1415
В нашем случае получаем:
13 EMBED Equation.3 1415
График функции 13 EMBED Equation.3 1415 представлен на рис. 3.
Пример 2. В условиях примера 1 найти статистические оценки.
Решение Обратимся к табл. 3: 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415;13 EMBED Equation.3 1415.
Контрольные вопросы:
Что такое выборка?
Что такое варианта выборки и частота?
Как графически изображается выборка?
Точечные оценки выборки.
Задачи на закрепление материала
Статистический ряд задан таблицей. Требуется:
а) построить гистограмму относительных частот;
б) перейти к вариантам и построить полигон относительных частот;
в) записать эмпирическую функцию распределения и построить ее график;
г) найти точечные оценки 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415;
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
Тема лекции: Интервальные оценки параметров распределения
План:
Интервальная оценка математического ожидания нормального распределения.
Интервальная оценка среднего квадратического отклонения нормального распределения.
Интервальная оценка вероятности события
Определение: Интервальной называют оценку, которая определяется двумя числами – концами интервала.
Так как любая оценка 13 EMBED Equation.3 1415 есть некоторое приближение оцениваемой величины a, то возникает вопрос об оценке точности данного приближения, т. е. можно ли утверждать, что 13 EMBED Equation.3 1415 для некоторого 13 EMBED Equation.3 1415.
Однако статистические методы не позволяют категорически утверждать, что оценка 13 EMBED Equation.3 1415 удовлетворяет неравенству 13 EMBED Equation.3 1415. Можно лишь говорить о вероятности ( наступления события, заключающегося в том, что мы получили оценку с точностью (: 13 EMBED Equation.3 1415. Эта вероятность называется доверительной вероятностью (или надежностью), а интервал 13 EMBED Equation.3 1415 – доверительным интервалом. Вероятность того, что интервал 13 EMBED Equation.3 1415 заключает в себе неизвестный параметр a, равна (. Обычно надежность выбирают близкой к единице (0,95; 0,99; 0,999).
Интервальная оценка математического ожидания нормального распределения
Если случайная величина распределена нормально и среднее квадратическое отклонение ( известно, то доверительный интервал для оценки математического ожидания a
13 EMBED Equation.3 1415, (1)
где n – объем выборки, t находится из равенства 13 EMBED Equation.3 1415 по таблице значений функции Лапласа 13 EMBED Equation.3 1415.
Если ( неизвестно, то в формуле (1) оно заменяется на исправленное среднее квадратическое отклонение S, t заменяется на 13 EMBED Equation.3 1415, которое находится по таблице (приложение )
13 EMBED Equation.3 1415. (2)
Интервальная оценка среднего квадратического отклонения нормального распределения
Доверительный интервал для оценки среднего квадратического отклонения ( нормального распределения с заданной надежностью ( находится по формуле
13 EMBED Equation.3 1415, (3)
где 13 EMBED Equation.3 1415 находится по таблице (приложение ).
Пример 1. Дано распределение частот выборки (табл. 1). Найти доверительные интервалы для математического ожидания a и среднего квадратического отклонения ( с доверительной вероятностью ( = 0,95, если известно, что генеральная совокупность распределена по нормальному закону
Таблица 1
13 EMBED Equation.3 1415
12 –15
15 – 18
18 – 21
21 – 24
24 – 27
27 – 30
13 EMBED Equation.3 1415
2
6
12
19
7
4
Решение
Имеем: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. Так как объем выборки 13 EMBED Equation.3 1415, то находим
13 EMBED Equation.3 1415.
По таблице приложения находим
13 EMBED Equation.3 1415.
Подставляя полученные значения S и t( в формулу (2), получим
13 EMBED Equation.3 1415
или
13 EMBED Equation.3 1415.
По таблице приложения найдем 13 EMBED Equation.3 1415.
Подставляя значения S и q в формулу (3), получим
13 EMBED Equation.3 1415
или
13 EMBED Equation.3 1415.
3.Интервальная оценка вероятности события
Интервальной оценкой (с надежностью 13 EMBED Equation.3 1415) неизвестной вероятности р биномиального распределения по относительной частоте 13 EMBED Equation.3 1415 служит доверительный интервал (с приближенными концами р1 и р2) 13 EMBED Equation.3 1415,
где 13 EMBED Equation.3 1415
n- общее число испытаний;
m- число появления события;
13 EMBED Equation.3 1415 - относительная частота, равная отношению m/n;
t- значение аргумента функции Лапласа, при котором 13 EMBED Equation.3 1415. (13 EMBED Equation.3 1415 - заданная надежность).
Замечание: При больших значениях n (порядка сотен) можно принять в качестве приближенных границ доверительного интервала
13 EMBED Equation.3 1415
Пример: Производятся независимые испытания с одинаковой, но неизвестной вероятностью р появления события А в каждом испытании. Найти доверительный интервал для оценки вероятности р с надежностью 0,95, если в 60 испытаниях событие А появилось 15 раз.
Решение: По условию, n=60, m=15, 13 EMBED Equation.3 1415=0.95. Найдем относительную частоту появления события А: 13 EMBED Equation.3 1415.
Найдем t из соотношения 13 EMBED Equation.3 1415. По таблице функции Лапласа находим t=1,96.
Найдем границы искомого доверительного интервала:
13 EMBED Equation.3 1415
Подставив в эти формулы n=60, 13 EMBED Equation.3 1415, t=1,96, получим р1=0,16, р2=0,37.
Итак, искомый доверительный интервал 13 EMBED Equation.3 1415.
Пример: Изготовлен экспериментальный игровой автомат, который должен обеспечить появление выигрыша в одном случае из 100 бросаний монеты в автомат. Для проверки пригодности автомата произведено 400 испытаний, причем выигрыш появился 5 раз. Найти доверительный интервал, покрывающий неизвестную вероятность появления выигрыша с надежностью 13 EMBED Equation.3 1415=0.999.
Решение: Найдем относительную частоту появления выигрыша 13 EMBED Equation.3 1415.
Найдем t из соотношения 13 EMBED Equation.3 1415. По таблице функции Лапласа находим t=3,3.
Учитывая, что n=400 велико, используем для отыскания границ доверительного интервала приближенные формулы: 13 EMBED Equation.3 1415
Подставив в эти формулы n=400, 13 EMBED Equation.3 1415, t=3,3,
получим р1= -0,0058, р2= 0,0308.
Итак, искомый доверительный интервал 13 EMBED Equation.3 1415.
Задачи на закрепление материала
Считая генеральную совокупность нормальной, найти интервальные оценки для ( и 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. Моделирование случайных величин
Тема лекции: Моделирование случайных величин. ДСВ. НСВ
План:
Разыгрывание ДСВ.
Разыгрывание полной группы событий.
Разыгрывание НСВ.
Моделирование (разыгрывание) с.в. проводится методом Монте-Карло.
Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. С этой целью выбирают с.в.Х, математическое ожидание которой равно а: М(Х)=а.
Практически же поступают так: вычисляют (разыгрывают) n возможных значений xi с.в.Х, находят их среднее арифметическое 13 EMBED Equation.3 1415 и принимают 13 EMBED Equation.3 1415 в качестве оценки (приближенного значения) 13 EMBED Equation.3 1415 искомого числа а: 13 EMBED Equation.3 1415.
1.Разыгрывание ДСВ
ПРАВИЛО: Для того, чтобы разыграть ДСВ Х, заданную законом распределения
Х
х1
х2
хn
р
р1
р2
рn
надо:
Разбить интервал (0,1) оси Or на n частичных интервалов: 13 EMBED Equation.3 1415
Выбрать (например, из таблицы случайных чисел) случайное число rj.
Если rj попало в частичный интервал 13 EMBED Equation.3 1415, то разыгрываемая величина приняла возможное значение xi.
ПРИМЕР: Разыграть шесть возможных значений ДСВ Х, закон распределения которой задан в виде таблицы:
Х
2
10
18
р
0,22
0,17
0,61
Решение:
Разобьем интервал (0,1) оси Or точками с координатами 0,22: 0,22+0,17=0,39 на три частичных интервала: 13 EMBED Equation.3 1415
Выпишем из таблицы случайных чисел (приложение) шесть случайных чисел, например 0,32; 0,17; 0,90; 0,05; 0,97; 0,87 (пятая строка снизу).
Случайное число r1=0.32 принадлежит частичному интервалу 13 EMBED Equation.3 1415, поэтому разыгрываемая ДСВ приняла возможное значение х2=10; случайное число r2=0.17 принадлежит частичному интервалу 13 EMBED Equation.3 1415, поэтому разыгрываемая ДСВ приняла возможное значение х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) на три частичных интервала: 13 EMBED Equation.3 1415
Выпишем из таблицы случайных чисел (приложение) пять случайных чисел, например 0,61; 0,19; 0,69; 0,04; 0,46.
Случайное число r1=0.61 принадлежит частичному интервалу 13 EMBED Equation.3 1415, Х=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 уравнение
13 EMBED Equation.3 1415, или уравнение 13 EMBED Equation.3 1415,
где а – наименьшее конечное возможное значение Х.
ПРИМЕР: Найти явную формулу для разыгрывания равномерно распределенной с.в. Х, заданной плотностью вероятности f(x)=b/(1+ax)2 в интервале (0;1/(b-a)); вне этого интервала f(x)=0.
Решение:
Используем правило 2, напишем уравнение 13 EMBED Equation.3 1415.
Решив это уравнение относительно xi , окончательно получим 13 EMBED Equation.3 1415.
Контрольные вопросы:
Разыгрывание ДСВ. Правило.
Разыгрывание полной группы событий. Правило.
Разыгрывание НСВ. Правило.
Задачи на закрепление материала
Разыграть шесть возможных значений ДСВ Х, закон распределения которой задан в виде таблицы:
Х
3
5
8
р
0,2
0,3
0,5
Заданы вероятности трех событий: А1, А2, А3, образующих полную группу: р1=Р(А1)=0,14, р2=Р(А2)=0,26, р3=Р(А3)=0,6. Разыграть пять испытаний, в каждом из которых появляется одно из трех рассматриваемых событий.
Разыграть четыре возможных значения НСВ Х, распределенной равномерно в интервале(6;16).
Найти явную формулу для разыгрывания равномерно распределенной с.в. Х, заданной плотностью вероятности f(x)=5 в интервале (0;0,2); вне этого интервала f(x)=0.
Тема 3.3. Современные пакеты прикладных программ многомерного статистического анализа
Тема лекции: Применение современные пакеты прикладных программ многомерного статистического анализа
1. Основные статистические характеристики.
Электронные таблицы Excel имеют огромный набор средств для анализа статистических данных. Наиболее часто используемые статистические функции встроены в основное ядро программы, то есть эти функции доступны с момента запуска программы. Другие более специализированные функции входят в дополнительную подпрограмму, называемую пакетом анализа. Команды и функции пакета анализа называют Инструментами анализа. Мы ограничимся изучением нескольких основных встроенных статистических функций и наиболее полезных инструментов анализа из пакета.
Среднее значение.
Функция СРЗНАЧ (или AVERAGE) вычисляет выборочное (или генеральное) среднее, то есть среднее арифметическое значение признака выборочной (или генеральной) совокупности. Аргументом функции СРЗНАЧ является набор чисел, как правило, задаваемый в виде интервала ячеек, например, =СРЗНАЧ (А3:А201).
Дисперсия и среднее квадратическое отклонение.
Для оценки разброса данных используются такие статистические характеристики, как дисперсия D и среднее квадратическое (или стандартное) отклонение 13EMBED Equation.31415. Стандартное отклонение есть квадратный корень из дисперсии: 13EMBED Equation.31415. Большое стандартное отклонение указывает на то, что значения измерения сильно разбросаны относительно среднего, а малое – на то, что значения сосредоточены около среднего.
В Excel имеются функции, отдельно вычисляющие выборочную дисперсию Dв и стандартное отклонение 13EMBED Equation.31415в и генеральные дисперсию Dг и стандартное отклонение 13EMBED Equation.31415г. Поэтому, прежде чем вычислять дисперсию и стандартное отклонение, следует четко определиться, являются ли ваши данные генеральной совокупностью или выборочной. В зависимости от этого нужно использовать для расчета Dг и 13EMBED Equation.31415г , Dв и 13EMBED Equation.31415в.
Для вычисления выборочной дисперсии Dв и выборочного стандартного отклонения 13EMBED Equation.31415в имеются функции ДИСП (или VAR) и СТАНДОТКЛОН (или STDEV). Аргументом этих функций является набор чисел, как правило, заданный диапазоном ячеек, например, =ДИСП (В1:В48).
Для вычисления генеральной дисперсии Dг и генерального стандартного отклонения 13EMBED Equation.31415г имеются функции ДИСПР (или VARP) и СТАНДОТКЛОНП (или STDEVP), соответственно.
Аргументы этих функций такие же как и для выборочной дисперсии.
Объем совокупности.
Объем совокупности выборочной или генеральной – это число элементов совокупности. Функция СЧЕТ (или COUNT) определяет количество ячеек в заданном диапазоне, которые содержат числовые данные. Пустые ячейки или ячейки, содержащие текст, функция СЧЕТ пропускает. Аргументом функции СЧЕТ является интервал ячеек, например: =СЧЕТ (С2:С16).
Для определения количества непустых ячеек, независимо от их содержимого, используется функция СЧЕТ3. Ее аргументом является интервал ячеек.
Мода и медиана.
Мода – это значение признака, которое чаще других встречается в совокупности данных. Она вычисляется функцией МОДА (или MODE). Ее аргументом является интервал ячеек с данными.
Медиана – это значение признака, которое разделяет совокупность на две равные по числу элементов части. Она вычисляется функцией МЕДИАНА (или MEDIAN). Ее аргументом является интервал ячеек.
Размах варьирования. Наибольшее и наименьшее значения.
Размах варьирования R – это разность между наибольшим xmax и наименьшим xmin значениями признака совокупности (генеральной или выборочной): R=xmax–xmin. Для нахождения наибольшего значения xmax имеется функция МАКС (или MAX), а для наименьшего xmin – функция МИН (или MIN). Их аргументом является интервал ячеек. Для того, чтобы вычислить размах варьирования данных в интервале ячеек, например, от А1 до А100, следует ввести формулу: =МАКС (А1:А100)-МИН (А1:А100).
Отклонение случайного распределения от нормального.
Нормально распределенные случайные величины широко распространены на практике, например, результаты измерения любой физической величины подчиняются нормальному закону распределения. Нормальным называется распределение вероятностей непрерывной случайной величины, которое описывается плотностью 13EMBED Equation.31415
13EMBED Equation.31415,
где 13EMBED Equation.31415 дисперсия, 13EMBED Equation.31415 - среднее значение случайной величины 13EMBED Equation.31415.
Для оценки отклонения распределения данных эксперимента от нормального распределения используются такие характеристики как асимметрия А и эксцесс Е. Для нормального распределения А=0 и Е=0.
Асимметрия показывает, на сколько распределение данных несимметрично относительно нормального распределения: если А>0, то большая часть данных имеет значения, превышающие среднее 13EMBED Equation.31415; если А<0, то большая часть данных имеет значения, меньшие среднего 13EMBED Equation.31415. Асимметрия вычисляется функцией СКОС. Ее аргументом является интервал ячеек с данными, например, =СКОС (А1:А100).
Эксцесс оценивает «крутость», т.е. величину большего или меньшего подъема максимума распределения экспериментальных данных по сравнению с максимумом нормального распределения. Если Е>0, то максимум экспериментального распределения выше нормального; если Е<0, то максимум экспериментального распределения ниже нормального. Эксцесс вычисляется функцией ЭКСЦЕСС, аргументом которой являются числовые данные, заданные, как правило, в виде интервала ячеек, например: =ЭКСЦЕСС (А1:А100).13EMBED Equation.31415
Задачи на закрепление материала
Задание 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 – «выборочная дисперсия», в В3 – «стандартное отклонение», в В4 – «Максимум», в В5 – «Минимум», в В6 – « Размах варьирования», в В7 – «Мода», в В8 – «Медиана», в В9 – «Асимметрия», в В10 – «Эксцесс». Выровняйте ширину этого столбца с помощью Автоподбора ширины.
Выделите ячейку С1 и нажмите на знак «=» в строке формул. С помощью Мастера функций в категории Статистические найдите функцию СРЗНАЧ, затем выделите интервал ячеек с данными и нажмите Enter.
Выделите ячейку С2 и нажмите на знак «=» в строке формул. С помощью помощью Мастера функций в категории Статистические найдите функцию ДИСП, затем выделите интервал ячеек с данными и нажмите Enter.
Проделайте самостоятельно аналогичные действия для вычисления стандартного отклонения, максимума, минимума, моды, медианы, асимметрии и эксцесса.
Для вычисления размаха варьирования в ячейку С6 следует ввести формулу: =МАКС (А1:А25)-МИН(А1:А25).
2. Инструменты статистического анализа: Генерация случайных чисел, Гистограмма, Описательная статистика.
Загрузка Пакета анализа.
Пакет анализа без дополнительных установок автоматически не загружается при запуске Excel. Он входит в так называемую Надстройку – набор дополнительных подпрограмм, к которым относятся, например, уже известные вам Мастер диаграмм и Мастер функций. Для загрузки Пакет анализа необходимо:
в Основном меню выбрать пункт Сервис;
выбрать пункт Надстройки;
в появившемся списке Надстроек активизировать переключатель AnalysisToolPak-VBA и нажать ОК.
После этого в меню Сервис добавится пункт Анализ данных. К этому пункту следует обращаться для вызова Пакета анализа.
Инструмент: Генерация случайных чисел.
В Excel имеется встроенная функция СЛЧИСЛ (или RAND) для генерации равномерно распределенных случайных чисел в интервале [0,1].
Пакет анализа позволяет генерировать случайные числа с различными типами распределений: равномерное, нормальное, Бернулли, биномиальное, Пуассона и дискретное (определенное пользователем). Для генерации случайных чисел следует:
в меню Сервис выбрать команду Анализ данных;
в появившемся диалоговом окне Анализ данных в группе Инструменты анализа выбрать пункт Генерация случайных величин и нажать ОК;
в появившемся диалоговом окне Генерация случайных чисел следует заполнить поля ввода:
в полях Число переменных и Число случайных чисел указать нужное количество столбцов и сколько чисел вы хотите получить в каждом столбце;
в поле Распределение следует выбрать один из имеющихся типов распределения случайных чисел;
в группе Параметры следует указать диапазон чисел, т.е. min и max числа распределения для Равномерного распределения; или среднее значение и стандартное отклонение для Нормального распределения и т.д.
поле Случайное рассеивание заполняется только в том случае, если вам необходимо несколько раз воспроизводить одну и туже последовательность случайных чисел;
в поле Выходной интервал указывается место, куда следует поместить последовательность чисел, как правило, это интервал ячеек (или столбец целиком).
Инструмент: Гистограмма.
Графическое представление результатов обработки статистических данных обычно оформляется в виде гистограммы. Совокупность данных разбивается на частичные интервалы, называемые нормальными. Интервалы разбиения могут быть любой ширины, но обязательно они должны следовать в порядке возрастания. Интервалы разбиения откладываются по оси абсцисс гистограммы. На оси ординат гистограммы откладывается число значений, попавших в интервал разбиения. Это число значений признака совокупности называется частотой. Для построения гистограммы:
в начале следует задать частичные интервалы разбиения;
затем в меню Сервис выбрать команду Анализ данных и указать инструмент анализа –Гистограмма и нажать ОК;
в диалоговом окне Гистограмма следует указать:
в группе Входные данные в поле Входной интервал – интервал ячеек с данными, а в поле Интервал карманов – интервал ячеек с частичными интервалами разбиения;
в группе Параметры вывода указывается интервал ячеек для вывода частот и отмечается галочкой переключатель Вывод графика.
После нажатия ОК инструмент Гистограмма выводит два столбца: карман и частота. Сама гистограмма выводится правее столбца частот. Форматирование гистограммы производится так же, как и любой диаграммы в Excel (см. лабораторную работу №6).
Инструмент: Описательная статистика.
В пакете анализа Excel содержится инструмент Описательная статистика, который создает таблицу основных статистических характеристик для совокупности данных. В этой таблице будут содержаться следующие характеристики: среднее, стандартная ошибка, дисперсия, стандартное отклонение, мода, медиана, размах варьирования интервала, максимальное и минимальное значения, асимметрия, эксцесс, объем совокупности, сумму всех элементов совокупности, доверительный интервал (уровень надежности). Инструмент Описательная статистика существенно упрощает статистический анализ тем, что нет необходимости вызывать каждую функцию для расчета статистических характеристик отдельно.
Для того, чтобы вызвать Описательную статистику, следует:
в меню Сервис выбрать команду Анализ данных;
в списке Инструменты анализа диалогового окна Анализ данных выбрать инструмент
Описательная статистика и нажать ОК;
в появившемся диалоговом окне Описательная статистика необходимо:
в группе Входные данные в поле Входной интервал указать интервал ячеек, содержащих данные;
если первая строка во входном диапазоне содержит заголовок столбца, то в поле Метки в первой строке следует поставить галочку;
активизировать переключатель (поставить галочку) Итоговая статистика, если нужен полный список характеристик;
активизировать переключатель Уровень надежности и указать надежность в %, если необходимо вычислить доверительный интервал.
Задание 2.
Сгенерировать 500 случайных чисел, распределенных нормально. Построить гистограмму и полный список статистических характеристик с помощью инструмента Описательная статистика.
1. Выполните команду Сервис(Анализ данных(Генерация случайных чисел;
2..В диалоговом окне Генерация случайных чисел введите в поле число переменных: 1; в поле Число случайных чисел 500; выберите Распределение Нормальное; задайте любое среднее значение (желательно около 100) и небольшое стандартное отклонение (не больше 10); в поле Выходной интервал укажите абсолютный адрес столбца $A$2. Нажмите ОК.
Теперь постройте гистограмму по совокупности случайных чисел. Сначала нужно задать интервалы решения. Пусть длины интервалов будут одинаковыми и равны 3. Для автоматического составления интервалов разбиения наберите в ячейку В2 начальное число, например, 75 для наших случайных чисел. Затем выполните команду Правка(Заполнить(Прогрессия. В появившемся диалоговом окне заполните данные:
в группе переключателей поле Расположение установите по столбцам;
в поле Шаг наберите 3;
в поле Предельное значение наберите 125;
в группе переключателей Тип установите арифметическая и нажмите ОК.
В результате столбец В будет содержать интервалы разбиения (карманы).
Выполните команду Сервис(Анализ данных(Гистограмма. В появившемся диалоговом окне Гистограмма заполните:
входной интервал появится, если щелкнуть мышью по столбцу А;
интервал карманов появится, если щелкнуть мышью по столбцу В;
поставьте галочку в поле метки;
укажите столбец С в поле Выходной интервал;
активизируйте переключатель Вывод графика; если это поле не содержит галочки, нажмите ОК.
Построение гистограммы займет от 5 до 10 минут. За это время письменно ответьте на контрольные вопросы. В результате вычисления получатся столбец под названием Карман, который дублирует ваш столбец интервалов разбиения, и столбец под название Частота с рассчитанными частотами. После того, как появилась гистограмма, измените ее размеры с помощью мыши так, чтобы хорошо были видны все столбцы и подписи.
Теперь осталось получить таблицу статистических характеристик с помощью Описательной статистики. Выполните команду Сервис(Анализ данных(Описательная статистика. В появившемся диалоговом окне Описательная статистика укажите:
в поле Входной интервал появится адрес, если выделить мышью интервал сданными или с клавиатуры набрать адрес $A$2: $A$501;
в поле Группирование активизировать переключатель по столбцам;
активизировать переключатель Метки в первой строке;
в группе Параметры вывода укажите Выходной интервал, щелкнув мышью по какой-либо пустой ячейке ниже столбца частот, например, по С 25;
активизируйте переключатель Итоговая статистика (если в этом поле нет галочки);
активизируйте переключатель Уровня надежности и установите 95%;
снимите галочки с полей наименьший и наибольший и нажмите ОК.
Результаты записать в отчет.
Контрольные вопросы:
Для чего предназначена функция СРЗНАЧ?
С помощью каких характеристик оценивают разброс статистических данных? Какие функции в Excel их вычисляют? В чем отличие функции оценки разброса данных для генеральной и выборочной совокупности?
В чем отличие функций СЧЕТ и СЧЕТЗ?
Что такое мода и какая функция ее вычисляет?
Что такое медиана и какая функция ее вычисляет?
Как вычислить размах варьирования?
С помощью каких характеристик оценивают отклонение случайного распределения от нормального? Какой смысл этих характеристик и какие функции в Excel их вычисляют?
Что такое Инструменты Анализа? Как загрузить Пакет Анализа?
Опишите последовательность действий, которые необходимо совершить для генерации случайных чисел распределенных нормально.
Как построить гистограмму?
Для чего предназначен инструмент Описательная статистика?
Практические занятия
Практическое занятие №10 «Использование расчетных формул, таблица, графиков при решении статистических задач. Построение по заданной выборке ее графической диаграммы, расчет числовых характеристик»
Практическое занятие №11 «Использование расчетных формул при решении статистических задач. Интервальная оценка математического ожидания нормального распределения. Интервальная оценка вероятности события»
Практическое занятие № 12 «Использование расчетных формул, таблица, графиков при решении статистических задач. Моделирование случайных величин, Моделирование сложных испытаний и их результатов»
Практическое занятие № 13 «Применение современные пакеты прикладных программ многомерного статистического анализа»
Раздел 4. Основы теории графов
Тема 4.1.Основные понятия теории графов
Тема лекции: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
План:
Введение
Основные понятия и определения теории графов
Некоторые типы графов
Введение
Основу теории графов составляет совокупность методов и представлений, сформировавшихся при решении конкретных задач.
Термин «граф» впервые появился в книге выдающе гося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Одна из задач, положивших начало теории графов, – задача о кенигсбергских мостах ( рассказать, показать граф).
Граф есть совокупность точек и линий, соединяющих эти точки. Эти соединения могут обладать различными характеристиками, и теория графов занимается изучением этих характеристик. Граф характеризует отношения между множествами объектов.
Большое значение в теории графов имеет проблема разрешимости: найти эффективный или хотя бы достаточно простой в практически важных случаях алгоритм решения задачи.
В последнее время теория графов принимает все более прикладной характер, являясь эффективным аппаратом для формализации множества задач, связанных с дискретным размещением объектов. К ним, в частности, относятся: проектирование и исследование сетей связи, анализ электрических цепей, графы потока сигналов и теория обратной связи, блок-схемы программы, исследование автоматов, анализ и синтез логических цепей, задачи календарного планирования, планирование и обеспечение материально-технического снабжения, поиск информации, стратегия инвестиций, анализ качества, исследование движения транспорта, размещение предприятий коммунального обслуживания, моделирование, экономические задачи, теория игр, головоломки, доказательство теорем.
Основные понятия и определения теории графов
Определение: Пусть задано некоторое конечное множество 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). 13 EMBED Equation.3 1415(хi) – множество вершин хj(X, для которых в графе 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 – неориентированный граф.
13 SHAPE \* MERGEFORMAT 1415
Рис. 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), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) – инцидентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину.
13 SHAPE \* MERGEFORMAT 1415
Рис.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.
13 SHAPE \* MERGEFORMAT 1415
Рис. 4 Рис.5
Некоторые типы графов
Определение: Граф G называется полным, если любые две его вершины смежны. Полный граф порядка n обозначается символом Кn, число ребер в нем равно 13 EMBED Equation.3 1415. На рис.6 изображены графы Кn , n(5.
13 EMBED Word.Picture.8 1415
Рис.6
Определение: Граф называется пустым, если в нем нет ребер. Пустой граф порядка n обозначается через Оn.
Определение: Граф, не содержащий вершин и, следовательно, ребер, называется ноль-графом. Граф, состоящий из одной вершины, называется тривиальным.
Красивыми примерами являются графы пяти платоновых тел (т. е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра
Контрольные вопросы:
Понятие графа.
Применение графов.
Основные определения теории графов.
Типы графов.
Тема лекции: Представление информации в форме графа
План:
Вводные понятия.
История возникновения и развития теории графов.
Представление графа в памяти компьютера.
Вводные понятия
Вы имеете представление о компьютерных сетях. Компьютеры в нашем кабинете объединены в локальную сеть. Понятно, что сеть образуется только тогда, когда компьютеры каким-либо образом соединены между собой каналами передачи данных.
Размещение абонентов сети (подключённых к ней компьютеров или других систем автоматической обработки данных) и способ их соединения друг с другом называется конфигурацией сети. Продемонстрировать различные типы конфигураций вычислительных сетей можно, например, с помощью таких информационных моделей, как графы.
Если вы любите решать олимпиадные задачи, тогда, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии. То есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы открывали для себя начала теории графов.
Граф совокупность точек, соединённых между собой линиями. Точки называют вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или рёбрами (если направленность двусторонняя, то есть направления равноправны).
Две вершины, соединенные ребром (дугой) называются смежными.
Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.
Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины с какими рёбрами (дугами) соединены и, возможно, указаны веса вершин и рёбер (дуг). Определение всех этих элементов и составляет суть формализации в этом случае.
История возникновения и развития теории графов
Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.
Теория графов дает простой и мощный инструмент построения моделей и решения задач упорядочения объектов. В настоящее время существует множество проблем, где требуется построить некоторые сложные системы с помощью определенного упорядочения их элементов. Сюда относятся календарное планирование промышленного производства, задачи теории сетевого планирования и управления, тактические и логические задачи, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы построения электрических сетей, задачи идентификации в органической химии и способы переключения переключательных схем. Таким же является большой круг экономических задач, проблемы выбора структуры социальных групп и т.д. Таким образом, область возможных применений теории графов очень широка. Комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений. Кроме языка теории графов, задачи упорядочения объектов можно формулировать в терминах теории матриц с элементами ноль - один.
С полным основанием можно сказать, что теория графов является одним из простейших и наиболее элегантных разделов современной математики с широкой областью применения. Имея в своей основе простейшие идеи и элементы: точки, соединенные линиями, теория графов строит из них богатое многообразие форм, наделяет эти формы интересными свойствами и в результате становится полезным инструментом при исследовании самых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов анализа широкого круга комбинаторных проблем. Если помимо основных чисто структурных соотношений в графе задаются некоторые количественные характеристики точек и линий, образующих граф, тогда вместо понятий графа можно использовать понятие сеть. В качестве примеров можно назвать электрические сети, сети выполнения работ в проектах сети потоков. При этом ребром сети ставятся в соответствие определенные количественные характеристики энергии, затрат и потока.
Представление графа в памяти компьютера
Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.
рис.1
На рис.1 представлены различные изображения одного и того же графа.
В прикладных задачах теории графов необходимость введения ориентации ребер возникает по 2-м причинам. Например, в системах городских улиц необходимо изображать улицы с одностороннем движением. При описании систем связи между людьми или машинами необходимо учитывать существенно однонаправленные устройства. С другой стороны, введение ориентации необходимо для установления системы координат и устранения неоднозначности.
Например, при соединении электрических приборов одно направление необходимо обозначить как положительное, для того чтобы однозначно описать распределение электрического тока, хотя действительное направление может и не быть жестко ограничено.
Способы описания графа:
Выбор подходящей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются способы описания графа: матрица инцидентности графа; матрица смежности графа; списки связи и перечня ребер.
Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.
Пример:
l1 V1 V3
l2 V1 V2
l3 V1 V2
l4 V2 V3
Матрица смежности – это двумерный массив А размерности N*N
1, если вершины i и j - смежные
A[i,j]=
0, если вершины i и j - несмежны
Пример: Данный граф можно представить в виде матрицы смежности:
V1 V2 V3 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
1, если 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 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:
шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К), информация от абонента-источника распространяется по каналу в обе стороны;
кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;
звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;
древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;
полносвязная конфигурация обеспечивает выбор наиболее быстрого маршрута связи между абонентами и удобна там, где управление оказывается достаточно сложным.
Рис. 2
Различные типы
конфигураций Шинная
локальных
вычислительных
сетей
Кольцевая
Звездообразная
Полносвязная
Древовидная
Тема лекции: Метрические характеристики графов
В теории графов применяются:
Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.
Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.
Пусть G=(X,U) - связный граф, а 13 EMBED Equation 1415 - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины 13 EMBED Equation 1415 (пути из 13 EMBED Equation 1415) называется расстоянием между вершинами 13 EMBED Equation 1415 и обозначается 13 EMBED Equation 1415. Положим 13 EMBED Equation 1415, если вершины 13 EMBED Equation 1415 не соединены маршрутом (путем). Расстояние 13 EMBED Equation 1415 удовлетворяет следующим аксиомам:
1) 13 EMBED Equation 1415;
2) 13 EMBED Equation 1415;
3) 13 EMBED Equation 1415 тогда и только тогда, когда 13 EMBED Equation 1415;
4) 13 EMBED Equation 1415 для симметрических графов;
5) 13 EMBED Equation 1415 (неравенство треугольника).
Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:
13 EMBED Equation 1415
Матрицу расстояний можно определить
Для фиксированной вершины 13 EMBED Equation 1415 величина
13 EMBED Equation 1415
называется эксцентриситетом (отклоненностью) вершины 13 EMBED Equation 1415.
Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):
13 EMBED Equation 1415
Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):
13 EMBED Equation 1415
Вершина, имеющая минимальный эксцентриситет, называется центром графа.
Для вершины 13 EMBED Equation 1415 число 13 EMBED Equation 1415 называется передаточным числом.
Вершина графа, которой соответствует минимальное передаточное число
13 EMBED Equation 1415
называется медианой графа. Центров и медиан в графе может быть несколько.
13 SHAPE \* MERGEFORMAT 1415
Рис. 1
Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:
13 EMBED Equation 1415
Радиус графа равен 1, диаметр равен 2. Центр графа - вершина 13 EMBED Equation 1415; Медиана графа - вершина 13 EMBED Equation 1415.
Контрольные вопросы:
Что такое граф?
Приведите разновидности графов.
Может ли пустой граф быть ориентированным?
Нарисуйте полный граф.
Что такое подграф?
Каким образом понятие дерева активно используется в информатике и программировании?
Метрические характеристики графов.
Тема 4.2.Остовы графов, деревья
Деревья
Определение: Деревом называют связный граф без циклов. Пример: Название достаточно жизненно - взгляните на рисунок:
Теорема: В любом дереве вершин ровно на одну больше, чем ребер.
Док-во: Будем доказывать этот факт индукцией по количеству вершин.
Когда вершин - две ясно, что ребро ровно одно, так что база индукции очевидна.
Переход: Возьмем любое дерево. В нем есть висячая вершина. Уберем ее вместе с ребром, которое к ней ведет. Оставшееся по-прежнему будет деревом, т.к. циклы появиться не могли, и связность нарушиться тоже не могла. Но тогда в остатке вершин на одну больше, чем ребер по предположению индукции, а значит и в исходном графе тоже, т.к. есть одна дополнительная вершина и одно ребро.
Теорема: В любом связном графе с n вершинами хотя бы n-1 ребро, причем если количество ребер ровно n-1, то это дерево.
Док-во: Пусть это не дерево (иначе ребер ровно n-1 по предыдущей теореме), значит, в нем есть цикл. Сотрем любое из ребер этого цикла - граф останется связным. Если в нем остался еще цикл, то сотрем ребро и из него, и т.д. Ясно, что граф все время остается связным, так что в конце получится связный граф без циклов - дерево - у него ровно n-1 ребро, а значит у исходного графа хотя бы п.
.
Теорема: Следующие утверждения равносильны:
1. Граф является деревом.
2. Граф связен и перестает быть таким при стирании любого ребра.
3. Граф связен и вершин в нем на одну больше, чем ребер.
4. В графе нет циклов и вершин на одну больше, чем ребер.
Док-во: 1<=>2: это ясно, т.к. если мы стираем ребро, а связность не нарушается, то значит между его концами есть какой-то другой путь, а значит, есть и цикл. И наоборот: если есть цикл, то можно стереть любое ребро из этого цикла, не нарушив связность графа.
1 =>3: В любом дереве вершин на одну больше; чем ребер. Это мы уже знаем.
3=>4: Пусть цикл все-таки есть. Уберем из него ребро - граф, естественно, останется связным, но это невозможно, т.к теперь ребер на два меньше, чем вершин (см. пред, теорему). Значит, цикла нет. 4=>1: Пусть граф несвязен. Тогда в каждой компоненте связности нет циклов, то есть каждая компонента - дерево, а значит в ней вершин на одну больше, чем ребер. Но тогда всего вершин более чем на одну больше, чем ребер, что невозможно. Значит, граф связен, а тогда это дерево.
Определение: пусть у нас есть произвольный связный граф. Максимальное дерево в нем - это подграф, который содержит все вершины исходного графа и некоторые из его ребер. Замечание: Таких максимальных деревьев может быть несколько.
Пример: На рисунке выделено одно из возможных максимальных деревьев.
Теорема: В любом связном графе можно выделить максимальное дерево.
Док-во: Будем действовать, как при доказательстве предпоследней теоремы: Пусть наш граф еще не дерево, тогда в нем есть цикл и мы можем убрать любое ребро из этого цикла так, что граф останется связным. Будем повторять этот процесс, пока не останется дерево. Это как раз то, что нам и надо.
С помощью графов-деревьев решают задачи планирования (дерево целей, дерево переборов вариантов). Графы используют также для иллюстрации классификаций в различных областях знаний при построении иерархических структур сложных систем.
Рассмотрим пример. Для классификации некоторого объекта предприятие. (варианты его названия 13 EMBED Equation.3 1415) выберем в качестве корня дерева сам объект . Компоненты, составляющие этот объект, разместим на первом уровне (ярусе) графа: это будут 13 EMBED Equation.3 1415 Второй уровень (ярус) графа содержит компоненты первого уровня (его подмножества: 13 EMBED Equation.3 1415). Аналогично на третьем уровне разместим подмножества компонентов второго уровня - 13 EMBED Equation.3 1415 От нижнего уровня к высшему ведёт лишь одна дуга, поэтому граф является деревом.
Определение: Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.
Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра это пары городов, между которыми есть маршрут, а вес ребра равен стоимости проезда по соответствующему маршруту.
Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:
[ Cкачайте файл, чтобы посмотреть ссылку ];
[ Cкачайте файл, чтобы посмотреть ссылку ];
[ Cкачайте файл, чтобы посмотреть ссылку ].
Тема лекции: Построения остовного дерева
Постановка задачи
Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c(e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX(G).
Методы решения данной проблемы
Остовным деревом графа называется дерево, содержащее все вершмины 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’ будет продолжать представлять подмножество некоторого минимального остовного дерева.
Описание алгоритма Краскала
Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.
Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины. На каждом шаге просматривается список ребер, начиная с ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро, которое не образует цикла с ребрами, уже включенными в решение.
Алгоритм состоит из следующей последовательности действий:
Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i),номер конечной вершины ребра (j), признак включения данного ребра в дерево.
Данный список упорядочивается в порядке возрастания длин ребер.
Просматривается список R и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 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) замыкает цепь, превращая ее в цикл.
Теорема. Алгоритм Прима–Краскала получает максимальное остовное дерево.
Пример Для заданного графа произвольно пронумеровать вершины и построить кратчайшее остовное дерево, определить его длину.
Решение:
Для построения кратчайшего остовного дерева воспользуемся алгоритмом Крускала.
В этом алгоритме мы начинаем с пустого дерева и добавляем к нему ребра в порядке возрастания их весов пока не получим набор ребер, объединяющий все вершины графа. Если ребра закончатся до того, как все вершины будут соединены между собой, то это означает, что исходный граф был несвязным, и полученный нами результат представляет собой объединение МОД всех его компонент связности.
Начнем с ребер наименьшего веса, равного 1, то есть с ребер AB, BE, ED, EL, LK.
Ребер веса 2 нет.
Следующими добавляем ребра веса 3, при этом следим, чтобы в графе не появлялись циклы. Добавляем ребра BC, CF.
К результирующему графу последовательно добавляются ребра веса 4- EG.
Добавление остальных ребер приведет к появлению цикла в уже построенной части МОД.
Таким образом, кратчайшее остовное дерево для заданного графа имеет вид:
Длина построенного кратчайшего остовного дерева равна 15.
Тема 4.3.Виды графов
Двудольные графы
Определение: Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям.
Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным.
Полный двудольный граф, доли которого состоят из р и из q вершин, обозначается символом Kp,q . При р=1 получаем звезду K1,q. На рис.1 изображены звезда К1,5 и полный двудольный граф K3,3.
Аналогично двудольным графам определяются k-дольный и полный k-дольный графы для k=3, 4, ... На рис.2 приведен трехдольный граф.
Рис. 1 Рис. 2
Для решения примеров удобно применять теорему
Теорема: Граф является двудольным т. и т.т., к. все его простые циклы имеют четную длину.
Легко подсчитать число всех графов с фиксированным множеством вершин X. Эти графы различаются своими ребрами, и потому их число равно количеству подмножеств в X(2), т.е. 213 EMBED Equation.3 1415 , где п=|X|. Однако эти графы не всегда следует различать. Как в применениях теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Оформим эти соображения в виде следующего определения.
Изоморфные графы
Определение: Два графа G1 и G2 называются изоморфными, если существует взаимно-однозначное отображение между множествами их вершин, сохраняющее смежность. Такое отображение называется изоморфизмом.
Два орграфа изоморфны, если существует изоморфизм между их основаниями, сохраняющий порядок вершин на каждой дуге.
Например, три графа, представленные на рис. 4, изоморфны, а графы на рис. 5 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.
Рис. 4.
13 EMBED Word.Picture.8 1415
Рис. 5
Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы можно отождествлять, т. е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игно рируется при введении понятия «граф».
В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помеченный граф». Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, ..., n. Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин – с множеством чисел {1, 2, ..., n}), определим равенство помеченных графов G1=(X,V1) и G2=(X,V2) одного и того же порядка: G1=G2 тогда, когда V1=V2. На рис. 6 изо бражены три разных помеченных графа.
При необходимости подчеркнуть, что рассматриваемые графы различаются лишь с точностью до изоморфизма, говорят: «абстрактный граф». Строго говоря, абстрактный (или непомеченный) граф – это класс изоморфных графов.
13 EMBED Word.Picture.8 1415
Рис. 6
Контрольные вопросы:
Двудольные графы.
Изоморфные графы.
Решить задачи:
1. Определите, является ли граф двудольным?
а) Граф К3,3 (задача о колодцах);
б) ;
в) граф – додекаэдр (пятиугольник).
2. Определите, являются ли графы изоморфными?
а) б)
3. Сколько можно построить графов с 3 вершинами с точностью до изоморфизма? (4)
Тема лекции: Эйлеровы и гамильтоновы циклы
Эйлеровы циклы и гамильтоновы циклы (контуры) часто встречаются в практических задачах и поэтому представляют особый интерес.
Одна из самых первых задач теории графов ( это известная задача о кенигсбергских мостах. Постановка и решение этой задачи Эйлером знаменует начало разработки теории графов. Расположение мостов через реку Прегель в г. Кенигсберге в его время приведено на рис.1.
Рис.1
Возник вопрос: можно ли, выйдя из дома, вернутся обратно, пройдя по каждому мосту ровно один раз.
Можно построить граф задачи, в которой каждой части города соответствует вершина, а каждому мосту – ребро, инцидентное вершинам, относящимся к соединяемым им частям (рис.1). Обходу мостов соответствует маршрут графа, который по условию должен быть простым циклом. Эйлер дал отрицательный ответ на поставленный вопрос, так как соответствующий граф не содержал эйлерова цикла.
В девятнадцатом веке Гамильтон придумал игру, где использовался додэкаэдр, всем вершинам которого были даны названия известных городов. Задача играющего состояла в том, чтобы обозначить замкнутый путь через все города, посетив каждый из них только один раз. Так возникло понятие гамильтонова цикла во взвешенном графе. Алгоритмы решения задачи коммивояжера и ее вариантов имеют большое число практических приложений в различных областях человеческой деятельности.
Эйлеровы циклы
Определение: Цикл, который проходит ровно один раз по каждому ребру неориентированного графа G, называется эйлеровым циклом.
Определение: Граф, в котором существует эйлеров цикл, называется эйлеровым графом.
Определение: Цепь, которая проходит ровно один раз по каждому ребру неориентированного графа G, называется эйлеровой цепью.
Определение: Граф, в котором существует эйлерова цепь, называется полуэйлеровым графом.
Рис 2.
На рис 2 а) неэйлеров граф; б) полуэйлеров граф; в) эйлеров граф;
Теорема: Связный граф является эйлеровым тогда и только тогда, когда каждая вершина в графе имеет четную степень.
Теорема: Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетную степень.
Утверждения.
1. Связный неориентированный граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0 (0 или 2).
2. Для связного графа G следующие утверждения эквивалентны:
а) G ( эйлеров граф;
б) каждая вершина графа G имеет четную степень;
в) множество ребер графа G можно разбить на простые циклы.
Метод Флёри построения эйлерова цикла
Метод Флёри построения эйлерова цикла начинает работу с некоторой вершины х и каждый раз вычеркивает пройденное ребро. Не проходить по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин).
Опишем алгоритм построения эйлерова цикла в связном неорграфе с четными степенями вершин, а также в орграфе с совпадающими полустепенями захода и исхода.
Замечание. Граф G=(X,V) задается множеством X своих вершин и набором реберных окрестностей всех его вершин S(x)={v | ребро v инцидентно вершине х}.
Шаг 1. Выбрать произвольную вершину х0(X и положить х=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. Выдать последовательность С, которая является эйлеровым циклом.
Гамильтоновы циклы
Определение: Путь, проходящий через все вершины графа (в точности по одному разу через каждую), называется гамильтоновым путем. Если начальная вершина и конечная вершина этого пути совпадают, то такой путь называется гамильтоновым контуром.
Определение: Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым.
Рис. 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. Можно ли ходом шахматного коня обойти шахматную доску размером 8*8 так, чтобы каждый ход встречался ровно один раз (при этом мы считаем, что ход встречался, если конь переместился с одной клетки на другую любым из двух возможных способом). Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.
3. Может ли ходом шахматный конь побывать на каждой клетке шахматной доски размером 8*8 ровно один раз и возвратиться в начальную клетку. Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.
4. Приведите пример графа, который является эйлеровым, но не гамильтоновым.
5. Приведите пример графа, который является гамильтоновым, но не. эйлеровым
6. Что можно сказать о графах, являющихся одновременно эйлеровыми и гамильтоновыми?
Плоские и планарные графы
Во многих случаях не имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацию. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.
Таким образом, возникает понятие плоского графа.
Определение: Плоским графом называется граф, вершины которого являются точками плоскости, а ребра – непрерывными линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.
а б
Рис. 1. Плоские графы.
Определение: Любой граф, изоморфный плоскому графу, будем называть планарным.
Рис.2.
Граф на рис.2 является планарным, так как он изоморфен графу на рис 1.б.
Очевидны следующие утверждения:
всякий подграф планарного графа планарен;
граф планарен тогда и только тогда, когда каждая его связная компонента – планарный граф.
О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).
Алгоритм укладки графа на плоскости
Для решения практических задач недостаточно знать, что граф планарен, а необходимо построить его плоское изображение. Существуют алгоритмы, которые не только проверяют граф на планарность, но и одновременно строят его плоскую укладку, если это возможно.
Одним из таких алгоритмов является следующий:
Рассмотрим граф G=(X,U). Алгоритм укладки графа представляет собой процесс последовательного присоединения к некоторому уложенному подграфу G' (G'=(X',U')) графа G новой цепи, оба конца которой принадлежат G'. Тем самым эта цепь разбивает одну из граней G' на две. При этом в качестве начального плоского графа G' выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В этом случае граф не является планарным.
Пошаговое описание алгоритма укладки графа на плоскости
Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G'=С.
Найдем грани графа G' и сегменты относительно G'. Если множество сегментов пусто, то перейдем к п. 7.
Для каждого сегмента S определим множество Г(S).
Если существует сегмент S, для которого Г(S)=(, то граф G непланарен. Конец. Иначе перейти к п. 4.
Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейти к п. 6. Иначе – к п. 5.
Для некоторого сегмента S (Г(S)>1) выбираем произвольную допустимую грань Г.
Поместить произвольную (–цепь L (S в грань Г; заменить G' на G'(L и перейти к п. 1.
Построена укладка 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).
Рис. 3.
Рис. 4.
Рис. 5.
Рис. 6.
Рис. 7.
Рис. 8.
Пример 2. Для графа К3,3, изображенного на рис.9, построить, если это возможно, его укладку на плоскости.
Решение: цикл G' и сегменты относительно этого цикла изображены на рис. 10. При этом Г(Si) = {Г1, Г2} (i=1,2,3). Помещает S1 в грань Г2. Тогда S2 необходимо поместить в грань Г1 (рис. 11). Поскольку Г(S1)=(, то К3,3 - непланарный граф.
Рис. 9.
Рис. 10.
Рис. 11.
Контрольные вопросы:
Плоские графы.
Планарные графы.
Решить задачи:
1. Для графа построить, если это возможно, его уклад ку на плоскости.
а)
б)
2. Для графа построить, если это возможно, его уклад ку на плоскости.
а) б)
в) г)
Практические занятия
Практическое занятие №14 «Метрические характеристики графов»
Практическое занятие №15 «Построения остовного дерева»
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Вопросы к экзамену
ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА»
Теоретическая часть:
Раздел 1. Основные понятия комбинаторики
Тема 1.1. Основные понятия комбинаторики
Основные комбинаторные объекты. Размещения. Примеры
Основные комбинаторные объекты. Сочетания. Примеры
Основные комбинаторные объекты. Перестановки. Примеры.
Два основных принципа комбинаторики
Раздел 2. Основы теории вероятностей
Тема 2.1. Основные теоремы теории вероятностей
Случайные события. Типы событий.
Классическое определение вероятности
Противоположное событие.
Теоремы сложения вероятностей
Теоремы умножения вероятностей
Формула полной вероятности
Формула Байеса
Схема Бернулли. Формула Бернулли
Тема 2.2. Дискретные случайные величины (ДСВ)
Случайные величины.
ДСВ. Распределение ДСВ.
Методика записи распределения функции от одной ДСВ, от двух ДСВ.
Числовые характеристики ДСВ и их свойства
Тема 2.3. Непрерывные случайные величины (НСВ)
Функция плотности НСВ. Свойства
Интегральная функция распределения НСВ. Свойства
Методика вычисления характеристик НСВ по ее функции плотности.
Виды распределений НСВ. Нормальное распределение с.в.
Раздел 3. Основы математической статистики
Тема 3.1. Выборочный метод. Статистические оценки параметров распределения.
Генеральная совокупность и выборка.
Полигон, гистограмма.
Числовые характеристики выборки.
Понятие интервальной оценки математического ожидания нормального распределения.
Интервальная оценка вероятности события.
Тема 3.2. Моделирование случайных величин
Моделирование случайных величин. ДСВ.
Моделирование случайных величин. НСВ.
Тема 3.3. Современные пакеты прикладных программ многомерного статистического анализа
Современные пакеты прикладных программ многомерного статистического анализа.
Раздел 4. Основы теории графов
Тема 4.1.Основные понятия теории графов
Понятие графа. Способы задания графов.
Операции над графами
Метрические характеристики графов
Тема 4.2.Остовы графов, деревья
Остов графа. Деревья.
Построения остовного дерева. Алгоритм
Тема 4.3.Виды графов
Эйлеровы графы
Гамильтоновы графы
Фундаментальные циклы
ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Основные источники
М.С. Спирина, П.А. Спирин Теория вероятностей и математическая статистика.- М.: Издательский центр «Академия», 2012.
Дополнительные источники
Н.В. Богомолов, П.И. Самойленко Математика.-М.: Дрофа, 2010.
Статистика : учебник для учреждений среднего профессионального образования / ред. В. С. Мхитарян . - 11-е изд., стер . - М. : Академия , 2012
Virtual Laboratory Wiki. Распределение вероятностей /Категория: Распределения_вероятностей. – М., 2010. / http://ru.vlab.wikia.com/wiki/
Кочетков Е.С. Теория вероятностей и математическая статистика: учебник для СПО / Е.С. Кочетков, С.О. Смерчинская, В.В. Соколов. – М.: Форум, 2011
Периодические издания
Журнал «Алгебра и анализ»
Журнал «Математические заметки»
Интернет-ресурсы
Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru
Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ].
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
13PAGE 14115
13 PAGE \* MERGEFORMAT 149815
l4
l3
l2
l1
V6
l7
l7
V6
V4’
V6’
V2’
V5’
V3’
V5
V4
V1
V3
V2
V1’
l3
l4
l6
l5
l2
l1
l3
l1
l5
l2
l4
l6
l7
l6
l4
l2
l3
l1
l5
V4
V3
V2
V1
V5
x1
x5
x3
x1
x3
x2
x4
x1
x3
x2
x4
x1
x2
x4
x3
x1
x5
x2
x3
x4
x2
x3
x4
x1
Рис. 3
Рис. 2
Рис. 1
Рис. 1
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
V1
V2
V3
V3
V1
V2
V4
V5
V8
V7
V6
e2
e1
e3
e5
e4
e6
V3
V1
V2
V4
V5
К1
К3
К2
К4
К5
К1
К3
К2
К4
К5
ЦК
К1
К3
К2
К4
К5
К1
К3
К2
К4
К5
К1
К3
К2
К4
К5
К7
К8
К6
К9
x4
x1
x2
x3
x5
Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native