11. Понятие алгоритма. Основные задачи и направления современной теории алгоритмов.
Алгоритм, от имени учёного аль-Хорезми - точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
- дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов.
- детерминированность (определённость). - в каждый момент времени следующий шаг работы однозначно определяется состоянием системы.
- понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
- завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
- массовость (универсальность) - алгоритм должен быть применим к разным наборам исходных данных.
- результативность — завершение алгоритма определёнными результатами.
Теория алгоритмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям:
- классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).
- теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах с увеличением объема входных данных.
- теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов.
12. Основные вопросы анализа алгоритмов. Понятие алгоритмической сложности.
Основные вопросы анализа алгоритмов – это доказательство корректности алгоритма и оценка времени его работы. Вместе с распространением информационных технологий увеличился риск программных сбоев. Одним из способов избежания ошибок в алгоритмах и их реализациях служат доказательства корректности систем математическими средствами. Использование математического аппарата для анализа алгоритмов и их реализаций называют формальными методами. Доказательство корректности программ позволяет выявлять их свойства по отношению ко всему диапазону входных данных. Для этого понятие корректности было разделено на два типа:
- частичная корректность — программа дает правильный результат для тех случаев, когда она завершается.
- полная корректность — программа завершает работу и выдает правильный результат для всех элементов из диапазона входных данных.
Во время доказательства корректности сравнивают текст программы со спецификацией желаемого соотношения входных-выходных данных. Распространенным критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объема входных данных. Для каждой конкретной задачи составляют некоторое число, которое называют ее размером. Время, которое тратит алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма T(n). Время, которое тратит алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма T(n). Асимптотику поведения этой функции при увеличении размера задачи называют асимптотичной временной сложностью. Именно асимптотическая сложность определяет размер задач, которые алгоритм способен обработать. Например, если алгоритм обрабатывает входные данные размером n за время cn², где c — некоторая константа, то говорят, что временная сложность такого алгоритма O(n²). Часто, во время разработки алгоритма пытаются уменьшить асимптотическую временную сложность для наихудших случаев. На практике же бывают случаи, когда достаточным является алгоритм, который «обычно» работает быстро. В следующей таблице приведены распространенные асимптотические сложности с комментариями:
|
Сложность |
Комментарий |
Примеры |
|
O(1) |
Устойчивое время работы не зависит от размера задачи |
Ожидаемое время поиска в в хеш-таблице |
|
O(log log n) |
Очень медленный рост необходимого времени |
Ожидаемое время работы интерполирующего поиска n элементов |
|
O(log n) |
Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину |
Вычисление xn; Двоичный поиск в массиве из n элементов |
|
O(n) |
Линейный рост — удвоение размера задачи удвоит и необходимое время |
Сложение/вычитание чисел из n цифр; Линейный поиск в массиве из n элементов |
|
O(n log n) |
Линеаритмичный рост — удвоение размера задачи увеличит необходимое время чуть более чем вдвое |
Сортировка слиянием или кучей n элементов; нижняя граница сортировки сопоставлением n элементов |
|
O(n²) |
Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза |
Элементарные алгоритмы сортировки |
|
O(n³) |
Кубичный рост — удвоение размера задачи увеличивает необходимое время в восемь раз |
Обычное умножение матриц |
|
O(cn) |
Экспоненциальный рост — увеличение размера задачи на 1 приводит к c-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат |
Некоторые задачи коммивояжёра, алгоритмы поиска полным перебором |
13. Алгоритмы поиска, выборки и сортировки.
Алгоритмы поиска:
Алгоритм последовательного поиска (АПП) последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Предполагается, что список не отсортирован. Наихудший случай: целевой элемент стоит в списке последним или его вовсе нет в списке. Средний случай: поиск всегда завершается успешно, или иногда целевое значение в списке отсутствует.
Алгоритм двоичного поиска (АДП): двоичный поиск осуществляется на отсортированном списке. Идея в том, что список делится пополам, берется средний эл-т и сравнивается с целевым эл-том. При сравнении возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка. Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В наихудшем случае число проходов равно k = log2(N +1). Средний случай A(N)≈ log2(N +1)-1.
Существуют и другие алгоритмы поиска:
- алгоритм перебора - модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке;
- дерево двоичного поиска – использует бинарное дерево для хранения элементов;
- интерполирующий поиск (предсказывающий поиск, поиск по словарю);
- линейный поиск — находит элемент в неотсортированном списке;
- поиск в глубину — проходит граф ветка за веткой;
- поиск в ширину — проходит граф уровень за уровнем;
- поиск по первому наилучшему совпадению - проходит граф в порядке важности, используя очередь приоритетов;
- троичный поиск - находит элемент в отсортированном списке.
Алгоритмы сортировки:
Сортировка вставками: на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора. Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).
Пузырьковая сортировка: алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Сортировка слиянием: алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сортируемый массив разбивается на две части примерно одинакового размера. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом. Два упорядоченных массива половинного размера соединяются в один. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Существуют и другие алгоритмы сортировки:
- наивная сортировка — генерация всех n! возможных перестановок и проверка на отсортированность;
- быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине;
- поразрядная сортировка — сортирует строки буква за буквой;
- сортировка с помощью двоичного дерева;
- сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка;
- сортировка Шелла — попытка улучшить сортировку вставками;
Алгоритмы выборки:
Иногда нам нужен эл-т из списка, обладающий некоторыми специальными св-ми, а не имеющий некоторое конкретное значение. Например, в списке сотрудников найти среднего по возрасту или найти 5 сотрудников с наименьшей оплатой труда. В более общем случае нас может интересовать запись с К-ым по величине значением поля. Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись с К-ым по величине значением окажется на К-ом месте. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, мы найдем К-ое по величине значение.
14. Алгоритмы решения задач на графах.
Поиск в ширину: метод обхода и разметки вершин графа.
Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.
Поиск в глубину: один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
Поиск по первому наилучшему совпадению: это алгоритм поиска, который исследует граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом. Некоторые авторы использовали поиск «Лучший — первый» специально для описания поиска с эвристикой, чтобы попытаться предсказать, насколько близко находимся к финальному состоянию, так что пути, которые имеют лучшую эвристическую оценку, рассматриваются первыми. Этот специфический тип поиска называется жадным поиском «Лучший — первый».
Ещё существуют алгоритмы поиска A*, Беллмана–Форда, Дейкстры, Джонсона, Флойда - Уоршелла, двунаправленный поиск.
15. Подход к решению задач недетерминированной полиномиальной сложности.
Класс Р (полиномиальные задачи):
Akxk + ak-1xk-1 +…+a0x0
Задача называется полиномиальной, т. е. относится к классу Р, если существует константа k и алгоритм, решающий эту задачу за время O(nk), где п есть длина входа алгоритма в битах . Отметим, что класс задач Р определяется через существование полиномиального по времени алгоритма ее решения, при этом неявно предполагается худший случай по времени для всех различных входов длины n. Задачи класса Р - это задачи, решаемые за реальное время. Отметим следующие преимущества задач из этого класса:
- для большинства реальных задач из класса Р константа k меньше 6;
- класс Р инвариантен по модели вычислений (для широкого класса моделей);
- класс Р обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).
Таким образом, задачи класса Р есть уточнение определения «практически разрешимой» задачи для входов больших размерностей.
Класс NP (полиномиально проверяемые задачи):
Понятие NP-полноты было введено независимо Куком (Stephen Cook, 1971) и Левиным (1973) и основывается на понятии сводимости одной задачи к другой. Сводимость задач может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2 с помощью алгоритма решения задачи 1. Таким образом, если задача 1 задана множеством конкретных проблем DA1,а задача 2 - множеством DA2, и существует функция fs (алгоритм), сводящая конкретную постановку dA2 задачи 2 к конкретной постановке dA1 задачи 1, т.е. fs(dA2 € DA2) = dA1 e DA1 , то задача 2 сводима к задаче 1. Если при этом временная сложность алгоритма fs есть 0(nk), т.е. алгоритм сведения принадлежит классу Р, то говорят, что задача 2 полиномиально сводится к задаче 1. В теории сложности вычислений принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 - языком L2, то полиномиальная сводимость языков, задающих задачи, обозначается следующим образом: L2 <=p L1
Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP, и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP. Для класса NPC доказана следующая теорема:
Если существует задача, принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения, то класс Р совпадает с классом NP, т.е. P = NP.
Схема доказательства состоит в сведении с полиномиальной трудоемкостью любой задачи из класса NP к данной задаче из класса NPC и решении этой задачи за полиномиальное время (по условию теоремы). В настоящее время доказано существование сотен NP-полных задач, но ни для одной из них пока не удалось найти полиномиального алгоритма решения. Отметим, что для многих из них предложены приближенные полиномиальные алгоритмы. Сегодня ученые предполагают следующее соотношение классов - Р <> NP, то есть NP \ Р <> 0, и ни одна задача из класса NPC не может быть решена, по крайней мере, сегодня, с полиномиальной сложностью.
16. Методы разработки алгоритмов.
Существует весьма большое количество методов и приемов разработки алгоритмов, среди них можно выделить небольшой набор основных и часто применяемых.
Разделяй и властвуй - важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Динамическое программирование - способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Метод подъема:
Этот метод, как и предыдущий, можно отнести к одному из общих «рецептов» разработки алгоритмов. Его суть заключается в следующей процедуре: алгоритм начинается с принятия начального предположения или построения начального решения задачи. Затем начинается (насколько возможно) быстрое движение «вверх» от начального уровня по направлению к лучшим решениям. Когда алгоритм достигает точки, из которой больше невозможно двигаться «наверх», он останавливается. Такой метод применяется, например, в задачах поиска экстремумов (максимумов и минимумов) среди некоторой совокупности числовых данных. Начальное решение можно сформулировать так: пусть экстремальным значением является значение первого элемента из заданной совокупности данных. Лучшим решением по отношению к начальному является такой элемент совокупности, у которого значение больше ( в случае поиска максимума) или меньше (в случае поиска минимума) по отношению к начальному значению или к промежуточному “лучшему” решению. Критерием окончания алгоритма (точкой из которой больше невозможно двигаться “наверх”) является просмотр всех элементов из заданной совокупности.
