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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовая Применение метода Форда-Фалкерсона для выделения Web-групп в WWW

Информация:

Тип работы: Курсовая. Предмет: Программирование. Добавлен: 29.12.2011. Сдан: 2011. Страниц: 34. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Оглавление


Введение 3
1. Теоретическая часть 5
1.2 Основные определения и теоремы 5
1.2 Нахождение максимального пропускного потока 8
1.3 Сводимость некоторых задач о максимальном потоке в сети к рассматриваемой 10
1.4 Алгоритм Форда-Фалкерсона 12
2. Практическая часть 16
2.1 Алгоритм решения 16
2.2 Работа с программой 18
2.3 Расчёт потока 20
2.4 Тестирование 22
Заключение 26

Введение

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.
60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.
К сожалению, в России, в настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли встретите что-либо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются.
В этой работе рассматривается и применение метода Форда-Фалкерсона для выделения Web-групп в WWW.

1. Теоретическая часть
1.2 Основные определения и теоремы

В этой главе приведены определения и теоремы без доказательства.
Рассмотрим орграф G = (V, E), где V – множество вершин, E – множество ребер. |V| = n, |E| = m. Под сетью понимается пара S = (G, c), где c: E R – функция, ставящая каждой дуге в соответствие положительное вещественное число – пропускную способность.
Вы делим в сети 2 вершины: s (источник) и t (сток)...........................................

Заключение

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



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

1. Вентцель Е.С. Исследование операции: задачи, принципы, методология.
2. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций.
3. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях.
4. Шикин Е.В., Чхартишвилли А.Г. Математические методы и модели управления.

Приложение А . Листинг программы

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, Grids;

type
TForm1 = class(TForm)
Panel1: TPanel;
Image1: TImage;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Edit4: TEdit;
Edit5: TEdit; ................................



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.