Московский государственный технический университет

⇐ ПредыдущаяСтр 4 из 4

Им. Н.Э. Баумана

Кафедра

“Системы обработки информации и управления”

(ИУ – 5)

Пояснительная записка

курсовой работы на тему “Алгоритмы ”

по дисциплине “Архитектура АСОИУ”

Выполнил:

студент гр. ИУ5 - 25

Петров Пётр (подпись)

_ октября 2019 г.

Оценка “---------- “

Проверил:

к.т.н., доцент

Шук В.П. (подпись)

_ октября 2019 г.

Москва – 2019 г.

Тема № 143 – пример № 2

Алгоритмы

А. Роль алгоритмов

Б. Виды алгоритмов

В. Эффективность алгоритмов

Литература: Кормен Т. и др. Алгоритмы: построение и анализ. М.: Вильямс. 2016. – 1323 с.

Шифр Российской государственной библиотеки 2 16-23/170

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

Позиция темы в базовой морфологической модели архитектуры АСОИУ:

Реферат

на тему “Алгоритмы: построение и анализ”

(тема № 143)

Данной теме посвящён фундаментальный труд [4]. Как отмечается в одном из отзывов на него, это одна из редких книг, удачно объединяющая в себе полноту охвата обозначенной проблемы и строгость изложения материала. Проблемой являются алгоритмы, без которых не мыслима работа компьютеров, построенных на их основе вычислительных сетей и вообще современных информационных технологий.

Алгоритм определён как корректно заданная последовательность шагов (вычислительных или логических), преобразующих входные величины (данные) в выходные результаты (величины). Алгоритм не существует сам по себе. Он должен соответствовать конкретной вычислительной задаче. Круг вычислительных задач обширен и весомая часть из них детально рассмотрена в [4], в частности такие задачи, как:

- сортировка и порядковая статистика,

- вероятностный анализ и рандоминизированные алгоритмы,

- вычисления на графах,

- работа с матрицами,

- полиномы и быстрое преобразование Фурье и многие другие.

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

Заслуживает внимания тот факт, что для конкретной вычислительной задачи можно теоретически доказать существование эффективного алгоритма, но также есть задачи, для которых нет таких алгоритмов. Этот вопрос детально обсуждается в [4].

Далее в пояснительной записке курсовой работы на основе материала [4] рассматриваются вопросы, касающиеся роли алгоритмов, их видов и эффективности.

Примечание : Разработка Реферата ведётся в соответствии Методические рекомендации для разработки реферата по теме курсовой работы по дисциплине “Архитектура АСОИУ”. М.: МГТУ им. Н.Э.Баумана. 2018. – 5 с. (электронный ресурс)

(В текст реферата на заданную тему это примечание не включается)

Содержание

Стр.

1. Введение ……………………………………………………………………..115

2. Роль алгоритмов ………………………………………………………….116

3. Виды алгоритмов …………………………………………………………117

4. Эффективность алгоритмов …………………………………………126

5. Заключение …………………………………………………………………127

6. Литература ………………………………………………………………….128

Введение

Целями выполнения индивидуального задания являются

- углубление и расширение теоретических знаний, полученных на лекциях,

- приобретение первоначального опыта самостоятельной работы с научно-технической литературой, включая её поиск, анализ и синтез,

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

(Примечание: Текст Введения един для всех курсовых работ)

Роль алгоритмов

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

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

Виды алгоритмов

В общем случае вычислительные задачи многообразны и не предсказуемы. Однако некоторые из них (и таких достаточно много) используются практически часто и для них построены и апробированы эффективные алгоритмы. Суть части таких алгоритмов рассматривается далее.

1. Алгоритмы сортировки и порядковой статистики

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

В множестве, состоящем из n чисел, i-й порядковой статистикой называется i-е по величине значение в порядке возрастания. Это значение является выходом соответствующего алгоритма сортировки.

В [4] рассмотрены следующие алгоритмы:

сортировка вставкой,

сортировка слиянием,

пирамидальная сортировка,

быстрая сортировка,

сортировка подсчётом,

поразрядная сортировка,

карманная сортировка.

При сортировке вставкой используется инкрементный подход: имея отсортированный подмассив, например, три карты из колоды, упорядоченные по старшинству слева направо, четвёртая карта помещается на своё место среди них т.д.

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

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

Быстрая сортировка также, как и сортировка слиянием, основана на декомпозиции. Отличие заключается в том, как осуществляется декомпозиция.

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

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

В карманной сортировке предполагается, что входные данные подчиняются нормальному закону распределения. Карманная сортировка разбивает интервал [0,1] на n одинаковых интервалов, или карманов, а затем распределяет по этим карманам n входных чисел. Поскольку последние равномерно распределены в интервале [0,1], то в каждый из карманов попадёт не очень много элементов. Чтобы получить выходную последовательность, нужно выполнить сортировку в каждом кармане, а затем последовательно перечислить элементы каждого кармана.

2. Алгоритмы для работы с графами

Графы представляют собой распространённые структуры в информатике, и алгоритмы для работы с графами очень важны [4]. Имеются сотни вычислительных задач, сформулированных с использованием графов.

Имеются два стандартных способа представления графа G = (V , E): как набора списков смежных вершин и как матрицы смежности. Оба способа представления применимы как для ориентированных, так и неориентированных графов. Каждому способу представления соответствует единая графическая интерпретация графа.

В [4] рассмотрены следующие алгоритмы для работы с графами:

поиск в ширину,

поиск в глубину,

топологическая сортировка,

поиск минимального остовного дерева (алгоритм Крускала и алгоритм Прима),

поиск кратчайшего пути из одной вершины (алгоритм Беллмана-Форда, алгоритм Дейкстры),

поиск кратчайших путей между всеми парами вершин (алгоритм Флойда-Уоршелла, алгоритм Джонсона).

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

Пусть задан граф G и выделена вершина (источник) s. Алгоритм поиска в ширину систематически обходит все рёбра G для “открытия” всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество рёбер) от s до каждой достижимой из s вершины. Кроме того, в процессе обхода строится “дерево поиска в ширину” с корнем s, содержащее все достижимые вершины. Заметим, действия на графе сопровождаются появлением деревьев. Если какое-то из множества этих деревьев удовлетворяет заданным условиям, то оно считается “остовным”.

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

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

При разработке, например, электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из n контактов можно использовать (n – 1) проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество проводов. Именно она будет соответствовать минимальному остовному дереву, которое следует построить, используя алгоритм Крускала или Прима.

Водителю автомобиля требуется найти самый короткий путь из города А в город В. У него есть карта, на которой указаны расстояния между пересечениями каждой пары дорог. Для решения задачи, стоящей перед водителем, следует воспользоваться алгоритмом Беллмана-Форда или Дейкстры.

Задача поиска кратчайших путей между всеми парами вершин графа может возникнуть, например, при составлении таблицы расстояний между всеми парами городов, нанесённых на атлас дорог. Решение подобных задач обеспечивают алгоритмы Флойда-Уоршелла и Джонсона. (с.747)

3. Потоковые алгоритмы

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

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

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

Форда-Фалкерсона,

Эдмондса-Карпа,

Голдберга,

“поднять-в-начало”,

Хопкрофта-Карпа.

4. Многопоточные алгоритмы

Представленные выше алгоритмы являются последовательными, пригодными для выполнения на однопроцессорном компьютере, который в каждый момент времени исполняет только одну инструкцию. Здесь же рассматриваются алгоритмы, которые могут выполняться на многопроцессорных компьютерах, допускающих одновременное выполнение нескольких команд.

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

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

Распространённым методом программирования многоядерных компьютеров с совместно используемой памятью является использование статической многопоточности или потоков, совместно использующих общую память. Операционная система загружает поток в процессор для выполнения и переключает потоки, когда выполнения требует другой поток. Хотя операционная система и позволяет создавать и уничтожать потоки, эти операции относительно медленные. Таким образом, для большинства приложений потоки сохраняются на протяжении всего времени вычислений, почему они и получили название “статические”.

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

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

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

Эти две возможности используются в многопоточных алгоритмах:

вычисления чисел Фибоначчи,

“разделяй и властвуй” для умножения матриц,

сортировки слиянием,

шаблонных вычислений,

рандомизированной быстрой сортировки.

5. Алгоритмы для решения задач линейного программирования

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

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

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

Эти и подобные им задачи могут быть решены с помощью алгоритмов: симплекс-алгоритм,

эллипсоидальный,

внутренней точки.

6. Теоретико-числовые алгоритмы

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

Целое число a 1, единственными делителями которого являются тривиальные делители 1 и a, называют простым числом или коротко простым. Примерами первых простых чисел в порядке возрастания являются следующие:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 и т.д.

Доказано, что простых чисел бесконечно много.

Целое число a 1, которое не является простым, называется составным. Например, число 39 – составное. Целое число 1 называется единицей, и оно не является ни простым, ни составным. Аналогично целое число 0 и все отрицательные целые числа также не являются ни простыми, ни составными.

В [4] представлены некоторые вопросы теории простых чисел и связанные с ними алгоритмы:

Евклида,

решения модульных линейных уравнений,

возведения в степень,

криптосистемы с открытым ключом RSA,

цифровой подписи, проверки простоты,

целочисленного разложения Полларда,

поиска наибольшего общего делителя.

7. Алгоритмы поиска подстрок

В программах, предназначенных для редактирования текста, часто необходимо найти все фрагменты текста, которые совпадают с заданным образцом. Обычно текст – это редактируемый документ, а образец – искомое слово, введённое пользователем. Эффективные алгоритмы решения этой задачи могут сократить время реакции текстовых редакторов на действия пользователя.

Среди множества приложений алгоритмы поиска подстрок используются, например, для поиска заданных образцов в молекулах ДНК. Поисковые системы в Интернете также используют их при поиске веб – страниц, отвечающих запросам.

Для поиска подстрок разработаны алгоритмы:

“в лоб”,

Рабина – Карпа,

конечный автомат,

Кнута – Морриса – Пратта.

8. Вычислительной геометрии

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

Роль входных данных в задачах вычислительной геометрии играют обычно описания множества таких геометрических объектов, как точки, отрезки или вершины многоугольника в порядке обхода в нужном направлении. На выходе даётся ответ на такие запросы об этих объектах, как наличие пересекающихся линий или параметры новых геометрических объектов, например, выпуклой оболочки множества точек (это минимальный выпуклый многоугольник, содержащий данное множество).

Вычислительная геометрия работает как на плоскости, так и в трёх и большем числе измерений, но при этом визуализация многомерных задач и результатов их решения оказывается очень трудной. Для двумерных задач в [4] рассмотрены алгоритмы:

пересечения прямых,

выметания,

выметание по кругу,

обход по Джарвису,

“разделяй и властвуй”.

Первый из этих алгоритмов отвечает на вопрос: Пересекаются ли прямые? И если “да”, то как передвигаться по ним при некоторых заданных условиях. Алгоритм выметания определяет наличие пересечений среди n отрезков. Алгоритмы выметания по кругу и обход по Джарвису позволяют, каждый за своё время, рассчитать наличие выпуклой оболочки во множестве из n точек. Алгоритм “разделяй и властвуй” предназначен для поиска пары ближайших точек в заданном на плоскости множестве из n точек.

9. NP – полнота

Представленные выше алгоритмы являются алгоритмами с полиномиальным временем работы: для входных данных размером n их время работы в наихудшем случае равно n^k, где k – некоторая константа (свойство полиномиальности каждый раз доказывается). Возникает вопрос: все ли вычислительные задачи можно решить в течение полиномиального времени? Ответ отрицательный. Примером является задача останова, предложенная Тьюрингом. Её невозможно решить ни на одном компьютере, каким бы количеством времени мы ни располагали.

Существуют также задачи, которые можно решить, но не удаётся сделать это за время n^k, где k – некоторая константа. Задачи, решаемые с помощью алгоритмов с полиномиальным временем работы, принято считать легко разрешимыми или простыми, а задачи, время решения которых превосходит полиномиальное, считаются трудно разрешимыми или сложными. Первые относятся к P-классу (polynomial) алгоритмов (алгоритмов, в которых следующий шаг зависит от предыдущего), вторые - NP-классу (non-deterministic polynomial) алгоритмов (алгоритмов, в которых следующий шаг не зависит от предыдущего). Но существует ещё, так называемый, класс NP-полных задач (практически достаточно важных), для которых не доказано ни то, что они могут быть решены за полиномиальное время, ни то, что они не могут быть решены за полиномиальное время. Для решения NP-полных задач до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-либо из этих задач такого алгоритма не существует. Этот так называемый вопрос P NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.

10. Приближённые алгоритмы

Многие задачи, представляющие практический интерес, являются NP-полными. Однако они слишком важны, чтобы отказаться от их решения лишь на том основании, что неизвестно, как получить их оптимальное решение за полиномиальное время. Но даже для NP-полных задач остаётся надежда. Во-первых, если объем входных данных небольшой, алгоритм, время работы которого выражается показательной функцией, вполне может подойти. Во-вторых, иногда удаётся выделить важные частные случаи, разрешимые за полиномиальное время. В-третьих, остаётся возможность найти за полиномиальное время решение, близкое к оптимальному (в наихудшем либо среднем случае). На практике такие решения часто являются достаточно хорошими. Алгоритмы, обеспечивающие решения, близкие к оптимальным, называются приближёнными алгоритмами.

Сейчас разработаны более тысячи приближенных алгоритмов решения частных случаев NP-полных задач. Некоторые из них исследуются в [4]. К ним относятся задачи о:

вершинном покрытии,

коммивояжере,

покрытии множества,

сумме подмножества,

а также задачи:

расфасовка по контейнерам,

расписание работы параллельной вычислительной машины,

загрузка рюкзака

и некоторые другие.

Приведённые алгоритмы исчерпывают основные виды алгоритмов, которые в [4] имеют достаточно детальные теоретические обоснования, включающие математические тонкости, в том числе доказательства многих теорем и лемм.

Эффективность алгоритмов

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

Рассмотрим два алгоритма сортировки: вставкой и слиянием. Для выполнения первого из них требуется время, которое оценивается как c₁n², где n – количество сортируемых элементов, а c₁- константа, не зависящая от n. Таим образом, время работы этого алгоритма приблизительно пропорционально n².

Для выполнения второго алгоритма – сортировки слиянием требуется время, приблизительно равное c₂n lg n, где lg n – краткая запись log₂ n, а c ₂ – некоторая другая константа, не зависящая от n. Как правило, c₁ ₂.

Проведём сравнение алгоритмов по времени их исполнения следующим образом. Запишем время работы алгоритма сортировки вставкой как c₁n n, а сортировки слиянием – как c₂n lg n. Записи различаются третьими сомножителями n и lg n, для которых всегда n lg n. Например, когда n = 1000, lg n приближенно равен 10, а когда n = 1 000 000, lg n – всего лишь около 20. Сортировка вставкой обычно работает быстрее сортировки слиянием для небольших количеств сортируемых элементов. Когда размер входных данных n становится достаточно большим, все заметнее проявляется преимущество сортировки слиянием, возникающее благодаря тому, что для больших n незначительная величина lg n по сравнению с n полностью компенсирует разницу между c₁n и c₂n.

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

Заключение

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

Эта мысль, как следствие работы над темой курсовой работы, дополняет и углубляет лекционный материал, в котором лишь обозначено присутствие и место алгоритмов в составе комплекса средств автоматизации АСОИУ, но не раскрыты их роль и значение.

(Примечание: В Заключении не следует перечислять вопросы, рассмотренные в основном разделе пояснительной записки. Здесь необходимо конкретно указать на связь с лекционной тематикой)

Литература

1. Шук В.П. Методические рекомендации для разработки реферата по теме курсовой работы по дисциплине “Архитектура АСОИУ”. М.: МГТУ им. Н.Э.Баумана. 2019. –10 с. (электронный ресурс)

2. Шук В.П. Методическое пособие по выполнению курсовой работы (индивидуального задания) по дисциплине “Архитектура АСОИУ”. М.: МГТУ им. Н.Э.Баумана. 2019. – 13 с. (электронный ресурс)

3. Конспект лекций по дисциплине “Архитектура АСОИУ”. М.: МГТУ им. Н.Э.Баумана. 2019. (рукопись)

4. Кормен Т. и др. Алгоритмы: построение и анализ. М.: Вильямс. 2016. – 1323 с.

Дата добавления: 2019-09-08; просмотров: 157; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 34

Мы поможем в написании ваших работ!