Методические указания по выполнению практических работ МДК.01.02 Математический аппрат для построения компьютерных сетей"

Министерство образования, науки и молодёжи

Республики Крым

Государственное бюджетное профессиональное образовательное учреждение Республики Крым

«Симферопольский автотранспортный техникум»

УТВЕРЖДАЮ

Заместитель директора

по учебной работе

_______________

«_______»_____________2017 г.

Методические указания
по выполненю практических работ

МДК.01.02 Математический аппарат для построения компьютерных сетей

Симферополь, 2017

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

Методические рекомендации по выполнению практических работ предназначены для студентов 2 курса по специальности:

09.02.02 «Компьютерные сети».

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

Практическая работа №1 «Решение задач по комбинаторике»

Практическая работа №2 «Решение задач по теории вероятности»

Практическая работа №3 Сложные вероятности

Практическая работа №4 Решение задач по математической статистике

Практическая работа №5 Решение задач по Решение задач по теории графов

Практическая работа №6 Решение задач по теории массового обслуживания

Организация-разработчик:

Симферопольский автотранспортный техникум (САТТ)

Разработчик:

Безменова Е.Ю., преподаватель математики, высшая квалификационная категория

^{Ф.И.О., ученая степень, звание, должность,}

Рассмотрены на заседании цикловой комиссии математического и общего естественнонаучного цикла.

Протокол №___ от «___» ________ 2017г.

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

_____________________

Содержание

Правила выполнения практических работ………………………………………………………….4

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

Практическая работа №1 «Решение задач по комбинаторике» 5

Практическая работа №2 «Решение задач по теории вероятности»……………………………….8

Практическая работа №3 Сложные вероятности…………………..………………………………11

Практическая работа №4 Решение задач по математической статистике……………………….16

Практическая работа №5 Решение задач по решение задач по теории графов………………….25

Практическая работа №6 Решение задач по теории массового обслуживания…………………..44

Правила выполнения практических работ

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

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

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

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

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

-задания выполнены правильно и полном объеме;

- студент может пояснить выполнение любого этапа работы;

- отчет выполнен в соответствии с требованиями к выполнению работы.

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

Содержание отчета

1. Название работы.

2. Цель работы.

3. Задание.

4. Решение задания.

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

Оценка «5» ставится, если: работа выполнена полностью; в логических рассуждениях и обосновании решения нет пробелов и ошибок; в решении нет ошибок (возможна одна неточность, описка, не являющаяся следствием незнания или непонимания учебного материала).

Оценка «4» ставится, если: работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки); допущена одна существенная ошибка или два-три несущественных ошибки.

Оценка «3» ставится, если допущены более одной существенной ошибки или более двух-трех несущественных ошибок, но студент владеет обязательными умениями по проверяемой теме; при этом правильно выполнено не менее половины работы.

Оценка «2» ставится, если: допущены существенные ошибки, показавшие, что студент не владеет обязательными умениями по данной теме в полной мере.

Оценка «1» ставится, если: работа показала полное отсутствие у обучающегося обязательных знаний и умений по проверяемой теме или значительная часть работы выполнена не самостоятельно.

Практическая работа 1 «Решение задач по комбинаторике»

Цель занятия: получить практические навыки в решении комбинаторных задач.

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

Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 17 века Блеза Паскаля (1623–1662) и Пьера Ферма (1601–1665) по теории азартных игр. Эти труды содержали принципы определения числа комбинаций элементов конечного множества. С 50-х годов 20 века интерес к комбинаторике возрождается в связи с бурным развитием кибернетики.

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

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

• Правило суммы Если некоторый элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то выбор «либо А, либо В» можно сделать n + m способами.

• Правило произведения Если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то пару А и В можно выбрать n • m способами.

• Перестановки. Упорядоченные выборки, объемом N из N элементов, где все элементы различны, называются перестановками из N элементов. Число перестановок из N элементов обозначается Pn. P_n=Aⁿ_n=n·(n-1)·...·2·1=n!

• Размещения. Упорядоченные выборки объемом M из N элементов (M N), где все элементы различны, называются размещениями. Число размещений из N элементов по M обозначается . A^k_n=n!/(n-k)!

• Сочетания. Неупорядоченные выборки объемом M из N элементов (M N) называются сочетаниями. Их число обозначается . C^k_n=A^k_n/k!=n!/(n-k)!k!

Примеры выполнения

Пример 1

В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение: По логике условия, детали считаются различными – даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать).

В задаче речь идёт о выборке из 4 деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:

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

Подробно:

 способами можно взять 4 детали из ящика.

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

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

 – единственным способом можно взять ни одной детали;
 способами можно взять 1 деталь (любую из пятнадцати);
 способами можно взять 14 деталей (при этом какая-то одна из 15 останется в ящике);
 – единственным способом можно взять все пятнадцать деталей.

Ответ: 1365 способами

Решить следующие задачи.

Задача 1. 

Есть 2 яблока и 3 груши. Каждый день в течение 5 дней подряд выдается по одному фрукту. Сколькими способами это может быть сделано?

Задача 2. 

Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Задача 3. 

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

Задача 4.

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

Задача 5. 

Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

Задача 6. 

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

Задача 7.

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

Задача 8.

 Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

Задача 9. 

Сколько слов можно получить, переставляя буквы в слове Гора и Институт?

Задача 10. 

Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается?

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

• Что изучает комбинаторика как наука?

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

• Что такое выборка?

• Приведите формулы определяющие число сочетаний, размещений и перестановок без повторений

• Приведите формулы определяющие число сочетаний, размещений и перестановок с повторениями

• Что такое неупорядоченная выборка?

Практическая работа №2 «Решение задач по теории вероятности»

Цель занятия: получить практические навыки в решении задач по теории вероятности.

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

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

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

События обозначаются, как правило, заглавными буквами латинского алфавита:

Непосредственные исходы опыта называются элементарными
событиями и обозначаются через . Элементарные события (их называют также «элементами», «точками», «случаями») рассматриваются как неразложимые и взаимоисключающие исходы этого опыта.

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

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

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

В примере 1.1 события и случайные; событие – невозможное; событие – достоверное.

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

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

Например, два стрелка делают по одному выстрелу по мишени. Если событие – попадание первого стрелка, а событие – второго, то сумма – это хотя бы одно попадание при двух выстрелах.

Произведением событий и называется событие , состоящее в совместном наступлении этих событий (т.е. и и одновременно).

Число называется частотой события , а отношение

называется относительной частотой (или частостью) события в рассматриваемой серии опытов.

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

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

Согласно данному определению

.

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

.

Примеры решения задач

Задача 1

Датчик случайных чисел генерирует двузначное случайное число. Какова вероятность того, что сгенерированное число делится на 5?

Решение

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

Событие – сгенерированное двузначное число делится на 5.

Всего двузначных чисел 90 (от 10 до 99). Общее число возможных исходов в данном эксперименте .

Число исходов, благоприятствующих событию (сгенерированное двузначное число делится на 5), будет .

Используя классическое определение вероятности:

.

Задача 2

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

Решение

Опыт: курсант угадывает расписание предметов.

Событие – курсант угадал расписание занятий.

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

Следовательно, число всех возможных исходов испытания равно числу размещений из 10 по 3, т.е.

.

Благоприятный же случай только один, т.е. .

Искомая вероятность будет равна

.

Задача 3

В группе 25 курсантов, из них 5 отличников. Наугад выбираются 7 курсантов. Какова вероятность того, что среди отобранных лиц окажутся 3 отличника.

Решение

Опыт: выбирают курсантов из группы.

Событие – среди 7 отобранных курсантов, 3 отличника.

Общее число возможных исходов (из 25 курсантов выбрано 7) равно .

Число исходов, благоприятствующих событию (из 5 отличников выбрано 3, а из остальных 20 курсантов выбраны 4), будет .

.

Задачи для самостоятельного решения

Задача 1. 

Абонент забыл последнюю цифру номера телефона и поэтому набирает её наугад. Определить вероятность того, что ему придётся звонить не более чем в 3 места.

Задача 2. 

Абонент забыл последние 2 цифры телефонного номера, но помнит, что они различны и образуют двузначное число, меньшее 30. С учетом этого он набирает наугад 2 цифры. Найти вероятность того, что это будут нужные цифры.

Задача 3. 

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

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

Задача 5. 

Шесть рукописей случайно раскладывают по пяти папкам. Какова вероятность того, что ровно одна папка останется пустой?

Задача 6. 

Цифры 1, 2, 3, …, 9, выписанные на отдельные карточки складывают в ящик и тщательно перемешивают. Наугад вынимают одну карточку. Найти вероятность того, что число, написанное на этой карточке: а) четное; б) двузначное.

Задача 7. 

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

Задача 8. 

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

Задача 9.

 Ребенок имеет на руках 5 кубиков с буквами: А, К, К, Л, У. Какова вероятность того, что ребенок соберет из кубиков слово "кукла"?

Практическая работа №3 Сложные вероятности

Цель занятия: получить практические навыки в решении задач по вероятности сложных событий.

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

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

Замечание

Если и – несовместны, – невозможное событие, тогда и теорема примет вид

Замечание

Теорема обобщается на n совместных событий, в частности для трех совместных событий , , имеем

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

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

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

События называются попарно-независимыми, если любые два события и из этого набора независимы.

Независимые события являются попарно-независимыми. Обратное, вообще говоря, неверно.

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

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

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

В частности, для независимых событий

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

Следствие

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

где – вероятность события , вычисленная в предположении, что события наступили.

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

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

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

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

Формула Бернулли

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

или

Примеры решения задач

Задача 1 Два станка работают независимо друг от друга. Вероятность бесперебойной работы первого станка в течение некоторого времени равна ; второго — . Найти вероятность бесперебойной работы обоих станков в течение указанного промежутка времени?

Решение

Опыт: бесперебойная работа станков в течение некоторого времени .

Событие — бесперебойная работа обоих станков в течение указанного времени.

Событие — бесперебойная работа первого станка в течение времени ;

Событие — бесперебойная работа первого станка в течение времени ;

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

.

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

Решение

Опыт: последовательно вынимают из урны шары.

Событие – событие, заключающееся в том, что шары вынуты в
последовательности: черный, красный, белый.

Событие — первый вынутый шар черный;

Событие — второй вынутый шар красный;

Событие — третий вынутый шар белый.

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

Найдем вероятности, входящие в правую часть этого равенства.

Вероятность того, что первоначально вынут черный шар

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

,

так как после изъятия черного шара в урне осталось 14 шаров и из них — 5 красных.

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

,

(после изъятия черного и красного 13 шаров в урне осталось 13 шаров и из них — 4 белых).

Таким образом, вероятность события :

.

Задачи для самостоятельного решения

Задача 1 Производится стрельба комплекса ЗРВ по трем бомбардировщикам противника, несущим ядерное оружие. На индикаторе кругового обзора РЛС бомбардировщики отображаются в виде одной метки, т.е. представляют собой как бы одну цель. По этой цели запускается одна ЗУР. Вероятности прямого попадания ракеты в бомбардировщики соответственно равны 0,35; 0,3 и 0,28. При попадании в один из них поражаются все три. Найти вероятность того, что бомбардировщики будут поражены.

Задача 2 Найти вероятность того, что наудачу взятое двузначное число окажется кратным или 2, или 5.

Задача 3

Три курсанта независимо друг от друга решают одну и ту же задачу. Вероятность, что первый курсант решит задачу, равна 0,8; второй – 0,7; третий – 0,75. Найти вероятность того, что:

1) все курсанты решили задачу;

2) задачу решил только первый курсант;

3) задачу решил только один курсант;

4) задачу решил хотя бы один курсант.

Задача 4

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

Практическая работа №4 Решение задач по математической статистике

Цель работы: научиться решать задачи по законам распределения дискретных случайных величин

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

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

Под случайной величиной (СВ) понимается величина, которая в результате опыта о случайным исходом принимает то или иное значение, причем, заранее неизвестно какое именно.

Обозначения случайной величины: ; значения случайной величины:

Пример 1

Случайная величина – число очков, выпавших при броске игральной кости;

– число появлений герба при 10 бросках монеты;

– число выстрелов до первого попадания в цель;

– расстояние от центра мишени до пробоины при попадании.

Можно заметить, что множество возможных значений для перечисленных случайных величин имеет разный вид: для и оно конечно (соответственно 6 и 11 значений), для – множество значений бесконечно и представляет собой множество натуральных чисел, а для
– все точки отрезка, длина которого равна радиусу мишени.

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

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

Дискретной (ДСВ) называют случайную величину, которая принимает отдельные, изолированные возможные значения с определенными вероятностями.

Число возможных значений дискретной случайной величины может быть конечным или бесконечным.

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

Для некоторых случайных величин число возможных значений, принимаемых этой величиной, бывает настолько велико, что удобнее представлять их в виде непрерывных случайных величин (НСВ), которые принимают любое значение, в некотором интервале, например, продолжительность работы электрической ламп, дальность полета снаряда, уровень воды в половодье и т.д.

Ниже дадим другое, более строгое, определение непрерывной случайной величины.

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

– указать все её возможные значения.

– задать вероятности, с которыми принимаются эти значения.

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

Он может иметь вид таблицы, формулы или графика.

Таблица, в которой перечислены возможные значения дискретной случайной величины и соответствующие им вероятности, называется рядом распределения (законом распределения):

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

.

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

Функцией распределения (интегральной функцией распределения) случайной величины называется вероятность того, что случайная величина примет значения, меньшие заданного значения , где — любое действительное число:

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

1. Значения функции принадлежит отрезку , т.е.

.

2. – неубывающая функция на всей числовой оси, т.е.

3. На минус бесконечности функция распределения равна нулю, на плюс бесконечности равна 1, т.е.

;

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

.

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

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

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

.

Математическое ожидание указывает точку на числовой оси, вокруг которой группируются возможные значения случайной величины. В определённом смысле эта точка является центром распределения вероятностей случайной величины. Заметим, что математическое ожидание случайной величины может не существовать.

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

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

.

Для вычисления дисперсии часто бывает удобно пользоваться следующей теоремой.

Теорема

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

.

Если – дискретная случайная величина, то дисперсию вычисляют по следующим формулам:

,

или

.

Для оценки рассеяния возможных значений случайной величины вокруг ее среднего значения кроме дисперсии служат и некоторые другие характеристики. К их числу относится среднее квадратическое отклонение.

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

.

Примеры дискретных распределений

Биномиальным называют закон распределения дискретной случайной величины – числа появлений события в независимых испытаниях (возможные значения случайной величины – ), в каждом из которых вероятность появления события равна ; вероятность возможного значения (числа появлений события ) вычисляют по формуле Бернулли:

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

;

;

.

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

Если число испытаний велико, а вероятность появления события в каждом испытании очень мала, то вместо формулы Бернулли пользуются формулой:

,

где – число появлений события в независимых испытаниях; , и говорят, что случайная величина распределена по закону Пуассона.

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

Числовые характеристики для закона Пуассона:

;

;

.

Примеры решения задач

Задача 1

Число очков, выбиваемых одним стрелком при одном выстреле, имеет закон распределения:

	2	3	4	5
	0,5	0,3	0,1

1) Определить значение ;

2) построить многоугольник распределения;

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

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

Решение

1) Для того, чтобы определить значение , воспользуемся условием нормировки:

значит,

;

Ряд распределения имеет вид:

	2	3	4	5
	0,5	0,3	0,1	0,1

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

Рис. 1 Многоугольник распределения

3) Возможные значения дискретной случайной величины : 2; 3; 4 и 5 разбивают все множество на промежутки:

.

Найдем значения – функции распределения дискретной случайной величины в каждом из этих промежутков:

1)

2)

3)

;

4)

;

5)

.

Следовательно,

Рис.2 График функции распределения

4) Числовые характеристики дискретной случайной величины:

;

;

.

Задача 2

Автомобиль на пути к месту назначения встретит 5 светофоров, каждый из которых пропустит его с вероятностью 0,3. Построить ряд распределения числа светофоров, пройденных машиной до первой остановки или до прибытия к месту назначения. Найти числовые характеристики данной случайной величины.

Решение

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

Общее число испытаний .

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

Вероятность наступления события в каждом испытании постоянна и равна ; вероятность ненаступления события равна .

Число появлений события в испытаниях равно ; согласно условию имеем .

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

Вероятности каждого из возможных значений найдем по формуле Бернулли:

Проверка, состоящая в нахождении суммы вероятностей , показывает, что сумма равна единице:

.

Рассматриваемая случайная величина имеет следующий ряд распределения:

	0	1	2	3	4	5
	0,16807	0,36015	0,3087	0,1323	0,02835	0,00243

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

.

Задача 3

Проверяется пария из 10 000 изделий. Вероятность того, что изделие окажется бракованным, равна 0,002. Найти вероятность того, что в партии есть хотя бы одно бракованное изделие. Найти математическое ожидание и дисперсию числа бракованных изделий в этой партии.

Решение

Событие – в партии содержится хотя бы одно бракованное изделие. Число опытов достаточно велико , а вероятность наступления события в каждом из них достаточно мала , поэтому можно считать, что случайная величина – число бракованных изделий – распределена по закону Пуассона.

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

,

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

,

где .

По условию задачи: , значит,

.

При ,

Значит,

.

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

;

.

Задачи для самостоятельного решения

Задача 1

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

	2	4	7
	0,3		0,2

1) Определить значение ;

2) построить многоугольник распределения;

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

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

Задача 2

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

Задача 3

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

Задача 4

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

Задача 5

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

Задача 6

Завод отправил на базу 2000 изделий. Вероятность повреждения изделия в пути равна 0,001. Найти вероятности того, что в пути будет повреждено:

1) ровно два изделия;

2) менее двух изделий;

3) более двух изделий;

4) хотя бы одно изделие.

Задача 7

Вероятность того, что стрелок попадет в мишень при одном выстреле, равна 0,8. Стрелку выдаются патроны до тех пор, пока он не промахнется. Требуется:

1) составить закон распределения дискретной случайной величины — числа патронов, выданных стрелку;

2) найти наивероятнейшее число выданных стрелку патронов.

Задача 8

На автобазе имеется десять автомашин. Вероятность выхода на линию каждой из них равна 0,8.

Найти:

1) вероятность того, что в определенный день на линию выйдут 9 автомашин;

2) вероятность нормальной работы автобазы в ближайший день, если для этого необходимо иметь на линии не менее восьми автомашин.

Задача 9

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

Требуется:

1) составить закон распределения случайной дискретной величины – числа дополнительных вопросов, которые задаёт преподаватель курсанту;

2) найти наивероятнейшее число заданных курсанту дополнительных вопросов.

Практическая работа №5 Решение задач по теории графов

Цель: Получить практические навыки, при представлении графов в матричной форме

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

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

Рис. 1.

Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V×V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Рис.2.

Например, кратность ребра {v₁, v₂} в графе, изображенном на рис. 2, равна двум, кратность ребра {v₃, v₄} − трем.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Граф − мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v,w) являются упорядоченными.

Ребра ориентированного графа называются дугами.

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или v_i)– вершина или номер вершины;

G, G₀ - неориентированный граф;

D, D₀ – ориентированный;

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

v,w - вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) - количество ребер, m(D) - количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v₁, v₂, v₃, v₄},

X={x₁=(v₁,v₂), x₂=(v₁,v₂), x₃=(v₂,v₂), x₄=(v₂,v₃)}.

Рис. 3.

2) Неориентированный граф G=(V, X), V={v₁, v₂, v₃, v₄, v₅},

X={x₁={v₁,v₂}, x₂={v₂,v₃}, x₃={v₂,v₄}, x₄={v₃,v₄}}.

Рис. 4.

Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w − концы ребра x.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}X.

Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число ⁺(v) (^(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в ⁺(v), так и в ^(v).

Маршруты и пути

Последовательность v₁x₁v₂x₂v₃...x_kv_k+1, (где k1, v_iV, i=1,...,k+1, x_iX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) x_j имеет вид {v_j,v_j+1} (для ориентированного графа (v_j,v_j+1)), называется маршрутом, соединяющим вершины v₁ и v_k+1 (путем из v₁ в v_k+1).

Пример

В графе, изображенном на рис.4, v₁x₁v₂x₂v₃x₄v₄x₃v₂ - маршрут, v₂x₂v₃x₄v₄ – подмаршрут;

маршрут можно восстановить и по такой записи x₁x₂x₄x₃ ;

если кратности ребер (дуг) равны 1, можно записать и так v₁v₂v₃v₄v₂ .

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

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

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

Матрицы смежности и инцидентности

Пусть D=(V,X) ориентированный граф, V={v₁,...,v_n}, X={x₁,...,x_m}.

Матрица смежности ориентированного графа D − квадратная матрица

A(D)=[a_ij] порядка n, где

Матрица инцидентности − матрица B(D)=[b_ij] порядка nm, где

Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[a_ij] порядка n, где

.

Матрица инцидентности графа G называется матрица B(G)=[b_ij] порядка nm, где

Связность. Компоненты связности

Подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).

Подграф называется собственным, если он отличен от самого графа.

Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w=v, либо существует путь (маршрут) из v в w.

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

Компонентой связности графа G (сильной связности ориентированного графа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (ориентированного графа D).

Матрицы достижимости и связности

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v₁,…, v_n}. Обозначим через A^k=[a^(k)_ij] k-ю степень матрицы смежности A(D).

Элемент a^(k)_ij матрицы A^k ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из v_i в v_j.

Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[t_ij] порядка n, элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[s_ij] порядка n, элементы которой равны

Пусть G=(V,X) – граф, V={v₁,…, v_n}, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A²+A³+… A^n-1] (E- единичная матрица порядка n).

Утверждение 3. Пусть D=(V,X) – ориентированный граф, V={v₁,…, v_n}, A(D) – его матрица смежности. Тогда

1. T(D)=sign[E+A+A²+A³+… A^n-1],

2. S(D)=T(D)T^T(D) (T^T-транспонированная матрица, - поэлементное умножение).

Расстояния в графе

Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.

Расстояние в графе удовлетворяют аксиомам метрики

1) ,

2) (не в ориентированном графе)

3)

4) в связном графе (не в ориентированном графе).

Пусть связный граф (или псевдограф).

Диаметром графа G называется величина .

Пусть .

Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .

Радиусом графа G называется величина

Центром графа G называется любая вершина такая, что .

Образ и прообраз вершины и множества вершин

Пусть ориентированный граф - некоторая вершина .

Обозначим - образ вершины ;

- прообраз вершины ;

- образ множества вершин V₁ ;

- прообраз множества вершин V₁.

Нагруженные графы

Нагруженный граф − ориентированный граф D=(V,X), на множестве дуг которого определена не которая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.

Обозначения: для любого пути П нагруженного ориентированного графа D через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

Если выбрать веса равными 1, то придем к ненагруженному графу.

Путь в нагруженном ориентированном графе из вершины v в вершину w, где vw, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный маршрут в нагруженном графе.

Введем матрицу длин дуг C(D)=[c_ij] порядка n, причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для  дуги , то  минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для  i,j : путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k+1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).

Деревья и циклы

Граф G называется деревом если он является связным и не имеет циклов.

Граф G называется лесом если все его компоненты связности - деревья.

Свойства деревьев:

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и не имеет простых циклов.

3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

4)  две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Утверждение 4. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Утверждение 5.Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Утверждение 6.Пусть G - дерево с n(G) вершинами и m(G) ребрами. Тогда m(G)=n(G)-1.

Утверждение 7.Пусть G – дерево. Тогда любая цепь в G будет простой.

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

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число − цикломатическое число графа G.

Примеры решения задач

Задание 1. Компоненты сильной связности ориентированного графа.

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

Cоставляем матрицу смежности A(D) размерности (n− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины v_i и входящая в v_j, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.

Алгоритм выделения компонент сильной связности

1. Присваиваем p=1 (p − количество компонент связности), .

2. Включаем в множество вершин V_p компоненты сильной связности D_p вершины, соответствующие единицам первой строки матрицы S_p. В качестве матрицы A(D_p) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V_p.

3. Вычеркиваем из S_p строки и столбцы, соответствующие вершинам из V_p. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как S_p+1, присваиваем p=p+1 и переходим к п. 2.

Пример

Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин n=5.

Рис. 6.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

.

Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:

, ,

,

Следовательно,

.

Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:

.

Присваиваем p=1 и составляем множество вершин первой компоненты сильной связности D₁: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S₁(D) строку и столбец, соответствующие вершине v₁, чтобы получить матрицу S₂(D):

.

Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S₂(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V₂:

.

Вычеркиваем из матрицы S₂(D) строки и столбцы, соответствующие вершинам из V₂ ,чтобы получить матрицу S₃(D), которая состоит из одного элемента:

и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:

D1:

D2:

D3:

Задание 2. Расстояния в ориентированном графе

С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

Пусть ориентированный граф с n2 вершинами и v,w (vw) – заданные вершины из V.

Алгоритм поиска минимального пути из в в ориентированном графе

(алгоритм фронта волны).

1. Помечаем вершину индексом 0, затем помечаем вершины  образу вершины индексом 1. Обозначаем их FW₁ (v). Полагаем k=1.

2. Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.

В противном случае продолжаем:

1. Если , то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин

есть этот минимальный путь. Работа завершается.

1. Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).

Замечания

• Множество называется фронтом волны k^го уровня.

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

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R(D)между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю (, i=1,..,n).

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

Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i-тая и на пересечении с j-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Примечание: В контрольной работе самый длинный путь найти при помощи алгоритма фронта волны.

Пример

Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин n=7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 7×7.

Рис.7.

Матрица смежности:

.

Начинаем заполнять матрицу R(D) минимальных расстояний: сначала ставим нули по главной диагонали и r_ij=a_ij, если a_ij=1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, , . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому . В итоге получаем следующую матрицу:

Таким образом, диаметром исследуемого ориентированного графа будет .

Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше : r(v_i) − максимальное из расстояний, стоящих в i-той строке. Таким образом,

r(v₁)=3, r(v₂)=3, r(v₃)=5, r(v₄)=4, r(v₅)=2, r(v₆)=2, r(v₇)=3.

Значит, радиусом графа G будет

Соответственно, центрами графа G будут вершины v₅ и v₆ , так как величины их эксцентриситетов совпадают с величиной радиуса.

Опишем теперь нахождение минимального пути из вершины v₃ в вершину v₆ по алгоритму фронта волны. Обозначим вершину v₃ как V₀, а вершину v₆  как W (см. рис. 8). Множество вершин, принадлежащих образу V₀, состоит из одного элемента  это вершина v₄, которую, согласно алгоритму, обозначаем как V₁: FW₁(v₃)={v₄}. Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня  это множество вершин, принадлежащих образу вершины V₁: FW₂(v₃)={v₇}, обозначаем v₇≡V₂. В образ вершины V₂ входят две вершины  v₅ и v₄, но, так как v₄ уже была помечена как V₀, то фронт волны третьего уровня состоит из одного элемента: FW₃(v₃)={v₅}, v₅≡V₃. Из непомеченных вершин в образ вершины V₃ входят v₁ и v₂, соответственно, FW₄(v₃)={v₁, v₂}, v₁≡V₄, v₂≡V₄. Теперь помечены все вершины, кроме v₆, которая входит в образ вершины , то есть FW₅(v₃)={v₆≡W}, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины v₃ в вершину v₆ выглядит так: v₃ v₄ v₇ v₅ v₁ v₆.

Рис.8.

Задания для самостоятельного решения

Задача 1

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

а)	б)	в)

Задача 2.

С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

а)	б)	в)

Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.

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

1.Что такое граф.

2. Как строятся матрицы смежности

3. Как строятся матрицы инциденций

4. Что такое изоморфизм графов

Практическая работа №6 Решение задач по теории массового обслуживания

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

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

Системы массового обслуживания с отказами

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

Имеется n каналов в обслуживании, на которые поступает поток заявок с интенсивностью λ. Поток обслуживания имеет интенсивность μ (величина, обратная среднему времени обслуживания ). Требуется найти вероятности состояний СМО и характеристики ее эффективности.

Так как оба потока – заявок и освобождений – простейшие, процесс, протекающий в системе, будет марковским. Рассмотрим ее как систему с конечным множеством состояний:

свободны все каналы;

занят ровно один канал;

…занятыk каналов;

…заняты все n каналов/

Через обозначим вероятность того, что в момент времени t система будет находиться в состоянии .

Простейшие задачи для систем массового обслуживания с отказами были впервые решены А.К. Эрлангом. Им же были выведены формулы оценки функционирования этих систем при условии поступления простейшего потока заявок и для показательного закона распределения времени обслуживания.

Для установившегося процесса обслуживания при этих условиях Эрланг получил следующие зависимости.

• Вероятность того, что обслуживанием заняты kаппаратов (линий, приборов и т.п.):

(1)

где k – количество занятых аппаратов,

λ – интенсивность потока заявок,

μ – интенсивность потока обслуживания.

Частные случаи:

• Вероятность простоя (того, что все обслуживающие аппараты свободны, нет заявок):

(2)

• Вероятность отказа (вероятность того, что все обслуживающие приборы заняты):

(3)

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

(4)

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

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

(5)

Доля каналов, занятых обслуживанием (коэффициент загрузки):

(6)

Пример решения задачи.

На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью λ = 4 заявки в минуту. Время обслуживания заявки одним каналом мин.

Найти показатели эффективности работы системы.

Решение.

Находим вероятность простоя трехканальной СМО по формуле (2):

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

Вероятность отказа определяем по формуле (3):

Относительная пропускная способность системы:

Абсолютная пропускная способность системы (среднее число заявок, обслуживаемых в единицу времени):

Среднее число занятых каналов (в ед. времени) определяем по формуле (5):

Доля каналов, занятых обслуживанием (формула (6)):

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

мин.

Системы массового обслуживания с неограниченным ожиданием

Пусть имеется n-канальная СМО с очередью, на которую не наложено ограничений ни по длине очереди, ни по времени ожидания. В силу неограниченности очереди каждая заявка рано или поздно будет обслужена, поэтому

Для СМО с неограниченной очередью накладывается ограничение .

Если это условие нарушено, то очередь растет до бесконечности, наступает явление «взрыва».

• Вероятность простоя (того, что все обслуживающие аппараты свободны, нет заявок):

(7)

• Вероятность занятости обслуживанием k каналов:

(8)

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

(9)

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

(10)

• Вероятность для заявки попасть в очередь есть вероятность занятости всех каналов, эта вероятность равна сумме вероятностей наличия очереди и занятости всех n каналов при отсутствии очереди:

(11)

• Среднее число занятых обслуживанием каналов:

(12)

• Доля каналов, занятых обслуживанием:

(13)

• Среднее число заявок в очереди (длина очереди)

(14)

• Среднее число заявок в системе

(15)

• Среднее время ожидания заявки в очереди

(16)

• Среднее время пребывания заявки в системе

(17)

Пример решения задачи.

На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью λ = 4 заявки в минуту. Среднее время обслуживания заявки ч.

Найти показатели эффективности работы системы.

Решение

Для рассматриваемой системы

Определяем вероятность простоя по формуле (4.7):

Среднее число заявок в очереди находим по формуле (14):

Среднее время ожидания заявки в очереди считаем по формуле (16):

ч.

Среднее время пребывания заявки в системе

ч.

Системы массового обслуживания с ожиданием и ограниченной длинной очереди

Имеется n-канальная СМО с ожиданием, в которой количество заявок, стоящих в очереди, ограничено числом m, т.е. заявка, заставшая все каналы занятыми, становится в очередь, только если в ней находится менее m заявок.

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

Системы с ограниченной очередью являются обобщением двух рассмотренных ранее СМО: при m = 0 получаем СМО с отказами, при m =  получаем СМО с ожиданием.

• Вероятность простоя (того, что все обслуживающие аппараты свободны, нет заявок):

(18)

• Вероятность отказа в обслуживании равна вероятности того, что в очереди уже стоят m заявок:

(19)

• Относительная пропускная способность есть величина, дополняющая вероятность отказа до 1, т.е. вероятность обслуживания:

(20)

• Абсолютная пропускная способность определяется равенством:

(21)

• Среднее число занятых обслуживанием каналов:

(22)

• Среднее число заявок в очереди (средняя длина очереди)

(23)

• Среднее время ожидания обслуживания в очереди

(24)

• Среднее число заявок в системе

(25)

• Среднее время пребывания заявки в системе

(26)

Пример решения задачи.

В парикмахерской работают 3 мастера, в зале ожидания расположено 3 стула. Поток клиентов имеет интенсивность λ = 12 клиентов в час. Среднее время обслуживания заявки мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.

Решение

Для данной задачи

Определяем вероятность простоя по формуле (18):

Вероятность отказа в обслуживании определим по формуле (19)

Относительная пропускная способность, т.е. вероятность обслуживания:

Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени):

Среднее число занятых обслуживанием каналов (парикмахеров):

Среднее число заявок в очереди (средняя длина очереди)

Среднее время ожидания обслуживания в очереди

ч.

Среднее число заявок в системе

.

Среднее время пребывания заявки в системе

ч.

Замкнутые системы массового обслуживания

До сих пор мы рассматривали системы, в которых входящий поток никак не связан с выходящим. Такие системы называются разомкнутыми. В некоторых же случаях обслуженные требования после задержки опять поступают на вход. Такие СМО называются замкнутыми.

Примеры:

• Поликлиника, обслуживающая данную территорию.

• Бригада рабочих, закрепленная за группой станков.

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

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

Пусть n – число каналов обслуживания, s – число потенциальных заявок, , λ –интенсивность потока заявок каждого потенциального требования,  – интенсивность обслуживания, . Поток

• Вероятность простоя (того, что все обслуживающие аппараты свободны, нет заявок):

(27)

• Финальные вероятности состояний системы

(28)

Через эти вероятности выражается среднее число замкнутых каналов:

или

(29)

Через находимабсолютную пропускную способность системы

(30)

а также среднее число заявок в системе

(31)

Пример решения задачи.

Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью λ = 0,5 отказа в час. Среднее время ремонта ч. Определить пропускную способность системы.

Решение

Эта задача рассматривает замкнутую СМО,

Вероятность простоя рабочего определяется по формуле (27):

Вероятность занятости рабочего

.

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

станков в час.

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

На практике часто встречаются; замкнутые системы обслуживания, у которых входящий поток заявок существенным образом зависит от состояния самой СМО. В качестве примера можно привести ситуацию, когда на ремонтную базу поступают с мест эксплуатации некоторые машины: понятно, что чем больше машин находится в состоянии ремонта, тем меньше их продолжает эксплуатироваться и тем меньше интенсивность потока вновь поступающих на ремонт машин. Для замкнутых СМО характерным является ограниченное число источников заявок, причем каждый источник «блокируется» на время обслуживания его заявки (т.е. он не выдает новых заявок). В подобных системах при конечном числе состояний СМО предельные вероятности будут существовать при любых значения интенсивностей потоков заявок и обслуживании. Они могут быть вычислены, если вновь обратиться к процессу гибели и размножения.

Задачи для самостоятельного решения

Вариант 1.

Станция «Железная дорога» в мегаполисе принимает составы для разгрузки угля на платформах. В среднем за сутки на станцию прибывают 16 составов с углем. Поступление носит случайный характер. Плотность прихода составов показала, что поступление на разгрузку удовлетворяет пуассоновскому потоку с параметром состава в час. Время разгрузки состава является случайной величиной, удовлетворяющей экспоненциальному закону со средним временем разгрузки час. Простой состава в сутки составляет y.e; простой платформы в сутки за опоздание прихода состава – y.e; стоимость эксплуатации платформы в сутки – y.e. Издержки подсчитать за сутки. Требуется провести анализ эффективности функционирования станции.

Вариант 2

Интернет-провайдер в небольшом городе имеет 5 выделенных каналов обслуживания. В среднем на обслуживание одного клиента уходит 25 минут. В систему в среднем поступает 6 заказов в час. Если свободных каналов нет, следует отказ. Определить характеристики обслуживания: вероятность отказа, среднее число занятых обслуживанием линий связи, абсолютную и относительную пропускные способности, вероятность обслуживания. Найти число выделенных каналов, при котором относительная пропускная способность системы будет не менее 0,95. Считать, что потоки заявок и обслуживаний простейшие.

Вариант 3

Порт имеет один причал для разгрузки судов. Интенсивность потока 0,4 в сутки, среднее время разгрузки одного судна 2 суток. В предположении неограниченности очереди определить показатели эффективности работы причала и вероятность ожидания разгрузки не более 2 судов.

Вариант 4

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

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

1. Перечислите основные характеристики системы массового обслуживания с отказами?

2. Дайте определение системы массового обслуживания с ограниченной очередью?

3. Определите процесс функционирования системы массового обслуживания с ограниченной очередью ?

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

5. В чем особенности замкнутых систем массового обслуживания?

25