Математическая логика и теория алгоритмов

Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов В результате анализа сложности алгоритма получаем асимптотическую оценку для количества задаваемых им операций. Класс функций O(f), растущих не быстрее функции f. Класс функций Θ(f), растущих также как и функция f. Класс функций Ω(f) , растущих не медленнее функции f. 1 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Трудоемкость алгоритма Под трудоемкостью алгоритма для данной конкретной проблемы, заданной множеством D, будем понимать количество «элементарных» операций, задаваемых алгоритмом в принятой модели вычислений. Соответствующую функцию будем обозначать как fa(D). Заметим, что значением функции трудоемкости является целое положительное число. 2 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма В теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения). В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов. Равенство этих классов выражается в задачу: действительно ли решение задачи проверить не легче, чем его отыскать? P ⊆ NP Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время. 3 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма NP-полная задача (P=NP) — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиноминальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). NP-полные задачи образуют подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Задача называется NP-полной в сильном смысле, если: • максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа; • является NP-полной. Класс таких задач называется NPC. Если гипотеза P ≠ NP верна, то для NPCS-задачи не существует псевдополиномиального алгоритма 4 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма DA — множество допустимых конкретных проблем данной задачи, решаемой алгоритмом A. D ∈ DA —конкретный набор входных данных алгоритма А, состоящих из элементов di. В общем случае существует подмножество Dn(для большинства алгоритмов собственное) множества DA, включающее все конкретные проблемы, имеющие размерность n. 𝑓𝐴∧ (𝑛) — худший случай — наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n. 𝑓𝐴∨ (𝑛) — лучший случай — наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n. 𝑓𝐴 (𝑛) средний случай — среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n. 5 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма 𝑓𝐴∧ 𝑛 = max {𝑓𝐴 (𝐷)} — худший случай. 𝐷∈𝐷𝐴 𝑓𝐴∨ (𝑛) = m𝑖𝑛 {𝑓𝐴 (𝐷)}— лучший случай. 𝐷∈𝐷𝐴 𝑓𝐴 𝑛 = 1 𝑀𝐷𝑛 𝐷∈𝐷𝐴 𝑓𝐴 (𝐷) — средний случай. 𝑀𝐷𝑛 = 𝐷𝑛 - мощность Выделим в функции 𝑓𝐴 (𝐷) количественную (зависящую от n) и параметрическую (зависящую от значений и порядка элементов в D) составляющие, обозначив их через 𝑓𝑛 (𝑛)и 𝑔𝑝 (𝐷)соответственно: 𝑓𝐴 𝐷 = 𝑓𝐴 (𝑓𝑛 𝑛 , 𝑔𝑝 (𝐷)) 6 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Для большинства алгоритмов эти зависимости могут быть представлены как композиция функций либо в мультипликативной, либо в аддитивной формах: 𝑓𝐴 𝐷 = 𝑓𝑛 𝑛 ∙ 𝑔𝑝∗ (𝐷) 𝑓𝐴 𝐷 = 𝑓𝑛 𝑛 + 𝑔𝑝+ (𝐷) Мультипликативная форма характерна для ряда алгоритмов, когда ярко выражена зависимость от значений элементов во внешнем цикле, определяющего перебор вариантов, а также содержит внутренний цикл, проверяющий решение с полиномиальной зависимостью от размерности. Такая ситуация возникает, например, для ряда алгоритмов, решающих задачи из класса NPC. 7 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма В зависимости от влияния различных характеристик множества исходных данных на функцию трудоемкости алгоритма, может быть предложена следующая классификация: Класс N — класс количественно-зависимых по трудоемкости алгоритмов. Класс PR — класс параметрически зависимых по трудоемкости алгоритмов. Класс NPR — класс количественно-параметрических по трудоемкости алгоритмов. 8 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма В силу конечности множества 𝐷𝑛 , существует худший случай для параметрической составляющей функции трудоемкости. 𝑔∗ 𝑛 = max 𝑔𝑝∗ 𝐷 𝑔+ (𝑛) = max {𝑔𝑝+ (𝐷) } 𝐷∈𝐷𝑛 𝐷∈𝐷𝑛 Класс N Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа. 𝑔+ 𝑛 = 0 и 𝑔∗ 𝑛 = 1 → 𝑓𝐴 𝐷 = 𝑓𝑛 𝑛 Примерами алгоритмов могут служить алгоритмы для стандартных операций с массивами и матрицами (умножение матриц, умножение матрицы на вектор и т. д.)Для них справедливо: 𝑓𝐴∧ 𝑛 = 𝑓𝐴∨ 𝑛 = 𝑓𝐴 𝑛 9 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Класс PR Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этого класса размерность входа обычно фиксирована), а конкретными значениями всех или некоторых элементов из входного множества D. 𝑓𝑛 𝑛 = 𝑐𝑜𝑛𝑠𝑡 = 𝑐 → 𝑓𝐴 𝐷 = 𝑐 ∙ 𝑔∗ 𝐷 Примерами алгоритмов являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Такие алгоритмы, имея на входе два числовых значения — аргумент функции и точность, задают зависящее только от значений количество операций. 10 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма 2 2 1 1 1 2 3 Интервал: (-1;5) Точность: 2 {-1; 1; 3} Три отрезка (min) Ответ: 1 4 х 1 1 2 3 4 х Интервал: (-1;5) Точность: 0,5 {-1; -0,5; 0; 0,5; 1; 1,5; 2; 2,5; 3; 3,5; 4} Семь отрезков (min) Ответ: 2 11 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Класс NPR Это достаточно широкий класс алгоритмов, т. к. в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от их значений. 𝑓𝑛 𝑛 ≠ 𝑐𝑜𝑛𝑠𝑡 𝑔∗ 𝑛 ≠ 1 → 𝑓𝐴∧ 𝑛 ≠ 𝑓𝐴∨ 𝑛 𝑓𝐴 𝐷 = 𝑓𝑛 𝑛 ∙ 𝑔𝑝∗ 𝐷 или 𝑓𝐴 𝐷 = 𝑓𝑛 𝑛 + 𝑔𝑝+ (𝐷) В качестве одного из общих примеров можно привести ряд алгоритмов численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности, порождая мультипликативную форму для 𝑓𝐴 𝐷 . 12 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Подкласс NPRL (Low) — подкласс алгоритмов, трудоемкость которых слабо зависит от параметрической составляющей 𝑔+ 𝑛 = Θ(𝑓𝑛 𝑛 ) и 𝑔∗ 𝑛 = Θ(1) Для алгоритмов этого подкласса параметрическая составляющая влияет не более чем на коэффициент главного порядка функции трудоемкости, который определяется количественной составляющей. В этом случае можно говорить о коэффициентно-параметрической функции трудоемкости. К этому подклассу относится, например, алгоритм поиска максимума в массиве, т. к. количество переприсваиваний максимума в худшем случае (массив отсортирован по возрастанию), определяющее 𝑔+ 𝑛 = Θ(n) имеет равный порядок с оценкой внешнего цикла для перебора п элементов. 13 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Подкласс NPRE (Equivalent) — подкласс алгоритмов, в трудоемкости которых составляющая 𝑔∗ 𝑛 имеет порядок роста, не превышающий 𝑓𝑛 𝑛 𝑔+ 𝑛 = Θ(𝑓𝑛 𝑛 ∗ 𝑓𝑛 𝑛 ) и 𝑔∗ 𝑛 = Θ(𝑓𝑛 𝑛 ) Для алгоритмов этого подкласса параметрический компонент имеет сопоставимое (в мультипликативной форме) с количественным компонентом влияние на главный порядок функции трудоемкости. Для алгоритмов, относящихся к этому подклассу, можно говорить о квадратичноколичественной функции трудоемкости. В этот подкласс входит, например, алгоритм сортировки массива методом пузырька, для которого количество перестановок элементов в худшем случае (обратно отсортированный массив) определяет порядок 𝑔+ 𝑛 = Θ 𝑛2 и 𝑔∗ 𝑛 = Θ(𝑛) 14 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Подкласс NPRH (High) — подкласс алгоритмов, в трудоемкости которых составляющая 𝑔∗ 𝑛 имеет порядок роста выше, чем 𝑓𝑛 𝑛 𝑔∗ 𝑛 = О(𝑓𝑛 𝑛 ) Для алгоритмов этого подкласса именно параметрический компонент определяет главный порядок функции трудоемкости. Можно говорить, что эти алгоритмы являются количественно-сильно-параметрическими по функции трудоемкости алгоритмами. В этот подкласс входят, например, алгоритмы точного решения NP-полных задач. 15 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Другая, и не зависимая от предыдущей, классификация алгоритмов в классе NPR предполагает выделение в функции 𝑔𝑝∗ 𝐷 аддитивных компонент в множестве D, связанных со значениями элементов — 𝑔𝑣 𝐷 , и их порядком — 𝑔𝑠 𝐷 : 𝑔𝑝∗ 𝐷 = 𝑔𝑣 𝐷 + 𝑔𝑠 𝐷 Подкласс NPRS (Sequence) — подкласс алгоритмов с количественной и порядковозависимой функцией трудоемкости: 𝑔𝑠 𝐷 = 𝑂(𝑔𝑣 𝐷 ). В этом случае трудоемкость зависит от размерности входа и от порядка расположения однородных элементов; зависимость от значений не может быть полностью исключена, но она не является существенной. В этом случае можно говорить о количественно-порядковом характере функции трудоемкости. Примерами могут служить большинство алгоритмов сортировки сравнениями, алгоритмы поиска минимума и максимума в массиве. 16 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Трудоемкость алгоритма Подкласс NPRV (Value) — подкласс алгоритмов с функцией трудоемкости, зависящей от длины входа и значений элементов в D: 𝑔𝑣 𝐷 = 𝑂(𝑔𝑠 𝐷 ). В этом случае трудоемкость зависит от размерности входа и от значений элементов входного множества; зависимость от порядка не является определяющей. Пример — алгоритм сортировки методом индексов, трудоемкость которого определяется количеством исходных чисел и значением максимального из них. При этом порядок чисел в массиве вообще не оказывает влияния на трудоемкость, за исключением фрагмента поиска максимума, лежащего в классе NPRS. 17 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции Для того, чтобы получить значения функции трудоемкости, и теоретические и экспериментальные, необходимо определить какие операции в нашей модели вычислений являются «элементарными». Поскольку в основном алгоритмы записываются на языке, близком к одному из процедурных языков высокого уровня, то наша задача— определить «элементарные» операции такой системы записи алгоритма. Практически значимые реализации вычислительных алгоритмов включают в себя обычно следующие программные фрагменты: • диалоговый или файловый ввод исходных данных; • проверка исходных данных на допустимость; • собственно решение поставленной задачи; • представление (вывод) полученных результатов 18 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции В рамках анализа алгоритмов по трудоемкости можем считать, что обслуживающие фрагменты программной реализации (ввод, проверка и вывод) являются общими или эквивалентными для разных алгоритмов решения данной задачи. Такой подход приводит к необходимости анализа только непосредственного алгоритма решения. При этом предполагается размещение исходных данных и результатов в «оперативной» памяти, включая в это понятие как собственно оперативную память, так и кэш память, регистры и буфера реального процессора. Таким образом, множество элементарных операций, учитываемых в функции трудоемкости, не включает операции ввода/вывода данных на внешние носители. 19 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции Для формального процедурного языка высокого уровня такими «элементарными» операциями, коррелированными с основными операциями языков процедурного программирования, будем считать следующие: 1) 2) 3) 4) 5) 6) простое присваивание: Одномерная индексация Арифметические операции Операции сравнения Логические операции Операции адресации в сложных типах данных: {←, :=, =} a[i]:(адрес; размер) {/, *, -, +} {<, >, =, ≥, ≤} {or, and, not} (name1.name2). 20 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции По отношению к введенному набору элементарных операций алгоритмического базиса формального процедурного языка высокого уровня необходимо сделать несколько замечаний. • Опираясь на идеи структурного программирования, из набора элементарных операций исключается команда перехода, поскольку ее можно считать связанной с операцией сравнения в конструкции ветвления или цикла по условию. Такое исключение оправдано запретом использования оператора перехода на метку в идеологии структурного программирования. • Операции доступа к простым именованным ячейкам памяти считаются связанными с операциями, операнды которых они хранят. • Конструкции циклов не рассматриваются, т. к. могут быть сведены к указанному набору элементарных операций. 21 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции По отношению к введенному набору элементарных операций алгоритмического базиса формального процедурного языка высокого уровня необходимо сделать несколько замечаний. • Опираясь на идеи структурного программирования, из набора элементарных операций исключается команда перехода, поскольку ее можно считать связанной с операцией сравнения в конструкции ветвления или цикла по условию. Такое исключение оправдано запретом использования оператора перехода на метку в идеологии структурного программирования. • Операции доступа к простым именованным ячейкам памяти считаются связанными с операциями, операнды которых они хранят. • Конструкции циклов не рассматриваются, т. к. могут быть сведены к указанному набору элементарных операций. 22 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции Конструкция «Следование»: Трудоемкость конструкции трудоемкостей блоков, следующих друг за другом 𝑓А 𝑛 = 𝑛1 + 𝑛2 + 𝑛3 + ⋯ есть сумма Конструкция «Ветвление»: Вероятности перехода на соответствующие блоки могут меняться, как в зависимости от данных, так и в зависимости от параметров внешних охватывающих циклов и/или других условий. 𝑓А 𝑛 = 𝑓лог_выр (𝑓𝑡ℎ𝑒𝑛 𝑝 + 𝑓𝑒𝑙𝑠𝑒 (1 − 𝑝)) Для анализа худшего случая может быть выбран тот блок ветвления, который имеет большую трудоемкость, а для лучшего случая — блок с меньшей трудоемкостью. 23 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции Конструкция «Цикл по счетчику». for i ← 1 to n [тело цикла] end i←1 тело цикла i ←i+1 until i ≤ n 𝑓А 𝑛 = 1 + 𝑛 ∙ 𝑓сравнений + 𝑛 ∙ 𝑓тело цикла Анализ вложенных циклов по счетчику с независимыми индексами не составляет труда и сводится к погружению трудоемкости цикла в трудоемкость тела охватывающего его цикла. Для k вложенных зависимых циклов трудоемкость определяется в виде вложенных сумм с зависимыми индексами. 24 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Элементарные операции Конструкция «Цикл по условию». Конкретная реализация цикла по условию (цикл с верхним или нижним условием) не меняет методику оценки его трудоемкости. На каждом проходе выполняется оценка условия и может быть изменение каких-либо переменных, влияющих на значение этого условия. Общие рекомендации по определению суммарного количества проходов цикла крайне затруднительны из-за сложных зависимостей от исходных данных. Для худшего случая могут быть использованы верхние граничные оценки. Так, например, для задачи решения системы линейных уравнений итерационными методами количество итераций по точности (сходимость) определяется собственными числами исходной матрицы, трудоемкость вычисления которых сопоставима по трудоемкости с получением самого решения. 25 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм суммирования элементов квадратной матрицы ←, +,≤ Этот простейший алгоритм, очевидно, выполняет одинаковое количество операций при фиксированном значении п. Таким образом, он является количественно зависимым и относится к классу N. Внутренний цикл не зависит от внешнего, что позволяет непосредственно применить методику анализа конструкции «Цикл по счетчику», в этом случае 𝑓А 𝑛 = 1 + 1 + 𝑛 ∙ 3 + 1 + 𝑛 ∙ 3 + 4 = 7 ∙ 𝑛2 + 4 ∙ n + 2 = O(𝑛2 ) 26 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм поиска максимума в массиве Данный алгоритм является количественно-параметрическим и относится к классу NPRS, поэтому при фиксированной размерности входа необходимо проводить отдельный анализ для худшего, лучшего и среднего случая. 27 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм поиска максимума в массиве Худший случай. Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна: 𝑓𝐴∧ 𝑛 = 1 + 2 + 𝑛 − 1 ∙ 3 + 2 + 2 = 7 ∙ 𝑛 − 4 = O(𝑛) Лучший случай. Минимальное количество переприсваивания максимума (ни одного на каждом проходе цикла) будет в случае, если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна: 𝑓𝐴∨ 𝑛 = 1 + 2 + 𝑛 − 1 ∙ 3 + 2 = 5 ∙ 𝑛 − 4 = O(𝑛) 28 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм поиска максимума в массиве Средний случай. Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается k-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых k элементов максимальным элементом является последний. В случае равномерного распределения S[i], вероятность того, что максимальный из k элементов расположен в определенной (последней) позиции равна 1/k. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как: 𝑛 1 = 𝐻𝑛 ≈ ln 𝑛 + 𝛾 ≈ ln 𝑛 + 0,57 𝑖 𝑖=1 29 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм поиска максимума в массиве Средний случай. Величина 𝐻𝑛 называется n-ым гармоническим числом, 𝛾 — постоянная Эйлера. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из п элементов определяется величиной 𝐻𝑛 (при очень большом количестве испытаний), тогда: 𝑓𝐴 𝑛 = 1 + 𝑛 − 1 ∙ 3 + 2 + 2 ∙ ln 𝑛 + 7 = 5 ∙ 𝑛 + 2 ln 𝑛 + 10 = 𝑂(𝑛) 30 Математическая логика и теория алгоритмов Лекция № 13. Основы анализа алгоритмов Примеры Алгоритм поиска максимума в массиве Средний случай. Величина 𝐻𝑛 называется n-ым гармоническим числом, 𝛾 — постоянная Эйлера. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из п элементов определяется величиной 𝐻𝑛 (при очень большом количестве испытаний), тогда: 𝑓𝐴 𝑛 = 1 + 𝑛 − 1 ∙ 3 + 2 + 2 ∙ ln 𝑛 + 7 = 5 ∙ 𝑛 + 2 ln 𝑛 + 10 = 𝑂(𝑛) 31