ель лабораторной работы
При выполнении данной лабораторной работы необходимо ознакомиться с описаниями объекта исследования с точки зрения принципов системного подхода. Задание, которое нужно сделать: найти максимальный поток в графе модели информационной системы.
писание исходных данных
Имеется схема расположения N абонентов локальной вычислительной сети
Необходимо:
- найти максимальный поток в графе модели информационной системы;
- дать описаниями объекта исследования с точки зрения принципов системного подхода;
Вариант 8: даны вершины 1, 2, 3, 4, 5, 6,7
(2,1)=3, (1,3)=4, (2,4)=4, (2,3)=5, (4,1)=4. (4,5)=2, (5,6)=3, (3,5)=7, (3,6)=9, (3,4)=3, (5,7)=6, (6,7)=2
асчет максимального потока
Используется метод поиска в ширину.
Опишем поиск в ширину на первом шаге.
1. Очередь состоит из единственной вершины 1. Посещена вершина 1. Предков нет.
2. Очередь состоит (от начала к концу) из вершины 3. Посещены вершины 1,3. Вершина 3 имеет предка 1.
3. Очередь состоит из вершин 4 и 5. Посещены 1,3,4,5. Вершина 3 имеет предка 1, вершины 4,5 — предка 3.
4. Вершина 4 удаляется из очереди: рёбра из неё ведут только в уже посещённые вершины.
5. Очередь состоит из вершин 6,7. Посещены 1,3,4,5,6,7. Вершина 3 имеет предка 1, вершины 4,5 — предка 3, вершины 6,5 — предка 5.
6. Обнаруживается ребро (5,7) и цикл останавливается. В очереди вершины (6,7). Посещены все вершины. Вершина 3 имеет предка 1, вершины 4,5 — предка 3, вершины 6,7 — предка 5.
7. Идём по предкам: 7->5->3->1. Возвращаем пройденный путь в обратном порядке: 1->3->5->7.
| Пропускная способность пути | Путь |
| min(cf(1,3),cf(3,5),cf(5,7)) = min(4 − 0, 7 − 0, 6 − 0) = min(4,7,6) = 4 | 1-3-5-7 |
| |
| min(cf(1,3),cf(3,5),cf(5,6),cf(6,7)) = min(4 − 4, 7 − 4, 3 − 0, 2 − 0) = min(0,3,3,2) = 0 | 1-3-5-6-7 |
|
Таким образом, максимальный поток = 4.
писание объекта исследования
С точки зрения принципов системного подхода система была рассмотрена в следующих аспектах:
1) каждый объект является системой (в данной задаче все абоненты взаимосвязаны, каждый имеет предка, каналы обладают свойством проводимости),
2) процесс исследования системы понимается как системный по своей логике и применяемым средствам (исследование системы можно разделить на систематизированные последовательные этапы: изучение теоретического материала, построение визуальной модели системы, непосредственное решение поставленной задачи)
При решении поставленной задачи мной были использованы основные принципы системного подхода, такие как:
l принцип цели - при выполнении работы я руководствовалась поставленной целью – нахождением максимального потока
l принцип двойственности - каждый исследуемый объект рассматривался как система, обладающая своими свойствами (например, номер абонента и его предок, пропускная способность канала) и как подсистема системы более высокого уровня иерархии – всей абонентской системы в целом
l принцип целостности – учитывалось, что абонентская система - это сложная совокупность различных элементов, находящихся в многообразных связях
l принцип историзма – при вычислении кратчайшего пути каждый раз учитывались предки объектов
ывод
Таким образом, при выполнении данной лабораторной работы я изучила способы описания объекта исследования с точки зрения принципов системного подхода, закрепила теоретические знания в этой области.
Ознакомилась с алгоритмом Эдмондса — Карпа, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t полагая, что каждое ребро имеет единичную длину и методом поиска этого кратчайшего дополняющего пути в ширину.
Получила навыки практического использования графических и текстовых редакторов при оформлении отчета к лабораторной работе.
