ОТДЕЛЕНИЕ «Автоматизации, радиоэлектроники и ИКТ»

ПЦК ( КМК) 230111 Компьютерные сети

УТВЕРЖДАЮ

Зам. директора по УМР

                                                      _________________________Бозрова И.Г.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ  ПО ПРОВЕДЕНИЮ

 ПРАКТИЧЕСКИХ  ЗАНЯТИЙ

для специальности 230111 Компьютерные  сети

(по программе углубленной подготовки)

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

ПМ 01. Участие в проектировании сетевой инфраструктуры

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

преподаватель ГБОУ СПО Колледж связи №54                            Казиханов Ф.И.

Методические указания рассмотрены и одобрены на заседании ПЦК ( КМК) спец. 230111 Компьютерные сети

протокол №___ от «__»_______. 2014 г.

Председатель ПЦК ____________         С.Н. Хохлов

Содержание

1.        Общие положения        

2.        Методика и средства выполнения практических работ        

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

4.        Тематика практических работ и задания к ним        

5.        Учебно-методическое и информационное обеспечение дисциплины        

1. Общие положения

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

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

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

ПР.1. Решение задач на тему: Матрица инцидентности. Изоморфизм графов.

ПР.2. Решение задач на тему: Элементы графов и орграфов: путь, длина,

источники, стоки, степени вершин. Деревья. Эйлеров цикл. Плоские и планарные графы

ПР.3. Решение задач на тему: Алгоритм поиска кратчайшего пути.  Алгоритм Белламана-Форда (геометрический и аналитический способ задания).

ПР.4. Решение задач на тему: Алгоритм поиска кратчайшего пути. Алгоритм  Дейкстры   (геометрический и аналитический способ задания).

1. ПР.5. Решение задач на тему: Алгоритм поиска кратчайшего пути.  Алгоритм Флойда-Уоршелла.

ПР.6. Решение задач на тему: Случайные события.

ПР.7. Решение задач на тему: Правило суммы и правило произведения — основные комбинаторные принципы.

ПР.8. Решение задач на тему: Задачи  на перестановки, размещения и сочетания.

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

ПР.10. Решение задач на тему: Математическое ожидание и дисперсия дискретной случайной величины

ПР.11. Решение задач на тему: Применение неравенств Маркова и  Чебышева для решения комбинаторных задач.

ПР.12. Решение задач на тему: Распределение Пуассона. Гауссовское распределение.

ПР.13. Решение задач на тему: Системы массового обслуживания.

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

1. уметь:

• Применять алгоритмы поиска кратчайшего пути;
• Планировать структуру сети с помощью графа с оптимальным расположением узлов;
•  Использовать математический аппарат теории графов;

2. знать:

• Вероятностные и стохастические процессы;
• Элементы теории массового обслуживания;
• Основные соотношения теории очередей;
• Основные понятия теории графов;
• Алгоритмы поиска кратчайшего пути;
• Основные проблемы синтеза графов атак;
• Построение адекватной модели;
• Система топологического анализа защищенности компьютерной сети;
• Архитектуру сканера безопасности;
• Экспертные системы.

3. актуализировать  общие и профессиональные компетенции:

2. Методика и средства выполнения практических работ

Выбор содержания и объем конкретной практической работы обусловлен сложностью учебного материала для усвоения, междисциплинарными связями и учетом значения конкретной практической работы для приобретения обучающимися соответствующих умений и компетенций, предусмотренных ФГОС.

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

Средством проведения практических работ  являются:

• Комплект персональных ЭВМ в  компьютерных классах, с выходом в ГКС Интернет;

Комплекс программного обеспечения:

• операционная система Windows ХР, Vista и др.;

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

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

• настоящие Методические указания.

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

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

1. Постановка задачи практической работы

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

2.  Ознакомление студента с содержанием и объемом практической работы.

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

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

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

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

3. Регистрация результатов и оформление отчета по практической работе.

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

Отчет по каждой практической  работе составляется по  следующей обобщенной  структуре:

• Наименование идентифицирующих признаков: «Отчет по практической работе №_____ по теме (наименование темы)».
• Студента (указываются фамилия и инициалы, курс, группа).
• Цель работы. Формулируется в соответствии с содержанием раздела «Цель работы», соответствующей практической работы.
• Необходимые принадлежности; задание; методика  работы. Определяется в соответствии с указанной выше формулировкой и при необходимости уточняется в зависимости от содержания конкретной практической работы.
• Этапы выполнения работы. Приводятся номера и наименования этапов работы,  указанные выше. Последовательно по каждому из этапов приводится характеристика содержания выполненных по этапу работ.
• Выводы по работе. К этой части работы студент должен быть особенно внимательным. Формулируются выводы теоретического и практического характера о выполненной практической работе. Обычно выводы излагаются последовательно по каждому из этапов работы (отчета) – 1-2 вывода. Выводы формулируются в сжатой и  четкой форме. Вывод должен содержать сжатую мысль о выполненном этапе работы, как результат аналитико-синтетической переработки содержания выполненного этапа. Не следует указывать в выводах содержание и объем выполненных работ.

Текст отчета должен быть изложен лаконично и вместе с тем информативно с соблюдением правил грамматики. В конце отчета может быть указана литература, которую студент применил в практической работе. Библиографические описания  литературных источников  должны быть оформлены в соответствии с ГОСТ 7.1-84. Правила библиографического описания документации.

4.  Заключительная часть практической работы.

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

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

4. Тематика практических занятий и задания к ним

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

Решение задач по теории графов. Матрица инцидентности. Изоморфизм графов.

1. Цель занятия:

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

2. Продолжительность занятия: 4 часа
3. Необходимые принадлежности:

• ПК, подключенный к ГКС
• Методические рекомендации

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

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

В случае ориентированного графа каждой дуге ставится в соответствие "-1" в строке вершины x и столбце дуги и "1" в строке вершины y и столбце дуги ; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".

Графы G’ и G’’ называются изоморфными, если существует взаимно-однозначное соответствие (биекция) между их ребрами и вершинами, причем ребра соединяют соответствующие вершины.

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

Пример:

5. Задания:

Решите ниже перечисленные задачи

6. Порядок выполнения практической работы

Задача 1.  

Построить матрицы смежности и инцидентности для графа G = (V, X)

Задача 2

Построить матрицы смежности и инцидентности для  орграфа D= (V, X)

Задача 3. 

Задана матрица

Нарисовать на плоскости орграф G = ( X, U ), единственный с точностью до изоморфизма, имеющий заданную матрицу В своей матрицей смежности. Найти матрицу инцидентности   С=С ij  орграфа G.

Задача 4

Задана симметрическая матрица А неотрицательных целых чисел.

А=

1. Нарисовать на плоскости граф G=(X,U)(единственный с точностью до

изоморфа), имеющий заданную матрицу А своей матрицей смежности. Найти

матрицу инцидентности  R= (r ij) графа G.

2. Нарисовать на плоскости орграф G=(X,U) (единственный с точностью до

изоморфизма), имеющий заданную матрицу А свое матрицей смежности. Найти

матрицу инцидентности C=(Cij) орграфа G.

Задача5.

Эйлерову цепь в неориентированном графе G, изображенном на рис.

Задача 6

Задан граф где   

1. Задайте граф с помощью бинарного отношения, т. ею совокупности множества V  и подмножества множества упорядоченных пар

2. Изобразите орграф на рисунке.

3. Постройте матрицу смежности.

Оформите и сдайте отчет

7. Содержание отчета:

1. Номер и тема лабораторной работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения лабораторной работы (этапы);
5. Выводы по выполненной работе.

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

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

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

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

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

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

Решение задач по теории графов. Элементы графов и орграфов: путь, длина, источники, стоки, степени вершин. Деревья. Эйлеров цикл. Плоские и планарные графы

1. Цель занятия:

• Получить практические навыки построения графов

• Сформировать представление об основных понятиях теории графов.

• Отработать на примерах основные понятия теории графов

2.  Продолжительность занятия: 4 часа.

3.  Необходимые принадлежности

• ПК, подключенный к ГКС;
• Методические указания.

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

Степенью или валентностью вершины p n графа Г, обозначаемой через d n , называют число рёбер (дуг), инцидентных этой вершине. Вершина степени 1 называется висячей или концевой. Ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется изолированной. По определению петля при вершине p n , добавляет 2 в степень соответствующей вершины.

Маршрут в графе Г представляет собой конечную чередующуюся последовательность вершин и рёбер. Маршрут называется открытым, если его концевые вершины различны, в противном случае он называется замкнутым. Маршрут называется цепью, если все его рёбра различны. Цепь называется элементарной, если при обходе по какому-нибудь направлению каждая вершина цепи встречается только один раз. Замкнутый маршрут образует цикл. Цикл может быть простым, если он содержит отличные друг от друга рёбра, сложным – в противном случае, элементарным, если при обходе по какому-нибудь направлению каждая вершина цикла встречается только один раз. Очевидно, нет смысла вводить для цепи термин “простая цепь”, если термин “простой”, как в определении графа и цикла, означает отсутствие повторяющихся рёбер.

Последовательность дуг, при которой конец одной дуги является началомдругой, называется путём. Если начальная и конечная точки путисовпадают, образуется контур. Длиной пути (или контура) называют число дуг, которые его образуют. Петля – контур единичной длины. Будем также под длиной пути от одной вершины до другой понимать количество рёбер, входящих в соответствующий маршрут. То есть будем применять термин “длина пути” не только к орграфам. Во всех случаях для орграфов и для неориентированных графов дуги и рёбра будем считать столько раз, сколько раз они входят в путь или маршрут.

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

Лес - упорядоченное множество упорядоченных деревьев.

Эйлеров цикл — это цикл графа, проходящий через каждое ребро (дугу) графа ровно по одному разу

Планарный граф — граф, который может быть изображён на плоскости без пересечения ребер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, т.е. графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями.

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

5. Задание

 В следующих задачах найти путь, длину графа, установить планарность графа

6. Порядок выполнения работы

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

Задача 1.

Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо "красный", либо "синий" граф не является плоским.

Задача 2.

Найти все пути из Х4 в Х7 в графе G=(Х,Г) изображенном на рисунке.

Задача 3.

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

Задача 4.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Задача 5.

Найдите Эйлерову цепь в неориентированном графе G.

Задача 6.

Найдите эйлеров цикл в эйлеровом графе.

Задача 7.

Постройте эйлеров цикл для второго графа

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

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

2. Докажите, что изоморфизм сохраняет циклы графа.

3. На основании решения какой задачи Леонард Эйлер вывел постулаты теории графов.

4. Чему равна степень изолированной вершины.

5. Что такое петля.

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

Решение задач по теории графов. Алгоритм поиска кратчайшего пути. Алгоритм Беллмана-Форда (геометрический и аналитический способ задания).

1. Цель занятия:

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

        Нахождение кратчайшего пути в ориентированных и неориентированный графах

2. Продолжительность занятия: 4 часа.

3. Необходимые принадлежности

1. Персональный компьютер, подключенный к ГКС.
2. Методические указания.

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

Зада́ча о кратча́йшем пути́ (англ. shortest path problem) — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.

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

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

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

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

• Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
• Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
• Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

5. Задание.

        С помощью алгоритма Беллмана — Форда найти решения задач.

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

6.  Порядок выполнения работы.

Задача 1.

Определить наименьшую стоимость проезда из 1 в s менее чем с k пересадками.

Реализовать алгоритм на языке программирования С++ и Pascal

Задача 2.

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

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

Реализовать алгоритм на языке программирования С++ и Pascal.

Задача 3.

В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход - в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Реализовать алгоритм на языке программирования С++ и Pascal.

Задача 4.

Во входном файле в первой строке записано число N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках находится по N чисел - матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Реализовать алгоритм на языке программирования С++ и Pascal.

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

1. Чем отличается кратчайший путь от остова

2. Какими языками программирования реализуется алгоритм Беллмана-Форда

3. Путь прохождения алгоритма Беллмана-Форда от первоначальной вершины до остальных.

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

Решение задач по теории графов. Алгоритм поиска кратчайшего пути. Алгоритм Дейкстры (геометрический и аналитический способ задания).

1. Цель занятия:

• Получить практические навыки при программировании и построении алгоритмов поиска кратчайшего пути

• Нахождение кратчайшего пути в ориентированных и неориентированный графах

2. Продолжительность занятия: 4 часа.

3. Необходимые принадлежности

3. Персональный компьютер, подключенный к ГКС.
4. Методические указания.

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

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Время работы алгоритма Дейкстры

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.

• В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
• Для разреженных графов (то есть таких, для которых m много меньше n2) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из U станет log n, при том, что время модификации d[i] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(n*log n + m*log n)
• Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(log n), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(n*log n + m)

Блок-схема алгоритма Дейкстры

5. Задание

Найти с помощью алгоритма Дейкстры кратчайшие пути в графах.

6. Порядок выполнения работы

Задача 1.

Найти расстояния от 1-й вершины до всех остальных.

Реализовать алгоритм на языке программирования С++ и Pascal.

Задача 2.

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

Реализовать на языке программирования С++ и Pascal

Задача 3.

Пусть Г(Х, U, Ф) — простой орграф, для каждого ребра u  U определен вес w(u)≥0.

Найти кратчайший путь между выделенными вершинами x0 и z.

Задача 4.

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

Оформите отчет, сделайте выводы по работе.

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

• Номер и тема практической работы;
• Цель работы;
• Необходимые принадлежности; задание; методика работы;
• Ход выполнения практической работы (этапы);
• Выводы по выполненной работе.

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

1. Достоинства и недостатки алгоритма Дейкстры

2. Основное отличие алгоритма Дейкстры от алгоритма Беллмана-Форда.

3. В чем заключается сложность алгоритма Дейкстры

4. Что такое отрицательный вес ребра

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

Решение задач по теории графов. Алгоритм поиска кратчайшего пути. Алгоритм Флойда-Уоршелла.

1. Цель занятия:

• Получить практические навыки при программировании и построении алгоритмов поиска кратчайшего пути.
• Нахождение кратчайшего пути в ориентированных и неориентированный графах

2. Продолжительность занятия: 4 часа.

3. Необходимые принадлежности

5. Персональный компьютер, подключенный к ГКС.
6. Методические указания.

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

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом, хотя в 1959 году Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Более строгая формулировка этой задачи следующая:
есть ориентированный граф G = (V, Е) каждой дуге v -> w этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин v, w) любого пути от вершины v в вершины w, длина которого минимальна среди всех возможных путей от v к w.

Оценка сложности алгоритма.

Время выполнения этой программы имеет порядок 0(V3), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого.

5. Задание.

С помощью алгоритма Флойда-Уоршилла найти решения следующих задач.

6. Порядок выполнения работы

Задача 1.

Необходимо найти кратчайшие пути между каждой парой вершин в графе, представленном на рисунке:

Задача 2.

Дан непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Задача3. 

Дан ориентированный взвешенный граф G = (V, E) c весовой функцией  w: E→ R. Для каждой пары вершин u, vÎ V требуется найти кратчайший путь из u в v, т.е. путь наименьшей длины (длина пути определяется как сумма весов всех его ребер). Таким образом,  ответом в задаче о кратчайших путях можно считать таблицу, в которой на пересечении строки u и столбца v находится вес кратчайшего пути из u в v (конечно, дополненную информацией о самих путях).

Задача 4.

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

Задача 5.

Задан взвешенный ориентированный граф (не более 100 вершин) без циклов отрицательного веса. Заданы m запросов вида (i; j). На каждый такой запрос требуется вывести длину кратчайшего пути из вершины i в вершину j.

Оформите отчет, сделайте выводы по работе.

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

1) Номер и тема практической работы;

2) Цель работы;

3) Необходимые принадлежности; задание; методика работы;

4) Ход выполнения практической работы (этапы);

5) Выводы по выполненной работе.

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

1. Что такое динамический алгоритм

2. Дайте характеристику понятия «время выполнения алгоритма»

3. Вложенные друг в друга циклы.

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

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

1. Цель занятия:

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

2. Продолжительность занятия: 4 часа.

3. Необходимые принадлежности

• Персональный компьютер.
• Методические указания.

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

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

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

Систематическое изложение статистических понятий и законов составляет содержание математической дисциплины «теория вероятностей» и специальных разделов физики (статистическая механика, статистическая радиофизика и т.п.)

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

Случайное событие. Познакомимся с этим понятием на примере случайных явлений, которые можно наблюдать в опытах с доской Гальтона. Это доска, поставленная вертикально, в которую набито много гвоздей. На гвозди можно бросать через воронку дробинки или сыпать зерна. Упавшие частицы попадают в ряд ячеек, расположенные  внизу. Бросим дробинку в воронку доски Гальтона. Она совершит сложный путь по гвоздям и упадет в одну из ячеек. Проделаем много раз такой опыт, соблюдая с максимальной тщательностью неизменность условий опыта, и убедимся, что опыты невозможно абсолютно точно воспроизвести. Дробинки летят по-разному. Попадание одной дробинки в какую-то ячейку назовем событием. Чтобы выразить то обстоятельство, что при самом тщательном соблюдении постоянства контролируемых внешних условий дробинки летят по разным путям, которые нельзя до опыта предсказать, говорят: падение дробинки – случайное событие.

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

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

Относительная частота и вероятность события. Произведем бросание частицы на доску Гальтона N раз. (Можно бросать одну частицу N раз или N одинаковых частиц один раз.) Каждое такое бросание называют испытанием. Обозначим через Nk число испытаний, при которых частица попадает в ячейку с номером k. Отношение Nk/N называется относительной частотой события, заключающегося в попадании частицы в ячейку k. Если произвести несколько серий испытаний с N опытами в каждой серии, то обнаружится, что относительная частота – случайная величина, но чем больше N, тем меньше она меняется от серии к серии. Иначе говоря, Nk/N слабо флюктуирует при большом N. Это свойство будем называть устойчивостью относительной частоты события. Устойчивость относительных частот при большом числе испытаний– частный случай проявления основного статистического закона, который называют законом больших чисел.

5. Задания.

При помощи формального аппарата теории вероятности решить следующие задачи

6. Порядок выполнения работы

Задача1. 
Даны следующие события:

А={при бросании монеты выпадает "орел"};

В={при бросании кубика  выпадает тройка};

С={при бросании кубика  выпадает  шестерка};

D={из колоды карт вытянут карту красной масти};

Е={из колоды карт вытянут туза};

F={из колоды карт вытянут пику}.

Определите, какие из следующих событий более вероятные, какие -  менее вероятные, и расположите их на вероятностной шкале.

Задача 2.

Какова вероятность того, что «доминошка», наудачу извлеченная из полного набора домино, имеет сумму очков, равную  5?

Задача 3.

Одновременно бросают два кубика.

а)  Сколько равновозможных исходов у этого эксперимента?

б)  Какова вероятность того, что на кубиках выпадет равное количество очков?

в) Какова вероятность, что на первом кубике выпадет количество очков больше, чем на втором?    

г)  Какая сумма будет выпадать чаще   5 или 6?

Задача 4.

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

Задача 5.

Из 20 экзаменационных билетов 3 содержат простые вопросы. Пять студентов по очереди берут билеты. Найти вероятность того, что хотя бы одному из них достанется билет с простыми вопросами.
Задача 6.

Из множества всех последовательностей длины 10, состоящих из цифр 0; 1; 2; 3, наудачу выбирается одна. Какова вероятность того, что выбранная последовательность содержит ровно 5 нулей, причем два из них находятся на концах последовательности.

Задача 7.

Имеется 100 одинаковых деталей, среди которых 3 бракованных. Найти вероятность того, что взятая наудачу деталь без брака.

Задача 8.

Код банковского сейфа состоит из 6 цифр. Найти вероятность того, что наудачу выбранный код содержит различные цифры?

Задача 9.

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

а) все трое акционеров с привилегированными акциями отсутствуют;
б) двое присутствуют и один не явился.

Оформите отчет, сделайте выводы по работе.

7. Содержание отчета:

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

• Что такое событие?

• Что такое вероятность наступления события?
• Что такое абсолютный результат.
• Охарактеризуйте термин испытание.

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

Решение задач по комбинаторике. Правило суммы и правило произведения — основные комбинаторные принципы.

1. Цель занятия:

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

2.  Продолжительность занятия: 4 часа

3.  Необходимые принадлежности

• ПК, подключенный к ГКС;
• Методические указания.

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

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

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

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

• Правило суммы 

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

        Правило произведения 

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

5. Задание.

С помощью правил суммы и произведения решить следующие задачи

6. Порядок выполнения работы.

Задача 1.

Сколько существует трехзначных чисел, начинающихся с 3 или 4? Трехзначные числа, о которых идет речь в задаче, разбиваются на два непересекающихся класса. К одному из них относятся числа, начинающиеся с 3, а ко второму - с 4. Для подсчета чисел в первом классе заметим, что существует один возможный исход для первой цифры (она должна быть равна 3), 10 исходов для второй и 10 исходов для последней цифры.

Задача 2.

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

Задача 3.

Ребенку предложили мешок с конфетами трех наименований: «Мишка на севере» (А), «Карамель» (В) и «Шоколад» (С). Сколькими способами ребенок может выбрать две конфеты из мешка?

Задача 4.

Целые числа в компьютере представляются строчкой из N двоичных знаков. Первый из них отведен на знак (+ или -), а остальные N - 1 отвечают за модуль целого числа. Сколько различных целых чисел может использовать компьютер?

Задача 5.

По меню в ресторане можно выбрать ровно три из семи главных блюд. Сколькими способами Вы можете сделать заказ?

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

• Что изучает комбинаторика как наука?
• Основные комбинаторные правилам
• Что такое выборка?

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

Решение задач по теории вероятностей. Задачи на перестановки, размещения и сочетания.

1. Цель занятия:

• Научиться решать задачи, используя правила комбинаторики;
• Решать задачи, используя операции над множествами;

2.  Продолжительность занятия: 4 часа.

3.  Необходимые принадлежности

1. ПК с ОС Windows XP;
2. Методические указания.

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

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

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

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

5. Задания

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

6. Ход выполнения работы:

Задача 1.

Пусть даны цифры: 7; 8; 9; 4; 5; 6. Определить сколько двузначных чисел можно составить из этих цифр.

Задача 2.

На библиотечной полке стоят 30 книг, причем 27 - книги разных авторов и еще 3 книги автора. Сколькими способами можно расставить эти книги так, чтобы книги одного автора стояли рядом друг с другом?

Задача 3.

Учитель хочет назначить 3 студентов для уборки класс из учеников. Сколькими способами можно это сделать?

Задача 4.

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

Задача 5. 

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

Задача 6.

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

Задача 7.

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

Задача 8.

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

Задача 9.

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

Задача 10.

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

Оформите отчет, сделайте выводы по работе.

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

6. Номер и тема практической работы;
7. Цель работы;
8. Необходимые принадлежности; задание; методика работы;
9. Ход выполнения практической работы (этапы);
10. Выводы по выполненной работе.

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

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

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

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

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

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

1. Цель занятия

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

2. Продолжительность занятия: 4 часа

3.  Необходимые принадлежности

• ПК с ОС Windows XP;
• Методические указания.

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

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

• Если событие А произошло, то это может изменить вероятности гипотез B_1, B_2, ..., B_n которые вычисляются по формуле Байеса (формуле Бейеса):
• Вероятности исходных событий  называются априорными вероятностями. Вероятности этих событий в предположении, что А наступило -  - апостериорными вероятностями.

5. Задание.

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

6. Ход выполнения работы

Задача 1.

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

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

того, что на зеленой карточке изображен треугольник, равна 0,85. Для белой карточки эта вероятность равна 0,9. Найти вероятность того, что наудачу взятая карточка будет содержать треугольник, если в эксперименте используется одинаковое количество карточек зеленого и белого цветов

Задача 2.

Прибор, установленный на борту самолета, может работать в двух режимах: в условиях нормального крейсеровского   полёта и в условиях перегрузки при взлете и посадке. Крейсерский режим полета составляет 80% всего времени полёта, условия перегрузки–20%. Вероятность выхода прибора из строя за время полета в нормальном режиме равна 0,1, в условиях перегрузки–0,4. Найти вероятность того, что прибор не откажет в течение всего полёта.

Задача 3.

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

Найти вероятность того, что: а) этот шар окажется белым,

б) белый шар вынут из второй урны.

Задача 4

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

Задача 5

На вход радиолокационного устройства с вероятностью 0,8 поступает смесь полезного сигнала с помехой, а с вероятностью 0,2 – только помеха. Если поступает полезный сигнал с помехой, то прибор регистрирует наличие какого -

то сигнала с вероятностью 0,7; если только помеха – то с вероятностью 0,3. Известно, что устройство зарегистрировало наличие какого - то сигнала. Найти вероятность того, что в его составе есть полезный сигнал

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

• Понятие условной вероятности.
• Несовместные события.
• Что такое априорная вероятность?
• Дайте определение понятия гипотеза.

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

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

1. Цель занятия:

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

2.  Продолжительность занятия: 4 часа.

3.  Необходимые принадлежности

1. Персональный компьютер, подключенный к ГКС.
2. Методические указания.

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

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

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

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

Пример 1. Случайной величиной является число очков, выпавших при бросании игральной кости, или рост случайно выбранного из учебной группы студента. В первом случае мы имеем дело с дискретной случайной величиной (она принимает значения из дискретного числового множества M={1, 2, 3, 4, 5, 6}; во втором случае - с непрерывной случайной величиной (она принимает значения из непрерывного числового множества - из промежутка числовой прямой I=[100, 3000]).

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

Если дискретная случайная величина принимает только значения x1, x2, ..., xn, вероятности которых соответственно равны p1, p2, ..., pn . Тогда математическим ожидание определяется равенством:

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

5. Задание.

Применив математическое ожидание решите следующие задачи.

6. Ход выполнения работы

Задача 1.

Выпущено 1000 лотерейных билетов: на 5 из них выпадает выигрыш в сумме 500 рублей, на 10 – выигрыш в 100 рублей, на 20 – выигрыш в 50 рублей, на 50 – выигрыш в 10 рублей. Определить закон распределения вероятностей случайной величины X – выигрыша на один билет.

Задача 2.

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

Задача 3.

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

Задача 4.

На полке из 6 книг 3 книги по математике и 3 по физике. Выбирают наудачу три книги. Найти закон распределения числа книг по математике среди выбранных книг. Найти математическое ожидание этой случайной величины.

Задача 5. 

На элеватор прибыло  машин агрофирмы «А1» и  машин агрофирмы «А2». Под разгрузку случайным образом загоняются  машин. Число машин фирмы «А1», попавших под разгрузку -случайная величина.

1) составить рад распределения этой случайной величины.

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

3) найти математическое ожидание, дисперсию и среднеквадратическое отклонение этого распределения.

4) определить коэффициент асимметрии.

Задача 6.

Из поступающих в ремонт 10 часов 7 нуждаются в общей чистке механизма. Часы не рассортированы по виду ремонта. Мастер, желая найти часы, нуждающиеся в чистке, рассматривает их поочередно и, найдя такие часы, прекращает дальнейший просмотр. Составить закон распределения числа просмотренных часов. Найти математическое ожидание и дисперсию этой случайной величины.

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

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

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

Решение задач по распределениям. Применение неравенств Маркова и Чебышева для решения комбинаторных задач.

1. Цель занятия:

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

2.  Продолжительность занятия: 4 часа.

3.  Необходимые принадлежности

• Персональный компьютер с ОС Windows XP.
• Методические указания.

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

Если случайная величина X принимает только неотрицательные значения и имеет математическое ожидание M(X),  то для любого положительного A верно неравенство:

Это выражение читается и понимается следующим образом: вероятность того, что случайная величина X в результате испытания примет значение большее A, где A – произвольное положительное число, не превышает величины  где M(X) – математическое ожидание случайной величины X.

Неравенство Маркова может быть записано и в другой форме: 

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

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

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

Неравенство Чебышева может быть представлено и в другой форме:

5. Задание.

По неравенствам Маркова и Чебышева оценить вероятность отклонения случайной величины от ее математического ожидания.

6. Ход выполнения работы.

Задача 1.

За сутки на станцию скорой помощи поступает в среднем 500 вызовов. Определить вероятность того, что за следующие сутки на станцию поступит     а) более 600 вызов; б) не более 800 вызовов.

Задача 2. 

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

Задача 3.

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

Задача 4.

Измеряется длина деталей в партии, состоящей из 100 одинаковых ящиков. Для определения средней длины детали из каждого ящика взяли по одной. Оценить вероятность того, что средняя длина 100 отобранных деталей отличается от средней длины деталей во всей партии не более, чем на 5 (ед. длины) по абсолютной величине, если известно, что среднее квадратическое отклонение длины детали в каждом ящике менее 7 (ед. длины).

Задача 5.

Используя неравенство Чебышева, оценить вероятность того, что , если .

Задача 6.

Дано: . Используя неравенство Чебышева, найти .

Оформите отчет, сделайте выводы по работе.

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

• Номер и тема лабораторной работы;

• Цель работы;

• Необходимые принадлежности; задание; методика работы;

• Ход выполнения лабораторной работы (этапы);

• Выводы по выполненной работе.

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

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

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

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

1. Цель занятия:

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

2.  Продолжительность занятия: 2 часа.

3.  Необходимые принадлежности

• Персональный компьютер, оптический диск.
• Методические указания.

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

Распределение Пуассона

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

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

Случайное число событий, происшедших за время от 0 до Т, распределено по закону Пуассона с параметром  l=аТ, где а>0 – параметр задачи, отражающий среднюю частоту событий. Вероятность k покупок в течение большого интервала времени,  (например, – дня)  составит 

P(Z=k) =

Нормальное (гауссовское) распределение

Нормальное (гауссовское) распределение занимает центральное место в теории и практике вероятностно-статистических исследований. В качестве непрерывной аппроксимации к биномиальному распределению его впервые рассматривал А.Муавр в 1733 г. Через некоторое время нормальное распределение снова открыли и изучили К.Гаусс (1809 г.) и  П.Лаплас, которые пришли к нормальной функции в связи с работой по теории ошибок наблюдений.

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

где   совпадает с математическим ожиданием величины Х:  =М(Х), параметр s совпадает со средним квадратическим отклонением величины Х: s =s(Х). График функции нормального распределения, как видно из рисунка, имеет вид куполообразной кривой, называемой Гауссовой, точка максимума имеет координаты (а;  ). Значит, эта ордината убывает с возрастанием значения s (кривая «сжимается» к оси Ох) и возрастает с убыванием значения s (кривая «растягивается» в положительном направлении оси Оу). Изменение значений параметра   (при неизменном значении s) не влияет на форму кривой, а лишь перемещает кривую вдоль оси Ох.

Нормальное распределение с параметрами  =0 и s=1 называется нормированным. Функция распределения СВ в этом случае будет иметь вид:

5. Задание

Решить задачи теории распределения применяя Гауссовское распределение и распределение Пуассона.

6. Ход выполнения работы.

Задача 1.

Микропроцессор имеет 10000 ранзисторов, работающих независимо друг от друга. Вероятность того, что транзистор выйдет из строя во время работы прибора, является величиной маловероятной и составляет 0,0007. Определить математическое ожидание М (Х) и среднее квадратическое отклонение S (Х) случайной величины Х — числа транзисторов, выйдут из строя во время работы процессора.

Задача 2.

В рыбацком городке 99,99% мужчин хотя бы раз в жизни были на рыбалке. Проводят социологические исследования среди 10000 наугад выбранных мужчин. Определить дисперсию D (X) и среднее квадратическое отклонени S (Х) случайной величины Х — числа мужчин, которые ни разу не были на рыбалке.

Задача 3.

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

Задача 4.

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

Задача 5.

В магазин привезли 300 стеклянных бутылок с минеральной водой. Известно, что в среднем при перевозке одна из 500 бутылок разбивается. Составить закон распределения случайной величины – числа разбитых бутылок в привезенной партии. Найти числовые характеристики этой случайной величины.

Задача 6.

Случайная величина Х распределена по закону Пуассона. Найти математическое ожидание, дисперсию и , если а=4.

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема практической работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения практической работы (этапы);
5. Выводы по выполненной работе.

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

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

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

Решение задач по системе массового обслуживания. Системы массового обслуживания

1. Цель занятия:

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

2. Продолжительность занятия: 2 часа

3. Необходимые принадлежности

1. Персональный компьютер, оптический диск.
2. Методические указания.

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

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

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

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

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

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

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

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

5. Задание. 

Решить задачи используя математический аппарат построения  СМО.

6. Ход выполнения работы.

Задача 1.

На диспетчерский пульт поступает поток заявок, который является потоком Эрланга второго порядка. Интенсивность потока заявок равна 6 заявок в час. Если диспетчер в случайный момент оставляет пульт, то при первой же очередной заявке он обязан вернуться к пульту. Найти плотность распределения времени ожидания очередной заявки и построить ее график. Вычислить вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут.

Задача 2.

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

Задача 3.

В двухканальную систему массового обслуживания (СМО) с отказами поступает стационарный пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону с параметром λ=5 заявок в минуту. Длительность обслуживания каждой заявки равна 0,5 мин. Методом Монте-Карло найти среднее число обслуженных заявок за время 4 мин. Указание: провести три испытания.

Задача 4.

Интенсивность потока телефонных звонков в агентство по заказу железнодорожных билетов, имеющему один телефон, составляет 16 вызовов в час. Продолжительность оформления заказа на билет равна 2.4 минуты. Определить относительную и абсолютную пропускную способность этой СМО и вероятность отказа (занятости телефона). Сколько телефонов должно быть в агентстве, чтобы относительная пропускная способность была не менее 0,75.

Задача 5.

Система массового обслуживания — билетная касса с одним окошком и неограниченной очередью. Касса продает билеты в пункты А и В. Пассажиров, желающих купить билет в пункт А, приходит в среднем трое за 20 мин, в пункт В — двое за 20 мин. Поток пассажиров простейший. Кассир в среднем обслуживает трех пассажиров за 10 мин. Время обслуживания — показательное. Вычислить финальные вероятности Р0, P2, P3, среднее число заявок в системе и в очереди, среднее время пребывания заявки в системе, среднее время пребывания заявки в очереди.

Оформите отчет, сделайте выводы по работе.

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

1. Номер и тема лабораторной работы;
2. Цель работы;
3. Необходимые принадлежности; задание; методика работы;
4. Ход выполнения лабораторной работы (этапы);
5. Выводы по выполненной работе.

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

1. Как иначе называют поток?

2. Как называют поток, состоящий из требований на обслуживание?

3. Поток требований, который уже обслуженных

4. Что называют системой обслуживания?

Учебно-методическое и информационное обеспечение дисциплины (ПМ)

1. Основная литература

2. Дополнительная литература

5.3. Базы данных, информационно-справочные и поисковые системы

1. М6435 Проектирование сетевой инфраструктуры на базе Windows Server 2008: видеокурс <Электронный ресурс>. – Режим доступа: http://soft-wins.net/video-lessons/4495-video-kurs-m6435-proektirovanie-setevoy-infrastruktury-na-baze-windjws-server-2008.html.