Магистрант 2-го года А.С.
Тулемисова, к.х.н., доцент Р.А. Амиров
ЮКГУ имени М.О.
Ауезова, г. Шымкент, Казахстан
ПРИМЕНЕНИЕ АЛГОРИТМОВ НА ГРАФАХ В СЕТЕВЫХ ТЕХНОЛОГИЯХ
Глобальная сеть Internet ежегодно расширяет свое влияние на все большие
сферы деятельности человека. Это приводит к необходимости улучшения
существующих и разработку новых оптимизационных алгоритмов [1] для
обмена данных между компьютерами в единой сети. Системы из отдельных
компьютеров превращаются в огромные хранилища данных, доступные всему миру.
Любая современная фирма, любой офис оснащен хотя бы простейшей сетью. Не выходя
из дома, сотни тысяч людей работают на персональных компьютерах, общаясь со
всем миром. Для работы в Internet применяют программы - броузеры. Они позволяют
легко обмениваться текстовой, графической и звуковой информацией, используя
популярную, простую в обращении мультимедийную службу Internet World Wide Web.
В настоящей статье ставится задача проведения анализа существующих графовых
алгоритмов, применяемых для определения оптимальных путей распространения
информации по глобальной сети.
Процесс разработки алгоритмов, как правило, состоит из следующих
основных шагов:
- принятие формулировки полной и частной задачи, включая определение
основных абстрактных операций, присущих задаче;
- тщательная разработка краткой реализации для простого алгоритма;
- разработка усовершенствованных реализаций путем пошагового улучшения,
проверки эффективности идей усовершенствований посредством эмпирического или
математического анализа либо их обоих;
- определение высокоуровневых абстрактных представлений структур данных
или алгоритмов посредством операций, которые позволяют эффективно разрабатывать
усовершенствованные версии на высоком уровне;
- стремление к получению гарантированной производительности в худшем
случае, когда это возможно, но принятие хорошей производительности при работе с
реальными данными, когда это доступно.
Потенциальная возможность впечатляющего повышения производительности
алгоритмов решения реальных задач, делает разработку алгоритмов увлекательной
областью исследования; лишь немногие другие области разработки позволяют
обеспечить экономию времени в миллионы, миллиарды и более раз. По мере
повышения вычислительных возможностей компьютеров и приложений разрыв между быстрыми
и медленными алгоритмами увеличивается. Новый компьютер может работать в 10 раз
быстрее и может обрабатывать в 10 раз больше данных, чем старый, но при
использовании квадратичного алгоритма, наподобие быстрого поиска, новому
компьютеру потребуется в 10 раз больше времени для выполнения новой задачи, чем
требовалось старому для выполнению старой. Это утверждение легко подтверждается
простым тождеством
(10*N)2/10=10*N2.
По мере того как вычислительные мощности увеличиваются, позволяя решать
все более сложные задачи, важность использования эффективных алгоритмов также
возрастает. Разработка эффективного алгоритма приносит моральное удовлетворение
и прямо окупается на практике. Анализ - это ключ к пониманию алгоритмов в
степени, достаточной для их эффективного применения при решении практических
задач. Очень часто нет возможности
проводить исчерпывающие эксперименты и глубокий математический анализ каждой
программы, при этом обычно работают на основе и эмпирического тестирования, и
приближенного анализа, которые помогают изучать основные характеристики
производительности алгоритмов, чтобы можно было сравнивать различные алгоритмы
и применять их для практических целей. Дадим общее описание сложности решения
различных классических задач обработки графов. Разобьем эти задачи примерно по
следующим категориям сложности их решения: а) легкие; б) поддаются решению; в)
трудно решаемые; г) неизвестно, существует ли решение. Такая классификация
предназначена для того, чтобы получать информацию о каждой такой категории и
чтобы иметь представление о текущем уровне знаний в области алгоритмов на
графах. Как показывает эта терминология, основная причина, побудившая ввести
подобную классификацию задач, заключается в том, что существует множество задач
на графах, подобных задаче поиска гамильтонова цикла, при этом никто не знает,
можно ли найти их эффективное решение. Легкая задача обработки графа - это
задача, которая может быть решена путем применения некоторых видов компактных,
элегантных и эффективных программ. Достаточно часто для выполнения этих
программ требуется в худшем случае линейные затраты времени, либо зависимость
этих затрат ограничивается полиномами низких степеней по числу вершин или числу
ребер. В общем случае, как это имело место во многих других предметных
областях, мы можем установить, что проблема относится к числу легких, путем
разработки решения "в лоб", которое, будучи слишком медленным, для
графов крупных размеров, допустимо для графов небольших, а иногда и средних
размеров. Затем, зная, что задача имеет легкое решение, мы предпринимаем
попытки найти эффективные решения, которыми мы смогли воспользоваться на
практике, и стремимся выбрать из них наилучшее. Задача поиска эйлерова цикла
может служить наиболее ярким примером легких задач.
Проведенный анализ существующих алгоритмов маршрутизации позволяет
наметить дальнейшие пути исследований в этой области информационных технологий.
1. Куроуз Дж., Росс К. Компьютерные сети. 2-е изд. пер. с англ. – СПб,: Питер, 2004.
2. Уэнделл О.
Компьютерные сети. пер. с англ. — М. : "Вильямс", 2006.