Оценка сложности алгоритма построения графа

ВВЕДЕНИЕ 2
Глава 1. Графы и способы их задания 4
1.1. Основные понятия теории графов 4
1.2. Область применения графов 9
1.3. Теоретические основы теории сложности вычислений 12
1.3.1. Основные понятия и принципы теории сложности вычислений 12
1.3.2. Сложностные классы задач 15
3. Проблема P NP 16
4. Класс NPC (NP – полные задачи) 17
1.3.3. Временная и емкостная сложности 18
1.4. Алгоритмы на графах и порядок оценки их сложности 19
1.4.1. Алгоритм построения минимального остова 19
1.4.2. Корректность теоремы Дейкстры 26
Глава 2. Оценка сложности алгоритма на графах 30
2.1. Оценка сложности алгоритма построения минимального остова 30
2.2. Оценка сложности алгоритма Дейкстры 32
Заключение 34
Список литературы 35

Традиционно понятие сложности алгоритма связано с использованием временных ресурсов и ресурсов памяти, т.е. насколько много необходимо времени для реализации алгоритма, насколько много при этом расходуется память? Учет памяти при этом ведется по объему данных и не принимается во внимание память, расходуемая для записи и выбора команд. Необходимо отметить, что время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой при различных незначительнымх вариациях.
Такой подход сложился исторически и ориентируется, прежде всего, на инженерные и научные теории алгоритмов, где объемы данных в несколько раз превышают размеры самого алгоритма, а алгоритм, в свою очередь, может выполняться несколько часов. В этом случае следует учесть вид и назначение приложения, для которого применяется алгоритм. Например, в научных и инженерных приложениях большое время вычислений может доставить неудобство только пользователям, а в то в ряде других областей ресурсы настолько принципиальны, что может возникнуть вопрос о целесообразности всего проекта из-за неэффективной работы алгоритма. В частности, к таким областям можно отнести системы реального времени (real-time systems). Это, основанные на компьютерах, системы, которые управляют процессами в реальном мире или обрабатывают информацию, которая служит для принятия оперативных решений.
Объект исследования: алгоритмы на графах.
Предмет исследования: оценка сложности алгоритмов на графах.
Цель исследования: на основе теоретического анализа временной и емкостной сложности алгоритмов на графах математически обосновать применение формул оценки сложности для алгоритма построения минимального остовного дерева.
Для достижения поставленной цели были сформулированы следующие задачи:
1. На основе теоретического анализа литературы сформулировать основные понятия теории графов, рассмотреть способы их задания.
2. Изучить сложностные классы задач, а также особенности оценки временной и емкостной сложности алгоритмов на графах.
3. Математически обосновать оценку сложности алгоритма минимального остовного дерева и алгоритма Дейкстры.
 

Теория алгоритмов - это наука, которая изучает общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. На основе формализации понятия алгоритма существует возможность их сравнения по эффективности, проверка их эквивалентности, определение областей применимости.
В 1930-х годах были разработаны разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч). Данные модели, также как и предложенные в 1950-х годах Колмогоровым и Марковым, оказались эквивалентными. Их эквивалентность определяется тем, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.
В настоящее время всё большее распространение в области проектирования и разработки программных систем получают практические рекомендации, полученные на основе теории алгоритмов.
Одной из основных задач, которая обычно ставится при разработке алгоритмов – это оптимизация их выполнения (по времени и по памяти). Теория сложности алгоритмов предлагает достаточные эффективные методы решения поставленной проблемы. Точное решение возможно в подавляющем большинстве практически важных ситуаций.
Однако по-прежнему остаются открытыми вопросы, связанные со сводимостью алгоритмов друг к другу и нерешенной остается известная проблема PNP.
В нашем исследовании:
1. Были сформулированы основные понятия теории графов, изучены способы их задания.
2. Изучены сложностные классы задач, а также особенности оценки временной и емкостной сложности алгоритмов на графах.
3. Математически обоснована оценка сложности алгоритма минимального остовного дерева и алгоритма Дейкстры.