Размещено на http://www.allbest.ru/

Содержание

Введение

1. FTP-протокол

1.1 Модели работы FTP

1.2 Режимы передачи файлов по протоколу FTP

1.3 Программное обеспечение для осуществления соединения 9 с помощью протокола FTP

1.4 Службы архивов FTP

1.5 Некоторые проблемы FTP-серверов

1.6 Команды FTP протокола

1.7 Протоколы TFTP и SFTP

1.8 Утилита FTP

2. Алгоритм Штор-Вагнера

Заключение

Список используемой литературы

Приложение А (обязательное) Листинг программы

Введение

протокол файл сервер

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

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

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

Пользователю глобальной сети доступен, по существу, весь мир. Сейчас слова «глобальная сеть» является синонимом понятия Интернет, связанного с объединением огромного числа сетей.

В данной работе мы рассмотрим основные протоколы, используемые в сети Интернет, а также принципы построения сетей.

l. FTP-протокол

FTP (File Transfer Protocol, или “Протокол передачи данных”) - один из старейших протоколов в Internet и входит в его стандарты. Первые спецификации FTP относятся к 1971 году. С тех пор FTP претерпел множество модификаций и значительно расширил свои возможности. FTP может использоваться как в программах пользователей, так и в виде специальной утилиты операционной системы.

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

Обмен данными в FTP происходит по TCP-каналу. Обмен построен на технологии “клиент-сервер”. FTP не может использоваться для передачи конфиденциальных данных, поскольку не обеспечивает защиты передаваемой информации и передает между сервером и клиентом открытый текст. FTP-сервер может потребовать от FTP-клиента аутентификации (т.е. при присоединении к серверу FTP-пользователь должен будет ввести свой идентификатор и пароль). Однако пароль, и идентификатор пользователя будут переданы от клиента на сервер открытым текстом.

1.1 Модели работы FTP

Простейшая модель работы протокола FTP представлена на рисунке 1. В FTP соединение инициируется интерпретатором протокола пользователя. Управление обменом осуществляется по каналу управления в стандарте протокола TELNET. Команды FTP генерируются интерпретатором протокола пользователя и передаются на сервер. Ответы сервера отправляются пользователю также по каналу управления. В общем случае пользователь имеет возможность установить контакт с интерпретатором протокола сервера и отличными от интерпретатора протокола пользователя средствами.

Рисунок 1- Модель работы протокола FTP

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

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

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

Алгоритм работы протокола FTP состоит в следующем:

· Сервер FTP использует в качестве управляющего соединение на TCP порт 21, который всегда находится в состоянии ожидания соединения со стороны пользователя FTP.

· После того как устанавливается управляющее соединение модуля “Интерпретатор протокола пользователя” с модулем сервера -- “Интерпретатор протокола сервера”, пользователь (клиент) может отправлять на сервер команды. FTP-команды определяют параметры соединения передачи данных: роль участников соединения (активный или пассивный), порт соединения (как для модуля “Программа передачи данных пользователя”, так и для модуля “Программа передачи данных сервера”), тип передачи, тип передаваемых данных, структуру данных и управляющие директивы, обозначающие действия, которые пользователь хочет совершить (например, сохранить, считать, добавить или удалить данные или файл и другие).

· После того как согласованы все параметры канала передачи данных, один из участников соединения, который является пассивным (например, “Программа передачи данных пользователя”), становится в режим ожидания открытия соединения на заданный для передачи данных порт. После этого активный модуль (например, “Программа передачи данных сервера”) открывает соединение и начинает передачу данных.

· После окончания передачи данных, соединение между “Программой передачи данных сервера” и “Программой передачи данных пользователя” закрывается, но управляющее соединение “Интерпретатора протокола сервера” и “Интерпретатора протокола пользователя” остается открытым. Пользователь, не закрывая сессии FTP, может еще раз открыть канал передачи данных.

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

Рисунок 2- Соединение с двумя серверами

Алгоритм работы при соединении двух FTP-серверов, ни один из которых не расположен на локальном хосте пользователя:

· Модуль “Интерпретатор протокола пользователя” указал модулю сервера “Интерпретатор протокола сервера 1” работать в пассивном режиме, после чего модуль “Интерпретатор протокола сервера 1” отправил пользователю адрес и номер порта (N) , который он будет слушать.

· Модуль “Интерпретатор протокола пользователя” назначил модуль сервера 2 “Интерпретатор протокола сервера 2” в качестве активного участника соединения и указал ему передавать данные на хост “Интерпретатор протокола сервера 1” на порт (N).

· “Интерпретатор протокола пользователя” подал “Интерпретатору протокола сервера 1” команду “сохранить поступившие данные в таком-то файле”, а “Интерпретатор протокола сервера 2” -- “передать содержимое такого-то файла”.

· Между модулями “Интерпретатор протокола сервера 1” и “Интерпретатор протокола сервера 2” образуется поток данных, который управляется клиентским хостом.

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

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

· Сервер получил от пользователя команду “прервать соединение”.

· Пользователь изменил параметры порта передачи данных.

· Было закрыто управляющее соединение.

· Возникли ошибки, при которых невозможно возобновить передачу данных.

1.2 Режимы передачи файлов по протоколу FTP

Существует два режима передачи файлов по протоколу FTP:

· Текстовый (ASCII) -- режим для передачи текстовых файлов, html-документов, php-скриптов и так далее.

· Двоичный (бинарный, binary, bin) -- режим для передачи картинок, исполняемых файлов, исполняемых cgi-скриптов и так далее.

· Для обычного пользователя это скорее бесполезные сведения, но иногда они становятся очень актуальными. Например, в случае если вы загружаете на сервер картинку, где она оказывается испорченной и не показывается в браузере, хотя доступна через веб. Это случается когда файл с картинкой (jpg, gif, bmp, png,..), который является двоичным, передается на сервер не в двоичном, а в текстовом режиме. Как правило, это происходит из-за неправильной работы FTP-программы.

· Текстовые файлы нельзя передавать в двоичном режиме, а двоичные файлы нельзя передавать в текстовом режиме. Вообще, FTP-программы по умолчанию должны сами определять, в каком режиме нужно передавать конкретные файлы. Однако, иногда они ошибаются, и файлы загружаются неправильно. В этом случае придется настроить FTP-программу так, чтобы она правильно передавала нужные виды файлов.

1.3 Программное обеспечение для осуществления соединения с помощью протокола FTP

Для получения файлов необходим FTP-client, программа, которая сегодня поставляется как составляющая часть всех современных броузеров. А вот с предоставлением доступа к вашим файлам немного сложнее, для этого необходим выход в Интернет, предпочтительно (но необязательно) с фиксированным (статичным) IP-адресом и постоянным соединением, и FTP-daemon - программа, выполняющая функции FTP-сервера.

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

1.4 Службы архивов FTP

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

Информация в FTP-архивах разделена, в основном, на три категории:

· Защищенная информация, режим доступа к которой определяется ее владельцами и разрешается по специальному соглашению с потребителем. К этому виду ресурсов относятся коммерческие архивы (к примеру, коммерческие версии программ в архивах ftp.microsoft.com), закрытые национальные и международные некоммерческие ресурсы (например, работы по международным проектам CES или IAEA), частная некоммерческая информация со специальными режимами доступа (например, частные благотворительные фонды).

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

· Свободно распространяемые информационные ресурсы или freeware, если речь идет о программном обеспечении. К этим ресурсам относится все, что можно свободно получить по сети без специальной регистрации. Это может быть документация, программы или что-либо еще. Следует отметить, что свободно распространяемое программное обеспечение не имеет сертификата качества, но его разработчики открыты для обмена опытом.

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

1.5 Некоторые проблемы FTP-серверов

FTP серверы могут работать в двух режимах: активном и пассивном. В активном режиме, когда начинается передача данных, клиент начинает прослушивание TCP порта и сообщает серверу, какой порт он прослушивает, после чего сервер открывает TCP соединение с порта 20 на порт, указанный клиентом. Затем данные передаются через это соединение. В пассивном режиме, клиент сообщает серверу, что он готов к передаче данных и сервер начинает прослушивать неспециальный TCP порт и сообщает клиенту, который именно. Затем клиент открывает TCP соединение на порт указанный сервером и обмен данными происходит через это соединение.

Проблема этих вспомогательных соединений в том, что существующая спецификация FTP протокола не предусматривает какого-либо метода проверки того, что клиент или сервер, который установил соединение это именно тот, кто запросил это соединение в управляющем сеансе. Это, в сочетании с фактом того, что многие операционные системы назначают TCP порты последовательно в возрастающем порядке, означает, что в результате в FTP протоколе создаются условия позволяющие атакующей стороне перехватить данные, которые передает кто-либо другой, либо подменить данные. Эти атаки слегка отличаются в активном и пассивном режиме. Когда передача данных осуществляется в активном режиме, атакующая сторона угадывает номер TCP порта, на котором конечный клиент ожидает соединения. Затем атакующий непрерывно посылает FTP серверу, к которому подключен клиент, команды PORT ip,of,client,machine,port,port RETR filename или STOR filename. Используя RETR, если надо подменить данные, передаваемые клиенту или STOR, если надо перехватить данные от клиента к серверу. Или, атакующий может использовать атаки, основанные на знании TCP sequence number и подменить сеанс связи от сервера к клиенту. Правда, используя этот тип атак невозможно перехватить данные, можно только подменить их своими.

1.6 Команды FTP протокола

Команды управления контролем передачи данных, которыми обмениваются «Интерпретатор протокола сервера» и «Интерпретатор протокола пользователя», можно разделить на три большие группы:

1. Команды управления доступом к системе.

2. Команды управления потоком данных.

3. Команды FTP-сервиса.

Рассмотрим несколько наиболее характерных команд из каждой группы. Среди команд управления доступом к системе следует отметить следующие:

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

PASS. Данная команда подается после ввода идентификатора пользователя и, в качестве аргумента содержит пароль пользователя. Напомним, что данные аутентификации FTP передаются по сети открытым текстом, поэтому для обеспечения защищенности канала пользователю необходимо предпринимать дополнительные меры.

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

REIN. Команда реинициализации. Эта команда очищает все переменные текущего пользователя, сбрасывает параметры соединения. Если в момент подачи команды происходит передача данных, передача продолжается и завершается с прежними параметрами.

QUIT. Команда закрывает управляющий канал. Если в момент подачи команды происходит передача данных, канал закрывается после окончания передачи данных.

Команды управления потоком устанавливают параметры передачи данных. Все параметры, описываемые этими командами, имеют значение по умолчанию, поэтому команды управления потоком используются только тогда, когда необходимо изменить значение параметров передачи, используемых по умолчанию. Команды управления потоком могут подаваться в любом порядке, но все они должны предшествовать командам FTP-сервиса. Из команд управления потоком данных следует выделить следующие:

PORT. Команда назначает адрес и порт хоста, который будет использоваться как активный участник соединения по каналу передачи данных. Аргументами команды являются 32-битный IP адрес и 16-битный номер порта соединения. Эти значения разбиты на шесть 8-битных полей и представлены в десятичном виде: h1, h2, h3, h4, p1, p2, где hN - байты адреса (от старшего к младшему), а pN - байты порта (от старшего к младшему).

PASV. Эта команда отправляется модулю, который будет играть пассивную роль, в передаче данных («слушать» соединение). Ответом на данную команду должна быть строка, содержащая адрес и порт хоста, находящиеся в режиме ожидания соединения в формате команды PORT - «h1, h2, h3, h4, p1, p2».

Команды TYPE, STRU, MODE определяют, соответственно, тип передаваемых данных (ASCII, Image и другие), структуру или формат передачи данных (File, Record, Page), способ передачи (Stream, Block и другие). Использование этих команд очень важно при построении взаимодействия в гетерогенных средах и весьма отличающихся операционных и файловых систем взаимодействующих хостов.

Команды FTP-сервиса определяют действия, которые необходимо произвести с указанными файлами. Как правило, аргументом команд этой группы является путь к файлу. Синтаксис указанного пути должен удовлетворять требованиям формата файловой системы обработчика команды. Из команд FTP-сервиса можно выделить следующие:

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

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

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

ABOR. Команда предписывает серверу прервать выполнение предшествующей сервисной команды (например, передачу файла) и закрыть канал передачи данных.

Команда DELE удаляет указанный файл.

Команды MKD и RMD, соответственно, создают и удаляют указанный в аргументе каталог.

При помощи команд LIST и NLST можно получить список файлов в указанном каталоге.

Все команды FTP-протокола отправляются «Интерпретатором протокола пользователя» в текстовом виде - по одной команде в строке. Каждая строка команды - идентификатор и аргументы - заканчиваются символами <CRLF>. Имя команды отделяется от аргумента символом пробела - <SP>.

Обработчик команд возвращает код обработки каждой команды, состоящий из трех цифр. Коды обработки составляют определенную иерархическую структуру и, как правило, определенная команда может возвратить только определенный набор кодов. За кодом обработки команды следует символ пробела - <SP>, затем следует текст пояснения. Например, строка успешного завершения операции выглядит следующим образом: «200 Command okay».

Ниже приведен пример работы с FTP-протокола. Обозначения: S - сервер, U - пользователь.

S: 220 Service ready for new user

U: USER Gluk

> S: 331 User name okay, need password

U: PASS murmur

S: 230 User logged in, proceed

U: RETR test.txt

S: 150 File status okay; about to open data connection

<Идет передача файла ...>

S: 226 Closing data connection, file transfer successful

U: TYPE I

S: 200 Command okay

U: STOR /home/images/first.my

S: 550 Access denied

U: QUIT

1.7 Протоколы TFTP и SFTP

FTP-протокол имеет двух «младших братьев»: SFTP - Simple FTP и TFTP - Trivial FTP.

TFTP-протокол - это простейший протокол передачи файлов. Он работает поверх транспортного протокола UDP и обеспечивает выполнение только самых элементарных операций передачи файлов, а именно, записи и чтения файлов. TFTP был разработан как простой и легкий в применении протокол. Он не позволяет вызвать список каталога и не имеет никаких средств аутентификации, но может передавать 8-битную информацию в соответствии со всеми стандартами Internet.

Поскольку передача данных осуществляется поверх UDP, протокол TFTP реализует собственные методы надежной доставки данных - пакеты подтверждения, нумерация блоков данных и пакетов подтверждения и т.п. Все очень похоже на упрощенный вариант эмуляции протокола TCP.

TFTP работает лишь пятью командами:

1. Read request (RRQ) - запрос на чтение.

2. Write request (WRQ) - запрос на запись.

3. Data (DATA) - пакет данных.

4. Acknowledgment (ACK) - подтверждение.

5. Error (ERROR) - ошибка.

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

При открытии соединения, каждая из сторон выбирает (случайным образом) уникальный идентификатор - TID, который используется и UDP как порт соединения. Каждый пересылаемый пакет ассоциирован с двумя TID, соответствующими каждой стороне соединения. Первоначальный запрос отправляется инициатором TFTP-соединения на UDP-порт 69 (порт инициализации), в котором указывается порт соединения. Дальнейший обмен уже происходит через порты, выбранные участниками передачи данных.

Если сервер разрешает запрос, обмен открывается, и указанный файл передается (блоками по 512 байт). Каждый пакет передаваемых данных содержит один блок (512 байт) и номер блока в передаваемом потоке. Поступление каждого блока на хост назначения должно быть подтверждено пакетом ACK (подтверждение), с номером поступившего блока. Только после получения пакета подтверждения будет отправлен следующий пакет данных.

Если длина пакета менее 512 байт - это служит сигналом для закрытия канала связи. В случае потери пакета при передаче, через некоторый промежуток времени сервер отправит этот пакет данных повторно.

Три типа ситуаций порождают отправку ошибочных пакетов:

· Не подтвержденный запрос, например, не был найден файл, нет прав доступа и др.

· Неправильный формат пакета, например, произошла ошибка коммутации.

· Потеря доступа к требуемому ресурсу.

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

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

SFTP поддерживает механизмы идентификации пользователя, передачу файлов, просмотр каталогов, изменение текущего каталога, переименование и удаление файлов. В большинстве операций, которые пользователь проводит с удаленным FTP-сервером, этого сервиса вполне достаточно. SFTP может передавать 8-битный поток данных и использует, как TFTP, только один канал соединения - как для команд, так и для данных. В отличие от TFTP, SFTP работает поверх TCP, порт 115.

Команда SFTP имеют почти тот же синтаксис и предназначение, что и аналогичные команды FTP.

SFTP вполне удовлетворяет работе с одним пользователем и одним сервером, кроме того, его легко использовать и программировать.

1.8 Утилита FTP

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

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

По сути, FTP-утилита представляет собой интерпретатор команд оболочки в команды (и их последовательности) FTP-протокола. Отправка команд FTP-соединения, анализ ответов сервера FTP, открытие канала передачи данных, процесс передачи данных -- все это происходит внутри FTP-модуля. Обо всех событиях передачи команд и данных пользователь информируется в соответствии с интерпретацией этих событий FTP-утилитой.

В качестве примера приведен сценарий передачи с FTP-сервера текстового файла на локальный хост.

C:\>ftp

ftp> open ftp.sun.com

220-Welcome to Sun Microsystems Corporate FTP Server.

220-

220- ftp FTP server (ftpd Wed Oct 30 23:31:06 PST 1996) ready.

User (ftp.sun.com: (none)): ftp

331 Guest login ok, send your complete e-mail address as password.

Password:

230 Guest login ok, access restrictions apply.

ftp> dir

200 PORT command successful.

150 Opening ASCII mode data connection for /bin/ls.

total 34

dr-xr-xr-x 8 root 0 512 Feb 14 1997 .

d--x--x--x 3 root users 512 Oct 31 1996 etc

drwxrwx-wt 3 root 42 5120 Nov 21 10:37 incoming

drwxrwxr-x 12 root 42 4096 Nov 19 23:26 pub

dr-xr-xr-x 4 root users 512 Jun 7 1996 usr

-rw-r--r-- 1 root users 49 Sep 27 1996 welcome.msg

226 Transfer complete.

624 bytes received in 19,66 seconds (0,03 Kbytes/sec)

ftp> get welcome.msg primer.txt

200 PORT command successful.

150 Opening ASCII mode data connection for welcome.msg (49 bytes).

226 Transfer complete.

50 bytes received in 2,73 seconds (0,02 Kbytes/sec)

ftp> quit

221 Goodbye.

Синтаксис команды:

ftp [-v] [-d] [-n] [host]

· v - подавляет ответы серверы и статистику передачи данных;

· n - управляет режимом идентификации пользователя. Если указан этот ключ, то сначала проверяется файл .netrc;

· i - выключает подтверждения передачи файла при массовом копировании файлов;

· d - включает режим отладки;

· g - отключает прозрачность передачи имен.

Важными командами являются команды приема/передачи данных get, put, mget, mput и bin. Команды get и put предназначены соответственно для приема и передачи одного файла. Команды mget и mput выполняют те же действия, что и предыдущие, но для группы файлов. Команда bin позволяет передавать данные в двоичном режиме, что важно для передачи программ и архивов, кроме того, этот режим бывает полезен для символьных данных с произвольной длиной строки (ASCII ограничивает длину строки 254 символами). Другой полезной командой является команда hash. Строка: “ftp> hash #” при работе с медленными линиями или передаче больших файлов

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

2. Алгоритм Штор-Вагнера

G - неориентированный взвешенный граф с n вершинами и m ребрами.

Разрезом называется такое разбиение множества V на два подмножества A и B, что:

A, B \subset V;

A, B \neq \emptyset;

A \cap B = \emptyset;

A \cup B = V.аф с n вершинами и m ребрами.

Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит A, а второй конец - B.

Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его O(n^2) раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.

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

Алгоритм

Идея алгоритма довольно проста. Будем n-1 раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин s и t, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности s и t). В конце концов, после n-1 итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех n-1 найденных разрезов. Действительно, на каждой i-ой стадии найденный минимальный разрез \langle A,B \rangle между вершинами s_i и t_i либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины s_i и t_i невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.

Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин s и t. Для этого вводим некоторое множество вершин A, которое изначально содержит единственную произвольную вершину s. На каждом шаге находится вершина, наиболее сильно связанная с множеством A, т.е. вершина v \not\in A, для которой следующая величина w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u) максимальна (максимальна сумма весов рёбер, один конец которых v, а другой принадлежит A). Этот процесс завершится, когда все вершины перейдут в множество A.

Корректность алгоритма

Если добавить в множество A по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с A, то пусть предпоследняя добавленная вершина -- s, а последняя -- t. Тогда минимальный s-t разрез состоит из единственной вершины -- t

Доказательство

Рассмотрим произвольный s-t разрез C и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины t:

w (\{t\}) \le w (C).

Пусть v - вершина, которую мы хотим добавить в A, тогда A_v - состояние множества A в этот момент. Пусть C_v - разрез множества A_v \cup v, индуцированный разрезом C. Вершина v - активная, если она и предыдущая добавленная вершина в A принадлежат разным частям разреза C, тогда для любой такой вершины:

w (v, A_v) \le w (C_v).

t - активная вершина, для нее выполняется:

w (t,A_t) \le w (C_t)

w (t,A_t) = w (\{t\}), w (C_t) = w (C)

Получили утверждение теоремы. Для доказательства воспользуемся методом математической индукции. Для первой активной вершины v это неравенство верно, так как все вершины A_v принадлежат одной части разреза, а v - другой. Пусть неравенство выполнено для всех активных вершин до v, включая v, докажем его для следующей активной вершины u.

w (u,A_u) \equiv w (u,A_v) + w (u,A_u \setminus A_v) (*)

Заметим, что

w (u,A_v) \le w (v,A_v) (**)

вершина v имела большее значение w, чем u, так как была добавлена в A раньше. По предположению индукции:

w (v,A_v) \le w (C_v)

Следовательно из (**):

w(u,A_v) \le w(C_v)

А из (*) имеем:

w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v)

Вершина u и A_u \setminus A_v находятся в разных частях разреза C, значит w (u,A_u \setminus A_v) равна сумме весов ребер, которые не входят в C_v, но входят в C_u.

w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v) \le w (C_u)

Что и требовалось доказать.

Заключение

FTP- протокол, несомненно, играет огромную роль в глобальной сети Интернет (и не только в ней). Этот удобный, действительно многофункциональный, а, главное, давно стандартизированный протокол является доминирующим и безоговорочным лидером в Интернете. На его базе построено множество файловых архивов, без которых техническая работа была бы не столь эффективна. Автоматизация и защищённость этого протокола, также не вызывает нареканий, что позволяет использовать его в государственных структурах.

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

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

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

Список литературы

1. Бройдо, В. Л. Вычислительные системы, сети и телекоммуникации / В. Л. Бройдо. - СПб. : Питер, 2002. - 688 с.

2. Телекоммуникационные системы и сети / Г.П. Катунин, Г.В. Мамчев и др. - М. : Телеком, 2004. - 672 с.

3. Столингс, В. Компьютерные системы передачи данных / В. Столингс. - М. : Вильямс, 2002. - 928 с.

4. Олифер, В. Г. Основы сетей передачи данных / В. Г. Олифер, Н. А. Олифер. - М. : ИНТУИТ.РУ,2003. - 248 с.

5. Новиков, Ю. Персональные компьютеры: аппаратура, системы, Интернет / Ю. Новиков, А. Черепанов. - СПб. : Питер, 2001. - 464 с.

6. Рудометов, Е. Устройство мультимедийного компьютера / Е. Рудометов, В. Рудометов. - СПб.: Питер, 2001. - 512 с.: ил.

Приложение А

( справочное )

Листинг кода

program Project2;

{$APPTYPE CONSOLE}

uses

SysUtils;

const maxn = 500;

var n: integer;

g: array [0..500, 0..500] of integer;

v: array[0..500, 0..500] of integer;

best_cost: integer;

best_cut : integer;

i,j: integer;

procedure mincut;

var i, ph, it, sel, k, j, prev: integer;

w: array [0..500] of integer;

exist, in_a: array [0..500] of boolean;

begin

for i := 0 to n-1 do

for j := 0 to n-1 do

if (i = j) then v[i][j] := 1;

for i := 0 to maxn do

exist[i] := true;

for ph := 0 to n-1 do

begin

for i := 0 to maxn do

begin

in_a[i] := false;

w[i] := 0;

end;

prev := 0;

for it := 0 to n-ph-1 do

begin

sel := -1;

for i := 0 to n-1 do

if (exist[i]) AND not (in_a[i]) AND ((sel = -1) OR (w[i] > w[sel])) then

sel := i;

if (it = n-ph-1) then

begin

if (w[sel] < best_cost) and (sel > 0) then

begin

best_cost := w[sel];

best_cut := sel;

INC(k);

end;

for i := 0 to n-1 do

if v[sel][i] = 1 then

v[prev][i] := 1;

for j := 0 to n-1 do

begin

g[j][prev] := g[j][prev] + g[j][sel];

end;

exist[sel] := false;

end

else

begin

in_a[sel] := true;

for j := 0 to n-1 do

w[j] := w[j] + g[sel][j];

prev := sel;

end;

end;

end;

end;

begin

best_cost := 1000000000;

assign(input, 'input.txt');

assign (output, 'output.txt');

readln(n);

for i := 0 to n-1 do

begin

for j := 0 to n-1 do

begin

read(g[i][j]);

end;

readln;

end;

mincut;

write('Стоимость минимального разреза = ');

writeln(best_cost);

write('Вершины минимального разреза: ');

for i := 0 to n-1 do

if v[best_cut][i] = 1 then

write(i,' ');

readln;

end. program Project2;

{$APPTYPE CONSOLE}

uses

SysUtils;

const maxn = 500;

var n: integer;

g: array [0..500, 0..500] of integer;

v: array[0..500, 0..500] of integer;

best_cost: integer;

best_cut : integer;

i,j: integer;

procedure mincut;

var i, ph, it, sel, k, j, prev: integer;

w: array [0..500] of integer;

exist, in_a: array [0..500] of boolean;

begin

for i := 0 to n-1 do

for j := 0 to n-1 do

if (i = j) then v[i][j] := 1;

for i := 0 to maxn do

exist[i] := true;

for ph := 0 to n-1 do

begin

for i := 0 to maxn do

begin

in_a[i] := false;

w[i] := 0;

end;

prev := 0;

for it := 0 to n-ph-1 do

begin

sel := -1;

for i := 0 to n-1 do

if (exist[i]) AND not (in_a[i]) AND ((sel = -1) OR (w[i] > w[sel])) then

sel := i;

if (it = n-ph-1) then

begin

if (w[sel] < best_cost) and (sel > 0) then

begin

best_cost := w[sel];

best_cut := sel;

INC(k);

end;

for i := 0 to n-1 do

if v[sel][i] = 1 then

v[prev][i] := 1;

for j := 0 to n-1 do

begin

g[j][prev] := g[j][prev] + g[j][sel];

end;

exist[sel] := false;

end

else

begin

in_a[sel] := true;

for j := 0 to n-1 do

w[j] := w[j] + g[sel][j];

prev := sel;

end;

end;

end;

end;

begin

best_cost := 1000000000;

assign(input, 'input.txt');

assign (output, 'output.txt');

readln(n);

for i := 0 to n-1 do

begin

for j := 0 to n-1 do

begin

read(g[i][j]);

end;

readln;

end;

mincut;

write('Стоимость минимального разреза = ');

writeln(best_cost);

write('Вершины минимального разреза: ');

for i := 0 to n-1 do

if v[best_cut][i] = 1 then

write(i,' ');

readln;

end.

Приложение Б

( справочное )

Пример работы программы:

В input находятся значения, которые считывает матрица смежности и результат записывает в output.

Размещено на Allbest.ru

...