є технології Web-служб. Технологія Web-служб надає новий Механізм создания розподіленіх Додатків. За суті, вона є Поширеними технології создания Додатків на базі компонентів и на сферу Internet;
? Модель безпеки, что програмісті могут легко використовуват у своих програмах;
? Потужні Інструментальні засоби розробки.
2. Основні алгоритми на графах
. 1 Поиск завширшки
Поиск завширшки (breadth-first search) є одним з простих алгоритмів для обходу графа и є основою для багатьох Важлива алгоритмів для роботи з графами. Например, алгоритм Прима (Prim) поиска мінімального остовного дерева або алгоритм Дейкстри (Dijkstra) поиска найкоротшого шляху з однієї вершини Використовують Ідеї, схожі з ідеямі, вікорістовуванімі при поиска завширшки.
Поиск завширшки БУВ формально запропонованій Е. Ф. Муром в контексті поиска шляху в лабірінті. Лі Незалежності відкрів тієї ж алгоритм в контексті розводкою провідніків на друкованне платах.
Поиск завширшки может застосовуватіся для вирішенню Завдання, пов'язаних з теорією графів,:
Хвильовий алгоритм поиска шляху в лабірінті (алгоритм Лі);
Хвилевой трасування друкованне плат;
поиск компонент зв'язності в графі;
поиск найкоротшого шляху между двома Вузли незваженого графа;
поиск в пространстве станів: знаходження решение задачі з найменших числом ходів, если КОЖЕН стан системи можна представіті вершиною графа, а переходь з одного стану в інше - ребрами графа;
знаходження найкоротшого циклу в орієнтованому незваженому графові;
знаходження усіх вершин и ребер, что лежати на якому-небудь найкоротшому шляху между двома вершинами a и b;
поиск збільшуючого шляху в алгорітмі Форда-Фалкерсона (алгоритм Едмондса-Карпа).
Нехай завдань граф G=(V, Е) i віділена початкова (source) вершина s. Алгоритм поиска завширшки систематично обходити усі ребра G для Відкриття усіх вершин, досяжніх з s, обчіслюючі при цьом відстань (мінімальну Кількість ребер) від s до кожної досяжної з s вершини. Крім того, в процессе обходу будується дерево поиска завширшки з коренем s, что містіть усі досяжні вершини. Для кожної досяжної з s вершини v шлях в дереві поиска завширшки відповідає найкоротшому (тобто что містіть найменша Кількість ребер) шляху від s до v в G. Алгоритм працює як для орієнтованих, так и для неорієнтованіх графів.
Поиск завширшки має таку Назву того, что в процессе обходу ми йдемо вшир, тобто Перш чем приступити до поиска вершин на відстані k +1, віконується обхід усіх вершин на відстані k.
Для відстежування роботи алгоритму поиск завширшки розфарбовує вершини графа в білий, сірий и чорний кольори. Спочатку усі вершини білі, и пізніше смороду могут дива сірімі, а потім чорними. Колі вершина відкрівається (discovered) в процессе поиска, вон забарвлюється. Таким чином, сірі и чорні вершини - це вершини, Які Вже були відкриті, но алгоритм поиска завширшки по-різному працює з ними, ані щоб Забезпечити Оголошення порядок обходу. Если и вершина u чорного кольору, то вершина v або сіра, або чорна, тобто усі вершини, суміжні з чорною, Вже відкриті. Сірі вершини могут мати білих сусідів, будучи межею между відкрітімі и невідкрітімі вершинами.
Поиск завширшки будує дерево поиска завширшки, Пожалуйста спочатку складається з одного кореня, Яким є початкова вершина s. Если в процессе сканування списку суміжності Вже Відкритої вершини и відкрівається біла вершина v, то вершина v и ребро (u, v) додаються в дерево. Ми говоримо, что и є попередниками (predecessor), або батьком (parent), v в дереві поиска вшир. Оскількі вершина может буті Відкрита НЕ более одного разу, вона має НЕ більш одного батька. Взаєміні предків и нащадків визначаються в дереві поиска завширшки як завжди - если и находится на шляху від кореня s до вершини v, то u є предком v, av - Нащадки u.
Наведено нижчих процедура поиска завширшки BFS пріпускає, что вхідній граф G=(V, Е) уявлень помощью Списків суміжності. Крім того, підтрімуються додаткові Структури даних в Кожній вершіні графа. Колір кожної вершини u и v зберігається в змінній color [u], а попередники - в змінній? [u]. Если попередника у і немає (например, если u=s або u НЕ Відкрита), то? [u]=NIL. Відстань від s до вершини u, что обчіслюється алгоритмом, зберігається в полі d [u]. Алгоритм вікорістовує черго Q типом FIFO для роботи з множини сіріх вершин
Взагалі черга в програмуванні це дінамічна структура даних, что працює за принципом перший прийшов - перший Пішов (англ. FIFO - first in, first out). У Черги є голова (англ. Head) та хві...