Алгоритм Дейкстры
Более эффективным алгоритмом для решения данной задачи является алгоритм Дейкстры , применяемый в том случае, если веса всех дуг неотрицательны [Липский,1988]. Исходная информация и результаты работы аналогичны предыдущему алгоритму.
For v I V do D [ v ]:= A [ s , v ];
D[s]:=0; T:=V\{s};
While T?0 do
begin
u:=Произвольная вершина rIT , такая, что D[ r ]= min {D[p]:pIT};
T:=T\{u};
For vIT do D[v]:=min(D[v],D[v]+A[u,v])
end
Механизм работы алгоритма Дейкстры представлен на следующем рисунке [ Бурковский , Холопкина , Райхель , Кравец,1996]:
Алгоритм Форда-Беллмана
Существует большое количество практических задач, сводящихся к поиску кратчайших путей в сети (графе). К их числу можно отнести: поиск кратчайшего расстояния между городами; поиск пути передачи информации, обеспечивающего минимальную стоимость или минимальное время передачи, или максимальную надежность при распространении информации в разветвленной сети.
Исходными данными для поиска кратчайшего пути в сети (графе) является матрица весов дуг заданного ориентированного графа. Это означает, что каждой дуге ( u,v )IE поставлено в соответствие некоторое вещественное число А( u,v ), называемое весом данной дуги. Длину крат-чайшего пути d ( s,t ) между вершинами s и t называют расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t , то полагают d ( s,t )=?, где ?- некоторый символ.
Большинство алгоритмов поиска расстояний между двумя фиксированными вершинами s и t включают в себя следующие действия: по данной матрице весов дуг A[ u,v ] ( u,vIV ) вычисляют некоторые верхние ограничения D[ v ] на расстояние от s до всех вершин v . На каждом шаге, если D[ v ]+A[ u,v ]<D[ v ] оценку D[ v ] улучшают: D[ v ]=D[ u ]+A[ u,v ]. Процесс прекращается, когда дальнейшее улучшение ни одного из ограничений невозможно.
Алгоритм Форда-Беллмана позволяет найти расстояние от источника до всех вершин D[ v ]= d ( s,v ), vIV ориентированного графа при условии, что граф не содержит контуров отрицательной длины ( n - количе-ство вершин в графе) [Липский,1988]. Исходными данными для этого алгоритма являются матрица весов дуг A[ u,v ].
For vIV do D[v]:=A[s,v];
D[s]:=0;
For k:=1 to n-2 do
For vaV\{s} do
For uIV do D[v]:=min(D[v],D[u]+A[u,v])
На рисунке [Бурковский,Холопкина,Райхель,Кравец,1996] приведен: (а) граф; (б) соответствующая ему матрица весов дуг; (в) результаты работы алгоритма Форда-Беллмана.
Приведенный алгоритм отыскания кратчайших путей в графах с отрицательными длинами дуг, принадлежащий Форду, Муру и Беллману, может служить одним из возможных способов обнаружения контуров отрицательной длины (или циклов в неориентированном графе) [Евстигнеев,Касьянов,1992,с.47-48].
Алгоритм обмена данными:
Рассмотрим алгоритм обмена данными между двумя компьютерами с подтверждением (справедливо для SPP-режима LPT порта). Пусть первый компьютер будет передающим, а второй - принимающим.
В момент времени t0 (начало передачи) передающий компьютер (передатчик) выставляет данные для передачи (записывает их в порт 378h). Пример :
outportb (dataport,16);
Причём в каждом цикле обмена записывается один полубайт в регистр передачи 378h.
В момент времени t1 передатчик выставляет сигнал готовности (порт 378h бит 5), который означает, что данные переданы и принимающий компьютер (приёмник) может их считать из приёмного регистра 379h (бит 7 = 0).
int data= inportb ( statusport );
В момент времени t2 приёмник определяет, что поступил сигнал готовности от передатчика и данные можно считать. Приёмник считывает данные из приёмного регистра (порт 379h) и устанавливает сигнал подтверждения приёма на стороне передатчика (порт 378h бит 5). Это нужно для того, чтобы передатчик смог определить, когда можно будет посылать следующие данные. Если этого не сделать, то передатчик может послать данные в тот момент, когда приёмник их ещё не считал и это может привести к сбою передачи или приёма.
В момент времени t3 передатчик получает сигнал подтверждения приёма от приёмника и сбрасывает сигнал готовности. Это нужно для того, чтобы приёмник смог сбросить свой сигнал подтверждения. Если этого не сделать то цикл обмена будет нарушен, так как в следующем цикле обмена передатчик не будет знать принял ли приёмник данные или нет.
В момент времени t4 приёмник определяет, что сигнал готовности сброшен и сбрасывает свой сигнал подтверждения приёма. Таким образом завершается цикл обмена полубайтом - передатчик снова готов к передачи данных, а приёмник - к приёму.
В следующем цикле посылается другой полубайт - если посылался младший полубайт, то посылается старший и наоборот. В следующем за этим цикле обмена снова посылается младший полубайт и т.д.
Цель работы
Ознакомиться с основными аппаратными средствами и оборудованием ЛВС.
Приобретение практических навыков связи двух компьютеров через LPT - порт.
Рассмотреть·
сетевые технологии, которые должны обеспечивать надежную и быструю передачу дискретных данных по линиям связи.
Ознакомиться с основными понятиями и определениями, связанными с сетями Петри
Ознакомиться с основными элементами эмулятора сетей Петри
Спроектировать 3 вида сетей Петри с использованием эмулятора
Двусторонние дороги
12. В системе двусторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.
13. Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз.
14. Задана система двусторонних дорог. Найти замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз.
15. Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна.
16. По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого из остальных городов, проезжая не более 100 км.
17. По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B.
18. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Определить N-периферию для заданного N.
19. В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города A в город B с минимальной величиной S+P, где S - сумма длин дорог пути, а P - сумма пошлин проезжаемых дорог.
20. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города A в город B ( ко-торый может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.
21. Система двусторонних дорог называется трисвязной , если для любой четверки разных городов A,B,C,D существует два различных пути из A в D, причем один из них проходит через B, а другой - через C. Определить, является ли трисвязной данная система двусторонних дорог.
| Оглавление | Вперед |
| Каталог | Индекс раздела |
FastWire
FastWire - это другая широко распространенная программа связи компьютеров через нуль-модем. По сравнению с программой Norton Commander FastWire предоставляет пользователю больше возможностей. Так, FastWire позволяет копировать не только отдельные файлы, но и целые каталоги. Кроме того, предоставлена возможность удаленного выполнения программ, т.е. запуск программ на удаленном компьютере.
Ход работы
Рассмотреть следующие аппаратные средства и оборудование ЛВС:
1. Исполнение сетевых адаптеров Ethernet и Token Ring для шин ISA, PCI, MCA.
2. Виды кабелей для сетей ( коаксиальный , неэкранированная витая пара, оптоволокно).
3. Устройства соединения BNC, RJ -45, настенные и модульные розетки, терминаторы.
4. Элементы ЛВС: монтажные короба, патч-панели , патч-корды , абонентские шнуры. Разделение кабеля UTP по стандартам TIA / EIA -568 A / B .
5. Варианты исполнения активных концентраторов ( хабы , комутаторы , MAU).
6. Протестировать сетевой адаптер с помощью утилит настройки.
4.1 Ознакомиться с основными элементами эмулятора сетей Петри.
Написать программу для моделирования следующих кодов (выбрать свой вариант):
1. Кодирование без возвращения к нулю (Non Return to Zero, NRZ).
2. Метод биполярного кодирования с альтернативной инверсией (Bipolar Alternate Mark Inversion, AMI).
3. Фазовая модуляция
4. Потенциальный код с инверсией при единице (Non Return to Zero with ones Inverted, NRZI).
5. Биполярный импульсный код.
6. Амплитудная модуляция
7. Метод HDB3 (High-Density Bipolar 3-Zeros) для корректировки кода AMI.
8. Манчестерский код.
9. Логический код 4В/5В.
10. Частотная модуляция
11. Скрэмблирование.
12. Метод B8ZS (Bipolar with 8-Zeros Substitution) для корректировки кода AMI.
13. Дискретная модуляция аналоговых сигналов.
14. Потенциальный код 2B1Q.
| Оглавление | Вперед |
| Каталог | Индекс раздела |
Интерфейс
Программа написана под Windows 95/NT. При написании использовался компилятор Borland Delphi 3.
Как это выглядит:
Кабели на основе витой пары
Витая пара (UTP/STP, unshielded / shielded twisted pair ) в настоящее время является наиболее распространенной средой передачи сигналов в локальных сетях. Кабели UTP/STP используются в сетях Ethernet , Token Ring и ARCnet . Они различаются по категориям (в зависимости от полосы пропускания) и типу проводников (гибкие или одножильные) . В кабеле 5-й категории, как правило, находится восемь проводников, перевитых попарно (то есть четыре пары).
Кабель UTP
Структурированная кабельная система, построенная на основе витой пары 5-й категории, имеет очень большую гибкость в использовании. Ее идея заключается в следующем.
На каждое рабочее место устанавливается не менее двух (рекомендуется три) четырехпарных розеток RJ-45. Каждая из них отдельным кабелем 5-й категории соединяется с кроссом или патч-панелью , установленной в специальном помещении, - серверной. В это помещение заводятся кабели со всех рабочих мест, а также городские телефонные вводы, выделенные линии для подключения к глобальным сетям и т.п. В помещении, естественно, монтируются серверы, а также офисная АТС, системы сигнализации и прочее коммуникационное оборудование.
Благодаря тому что кабели со всех рабочих мест сведены на общую панель, любую розетку можно использовать как для подключения рабочего места к ЛВС, так и для телефонии или вообще чего угодно. Допустим, две розетки на рабочем месте были подключены к компьютеру и принтеру, а третья - к телефонной станции. В процессе работы появилась необходимость убрать принтер с рабочего места и установить вместо него второй телефон. Нет ничего проще - патч-корд соответствующей розетки отключается от концентратора и переключается на телефонный кросс, что займет у администратора сети никак не больше нескольких минут.
Розетка на 2 порта
Патч-панель , или панель соединений, представляет собой группу розеток RJ-45, смонтированных на пластине шириной 19 дюймов . Это стандартный размер для универсальных коммуникационных шкафов - рэков ( rack ), в которых устанавливается оборудование (концентраторы, серверы, источники бесперебойного питания и т.п.).
На обратной стороне панели смонтированы соединители, в которые монтируются кабели.
Кросс в отличие от патч-панели розеток не имеет. Вместо них он несет на себе специальные соединительные модули. В данном случае его преимущество перед патч-панелью в том, что при его использовании в телефонии вводы можно соединять между собой не специальными патч-кордами , а обычными проводами. Кроме того, кросс можно монтировать прямо на стену - наличия коммуникационного шкафа он не требует. В самом деле, нет смысла приобретать дорогостоящий коммуникационный шкаф, если вся ваша сеть состоит из одного-двух десятков компьютеров и сервера.
Кабели с многожильными гибкими проводниками используются в качестве патч-кордов , то есть соединительных кабелей между розеткой и сетевой платой, либо между розетками на панели соединений или кроссе. Кабели с одножильными проводниками - для прокладки собственно кабельной системы. Монтаж разъемов и розеток на эти кабели совершенно идентичен, но обычно кабели с одножильными проводниками монтируются на розетки рабочих мест пользователей, панели соединений и кроссы, а разъемы устанавливают на гибкие соединительные кабели.
Патч-панель
Как правило, применяются следующие виды разъемов:
S110 - общее название разъемов для подключения кабеля к универсальному кроссу " 110" или коммутации между вводами на кроссе;
RJ-11 и RJ-12 - разъемы с шестью контактами. Первые обычно применяются в телефонии общего назначения - вы можете встретить такой разъем на шнурах импортных телефонных аппаратов. Второй обычно используется в телефонных аппаратах, предназначенных для работы с офисными мини-АТС, а также для подключения кабеля к сетевым платам ARCnet ;
RJ-45 - восьмиконтактный разъем, использующийся обычно для подключения кабеля к сетевым платам Ethernet либо для коммутации на панели соединений.
Разъем RJ-45
В зависимости от того, что с чем нужно коммутировать, применяются различные патч-корды : "45- 45" (с каждой стороны по разъему RJ-45), "110- 45" (с одной стороны S110, с другой - RJ-45) или "110- 110" .
Для монтажа разъемов RJ-11, RJ-12 и RJ- 45 используются специальные обжимочные приспособления, различающиеся между собой количеством ножей (6 или 8) и размерами гнезда для фиксации разъема. В качестве примера рассмотрим монтаж кабеля 5-й категории на разъем RJ-45.
1. Аккуратно обрежьте конец кабеля. Торец кабеля должен быть ровным .
2. Используя специальный инструмент, снимите с кабеля внешнюю изоляцию на длину примерно 30 мм и обрежьте нить, вмонтированную в кабель (нить предназначена для удобства снятия изоляции с кабеля на большую длину). Любые повреждения (надрезы) изоляции проводников абсолютно недопустимы - именно поэтому желательно использовать специальный инструмент, лезвие резака которого выступает ровно на толщину внешней изоляции.
Аккуратно разведите, расплетите и выровняйте проводники. Выровняйте их в один ряд, при этом соблюдая цветовую маркировку. Существует два наиболее распространенных стандарта по разводке цветов по парам: T568A ( рекомендуемый компанией Siemon ) и T568B (рекомендуемый компанией AT&T и фактически наиболее часто применяемый).
На разъеме RJ-45 цвета проводников располагаются так:
Проводники должны располагаться строго в один ряд, без нахлестов друг на друга. Удерживая их одной рукой, другой ровно обрежьте проводники так, чтобы они выступали над внешней обмоткой на 8- 10 мм .
4. Держа разъем защелкой вниз, вставьте в него кабель. Каждый проводник должен попасть на свое место в разъеме и упереться в ограничитель. Прежде чем обжимать разъем, убедитесь, что вы не ошиблись в разводке проводников. При неправильной разводке помимо отсутствия соответствия номерам контактов на концах кабеля, легко выявляемого с помощью простейшего тестера, возможна более неприятная вещь - появление "разбитых пар" ( splitted pairs ).
Для выявления этого брака обычного тестера недостаточно, так как электрический контакт между соответствующими контактами на концах кабеля обеспечивается и с виду все как будто бы нормально. Но такой кабель никогда не сможет обеспечить нормальное качество соединения даже в 10-мегабитной сети на расстояние более 40- 50 метров .
Поэтому нужно быть внимательным и не торопиться, особенно если у вас нет достаточного опыта.
5. Вставьте разъем в гнездо на обжимочном приспособлении и обожмите его до упора-ограничителя на приспособлении. В результате фиксатор на разъеме встанет на свое место, удерживая кабель в разъеме неподвижным . Контактные ножи разъема врежутся каждый в свой проводник, обеспечивая надежный контакт.
Аналогичным образом можно осуществить монтаж разъемов RJ-11 и RJ-12, используя соответствующий инструмент.
Для монтажа разъема S110 специального обжимочного инструмента не требуется. Сам разъем поставляется в разобранном виде. Кстати, в отличие от "одноразовых" разъемов типа RJ разъем S110 допускает многократную разборку и сборку, что очень удобно. Последовательность действий при монтаже следующая:
1. Снимите внешнюю изоляцию кабеля на длину примерно 40 мм , разведите в стороны пары проводников, не расплетая их.
2. Закрепите кабель (в той половинке разъема, на которой нет контактной группы) с помощью пластмассовой стяжки и отрежьте получившийся "хвост".
3. Аккуратно уложите каждый проводник в органайзер на разъеме. Не расплетайте пару на большую, чем требуется, длину - это ухудшит характеристики всего кабельного соединения. Последовательность укладки пар обычная - синяя-оранжевая-зеленая-коричневая ; при этом светлый провод каждой пары укладывается первым.
4. Острым инструментом ( бокорезами или ножом) обрежьте каждый проводник по краю разъема.
5. Установите на место вторую половинку разъема и руками обожмите ее до защелкивания всех фиксаторов. При этом ножи контактной группы врежутся в проводники, обеспечивая контакт.
Коаксиальные кабели
В начале развития локальных сетей коаксиальный кабель как среда передачи был наиболее распространен. Он использовался и используется преимущественно в сетях Ethernet и отчасти ARCnet . Различают "толстый" и "тонкий" кабели.
" Толстый Ethernet ", как правило, используется следующим образом. Он прокладывается по периметру помещения или здания, и на его концах устанавливаются 50-омные терминаторы. Из-за своей толщины и жесткости кабель не может подключаться непосредственно к сетевой плате. Поэтому на кабель в нужных местах устанавливаются "вампиры" - специальные устройства, прокалывающие оболочку кабеля и подсоединяющиеся к его оплетке и центральной жиле. "Вампир" настолько прочно сидит на кабеле, что после установки его невозможно снять без специального инструмента. К "вампиру", в свою очередь, подключается трансивер - устройство, согласовывающее сетевую плату и кабель. И, наконец, к трансиверу подключается гибкий кабель с 15-контактными разъемами на обоих концах - вторым концом он подсоединяется к разъему AUI ( attachment unit interface ) на сетевой плате.
Все эти сложности были оправданы только одним - допустимая максимальная длина "толстого" коаксиального кабеля составляет 500 метров . Соответственно одним таким кабелем можно обслужить гораздо большую площадь, чем "тонким" кабелем, максимально допустимая длина которого составляет, как известно, 185 метров . При наличии некоторого воображения можно представить себе, что "толстый" коаксиальный кабель - это распределенный в пространстве Ethernet-концентратор, только полностью пассивный и не требующий питания. Других преимуществ у него нет, недостатков же хоть отбавляй - прежде всего высокая стоимость самого кабеля (порядка 2,5 долл. за метр), необходимость использования специальных устройств для монтажа (25-30 долл. за штуку), неудобство прокладки и т.п. Это постепенно привело к тому, что "толстый Ethernet " медленно, но верно сошел со сцены, и в настоящее время мало где применяется.
"Тонкий Ethernet " распространен значительно шире, чем его "толстый" собрат. Принцип использования у него тот же, но благодаря гибкости кабеля он может присоединяться непосредственно к сетевой плате. Для подключения кабеля используются разъемы BNC ( bayonet nut connector ), устанавливаемые собственно на кабель, и T-коннекторы , служащие для отвода сигнала от кабеля в сетевую плату. Разъемы типа BNC бывают обжимные и разборные (пример разборного разъема - отечественный разъем СР-50-74Ф).
Т-коннектор
Для монтажа разъема на кабель вам потребуется либо специальный инструмент для обжимки, либо паяльник и плоскогубцы.
Кабель необходимо подготовить следующим образом:
1. Аккуратно отрежьте так, чтобы его торец был ровным. Наденьте на кабель металлическую муфту (отрезок трубки), который поставляется в комплекте с BNC-разъемом.
2. Снимите с кабеля внешнюю пластиковую оболочку на длину примерно 20 мм . Будьте аккуратны, чтобы не повредить по возможности ни один проводник оплетки.
3. Оплетку аккуратно расплетите и разведите в стороны. Снимите изоляцию с центрального проводника на длину примерно 5 мм .
4. Установите центральный проводник в штырек, который также поставляется в комплекте с разъемом BNC. Используя специальный инструмент, надежно обожмите штырек, фиксируя в нем проводник, либо впаяйте проводник в штырек. При пайке будьте особенно аккуратны и внимательны - плохая пайка через некоторое время станет причиной отказов в работе сети, причем локализовать это место будет достаточно трудно.
5. Вставьте центральный проводник с установленным на него штырьком в тело разъема до щелчка. Щелчок означает, что штырек сел на свое место в разъеме и зафиксировался там.
6. Равномерно распределите проводники оплетки по поверхности разъема, если необходимо, обрежьте их до нужной длины. Надвиньте на разъем металлическую муфту.
7. Специальным инструментом (или плоскогубцами) аккуратно обожмите муфту до обеспечения надежного контакта оплетки с разъемом. Не обжимайте слишком сильно - можно повредить разъем или пережать изоляцию центрального проводника.Последнее может привести к неустойчивой работе всей сети. Но и обжимать слишком слабо тоже нельзя - плохой контакт оплетки кабеля с разъемом также приведет к отказам в работе.
Отмечу, что отечественный разъем СР-50 монтируется примерно так же, за исключением того, что оплетка в нем заделывается в специальную разрезную втулку и закрепляется гайкой. В некоторых случаях это может оказаться даже удобнее.
Кратчайшие пути в сети
1. Связный граф G с неотрицательными весами задан списком смежных вершин. Найдите медиану графа G. (Медиана графа - такая вершина графа, что сумма расстояний от нее до остальных вер-шин минимальна).
2. Задан орграф G с неотрицательными весами. Постройте по нему последовательность графов G i с тем же множеством вершин, что и у графа G. Ребро между вершинами в G i проводится тогда, когда расстояние между соответствующими вершинами в G не превышает S=i+Длина_кратчайшего_пути .
3. Задан орграф G с неотрицательными весами, заданными матрицей. Найдите вершины, длины кратчайших путей до ко-торых от выделенного источника равны.
4. Задан орграф G с неотрицательными весами, заданными матрицей A[ u,v ]. Найдите кратчайший путь от источника S до выделенной вершины T. Для этого найти по алгоритму Дейкстры расттояния D[ v ] от S до прочих вершин графа. Затем найти вершину V, такую, что D[ t ]=D[ v ]+A[ v,t ]. Это предпоследняя вершина пути. Предыдущая вершина пути u ищется из условия D[ v ]=D[ u ]+D[ u,v ] и т.д. до тех пор, пока не найдется первая вершина пути.
5. Задан взвешенный граф Е (дугам графа приписаны веса - вещественные числа). Определить, существуют ли два пути одинаковой длины из i-ой вершины в j-ю (написать рекурсивную функцию, определяющую количество путей заданной длины между двумя вершинами).
Краткие теоретические сведения
При передаче дискретных данных по каналам связи применяются два основных типа физического кодирования - на основе синусоидального несущего сигнала и на основе последовательности прямоугольных импульсов. Первый способ часто называется также модуляцией или аналоговой модуляцией , подчеркивая тот факт, что кодирование осуществляется за счет изменения параметров аналогового сигнала. Второй способ обычно называют цифровым кодированием . Эти способы отличаются шириной спектра результирующего сигнала и сложностью аппаратуры, необходимой для их реализации.
При использовании прямоугольных импульсов спектр результирующего сигнала получается весьма широким. Это не удивительно, если вспомнить, что спектр идеального импульса имеет бесконечную ширину. Применение синусоиды приводит к спектру гораздо меньшей ширины при той же скорости передачи информации. Однако для реализации синусоидальной модуляции требуется более сложная и дорогая аппаратура, чем для реализации прямоугольных импульсов.
В настоящее время все чаще данные, изначально имеющие аналоговую форму - речь, телевизионное изображение, - передаются по каналам связи в дискретном виде, то есть в виде последовательности единиц и нулей. Процесс представления аналоговой информации в дискретной форме называется дискретной модуляцией . Термины и часто используют как синонимы.
меткой в виде синего кружочка. Переходы обозначаются горизонтальными или вертикальными линиями. Каждый переход имеет нуль или более входных дуг , исходящих из позиций, и нуль или более исходящих дуг , направленных к выходным позициям. Переход разрешен, если имеется как минимум одна входная метка в каждой из его исходных позиций. Любой разрешенный переход может произойти (fire), удалив все входные метки и установив метки в выходных позициях, что отражает изменение условий (и емкостей). Если числа входных и выходных дуг отличаются, число меток не сохраняется. Если разрешено более одного перехода, может произойти любой из них. Причем один из осуществившихся переходов, может блокировать реализацию всех остальных переходов из данного набора. Формализм сетей Петри не предусматривает каких-либо механизмов преодоления подобных конфликтов. Переход осуществляется, если выполнены все условия реализации данного события. Если два или более переходов могут осуществиться (выполнены все условия) и они не имеют общих входных позиций, то из реализация некоррелирована и может происходить параллельно или в любой последовательности. Выбор перехода, вообще говоря, не определен. В отличии от модели машины конечных состояний здесь отсутствуют комбинированные состояния типа отправитель-канал-получатель, и переходы из состояния в состояние для каждого процесса или объекта рассматриваются независимо. Если условия ни для одного из переходов не реализованы, сеть переходит в заблокированное состояние.
Аналитическое определение. Сеть Петри - набор N = (P, T, F, W, M 0 ), где (P, T, F) - конечная сеть (множество Х = ЗuT конечно), а W: F N\ {O} (знак \ здесь означает разность множеств) и M 0 : PN - две функции, называемые кратностью дуг и начальной пометкой. Первая ставит в соответствие каждой дуге число N>0 (кратность дуги). Если N>0, то при графическом представлении сети число N выписывается рядом с короткой чертой, пересекающей дугу. Дуги с кратностью 1 не помечаются. Каждой позиции p ставится в соответствие некоторое число M 0 (p) N (пометка позиции).
Формально работа сети Петри описывается множеством последовательностей срабатываний и множеством реализуемых разметок позиций.
Для сетей Петри существует удобная алгебраическая нотация. Каждому переходу ставится в соответствие правило грамматики. Каждое правило специфицирует входную и выходную позиции. Текущее состояние сети Петри характеризуется неупорядоченным набором позиций. Каждая позиция присутствует в этом наборе столько раз, сколько меток она имеет.
Norton Commander
Самая простая программа, которая применяется для непосредственной связи двух компьютеров через нуль-модемный кабель, - это Norton Commander . Сервис, предоставляемый данной программой, минимален, т.е. имеется возможность только передавать файлы и при этом работать только на одном компьютере.
Примеры разводки нуль-модемного кабеля для соединения двух компьютеров через последовательные или параллельные порты (рис.1, рис.2).
Рис.1 Для последовательных (COM) портов: разъемы на 25 штырьков, разъемы на 9 штырьков
Рис.2 Для LPT-портов: разъемы на 25 штырьков
Односторонние дороги
6. Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через заданное множество городов.
7. В системе односторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.
8. По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.
9. Определить, можно ли в заданной системе односторонних дорог проехать из города A в город B таким образом, чтобы посетить город C и не проезжать никакой дороги более одного раза.
10. Найти длину самого длинного простого пути от города A до города B в заданной системе односторонних дорог.
11. По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из любого другого города, проезжая не более 100 км.
Оптоволоконный кабель
Оптоволоконные кабели - наиболее перспективная и обеспечивающая наибольшее быстродействие среда распространения сигналов для локальных сетей и телефонии. В локальных сетях оптоволоконные кабели используются для работы по протоколам ATM и FDDI.
Приспособление для снятия изоляции и обжимки разъема
Оптоволокно, как понятно из его названия, передает сигналы при помощи импульсов светового излучения. В качестве источников света используются полупроводниковые лазеры, а также светодиоды. Оптоволокно подразделяется на одно- и многомодовое .
Одномодовое волокно очень тонкое, его диаметр составляет порядка 10 микрон. Благодаря этому световой импульс, проходя по волокну, реже отражается от его внутренней поверхности, что обеспечивает меньшее затухание. Соответственно одномодовое волокно обеспечивает большую дальность без применения повторителей. Теоретическая пропускная способность одномодового волокна составляет 10 Гбит/с. Его основные недостатки - высокая стоимость и высокая сложность монтажа. Одномодовое волокно применяется в основном в телефонии.
Многомодовое волокно имеет больший диаметр - 50 или 62,5 микрона. Этот тип оптоволокна чаще всего применяется в компьютерных сетях. Большее затухание во многомодовом волокне объясняется более высокой дисперсией света в нем, из-за которой его пропускная способность существенно ниже - теоретически она составляет 2,5 Гбит/с.
Для соединения оптического кабеля с активным оборудованием применяются специальные разъемы. Наиболее распространены разъемы типа SC и ST.
Монтаж соединителей на оптоволоконный кабель - очень ответственная операция, требующая опыта и специального обучения, поэтому не стоит заниматься этим в домашних условиях, не будучи специалистом. Если уж вам " приспичило " строить сеть с использованием оптоволокна, легче приобрести кабели с соединителями. Впрочем, учитывая стоимость кабеля, соединителей, а также активного оборудования для оптики, можно предположить, что в домашних и небольших ЛВС это оборудование будет использоваться еще нескоро.
Основной режим (normal mode).
При этом кнопка находится в нажатом состоянии. В основном режиме, Вы можете смотреть и изменять свойства объектов сети, которые находятся на рабочем поле. Для того чтобы открыть диалог со свойствами объекта, необходимо щелкнуть на нем правой кнопкой мыши и, затем выбрать пункт меню "Properties".. В основном режиме Вы также можете перетаскивать имеющиеся объекты по рабочему полю. Вы также можете удалить объект из сети, для этого необходимо выбрать объект и нажать Delete.
Последовательность действий для
Выключите питание обоих компьютеров. Соедините их нуль-модемным кабелем через асинхронные последовательные или параллельные порты. Затем включите компьютеры и запустите программу Norton Commander .
Для каждого компьютера выберите из меню Left или Right элемент Link. При этом на экране появляется диалоговое окно Commander Link (рис. 3):
Рис. 3. Диалоговое окно Commander Link .
Далее вам необходимо выбрать режим работы - Master (главный, ведущий, основной) или Slave (ведомый), а также порт, который вы будете использовать для соединения - COM1, COM2 или LPT1, LPT2.
Для одного из соединяемых компьютеров, выбираем основной режим, а для другого - ведомый. При этом вы сможете работать только на компьютере, находящемся в основном режиме. Ведомый компьютер можно рассматривать только как дополнительную внешнюю память, работать на нем нельзя.
Работая за основным компьютером можно только копировать файлы на или с ведомого компьютера. При этом нет различий в том, в каком направлении копируются файлы.
Turbo Mode - устанавливает повышенную скорость обмена данными. Режим Turbo Mode должен быть установлен одновременно на обоих компьютерах.
При помощи программы Norton Commander вы можете выполнять следующие действия:
копировать и перемещать файлы с одного компьютера на другой; удалять, создавать новые файлы на ведомом компьютере, изменять атрибуты файлов ; создавать, удалять каталоги на ведомом компьютере.
Вы не можете выполнить следующие действия с основного компьютера:
просматривать дерево каталогов ведомого компьютера;
Постановка задачи
Рассмотреть следующие аппаратные средства и оборудование ЛВС:
1. Виды кабелей для сетей ( коаксиальный , неэкранированная витая пара, оптоволокно).
2. Устройства соединения BNC, RJ -45, настенные и модульные розетки, терминаторы.
3. Элементы ЛВС: монтажные короба, патч-панели , патч-корды , абонентские шнуры. Разделение кабеля UTP по стандартам TIA / EIA -568 A / B .
4. Варианты исполнения активных концентраторов ( хабы , комутаторы , MAU).
Ознакомиться с основными способами соединения компьютеров для обмена информацией:
непосредственная связь, через асинхронный порт; связь с использованием модема; связь через локальные сети.
Пример программы "Server"
#include <stdio.h>
#include <conio.h>
#include <dos.h>
main() {
union REGS rr;
int dataport,statusport,ctrlport; /* Номера портов */
unsigned char stat; /* Байт статуса */
int i, c;
int b1, b2, count=0, flag;
/* Определение адресов портов принтера */
dataport=peek(0x40,8);
statusport=dataport+1;
ctrlport=statusport+1;
outportb(dataport,0);
clrscr();
printf(" Порты LPT1\n");
printf(" Базовый адрес %03X\n",dataport);
printf(" Адрес порта состояния %03X\n",statusport);
printf(" Адрес порта управления %03X\n",ctrlport);
outportb(dataport,0);
flag=0;
while(flag==0) {
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)!=0) {
count=1;
outportb(dataport,0); }
}
printf("\n Введите число : ");
scanf("%d",&c);
b1=(c&15)|16;
b2=(c>>4)&15;
outportb(dataport,b1);
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)==0) {
count=1;
outportb(dataport,b2); }
}
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)!=0) {
count=1;
outportb(dataport,16); }
} }
return 0;
}
Пример программы "Slave"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
main() {
union REGS rr;
int dataport,statusport,ctrlport; /* Номера портов */
unsigned char stat; /* Байт статуса */
int i, count=0, c, c1, res;
/* Определение адресов портов принтера */
dataport=peek(0x40,8);
statusport=dataport+1;
ctrlport=statusport+1;
clrscr();
printf(" Порты LPT1\n");
printf(" Базовый адрес %03X\n",dataport);
printf(" Адрес порта состояния %03X\n",statusport);
printf(" Адрес порта управления %03X\n",ctrlport);
outportb(dataport,0);
stat=inportb(statusport);
printf(" Состояние принтера - ");
for (i=7; i>=0; i--)
if ((stat>>i)&1) printf("1"); else printf("0");
while (!kbhit()) {
printf("\nEtap 1\n");
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)==0) {
count=1;
c=(stat>>3)&15;
outportb(dataport,16); }
}
printf("Etap 2\n");
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)!=0) {
stat=inportb(statusport);
c1=(stat<<1)&240;
count=1;
outportb(dataport,0); }
}
res=c|c1;
printf("%d\n",res);
count=0;
while(count==0) {
stat = inportb(statusport);
if((stat&128)==0) {
count=1;
outport(dataport,0); }
}}
return 0;
}
| Оглавление | Вперед |
| Каталог | Индекс раздела |
Прямое кабельное соединение в Windows ( Direct Cable Connection - DCC )
Установить оснастку Direct Cable Connection (DCC). После этого выбрать Пуск/Программы/Стандартные/Связь , чтобы запустить коммуникационный модуль для непосредственного кабельного соединения (рис. 4).
Рис. 4. Непосредственное кабельное соединение
Если вы используете DCC впервые, то процессом установки управляет программа - "Мастер", которая может потребовать у вас выполнения определенных шагов с помощью других модулей Windows 95/98. Например, нужно установить один и тот же сетевой протокол на обоих компьютерах и разрешить совместное использование принтеров и файлов (обратитесь к диалоговому окну Networking dialog - настройка сетевого оборудования панели управления, чтобы подтвердить выбор обоих этих условий).
После этого DCC потребует, чтобы вы определили одну систему в качестве "ведомой" машины, а другую в качестве "ведущей", но впоследствии эту конфигурацию можно будет поменять.
Вам также нужно определить, какие ресурсы "хозяина" вы хотите использовать совместно с клиентом. Чтобы установить разделяемые ресурсы на главной машине, запустите на ней программу Explorer (Проводник), выделите каталог, который хотите назначить для совместного использования, выберите пункт File / Properties (Файл/Свойства) и перейдите к закладке Sharing (Доступ) появившегося диалогового окна. Переключатель Shared As (Разделять как...) позволяет вам указать разделяемое имя, которое будет воспринято клиентом. Если же вы подключены к сети NetWare , то нажав кнопку Add (Добавить), можно просмотреть на экране имеющуюся на сервере информацию о пользователях и групповой безопасности, которой вы можете воспользоваться для управления сетевым доступом к совместно используемым ресурсам вашего компьютера. Программа-"мастер" DCC Wizard позволит вам при необходимости защитить с помощью пароля "ведомую" машину от несанкционированного внешнего доступа.
После того как вы должным образом установили DCC и соединили компьютеры специальным параллельным или последовательным кабелем, запустите программу, устанавливающую соединение сначала на "ведомом", а затем и на "ведущем" компьютере.
Если для доступа необходим пароль, диалоговое окно выдаст запрос на его ввод; появятся также приглашения на регистрацию в сети. После установления соединения "ведомая" машина будет показана как сервер в сетевом окружении ( Network Neighborhood ) клиента. Свойства этого компьютера покажут совместно используемые ресурсы, которые вы задали с помощью программы Explorer главной машины. Теперь можно переносить файлы с любой из этих систем в другую простыми средствами drag-and-drop .
Если вы используете соединение DCC для более сложных операций, нежели просто обмен файлами, то вам следует отобразить совместно используемые ресурсы "ведомой" машины на диски управляющего компьютера. Это необходимо сделать, например, если вы хотите использовать 16-разрядные прикладные программы для доступа к файлам на "ведомой" машине. Чтобы определить новые диски, откройте Network Neighborhood (Сетевое окружение), выберите нужный вам ресурс (например, любой каталог), выберите пункт View / Toolbar и по кнопке Map Network Drive (Подключить сетевой диск) выберите букву для диска из выпадающего списка (необходимо также ввести точный путь UNC ( Universal Naming Convention - универсальное соглашение об именовании) для данного ресурса, так как средства просмотра здесь отсутствуют). Распределение дисков может быть сохранено и в дальнейшем, если вы установите флажок Reconnect (Выполнить повторное соединение) для процедуры входа в систему.
Может быть, непосредственное кабельное соединение - не самое простое средство в Windows 95/98, но способность DCC отображать ресурсы "ведомого" компьютера на диски клиента позволяет рассматривать его не только как удобное средство для передачи данных, но и практически как настоящее сетевое соединение.
Проектирование сети.
Проектирование сети заключается в размещении объектов сети на рабочем поле и установке связей между ними. Если возникает необходимость использования позиции, то все что нужно сделать - это щелкнуть левой кнопкой мыши над требуемым объектом в панели инструментов (в данном случае - позицией), а затем опять щелкнуть левой кнопкой мыши на рабочем поле в том месте, куда Вы хотите разместить объект (позицию). На рабочем столе должен появиться кружок синего цвета с белой окантовкой - это и есть позиция. Далее точно так же, Вы можете поместить на рабочий стол любой из имеющихся переходов.
После того, как Ваш проект или его часть будут созданы, Вы можете протестировать его в пошаговом режиме или запустить в режим автономной работы. В последнем случае, программа самостоятельно будет переходить к следующему состоянию сети.
Сохранение сети осуществляется либо выбором соответствующего пункта в меню "File", либо нажатием на кнопку с изображением дискеты (опять же на панели управления), либо нажатием F2. Для загрузки сети или создания новой сети также предусмотрены соответствующие пункты меню, кнопки на панели управления и горячие клавиши (F3 соответственно).
4.5.1 Спроектировать 3 вида сетей Петри, изображенных на рис. 1, рис.2 и рис 3.
Программирование параллельного порта (LPT).
DOS может работать с тремя параллельными принтерами, именуемыми LPT1, LPT2, LPT3. Каждый принтер имеет по три порта: порт вывода (базовый порт), порт состояния и порт управления. Адреса портов строго не фиксированы. В области данных BIOS по адресам 0040:0008, 0040:000A, 0040:000C содержатся адреса базовых портов для LPT1, LPT2, LPT3 соответственно. Адрес порта состояния - на 1 больше базового, порта управления - еще на 1 больше.
Для обращения к регистрам LPT удобно использовать следующий алгоритм :
/*============== Получение статуса портов ==============*/
# include < dos.h >
main () {
union REGS rr ;
int dataport , statusport , ctrlport ; /* Номера портов */
unsigned char stat ; /* Байт статуса */
int i ; /* Определение адресов портов принтера */
dataport =peek(0x40,8);
statusport =dataport+1;
ctrlport =statusport+1;
clrscr ();
/* Проверка состояний */
printf (" Порты LPT1 = %03X, %03X, %03X\n", dataport,statusport,ctrlport );
stat= inportb ( dataport );
printf ("\ n Регистр выходных данных - ");
for ( i =7; i >=0; i --) if ((stat>> i )&1) printf ("1"); else printf ("0");
stat= inportb ( statusport );
printf ("\ n Регистр статуса - ");
for ( i =7; i >=0; i --) if ((stat>> i )&1) printf ("1"); else printf ("0");
stat= inportb ( ctrlport );
printf ("\ n Регистр управления - ");
for ( i =7; i >=0; i --) if ((stat>> i )&1) printf ("1"); else printf ("0");
}
Регистр выходных данных - это тот адрес порта, через который проходит каждый байт данных, посылаемый в принтер.
Регистр статуса сообщает различную информацию о принтере; процессор может постоянно опрашивать его, чтобы распознать момент, когда все в порядке и можно посылать данные. Регистр статуса сообщает также, что произошла ошибка на принтере.
Регистр управления инициализирует адаптер и управляет выводом данных. Он может также подготавливать параллельный порт для операций прерывания, с тем чтобы принтер посылал прерывание к процессору, когда он готов к приему очередного символа, оставляя процессор свободным для других дел.
Значения битов регистров статуса и управления:
Регистр управления:
| бит 0 | 0 = нормальная установка, 1 = вызывает вывод байта данных |
| 1 | 0 = нормальная установка, 1 = автоматический перевод строки после возврата каретки |
| 2 | 0 = инициализировать порт принтера, 1 = нормальная установка |
| 3 | 0 = отмена выбора принтера, 1 = нормальная установка |
| 4 | 0 = прерывание принтера запрещено, 1 = разрешено |
| 5-7 | не используются |
| бит 0-2 | не используются |
| 3 | 0 = ошибка принтера, 1 = нет ошибки |
| 4 | 0 = принтер off-line, 1 = принтер on-line |
| 5 | 0 = бумага вставлена, 1 = нет бумаги |
| 6 | 0 = принтер подтверждает прием символа, 1 = нормальная установка |
| 7 | 0 = принтер занят, 1 = принтер свободен |
Пути в бесконтурной сети
Займемся теперь вторым случаем, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O(n 2 ), а именно случаем, когда граф является бесконтурным (теперь веса дуг могут быть произвольными). При описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером.
Исходной информацией для алгоритма поиска расстояний D[v 1 ]= d (v 1 ,v i ), i=1,..., n от источника v 1 до всех заданных вершин в бесконтурном графе является ориентированный граф (V,Е), где V={v 1 ,..., v n }, и для произвольной дуги < v i ,v j >IЕ имеем i < j . Граф опре-деляется линейными списками Предш [ v ], vIV [Липский,1988].
D[v 1 ]:=0;
For j:=2 to n do D[v j ]:= ? ;
For j:=2 to n do
For v i I Предш [v j ] do D[v j ]:=min(D[v j ],D[v i ]+A[v i ,v j ])
Режим создания соединения (adding vector).
При данном режиме осуществляется соединение позиций и переходов. Для того чтобы соединить два объекта между собой, необходимо сначала указать объект с которого начнется соединение, щелкнув на нем левой кнопкой мыши. Линия может быть ломаной и установка очередного узла линии осуществляется нажатием левой кнопки мыши на рабочем поле. Для завершения соединения, необходимо также как и вначале щелкнуть левой кнопкой мыши над одним из объектов. При этом следует учесть, что соединение можно установить только между противоположными объектами - позицией и переходом.
Режим вставки перехода (adding bridge).
Эквивалентен предыдущему режиму, но при нажатии на левую кнопку мыши вставляется не позиция, а переход, при нажатии на уже существующий переход переход поворачивается на 15 против часовой стрелки.
Режим вставки позиции (adding place).
Во время этого режима, появляется возможность вставить позицию на рабочее поле, для чего в нужном месте необходимо щелкнуть левой кнопкой мыши. При нажатии на существующую позицию в нее добавится 1 фишка.
Система дорог
Система дорог [Касьянов,Сабельфельд,1986,с.97-98] - это размеченный мультиграф (без петель), который отличается от графа тем, что в нем одна и та же пара (различных) вершин может быть связана более чем одним ребром. При этом вершины соответствуют городам, а ребра - дорогам. Односторонним дорогам соответствуют дуги, а двусторонним дорогам - ребра.
Каждая дорога имеет некоторую длину - положительное вещественное число. Понятие пути, достижимости и замкнутого пути определяются для системы дорог аналогично подобным понятиям для графа и ориентированного графа. Длина пути в системе дорог - это сумма длин дорог этого пути. Расстояние между двумя городами - это длина минимального пути между этими городами.
4. Ход работы
Пример 1.
Нахождение расстояния от источника до всех вершин (метод Форда-Беллмана ). Нахождение кратчайшего пути из S в T.
PROGRAM F _ o _ r _ d __ B _ e _ l _ l _ m _ a _ n ;
const MaxNodes = 5;
B = 1000; { Машинный эквивалент "бесконечности" 7 0}
type NodePtr = 1.. MaxNodes ;
Matrix = Array [NodePtr,NodePtr] of Integer;
Matrix1 = Array [NodePtr] of Integer;
{ Описание типа узла стека }
TipElement = NodePtr;
svqz = ^Zveno;
Zveno = Record
Element: TipElement;
Sled: svqz
end;
var A : Matrix; { Матрица весов дуг }
D : Matrix1; { Матрица расстояний от источника }
{ до всех вершин графа }
S : NodePtr ; { Начальная вершина пути (источник) }
T : NodePtr ; { Конечная вершина пути }
u,v : NodePtr;
i,j,k : NodePtr;
Stack : svqz ; { Указатель на рабочий стек }
UkZv : svqz;
{ ------------------------------------------- }
PROCEDURE U_d_a_l_e_n_i_e (var Stack: svqz;
var Klad : TipElement );
{ Удаление элемента из стека Stack и сохранение его в Klad }
var q: svqz;
BEGIN
If Stack=Nil
then WriteLn ('Попытка выбора из пустого стека!')
else begin
Klad:=Stack^.Element; q:=Stack;
Stack:=Stack^.Sled;
Dispose (q)
end
END;
{ ---------------------------------------------------------- }
PROCEDURE V__S_t_a_c_k (var Stack: svqz; Elem: TipElement);
{ Помещение Elem в стек Stack }
var q: svqz;
BEGIN
New (q); q^.Element:=Elem; q^.Sled:=Stack; Stack:=q
END;
{ --- }
BEGIN
{ Ввод матрицы весов дуг заданного графа }
WriteLn ('Вводите элементы матрицы весов дуг по стро-кам :');
For i:=1 to MaxNodes do
For j:=1 to MaxNodes do
begin
Write (' Введите A[',i,',',j,']: ');
ReadLn (A[i,j]);
If A[i,j]=0 then A[i,j]:=B
end ;
Write ('Введите источник: '); ReadLn ( S );
{ Инициализация }
For i:=1 to MaxNodes do D[i]:=A[S,i];
D[S]:=0;
{ Вычисление матрицы расстояний от источника до всех вершин графа }
For k:=1 to MaxNodes-2 do
For i:=1 to MaxNodes do
If i<>S
then For j:=1 to MaxNodes do
If D[i]>D[j]+A[j,i] then D[i]:=D[j]+A[j,i];
{ Вывод матрицы расстояний от источника до всех вершин графа }
WriteLn (' Матрица расстояний : ');
For i:=1 to MaxNodes do Write (D[i],' ');
WriteLn ;
{ Нахождение кратчайшего пути из S в T с помощью }
{ построенной матрицы расстояний }
Write ('Введите конечную вершину пути: '); ReadLn (T);
Stack:=Nil; V__S_t_a_c_k (Stack,T); v:=T;
While v<>S do
begin
For i:=1 to MaxNodes do
If D[v]=D[i]+A[i,v] then u:=i;
V__S_t_a_c_k (Stack,u); v:=u
end ;
{ Вывод кратчайшего пути на экран дисплея }
Write ('Кратчайший путь: '); UkZv:=Stack ;
While UkZv<>Nil do
begin Write (UkZv^.Element,' '); UkZv:=UkZv^.Sled end;
WriteLn
END.
Рассмотрим тестовый пример [Евстигнеев,Мельников,1981]. Вычислить кратчайшее расстояние между вершинами s и t в сети:
(s,a,4), (s,d,6), (a,d,-3), (a,b,8), (b,t,2), (a,e,5),
(d,e,2), (e,c,3), (d,c,11), (c,b,-4), (c,t,7), (b,d,-6).
Перенумеруем вершины следующим образом:
(s,1), (a,2), (d,3), (b,4), (c,5), (e,6), (t,7),
а затем выпишем матрицу весов дуг
и применим алгоритм Форда-Беллмана к этой матрице. В результате получим:
Введите источник: 1
Матрица расстояний: 0 4 -4 2 1 -2 4
Введите конечную вершину пути: 7
Кратчайший путь: ...
Компьютер "зависает", ибо в графе имеется контур отрицательной длины 3-6-5-4 (его длина -6+2+3-4=-5), что приводит к появлению бесконечного множества путей, каждый из которых "короче" предыдущего, например:
путь 1-2-3-6-5-4-7 с длиной 4,
путь 1-20-3-6-5-4-3-6-5-4-7 с длиной -1,
путь 1-2-3-6-5-4-3-6-5-4-3-6-5-4-7 с длиной -6 и т.д.
Алгоритмом Форда- Беллмана определить кратчайший путь нельзя.
Пример 2.
Нахождение расстояния от источника до всех вершин в графе с неотрицательными весами (метод Дейкстры ). Нахождение кратчайшего пути из S в T.
PROGRAM D _ i _ j _ k _ s _ t _ r _ a ;
const MaxNodes = 6;
B = 1000; { Машинный эквивалент "бесконечности" 7 0}
type NodePtr = 1.. MaxNodes ;
Matrix = Array [NodePtr,NodePtr] of Integer;
Matrix1 = Array [NodePtr] of Integer;
{ Описание типа узла стека }
TipElement = NodePtr;
svqz = ^Zveno;
Zveno = Record
Element: TipElement;
Sled: svqz
end;
var A : Matrix; { Матрица весов дуг }
D : Matrix1; { Матрица расстояний от источника }
{ до всех вершин графа }
S : NodePtr ; { Начальная вершина пути (источник) }
T : NodePtr ; { Конечная вершина пути }
Q : Set of NodePtr;
u,v : NodePtr;
i,j,k : NodePtr;
Min : Integer;
Stack : svqz ; { Указатель на рабочий стек }
UkZv : svqz;
{ ---------------------------------------------------------- }
PROCEDURE U_d_a_l_e_n_i_e (var Stack: svqz; var Klad: TipElement);
{ Удаление элемента из стека Stack и сохранение его в Klad }
var q: svqz;
BEGIN
If Stack=Nil
then WriteLn ('Попытка выбора из пустого стека!')
else begin
Klad:=Stack^.Element; q:=Stack; Stack:=Stack^.Sled;
Dispose (q)
end
END;
{ ---------------------------------------------------------- }
PROCEDURE V__S_t_a_c_k (var Stack: svqz; Elem: TipElement);
{ Помещение Elem в стек Stack }
var q: svqz;
BEGIN
New (q); q^.Element:=Elem; q^.Sled:=Stack; Stack:=q
END;
{ --- }
BEGIN
{ Ввод матрицы весов дуг заданного графа }
WriteLn ('Вводите элементы матрицы весов дуг по стро-кам :');
For i:=1 to MaxNodes do
For j:=1 to MaxNodes do
begin
Write (' Введите A[',i,',',j,']: ');
ReadLn (A[i,j]);
If A[i,j]=0 then A[i,j]:=B
end ;
Write ('Введите источник: '); ReadLn ( S );
{ Инициализация }
For i:=1 to MaxNodes do D[i]:=A[S,i];
D[S]:=0; Q:=[];
For i:=1 to MaxNodes do Q:=Q+[i];
Q:=Q-[S];
{ Вычисление матрицы расстояний от источника до всех вершин гра-фа }
While Q<>[] do
begin
Min:=B;
For i:=1 to MaxNodes do
If (i IN Q) AND (D[i]<Min)
then begin Min:=D[i]; u:=i end;
Q:=Q-[u];
For i:=1 to MaxNodes do
If i IN Q
then If D[i]>D[u]+A[u,i]
then D[i]:=D[u]+A[u,i]
end ;
{ Вывод матрицы расстояний от источника до всех вершин графа }
WriteLn (' Матрица расстояний : ');
For i:=1 to MaxNodes do Write (D[i],' ');
WriteLn ;
{ Нахождение кратчайшего пути из S в T }
Write ('Введите конечную вершину пути: '); ReadLn (T);
Stack:=Nil; V__S_t_a_c_k (Stack,T); v:=T;
While v<>S do
begin
For i:=1 to MaxNodes do
If D[v]=D[i]+A[i,v] then u:=i;
V__S_t_a_c_k (Stack,u); v:=u
end ;
{ Вывод кратчайшего пути на экран дисплея }
Write ('Кратчайший путь: '); UkZv:=Stack ;
While UkZv<>Nil do
begin Write (UkZv^.Element,' '); UkZv:=UkZv^.Sled end;
WriteLn
END.
Приведем контрпример к алгоритму Дейкстры [Евстигнеев, Мель-ников , 1981]: вычислим кратчайшее расстояние между вершинами s и t в сети: ( s , a ,4),( s , d ,6), ( a , d ,-3), ( a , b ,8), ( b , t ,2), ( a , e ,5), ( d , e ,2), ( e , c ,3), ( d , c ,11), ( c , b ,-4), ( c , t ,7), ( b , d ,-6). Заметим, что мы допустили существование отри-цательных весов!
Перенумеруем вершины: (s,1),(a,2),(d,3),(b,4),(c,5),(e,6),(t,7), а затем
выпишем матрицу весов дуг:
и применим алгоритм Дейкстры к этой матрице. В результате получим:
Введите источник: 1
Матрица расстояний: 0 4 1 2 6 3 4
Введите конечную вершину пути: 7
Кратчайший путь: 1 2 3 6 5 4 7
Однако, как уже было отмечено ранее, в графе имеется контур отрицательной длины 3-6-5-4 (его длина -6+2+3-4=-5), что приводит к появлению бесконечного множества путей, каждый из которых "короче" предыдущего, например:
путь 1-2-3-6-5-4-7 с длиной 4,
путь 1-2-3-6-5-4-3-6-5-4-7 с длиной -1,
путь 1-2-3-6-5-4-3-6-5-4-3-6-5-4-7 с длиной -6 и т.д.
Таким образом, кратчайший путь алгоритмом Дейкстры определить нельзя, так как в графе имеется контур отрицательной длины.
Пример 3.
Нахождение расстояний от источника до всех вершин в бесконтурном графе.
PROGRAM P_a_t_h;
const MaxNodes = 9;
B = 1000; { Машинный эквивалент "бесконечности" 7 0}
type NodePtr = 1..MaxNodes;
Matrix = Array [NodePtr,NodePtr] of Integer;
Matrix1 = Array [NodePtr] of Integer;
{ Описание типа узла стека }
TipElement = NodePtr;
svqz = ^Zveno;
Zveno = Record
Element: TipElement;
Sled: svqz
end;
var A : Matrix; { Матрица весов дуг }
D : Matrix1; { Матрица расстояний от источника }
{ до всех вершин графа }
S : NodePtr ; { Начальная вершина пути (источник) }
u,v : NodePtr;
i,j,k : NodePtr;
{ ----------------------- }
BEGIN
{ Ввод матрицы весов дуг заданного графа }
WriteLn ('Вводите элементы матрицы весов дуг по стро-кам :');
For i:=1 to MaxNodes do
For j:=1 to MaxNodes do
begin
Write (' Введите A[',i,',',j,']: ');
ReadLn (A[i,j]);
If A[i,j]=0 then A[i,j]:=B
end;
S:=1;
{ Инициализация }
For j:=2 to MaxNodes do D[j]:=B;
D[S]:=0;
{ Вычисление матрицы расстояний от источника до всех вершин графа }
For j:=2 to MaxNodes do
For i:=1 to MaxNodes do
If (A[i,j]<>0) AND (D[j]>D[i]+A[i,j])
then D[j]:=D[i]+A[i,j];
{ Вывод матрицы расстояний от источника до всех вершин графа }
WriteLn (' Матрица расстояний : ');
For i:=1 to MaxNodes do Write (D[i],' ');
WriteLn
END.
Проверьте работу программы для следующей путевой матрицы:
Приведенный алгоритм может найти применение в методах управ-ления выполнением проекта, называемых PERT ( Project Evaluation and Review Technique ) или CPM ( Critical Path Method ). Эти методы основываются на построении графа (сети PERT, сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме этого, мы предполагаем, что для произвольных дуг этого графа ( u,v ) и ( v,t ) задача, изображаемая дугой ( u,v ), должна быть закончена перед началом решения задачи, изображаемой дугой ( v,t ).
Легко заметить, что такой граф должен быть бесконтурным .
Нашей задачей является нахождение самого длинного пути из вер-шины s , соответствующей началу проекта, до вершины t , соответствующей его окончанию. Такой путь называется критическим. Его длина определяет время, необходимое для реализации всего проекта. Эта задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса A( u,v ), где u -> v , на обратный. Так, например, выполните предыдущую программу для следующей путевой матрицы:
Пример 4 [Библиотека,1975,с.100-104].
Планирование критического пути (анализ сети ПЕРТ).
PROGRAM C_r_i_t_P_a_t_h;
{ Автор алгоритма : Leavenworth B. (CACM,1961,3) }
type Massiv = Array [1..20] of Integer;
var n : Integer ; { Общее количество работ по проекту }
{ (количество ребер ориентированного графа) }
i : Massiv ; { Вектор-пара, представляющая k-ю работу, }
j : Massiv ; { которая понимается как стрелка, связыва - }
{ ющая событие i [ k ] с событием j [ k ] }
{ Граф задан массивом ребер: }
{ ( i [1], j [1]),( i [2], j [2]),...,( i [ n ], j [ n ]) }
{ Должно быть выполнено: }
{ i [1]=1, i [ k ]< i [k+1], i [ k ]< j [ k ] }
dij : Massiv ; { dij [ k ] - продолжительность k-й операции }
s1 : Massiv ; { s1[ k ] - самый ранний срок начала k-й }
{ операции }
s2 : Massiv ; { s2[ k ] - самый поздний срок начала k-й }
f1 : Massiv ; { f1[ k ] - самый ранний срок завершения k-й }
f2 : Massiv ; { f2[ k ] - самый поздний срок завершения k-й }
{ операции }
tf : Massiv ; { tf [ k ] - полный резерв времени k-й операции}
ff : Massiv ; { ff [ k ] - свободный резерв времени k-й }
{ операции }
k : Integer ; { Параметр цикла }
{ ----------------------------------------------------------- }
PROCEDURE C_r_i_t_i_c_a_l_P_a_t_h (n: Integer; i: Massiv;
j: Massiv; dij: Massiv;
var s1,s2,f1,f2,tf,ff: Massiv);
var k,index,max,min: Integer;
ti,te : Massiv;
BEGIN
index:=1;
For k:=1 to n do
begin
If i[k]=index+1 then index:=i[k];
ti[k]:=0; te[k]:=9999
end;
For k:=1 to n do
begin
max:=ti[i[k]]+dij[k];
If ti[j[k]]<max then ti[j[k]]:=max
end;
te[j[n]]:=ti[j[n]];
For k:=n downto 1 do
begin
min:=te[j[k]]-dij[k];
If te[i[k]]>min then te[i[k]]:=min
end;
For k:=1 to n do
begin
s1[k]:=ti[i[k]]; f1[k]:=s1[k]+dij[k];
f2[k]:=te[j[k]]; s2[k]:=f2[k]-dij[k];
tf[k]:=f2[k]-f1[k]; ff[k]:=ti[j[k]]-f1[k]
end
END;
{ --- }
BEGIN
Write (' Введите общее количество работ по проекту: ');
ReadLn (n);
For k:=1 to n do
begin
Write ('Вводите начало, конец дуги и продолжительность: ');
ReadLn (i[k],j[k],dij[k])
end;
C_r_i_t_i_c_a_l_P_a_t_h (n,i,j,dij,s1,s2,f1,f2,tf,ff);
{ Вывод результатов }
Write ('Самый ранний срок начала : ');
For k:=1 to n do Write (s1[k]:2,' '); WriteLn;
Write ('Самый поздний срок начала : ');
For k:=1 to n do Write (s2[k]:2,' '); WriteLn;
Write ('Самый ранний срок завершения : ');
For k:=1 to n do Write (f1[k]:2,' '); WriteLn;
Write ('Самый поздний срок завершения: ');
For k:=1 to n do Write (f2[k]:2,' '); WriteLn;
Write ('Свободный резерв времени : ');
For k:=1 to n do Write (ff[k]:2,' '); WriteLn;
Write ('Полный резерв времени : ');
For k:=1 to n do Write (tf[k]:2,' '); WriteLn;
{ Определение критического пути. Критический путь задается }
{ стрелками, соединяющими события, для которых полный ре- }
{ зерв времени равен нулю }
Write ('Критический путь: '); Write (1,' ');
For k:=1 to n do
If tf[k]=0 then Write (j[k],' ')
END.
Темы для предварительного изучения
1. Общие принципы построения вычислительных систем
1. Связь компьютера с периферийными устройствами
2. Взаимодействие двух компьютеров.
3. Проблемы физической передачи данных по линиям связи.
Возможно использование следующих элементов сети :
Позиция (Place) - Содержит определенное количество фишек, количество которых отображается точками или числом, отсутствие числа или точки означает отсутствие фишки в позиции. Переход (Bridge) - Моделирует некоторый процесс, имеет время выполнения (м.б. выбрана случайная величина в заданном диапазоне). При запуске сети занятость перехода отображается красной точкой в центре перехода. Линия (Vector) - Является связующим элементом между переходами и позициями, в канонической сети Петри вводится понятие "пропускная способность" - число фишек, которое проходит через линию при запуске, если число фишек в позиции меньше чем пропускная способность, то переход не может сработать. Я ввел расширение для линии: число переносимых фишек через линию и минимальное число фишек для срабатывания перехода могут не совпадать , (это может использоваться для организации переходов типа "проверка"). Опорная точка (Vector point) - не несет смысловой нагрузки, используется только для удобства представления длинных линий.
