Математический аппарат для построения компьютерных сетей программа
ПОВТОРЕНИЕ И ПРЕДЫДУЩИХ
ЗАНЯТИЙ
1. Эйлеровым путем (циклом) называется . . .
2. Связный граф эйлеров тогда и только тогда . . .
3. Если граф G(V,E) обладает эйлеровым циклом, то он . . .
4. Эйлеров путь в связном графе существует тогда и только тогда,
когда в нем имеется не более . . .
двух ребер, связанных с одной вершиной
двух вершин четной степени
двух вершин нечетной степени
трех ребер, сходящихся к одной вершине
5. Алгоритм поиска эйлерова цикла . . .
Рассмотренные ранее задачи – это задачи на алгебраическое
понятие графа.
Однако в теории графов встречаются и задачи, в которых граф
рассматривается как геометрическая фигура (или
геометрическое «изображение» графа, заданного
алгебраически)
При прокладке различных коммуникаций может требоваться,
чтобы их линии не пересекались (пример – головоломка о
домах и колодцах). Аналогичная проблема существует в
электротехнике при проектировании и изготовлении печатных
плат.
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Каждый граф укладывается в трехмерное пространство
Граф, изображенный на плоскости, называется плоским,
если его ребра не пересекаются в точках, отличных от
вершин графа.
Один и тот же граф (как множество вершин + множество ребер)
может иметь как плоские, так и не плоские изображения
Принципиальный вопрос, на который нужно отвечать при
решении задач типа прокладки коммуникаций, это:
имеет ли данный граф хотя бы одно плоское
изображение?
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Два графа G1 и G2 называются изоморфными, если между их
вершинами установлено взаимнооднозначное соответствие: что
любые две вершины графа G1 соединены так же, как и
соответствующие вершины графа G2
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Граф называется планарным, если он изоморфен
плоскому графу.
граф G2 –
планарный, но
не плоский
Свойство графа быть или не быть плоским это свойство
геометрического изображения, а не алгебраического объекта.
Знания матрицы смежности графа может не хватить для
проверки этого свойства.
ТЕОРЕМА ЭЙЛЕРА О ПЛОСКИХ ГРАФАХ
Если плоскость разрезать по ребрам плоского графа, она
распадется на связные части, которые называют гранями. Всегда
имеется одна неограниченная внешняя грань, все остальные
грани называются внутренними.
это тоже
внутренняя
область
это внешняя
область
это
внутренняя
область
Плоский граф с пятью гранями. Граница грани с номером 3
состоит из двух циклов, а граница грани с номером 2 кроме
цикла длины 5 включает еще дерево из трех ребер.
ТЕОРЕМА ЭЙЛЕРА О ПЛОСКИХ ГРАФАХ
Количество граней в любой плоской укладке планарного графа,
имеющего n вершин, m ребер и k компонент связности, равно
Методические указания по выполнению контрольной работы по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей» для студентов специальности 09.02.02 «Компьютерные сети» заочной формы обучения. В методических указаниях изложены цели и задачи изучения МДК; приведены методические указания к изучению тем МДК, задания для выполнения контрольной работы, а также список основной и дополнительной рекомендуемой литературы. Контрольные задания для студентов-заочников, разработаны в соответствии с требованиями ФГОС СПО по МДК.
Составлено преподавателем КГБ ПОУ ХМТ Богдановой Т.С.
1. Методические указания по выполнению контрольной работы
2. Критерии оценки
3. Задания к выполнению контрольной работы
4. Рекомендуемая литература
Пояснительная записка
Междисциплинарный курс «МДК.01.02. Математический аппарат для построения компьютерных сетей» является частью профессионального модуля «ПМ.01. Участие в проектировании сетевой инфраструктуры» в соответствии с ФГОС по специальности СПО 09.02.02 «Компьютерные сети».
Результатом освоения «МДК.01.02. Математический аппарат для построения компьютерных сетей» является овладение обучающимися профессиональными (ПК) и общими (ОК) компетенциями:
Выполнять проектирование кабельной структуры компьютерной сети.
Осуществлять выбор технологии, инструментальных средств и средств вычислительной техники при организации процесса разработки и исследования объектов профессиональной деятельности.
Обеспечивать защиту информации в сети с использованием программно-аппаратных средств.
Выполнять требования нормативно-технической документации, иметь опыт оформления проектной документации.
Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.
Осуществлять поиск, анализ и оценку информации, необходимой для постановки и решения профессиональных задач, профессионального и личностного развития.
Использовать информационно-коммуникационные технологии в профессиональной деятельности.
Работать в коллективе и в команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.
Ставить цели, мотивировать деятельность подчиненных, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий.
Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
Быть готовым к смене технологий в профессиональной деятельности.
В результате освоения междисциплинарного курса обучающийся должен:
иметь практический опыт:
проектирования архитектуры локальной сети в соответствии с поставленной задачей;
установки и настройки сетевых протоколов и сетевого оборудования в соответствии с конкретной задачей;
выбора технологии, инструментальных средств при организации процесса исследования объектов сетевой инфраструктуры;
обеспечения целостности резервирования информации, использования VPN;
установки и обновления сетевого программного обеспечения;
мониторинга производительности сервера и протоколирования системных и сетевых событий;
использования специального программного обеспечения для моделирования, проектирования и тестирования компьютерных сетей;
оформления технической документации;
проектировать локальную сеть;
выбирать сетевые топологии;
рассчитывать основные параметры локальной сети;
читать техническую и проектную документацию по организации сегментов сети;
применять алгоритмы поиска кратчайшего пути;
планировать структуру сети с помощью графа с оптимальным расположением узлов;
использовать математический аппарат теории графов;
контролировать соответствие разрабатываемого проекта нормативно-технической документации;
настраивать протокол TCP/IP и использовать встроенные утилиты операционной системы для диагностики работоспособности сети;
использовать многофункциональные приборы и программные средства мониторинга;
использовать программно-аппаратные средства технического контроля;
использовать техническую литературу и информационно-справочные системы для замены (поиска аналогов) устаревшего оборудования;
общие принципы построения сетей;
многослойную модель OSI;
требования к компьютерным сетям;
этапы проектирования сетевой инфраструктуры;
требования к сетевой безопасности;
организацию работ по вводу в эксплуатацию объектов и сегментов компьютерных сетей;
вероятностные и стохастические процессы, элементы теории массового обслуживания, основные соотношения теории очередей, основные понятия теории графов;
алгоритмы поиска кратчайшего пути;
основные проблемы синтеза графов атак;
построение адекватной модели;
системы топологического анализа защищенности компьютерной сети;
архитектуру сканера безопасности;
базовые протоколы и технологии локальных сетей;
принципы построения высокоскоростных локальных сетей;
основы проектирования локальных сетей, беспроводные локальные сети;
стандарты кабелей, основные виды коммуникационных устройств, термины, понятия, стандарты и типовые элементы структурированной
кабельной системы: монтаж, тестирование;
средства тестирования и анализа;
программно-аппаратные средства технического контроля;
диагностику жестких дисков;
резервное копирование информации, RAID технологии, хранилища данных.
междисциплинарного курса «МДК.01.02. Математический аппарат для построения компьютерных сетей»
Тема 2.1 Теория графов
Определения и примеры
Что такое граф? Примеры графов. Укладки графов. Понятие пути. Сильно связные графы.
Цепи и циклы
Эйлеровы графы. Гамильтоновы графы. Конечные и бесконечные графы. Теорема Эйлера. Алгоритм Краскаля.
Свойства деревьев. Перечисление деревьев.
Планарность и двойственность
Планарные и двойственные графы. Двойственность по Уитни.
Приложения теории графов
Алгоритмы поиска кратчайшего пути. Основные проблемы синтеза графов атак.
Практические занятия
Решение задач по теории графов. Построение матриц смежностей и инциденций.
Решение задач по теории графов. Построение матрицы достижимостей.
Решение задач по теории графов. Выделение связных компонентов.
Решение задач по теории графов. Нахождение максимального потока и минимального разреза.
Решение задач по теории графов. Нахождение путей в графе.
Решение задач по теории графов. Нахождение минимально доминирующих множеств (МДМ).
Решение задач по теории графов. Нахождение максимально независимых множеств (МНМ).
Решение задач по теории графов. Нахождение кратчайшего пути.
Тема 2.2. Элементы теории конечных автоматов
Алгебраическая теория конечных автоматов
Определение конечного автомата. Способы задания автомата. Некоторые примеры автоматов. Лемма о разрастании. Автоматы Миля и Мура и их эквивалентность. Распознающие автоматы. Автоматы для распознавания языков. Недетерминированные автоматы. Приведение автоматов к детерминированному виду. Эквивалентные состояния. Минимизация конечных автоматов.
Структурная теория конечных автоматов
Базис конечных автоматов. Декомпозиция конечных автоматов. Проблема полноты автоматного базиса. Синтез конечных автоматов. Дизъюнктивные нормальные формы. Минимизация дизъюнктивных нормальных форм. Алгоритм Квайна. Минимизация частично заданных булевых функций. Минимизация систем булевых функций.
Основная модель
Многополюсный чёрный ящик. Конечность алфавита. Определение основной модели. Примеры конечных автоматов.
Таблицы, графы и матрицы переходов
Таблица переходов. Граф переходов. Элементарные пути. Определение минимальных путей и полных контуров.
Практические занятия
Решение задач по теории конечных автоматов. Алгебраическая теория конечных автоматов.
Решение задач по теории конечных автоматов. Структурная теория конечных автоматов.
Решение задач по теории конечных автоматов. Основная модель.
Решение задач по теории конечных автоматов. Таблицы, графы и матрицы переходов.
Тема 2.3. Элементы теории вероятностей и очередей. Система сетевого планирования.
Основные понятия теории вероятностей и теории распределений
Событие. Элементы комбинаторики. Математическое ожидание. Дисперсия. Типовые распределения. Преобразования распределений.
Теория очередей
Задачи теории очередей. Поток заявок. Процесс обслуживания. Основные соотношения теории очередей. Элементы
Система сетевого планирования (ССП)
Практические занятия
Решение задач по комбинаторике.
Решение задач по теории вероятностей. Детерминированные и стохастические процессы.
Решение задач по теории вероятностей. Математическое ожидание. Дисперсия.
Решение задач по теории вероятностей. Типовые распределения.
Решение задач по теории вероятностей. Преобразования распределений.
Решение задач по теории очередей.
Решение задач по теории массового обслуживания.
Решение задач сетевого планирования.
Решение задач сетевого планирования. Задачи оптимизации.
1. Методические указания по выполнению контрольной работы
Контрольная работа выполняется по одному из 10 вариантов. Каждый вариант содержит три задания.
Вариант контрольной работы определяется по номеру зачетной книжки и соответствует ее последней цифре. Если последней цифрой является ноль, то студентом выбирается десятый вариант.
При выполнении работы следует соблюдать научную терминологию и обозначения.
Контрольную работу следует оформлять в печатном виде в соответствии со следующими требованиями:
Печать на бумаге формата А4 (210х297 мм).
Поля документа: верхнее: 1,5 см; левое: 2,5 см; нижнее: 1,5 см; правое: 1,5 см.
Шрифт: Times New Roman, 14 пт., одинарный междустрочный интервал.
Абзац: выравнивание по ширине, отступ первой строки 1,25 см.
Нумерация страниц: внизу страницы, от центра, первая страница не нумеруется.
Объем работы не менее 8 листов.
Контрольная работа должна быть оформлена в следующем порядке:
Титульный лист установленного образца (Приложение 1).
Список использованной литературы.
2. Критерии оценки
При ответе на вопросы соответственно своему варианту, студент должен четко изложить термины и логическую структуру сопроводительного материала.
Оценка «отлично» ставится, если выполненная контрольная работа удовлетворяет следующим требованиям: в работе отражено знание студентом теоретических и практических основ вопроса, даны определения, дан сопроводительный материал или материал дан в свободном стиле.
Оценка «хорошо» ставится при соблюдении всех вышеперечисленных требований, но сопроводительный материал дан не в полной мере, исключая имеющие значение элементы.
Оценка «удовлетворительно» ставится, если содержание работ носит описательный характер, отсутствует фактический материал. При этом имеют место: слабая аргументированность суждений, не были даны четкие определения, сопроводительный материал дан не в полной мере, исключая значительные элементы; имеются погрешности в оформлении.
Оценка «неудовлетворительно» ставится, если работа полностью не отвечает требованиям к данному виду работ: при этом, не были даны четкие определения, сопроводительный материал подобран не по существу рассматриваемых вопросов, не раскрыты главные элементы вопросов; имеются значительные погрешности в оформлении.
В установленные учебным графиком сроки студент направляет выполненную работу для проверки на заочное отделение. Последний срок сдачи контрольной работы - за две недели до начала сессии.
Если контрольная работа не зачтена, то студент выполняет ее вторично и оправляет на проверку вместе с работой, в которой сделаны замечания.
Цель: изучить основы теоретико-множественного и графического представлений графов, простейших свойств графов, получить практический навык задания и визуализации графа на плоскости; закрепить навыки построения графов по образцу в графических средах (программы для графического представления графов).
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
Материальное обеспечение:
Программы для графического представления графов: grin_rus, Grafoanalizator1.3.3 rus, windisc ru.
Теоретическая часть:
Графические представления в широком смысле – любые наглядные отображения исследуемой системы, процесса, явления на плоскости. К ним могут быть отнесены рисунки, чертежи, графики зависимостей характеристик, планы-карты местности, блок-схемы процессов, диаграммы и т. д. Такие изображения наглядно представляют различные взаимосвязи, взаимообусловленности: топологическое (пространственное) расположение объектов, хронологические (временные) зависимости процессов и явлений, логические, структурные, причинно-следственные и другие взаимосвязи.
Графические представления – удобный способ иллюстрации содержания различных понятий, относящихся к другим способам формализованных представлений (например, диаграммы Венна и другие графические иллюстрации основных теоретико-множественных и логических представлений).
Всё более распространенными становятся представления количественных характеристик, взаимосвязей между объектами в виде разного рода одно-, двух- и более мерных гистограмм, круговых диаграмм, других аналогичных способов представления в виде тех или иных геометрических фигур, по наглядным характеристикам которых (высоте, ширине, площади, радиусу и пр.) можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.
Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы, изучаемые в теории графов.
Теория графов – это раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.
Основные понятия теории графов
Граф – это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.
Г раф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и тогда определение графа таково:
Граф – это конечное множество Х, состоящее из n элементов называемых вершинами графа, и подмножество V декартова произведения называемое множеством дуг.
Ориентированным графом G (орграфом) называется совокупность (Х, V).
Неориентированным графом называется совокупность множеств Х и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству Х.
Дугу между вершинами i и j, будем обозначать (i, j). Число дуг графа будем обозначать
Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми рёбрами (дугами), соединяющими вершины из этого множества. Если в графе удалить часть рёбер (дуг), то получим частичный граф.
Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.
Граф называется полным, если каждые две вершины его соединены одним и только одним ребром.
Граф, для которого из следует называется симметричным. Если из следует , то соответствующий граф называется антисимметричным.
Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат.
Степень вершины называется число рёбер графа, которым принадлежит эта вершина. Степень графа ещё называют его валентностью и обозначают . Вершина графа, для которой является изолированной, для которой висячей.
Вершина называется нечётной, если нечётное число. Вершина называется чётной, если чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.
В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Число нечётных вершин любого графа чётно. Во всяком графе с n вершинами, где всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.
Если в графе с n вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени
Маршруты, цепи, циклы
Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны:
Если то маршрут замкнут, в противном случае открыт.
Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.
Простой путь – путь, в котором ни одна дуга не встречается дважды.
Контур – путь, у которого конечная вершина совпадает с начальной вершиной.
Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.
Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью.
Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.
Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.
Связностью графа называется минимальное число рёбер, после удаления которых граф становится несвязным.
Ориентированные графы
Если элементы множества Е графа упорядоченные пары, то граф называется ориентированным или орграфом.
Ребро графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.
Одна и та же вершина ориентированного графа может служить началом для одних рёбер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.
Степенью входа вершины орграфа называется число входящих в вершину рёбер.
В орграфах в зависимости от сочетаний степеней входа и выхода для данной вершины рассматривается три случая.
Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.
Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.
Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.
Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для орграфов цепь называется путём.
Простым путём в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.
Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.
Длиной пути называется число рёбер в этом пути.
Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром.
Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.
Петлёй называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.
Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными рёбрами. Для ориентированного мультиграфа вершины и могут соединяться несколькими рёбрами в каждом из направлений.
Изоморфизм графов
Два графа и называются изоморфными, если между множествами их вершин существует биективное (взаимнооднозначное) соответствие, такое, что вершины соединены рёбрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направление в изоморфных графах должно совпадать. Изоморфизм графов есть отношение эквивалентности, так как обладает свойствами рефлексивности, симметричности, транзитивности. Для того чтобы граф был изоморфен графу необходимо и достаточно существования такой подстановки, которая бы установила взаимнооднозначное соответствие между вершинами графа, а также между их рёбрами.
При замене графа любым ему изоморфным все свойства графа сохраняются. Строго говоря, графы отличающиеся только нумерацией вершин, являются изоморфными.
Алгоритм распознания изоморфизма двух графов и
1. Подсчитаем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные).
2. Выписываем все элементы обоих графов в естественной упорядоченности и определяем пары и для каждого элемента, где число исходов для каждой вершины графов и , а число заходов для соответствующих графов.
3. Для каждого элемента х графа ищем такой элемент у графа что выполняется условие: число исходов х совпадает с числом исходов у, и число заходов х совпадает с числом заходов у. Найденные элементы х и у соединяем ребром, т. е. строим граф соответствия (если соответствия нет, то графы не изоморфны).
4. Выписываем подстановку, которая переводит граф в граф .
Плоские графы
Граф называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа .
В качестве характеристики плоского представления графа вводится понятие грани.
Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Операции над графами
Рассмотрим графы и
а) Дополнением графа называется граф множеством вершин которого является множество а множеством его рёбер является множество
б) Объединением графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер является множество
в) Пересечением графов и называется граф множеством вершин которого является множество а множеством его рёбер является множество
г) Суммой по модулю два графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер – множество Т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно.
Способы задания графов
Существуют три эквивалентных способа задания графов: аналитический, геометрический и матричный. Рассмотрим каждый из них.
Аналитический способ задания графов
Граф задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.
Пусть дано множество которое имеет мощность
Для того чтобы задать отображение Е на V , необходимо каждому элементу поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через Поэтому Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.
Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар
Геометрический способ задания графов
Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину соединяют линиями с теми вершинами , для которых выполняется условие Множество линий, которое соответствует множеству упорядоченных пар есть множество рёбер.
Матричный способ задания графов
Квадратная матрица элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа тогда и только тогда, когда её элементы образуются по следующему правилу: элемент стоящий на пересечении й строки и го столбца, равен единице, если имеется ребро, идущее из вершины в вершину и равен нулю в противном случае. Элемент равен единице, если при вершине имеется петля, и равен нулю в противном случае. Элемент равен некоторому числу m, где m – число рёбер графа, идущее из вершины в вершину
Таким образом, если граф задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания. Наиболее часто для задания графа используется аналитический и матричный способы, а геометрический способ служит для иллюстрации полученных результатов.
по специальности 09.02.06 Сетевое и системное администрирование
ПМ. 01 Выполнение работ по проектированию сетевой инфраструктуры
МДК.01.01. Организация, принципы построения и функционирования компьютерных сетей
МДК.01.02. Математический аппарат для построения компьютерных сетей
МДК 01.03 (В) Аппаратное обеспечение компьютерных сетей
Студента Овсянникова Владислава Викторовича
Курса _3_______________ группы___ССА -3__________________________________
Дата прохождения практики: с ______________ 2021 г. по ______________ 2021 г.
Год обучения, семестр: 3 год, 6 семестр
Классный руководитель: Бочарова Анна Анатольевна
Руководитель практики от ОУ: Мурашев Роман Константинович
на студента с оценкой производственной практики
студента Овсянникова Владислава Викторовича группа ССА -3 курс_3______
проходил(а) практику по специальности 09.02.06 Сетевое и системное администрирование
ПМ. 01 Выполнение работ по проектированию сетевой инфраструктуры
Выполнение работ по специальности «Сетевое и системное администрирование» на базе АО «Авиаавтоматика» им. В.В Тарасова» Запольная ул., 47
2. Уровень теоретической подготовленности, умение применять имеющиеся знания на практике уровень теоретической подготовленности соответствует требованиям предприятия, имеющиеся знания умело применяет на практике.
3.Трудовая учебная дисциплина студента: Овсянникова Владислава Викторовича
(фамилия, имя, отчество)
Соответствует требованиям, предъявляемым предприятием
4.Внешний вид студента удовлетворительный
5.Понятие сущности и социальной значимости специальности Понимает сущность и социальную значимость выбранной специальности.
6.Работа с документаций (учебной и производственной):
Работал со следующей документацией: ГОСТ Р 53114-08 Защита информации. Обеспечение информационной безопасности в организации.
7.Степень овладения практическими навыками (выполнение норм выработки)
Степень овладения практическими навыками 100%
8.Индивидуальные качества студента
Коммуникабельный, ответственный, исполнительный
9.Умение работать в команде умеет работать в команде
10.Особые замечания особых замечаний нет
(производственных участков) Роспись руководителя инциалы
Заместитель директора по УПР /А.А.Грунева
Старший мастер /И.Н.Смирнова
Руководитель практики от ОУ _____________________/Р.К.Мурашев_______
Общая характеристика и структура предприятия. Использование теории графов для анализа сети и составление ее схемы. Нахождение минимального пути по алгоритму Краскала. Построение и структура матрицы инцидентности. Задача линейного программирования.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 30.05.2014 |
Размер файла | 158,9 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
КУРСО ВАЯ РАБОТА
граф сеть программирование алгоритм
Основной целью данной курсовой работы является анализ компьютерной сети с помощью математического аппарата. В ходе данной работы будут прим е нены все теоритические знания, полученные за время изучения дисциплины «Математический аппарат для построения компьютерных сетей.
Задачи данной курсовой работы:
- Изучение схемы сети предприятия;
- С помощью теории графов проанализировать участок сети;
- Рассчитать н аибольший поток в сети компании ;
- Сформулировать задачу по линейному программированию.
- Поиск кратчайших путей;
- Поиск многополюсной сети с максимальной пропускной способностью;
- Поиск максимального потока и т.д.
В настоящее вр емя, теория графов является одной из основных теорий м а тематиче ского аппарата, применяемых для анализа поведения сети на сетевом уровне. Высокая методологическая проработанность, простота, наглядность - основ ные качества моделей, построенных на базе математического аппарата те о рии графов .
1 . Описание предприятия
Страховая компания «Без страха» это бренд на рынке страхования. Наша компания предлагает самые выгодные условия страхования. Наша компания ра ботает с людьми любого возраста и социального статуса. Наша компания пре д лагает огромный выбор страховых услуг и не останавливается в поиске новых видов страхования. Перечень видов страхования:
- Страхование любого вида имущества
- Страхование жилья и т.д.
Наша компания присутствует на рынке услуг уже 25 лет и знает, с какой стороны «подойти» к клиенту, чтобы удовлетворить его желания. За все время работы нашей компании мы оформили около 15 миллионов страх о вок. Наши клиенты рады с нами сотрудничать.
Компания «Без страха» пожертвовала 12 миллионов долларов на благотв о рительные акции. К аждый год наша компания производит пожертвования в детские дома.
Дополнительно наша компания проводит обучающие курсы по страхово му делу, в случае удачного окончания которых вы можете устроиться на работу в нашу фирму.
Здание страховой компании состоит из одного этажа и занимает площадь рав ную 270 кв. метрам. В школе 7 кабинетов с центральным коридором. Есть кабинет охраны серверная и зал для конференций .
2 . Схема сети
Площадь компании составляет 270 м 2 . Здание состоит из 7 кабинетов с центральным коридором .
Компьютеры в предприятии расположены вдоль стены. Между собой они соединяются при помощи витой пары, которая вкладывается в кабель-канал, прикрепленный к стене, также подключаются к коммутатору.
В организации имеется 14 рабочих станций , которые объеди нены в корпоративную сеть.
Под логической структурой сети понимается ее организация на 3-м и выше уровнях модели OSI, т.е. сетевые протоколы, адресация, взаимодействие рабочих станций с серверами. В качестве основного сетевого протокола в вычислител ь ной сети Предприятия используется протокол IP. Адреса на сетевом уровне для рабочих станций задаются динамически по протоколу DHCP.
Рисунок 1 - Логическая схема сети
На данной логической схеме отображена топология расширенная звезда. В схеме показаны необходимые компоненты се ти: коммутатор, 14 компьютер ов , Web -с ервер и сервер.
3. Использование теории графов для анализа сети
Теория графов в качестве теоретической дисциплины может рассматри ваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы рассматривать мы не будем) с заданными отн о шениями между их элементами. Как прикладная дисциплина теория графов по з воляет описывать и исследовать многие технические, экономические, биолог и ческие и социальные системы. Родоначальником теории графов считае т ся Леонард Эйлер . В 1736 году в одном из своих писем он формулирует и пре д лагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии о д ной из классических задач теории графов.
Основные понятия теории графов
Граф - система, которая может быть рассмотрена как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами.
Способы задания графов:
А) Матрица инцидентности A. По вертикали указываются вершины, по го ризонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в верш и ну i входит ребро j. Если ребро - петля, то aij=2.
Б) Список ребер. В первом столбце ребра, во втором вершины им инц и дентные.
В) Матрица смежности - квадратная симметричная матрица. По горизонт а ли и вертикали - все вершины. Dij= число ребер, соединяющее вершины i , j .
Г) Матрица Кирхгофа. bij=-1, если вершины i и j смежны, bij=0 если ве р шины i и j не смежны, bii = deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.
Путями в графах называется последовательность дуг этого графа, такая что каждая начальная точка новой дуги является концом предыдущей. Длиной пути называется число дуг, входящих в путь L ( M ).
Если все дуги некоторого пути различны, то такой путь считается про стым, иногда составным . Если в некотором пути вершины встречаются не более одного раза, то такой путь называется элементарным.
Если начало пути графа совпадает с концом, то такой граф называется кон туром. Контур единичной длины является петлей в графе.
Основные виды графов :
А) Симметричный граф - граф, в котором две смежные вершины соедин е ны противоположно ориентированными дугами.
Б) Ориентированный граф - это граф, на котором указаны стрелки на ка ж дом ребре. Неориентированный граф не имеет стрелок.
В) Полный граф - это когда любые две вершины соединены хотя бы одним ребром.
Г) Сильно связным граф является, когда для любых двух вершин сущ е ствует путь из одной вершины в другую.
Д) Эйлеровым путем в графе называется путь, содержащий все ребра гр а фа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.
Е) Гамильтонов путь - путь, содержащий каждую вершину графа ровн о один раз.
Рисунок 3 - Эйлеров граф
Нахождение минимального пути по алгоритму Краскала
Алгоритм Краскала - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа . Алгоритм впервые оп и сан Джозефом Кра скалом в 1956 году .
Алгоритм нахождения кратчайшего пути :
А) Выбираем ребра наименьшей длины
Б) Из оставшихся ребёр вновь выбираем наименьшей длины
В) Выбираем ребра наименьшей длины при условии, что оно не образует цикла с рёбрами, выбранными в пунктах 1, 2
Г) Из оставшихся рёбер выбираем то, которое меньшей длины и не образовывает цикла с рёбрами, выбранными в пунктах 1-3
Для того, чтобы найти минимальный путь в приведенной выше сети, возь мем для рассмотрения небольшую часть этой сети. Для построения графа воз ь мем компьютеры под номерами: 1, 2, 3, 4, 5, 6 и Ком 2 .
Рисунок 4 - Участок сети №1
В приведенной ниже таблице размещены числовые значения для каждой дуги графа.
Таблица 1 - Числовые значения дуг
Вычислим число ребер в полном графе по формуле:
где m - чи сло ребер, n - чи сло вершин
Для данного графа m = 21
Высчитаем число шагов, за которые мы найдем наименьший путь по сл е дующей формуле:
? находим по еще одно формуле:
В данном графе наименьший путь мы найдем за 6 шагов.
Шаг 1: Выберем любой самый короткий путь, например ПК26 ПК27. Числовое значение этой дуги равно 1
Шаг 2: Так же произвольно выбираем еще один путь, учитывая длину. Возьмем ПК29 ПК31 = 1
Шаг 3: Оставшиеся четыре шага мы выбираем кратчайшие пути. При пр а вильном выборе не должны образовываться петли. Берм дугу между ПК25 и ПК26. Она равна 2.
Шаг 4:ПК28 ПК31= 2
Шаг 5: ПК26 ПК31= 3
Шаг 6: ПК29 ПК30 = 3
Считаем общий путь. Для этого необходимо сложить все дуги.
Наименьший путь в данном графе равен 12.
Построение матрицы смежности
Матрица смежности - один из способов представления графа в виде ма т рицы.
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n ) - это квадратная матр и ца A размера n , в которой значение элемента a ij равно числу рёбер из i -й вершины графа в j -ю вершину.
Иногда, особенно в случае неориентированного графа, петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a ii в этом случае равно удвоенному числу петель вокруг i -й вершины.
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали. Ма т рица смежности и cписки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах.
Свойства матриц смежности:
- если граф симметричен, то его матрица тоже смежности тоже симметрична
- элементами матрицы A(G) являются целые положительные числа и число ноль
- Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины d(xi)
- В графе, имеющей матрицу смежности А существует путь длины л, если не равна 0.В графе не существует контуров тогда и только тогда, когда
=0, начиная с некоторого k .
Рассмотрим новый участок сети для построения матрицы смежности.
В граф будут входить следующие элементы сети: коммутатор 1, коммут а тор 4 , коммутатор 5, 4 ПК под номе рами 11, 12, 13, 14 .
Рисунок 5 - Участок сети №2
Рисунок 6 - Г раф участка сети №2
В данном графе черные дуги обозначают физическое соединение между устройствами, а красные - только логическое.
Для данного графа построим матрицу смежности A = ( ), где - чи сло дуг, идущих из вершины в вершину .
Проанализировав матицу, можно сделать некоторые выводы:
- диагональ матрицы содержит только нули, следовательно, матрица не имеет петель;
- нет таких вершин, которые соединялись бы между собой более чем одной дугой, потому что матрица содержит только 0 и 1.
Графы и их матрицы используются для описания и анализа потоков инфо р мации в управляющих системах. В любую управляющую систему поступают и с ходные данные. В итоге обработки информации от исходных данных получаю т ся промежуточные данные, а из промежуточных данных окончательные резул ь таты.
Последовательность движения всей информации в какой-либо управля ю щей системе можно изобразить в виде графа, который называется - информац и онный граф.
Вершины такого г рафа - э то исходные данные, промежуточные результаты.
Ребра информационного графа указывают на взаимосвязь между этими в е личинами.
Изобразим участок сети №2 , из предыдущего пункта, в виде информац и онного графа.
Рисунок 7 - Информационный граф
ПК11 - исходные данные
К1 - конечный результат
К5, К4, ПК12, ПК13, ПК14 - промежуточные вершины
Каждый информационный граф содержит вершины каждая, из которых имеет отношение порядка.
Оно разбивает весь процесс движения информации от исходных данных до результатов на такты. Для формирования любой величины необходимо чтобы информация поступала в эту вершину по всем путям вершины от исходных дан ных.
Порядком вершины Х i называется число равное максимальной из длин п у тей, ведущих к этой вершине от любого из исходных данных.
Порядком графа будем называть максимальный из порядков его вершин, отвечающих окончательным результатам.
Так как последний столбец 0, то вершина С - исходные данные. Главная диагональ 0 - граф без петель. Третья строка 0, значит вершина К - конечный результат.
Найдем порядки вершин.
Таблица 2 - Порядки вершин
Порядок вершины позволяет определить номер того такта, после которого тот или иной результат перестает участвовать в движении информации, а значит этот результат может быть погашен во внешней памяти.
Построение матрицы инцидентности графа
Матрица инцидентности - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро (дуга) и ве р шина). Столбцы матрицы соответствуют ребрам, строки - вершинам. Ненул е вое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
Матрица будет матрицей инцидентности дуг, если у нее нет одинаковых столбцов. В каждом столбце содержится только одна 1 и одна -1. Вся матрица состоит только из 0 и + - 1.
Рисунок 7 - Граф для участка сети №2
Нахождение наибольшего потока сети
Теория потока в сети является одной из наиболее развитых и изящных и с следований в теории графов.
Транспортной сетью (сетью) называется граф без петель с конечным числом вершин, если каждой дуге поставлено в соответствие некоторое число которое является пропускной способностью дуги и выполняются следующие условия:
- существует только одна вершина X0 из которой дуги только исходят, эта вершина называется источником;
- существует только одна вершина Z в которую дуги только приходят, эта вершина называется выходом из сети;
Потоком в транспортной сети называется функция , определенная на множестве U -д уг сети, которое принимает целое неотрицательное значение, т а кое что выполняются 2 условия:
- значение этой функции для дуги U не превосходит пропускную способность этой дуги U. ;
- для каждой вершины X сети (кроме X0 и выхода Z) сумма значений функции на дугах входящих в вершину X равна сумме значений функций на дугах исходящих из этой вершины.
- реальное значение тех данных, которые передаются по дуге;
- множество всех дуг сети заходящих в вершину X ;
- множество всех дуг сети исходящих из вершины X .
Пусть X - множество всех вершин в сети .
А - подмножество множества X , причем , а .
Множество дуги сети концы которых содержатся в множестве А. такое множество называют разрезом сети.
Пропускная способность - это максимальное количество информации, к о торое можно передать по данной дуге. - это реальное значение тех данных , которые передаются по данной дуге.
Информация, двигаясь из точки в точку , обязат е льно пройдет хотя бы один раз по какой-либо дуге разреза A , поэтому справедливо неравенство . Следовательно, поток в сети всегда равен этому разрезу.
Посчитаем наибольший поток участка сети №2 .
Рисунок 8 - Граф для нахождения наибольшего потока в сети
Таблица 3 - Пропускная способность дуг
Возьмем некоторые множества дуг сети:
Найдем пропускную способность каждого разреза:
Из данных найденных пропускных способностей разрезов сети имеет самую большую. Значит дуги, входящие в данный разрез могут передать больше количества информации, чем дуги, входящие в два других разреза.
4. Задача линейного программирования
Линейное программирование - математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.
Особенности задач линейного программирования:
- по условиям задачи составляют показатель эффективности (целевую функцию), которая является линейной функцией от нескольких переменных;
- учитывая ограничения на налагаемые решения, составляют систему линейных уравнений и неравенств.
Линейность - предполагает наличие двух свойств: пропорциональности и аддитивности.
Пропорциональность означает, что вклад каждой переменной в целевую функцию прямо пропорционален величине этой переменной.
Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных.
Необходимо было составить самостоятельно задачу линейного программ и рования, связанную с областью компьютерных сетей.
Постановка задачи
На изготовления трех видов изделий: патчкордов, кросспанелей и конне к торов - работает 4 бригады. Затраты времени на изготовление одного вида изд е лий указаны в таблице. В ней же указан общий фонд рабочего времени каждой бригады, а так же прибыль от реализации одного изделия каждого вида.
Читайте также: