Слайд 1Алгоритмически неразрешимые задачи
Слайд 2Любая вычислимая функция может задаваться разными алгоритмами (разными программами для
выбранного универсального исполнителя) и может быть вычислена с помощью любого
универсального исполнителя: машин Тьюринга и Поста, нормальных алгоритмов Маркова и др., но существуют и алгоритмически невычислимые функции.
Однако алгоритмическая неразрешимость задачи того или иного класса вовсе не означает невозможность решения любой конкретной задачи из этого класса. Речь идет о невозможности решения всех задач данного класса одним и тем же приемом.
Формализация понятия алгоритма позволила исследовать существование задач, для которых нет алгоритмических решений.
Слайд 3Примеры алгоритмически неразрешимых задач.
Пример 1.
Вычисление функции h(n), которая для любого
натурального числа n равна 1, если в десятичной записи числа
π есть n стоящих подряд девяток, окруженных другими цифрами, и равна нулю, если такой цепочки девяток нет.
Пример 2.
Десятая проблема Гильберта, сформулированная в 1900 году, состоит в нахождении алгоритма решения произвольных алгебраических диофантовых уравнений вида где P —целочисленная функция (например, полином с целыми коэффициентами), а переменные принимают целые значения.
- решениями этого уравнения являются пифагоровы тройки.
Согласно теореме Ферма это уравнение не имеет ненулевых целых решений при n>2.
Слайд 4Пример 3.
Проблема Эйлера - любое четное число не меньше четырех
можно представить в виде суммы двух простых чисел.
Пример 4.
Теорема Гёделя
о неполноте формальной арифметики. Существуют некоторые утверждения, которые не могут быть ни доказаны, ни опровергнуты на основе любого набора непротиворечивых аксиом (такие утверждения называются невыводимыми).
Слайд 5
Методы доказательства алгоритмической неразрешимости
Прямой метод использует диагональный метод Кантора. Заключается
он в следующем: из предположения о разрешимости данной проблемы в
ходе рассуждений приходят к противоречию.
Косвенный метод состоит в следующем: показывается, что разрешимость исследуемой проблемы влечёт разрешимость проблемы, о которой уже известно, что она неразрешима. Метод сведения часто бывает более удобным, чем прямой метод. Применяя метод сведения, обычно ссылаются на искусственные задачи, которые не представляют самостоятельного интереса, но для которых легко непосредственно доказать их неразрешимость.
Слайд 6Диагональный метод Кантора
Теорема Кантора о несчетности множества действительных чисел: множество
натуральных чисел и множество действительных чисел сегмента [0, 1] имеют
разную мощность.
Доказательство (от противного).
Действительные числа сегмента [0, 1] будем представлять бесконечной десятичной дробью, у которой на первом месте 0, а далее через запятую следует бесконечная последовательность цифр: например 0,31415926536... Положим, что такое соответствие установлено (т.е. положим, что мы занумеровали все числа отрезка [0, 1].)
Слайд 71 0, a1,1a1,2a1,3a1,4a1,5a1,6a1,7. . .
2 0, a2,1a2,2a2,3a2,4a2,5a2,6a2,7. . .
3 0, a3,1a3,2a3,3a3,4a3,5a3,6a3,7. . .
4 0, a4,1a4,2a4,3a4,4a4,5a4,6a4,7. . .
5 0, a5,1a5,2a5,3a5,4a5,5a5,6a5,7. . .
6 0, a6,1a6,2a6,3a6,4a6,5a6,6a6,7. . .
. . . . . . . . . . . . . . . . . . . . . . .
n 0, an,1an,2an,3an,4an,5an,6an,7. . .
. . . . . . . . . . . . . . . . . . . . . . .
ai,j - цифра от 0 до 9, i - номер числа, в записи
которого она участвует, j - номер ее позиции в этом числе. Докажем,
что есть число не вошедшее в эту нумерацию.
Слайд 8Строим число 0, b1b2b3b4b5 . . ., ставя на n-ое место цифру bn, такую, что bn an,n. Таким
образом получаем число отличное от числа с номером n. Поскольку
так можно проделать для любого числа, получаем противоречие предположению, что можно занумеровать все действительные числа.
Слайд 9Теорема: множество арифметических функций n-переменных несчетно.
Док-во (с
помощью диагонального метода):
Для доказательства несчетности множества достаточно доказать несчетность какого-нибудь
его подмножества. Рассмотрим функции одной переменной вида Fi(x). Пусть функций одной переменной счетное множество, т.е. их можно перенумеровать. F0(x), F1(x), F2(x), …
Построим новую функцию G(x)=Fx(x)+1. Это так называемая диагональная функция G(0)=F0(0)+1, G(1)=F1(1)+1, G(2)=F2(2)+1 и т.д. G-отлична от всех перечисленных функций, т.к. от каждой из функций она отличается хотя бы в одной точке. От функции F0(x) отличается в точке х=0, от функции F1(x) в точке х=1 и т.д. Однако по построению G(x) принадлежит множеству арифметических функций одной переменной, значит должна быть в списке, т.е. совпадать с одной из перечисленных функций.
Получили противоречие, следовательно исходное предположение неверно, и функций одной переменной несчетное множество. А значит и всех функций n переменных – тоже несчетное множество.
Слайд 10Теорема: вычислимых функций счетное множество. (Множество машин Тьюринга счетно).
Таким образом,
каждая машина Тьюринга вполне определяется некоторым конечным словом в конечном
стандартном алфавите. Поскольку множество всех конечных слов в конечном алфавите счетно, то и всех мыслимых машин Тьюринга (отличающихся друг от друга по существу своей работы) имеется не более чем счетное множество.
Слайд 11Оценка мощности множества невычислимых арифметических функций.
Невычислимых арифметических функций несчетное множество.
Слайд 12 Эти задачи часто используют для доказательства неразрешимости других проблем путем
сведения к ним.
Нумерация алгоритмов
Существует вычислимая функция, которая по номеру машины
Тьюринга (алгоритма) восстанавливает её программу (описание алгоритма) : N→A. Такая функция называется нумерацией алгоритмов. Это позволяет отождествлять алгоритм с его номером. Если (n)=A, то число n называется номером алгоритма A. Из взаимной однозначности отображения следует существование обратной функции −1, восстанавливающей по описанию алгоритма An его номер в этой нумерации −1(An)=n.
Существование нумераций позволяет работать с алгоритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами.
Проблемы самоприменимости и остановки.
Слайд 13Проблема остановки.
Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного
алгоритма (его номеру) и исходных данных (и алгоритм и данные заданы символами на ленте машины
Тьюринга) определить, останавливается ли этот алгоритм на этих данных или будет работать бесконечно.
Самоприменимость (частный случай проблемы остановки) в теории алгоритмов — свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма.
Пример самоприменимого алгоритма: тождественные преобразования строк в алфавите A.
Слайд 14Теорема. Не существует машины Тьюринга Т0 , которая решает проблему самоприменимости.
Возьмем в
качестве внешнего алфавита для машин Тьюринга А={0,1}. Будем говорить, что
МТ Т0 решает проблему
самоприменимости, если для любой машины Т конфигурацию q1Код(Т) она переводит в конфигурацию q01, если Т самоприменима, и в конфигурацию q00, если Т - несамоприменима.
Доказательство.
Допустим, что существует машина T0, решающая проблему самоприменимости. Построим машину T1, в которой вместо cостояния q0 введем новое заключительное состояние qr и добавим к программе машины T0 новые команды
q01 q01E, (зацикливание)
q00 qr0E (*)
Слайд 15Машина T1 построена по машине T0 вполне конструктивными средствами и применима к кодам несамоприменимых
машин и не применима к кодам самоприменимых машин.
Существование такой машины
приводит к противоречию, потому что Т1 не может быть ни самоприменимой, ни несамоприменимой.
Действительно, если Т1 - самоприменима, то q1Код(Т1) переходит в q01 и согласно (*) q01 в q01Е и T1 никогда не остановится, т.е. по построению она не применима к коду самоприменимых машин. Если T1 - несамоприменима, то q1Код(Т1) переходит в q00 и согласно (*) q00 в qr0 и машина Т1 остановится, т.е. по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины, а это как раз означает, что T1 самоприменима. Получили противоречие, т.е. допущение о существовании МТ, решающей проблему самоприменимости, неверно. В силу тезиса Тьюринга невозможность построения МТ означает отсутствие алгоритма решения данной проблемы.
Слайд 16Проблема останова МТ и доказательство её неразрешимости
Одна из первых задач,
для которой была доказана неразрешимость.
Доказательство её неразрешимости проводится с помощью
диагонального метода и свойства самоприменимости алгоритма.
Задачу останова часто используют для доказательства неразрешимости других проблем путем сведения к ней.
Теорема. Не существует алгоритма (МТ), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или будет работать бесконечно.
Слайд 17Доказательство.
Рассмотрим множество всех алгоритмов, получающих на вход натуральное число, и
возвращающих в качестве результата натуральное число, т.е. отображения N ->
N*, где N* = N undef, undef — случай, когда алгоритм зацикливается, то есть не заканчивает свою работу. Эта абстракция допустима, так как слова в любом конечном алфавите можно однозначно закодировать натуральными числами.
Докажем, что не существует универсальной функции, которая определяет остановится ли алгоритм на данном входе или будет работать бесконечно.
Пусть существует вычислимая функция F(a,x), принимающая значения на N*. Первый аргумент a — номер описания алгоритма на некотором языке, второй аргумент x — входные данные для этого алгоритма. F(a,x) по определению есть результат выполнения алгоритма a на входных данных x.
Слайд 18Вычислимая функция F(a,x) двух натуральных аргументов как бы перечисляет ВСЕ
вычислимые функции с одним натуральным аргументом. (Предполагается, что натуральными числами
a шифруются множество всех алгоритмов.)
Рассмотрим эту функцию с точки зрения самоприменимости т.е. F(x,x), где входом для алгоритма с номером x будет формальная запись этого же алгоритма, и построим функцию h(x) = F(x,x)+1. Функция h(x) - вычислимая, так как она использует результат вычислимой функции F и после прибавляет к нему единицу. Пусть функция h(x) имеет номер а, то есть F(a,x)=h(x). Но по определению h(x)=F(x,x)+1 и при x=a имеем F(a,a)=h(a) и h(a)=F(a,a)+1. Получили противоречие.
Таким образом определение того, остановится или нет программа, является невычислимой функцией.
Слайд 19 Неразрешимость проблемы останова можно интерпретировать как несуществование общего алгоритма для
отладки программ, точнее, алгоритма, который по тексту любой программы и
данным для нее определял бы, зациклится ли программа на этих данных или нет.
Слайд 20Основы анализа сложности алгоритмов
Слайд 21Критерии оценки эффективности алгоритмов:
Процессорное время (вычислительная сложность)
Память (максимальное количество ячеек
задействованных алгоритмом)
Каждое вычислительное устройство имеет свои особенности, которые могут влиять
на длительность вычисления при этом алгоритм не становится хуже или лучше!
Пример:
Необходимо отсортировать массив из миллиона чисел. Имеется два алгоритма: один требует выполнения 2n2 операций, другой 50nlog(n) - операций. Имеется два компьютера: один выполняет 108 операций в секунду, другой 106 операций.
Слайд 22Модель абстрактного вычислителя - машина с произвольным доступом к памяти
(RAM)
Модель состоит из памяти и процессора, которые работают следующим образом:
память
состоит из ячеек, каждая из которых имеет адрес и может хранить один элемент данных;
каждое обращение к памяти занимает одну единицу времени, независимо от номера адресуемой ячейки;
количество памяти достаточно для выполнения любого алгоритма;
процессор выполняет любую элементарную операцию (основные логические и арифметические операции, чтение из памяти, запись в память, вызов подпрограммы и т.п.) за один временной шаг;
циклы и подпрограммы не считаются простыми операциями.
Число элементарных операций алгоритма на этой модели показывает относительное время выполнения алгоритма.
Слайд 23Неудобно оценивать алгоритм по фактическому количеству элементарных операций на тех
или иных входных данных.
Задача анализа сложности алгоритма состоит в исследовании
того, как меняется время работы при увеличении объема входных данных.
Поэтому временная сложность алгоритма определяется числовой функцией, соотносящей время работы алгоритма с размером задачи, т.е. показывающей зависимость числа операций конкретного алгоритма от размера входных данных, что дает возможность сравнить два алгоритма по скорости роста числа операций.
Именно скорость роста играет ключевую роль, поскольку при небольшом размере входных данных алгоритм А на входе длины n может требовать меньшего количества операций, чем алгоритм В, но при росте объема входных данных ситуация может поменяться на противоположную.
Пример:
Сложность алгоритма А = 372n3 + 15n2 +100
Сложность алгоритма В = 2n4
На входе n=186 почти одинаковое количество операций, при n > 187, второй алгоритм выполняет большее количество операций.
Слайд 24Формальное описание:
Размер входа определяется для каждой задачи индивидуально.
1) в
задачах обработки одномерных массивов размером входа принято считать количество элементов
в массиве;
2) в задачах обработки двумерных массивов размером входа так же является количество элементов в массиве;
3) в задачах обработки чисел (длинная арифметика, проверка на простоту и т.д.) более естественно считать размером общее число битов, необходимое для представления данных в памяти компьютера;
4) в задачах обработки графов разумно за размер входа принять количество вершин графа, а иногда представить двумя значениями: число вершин и число ребер графа.
Слайд 25Конкретная проблема задается N словами памяти по битов каждое
N = N*
Программа, реализующая алгоритм состоит из М машинных
инструкций по битов – М = М*
Sd – память для хранения промежуточных результатов
Sr – память для организации вычислительного процесса
Трудоёмкость алгоритма - количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.
Функцией трудоемкости Ta (N) называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.
Комплексная оценка алгоритма: (ci – веса ресурсов.)
c1 * Ta(N) + c2 * + c3 * Sd + c4 * Sr
Формальное описание
Слайд 26 Не всегда количество элементарных операций, выполняемых алгоритмом на одном входе
длины N, совпадает с количеством операций на другом входе такой
же длины.
Пусть DА – множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D DА –конкретная проблема и |D| = N.
Обозначим подмножество множества DА, включающее все конкретные проблемы, имеющие мощность N через DN: DN = {D DN,: |D| = N} и мощность множества DN через MDN = |DN |.
Зависимость трудоемкости от входных данных
Слайд 27Для нахождения среднего значения, сначала определяются всевозможные группы, на которые
следует разбить входные данные так, чтобы время работы алгоритма на
всех данных одной группы было одинаковым. Затем подсчитывается время работы алгоритма на данных из каждой группы и определяется вероятность, с которой входной набор данных принадлежит каждой группе. Среднее время вычисляется как сумма (по всем группам) произведений вероятностей того, что входные данные принадлежат данной группе на время обработки данных этой группы.
Слайд 281. Количественно-зависимые
Это алгоритмы, функция трудоемкости которых зависит только от размерности
конкретного входа, и не зависит от конкретных значений:
Ta (D) =
Ta (|D|) = Ta (N)
2.Параметрически-зависимые
Это алгоритмы, трудоемкость которых определяется конкретными значениями обрабатываемых слов памяти:
Ta (D) = Ta (d1,…,dn) = Ta (P1,…,Pm), m n
Пример:
а) Вычисление xk последовательным умножением Ta(x, k) = Ta (k).
б) Вычисление ex=(xn/n!), с точностью до Ta = Ta (x, )
Классификация алгоритмов по виду функции трудоёмкости
Слайд 293. Количественно-параметрические
Функция трудоемкости зависит как от количества данных на входе,
так и от значений входных данных, в этом случае:
Ta (D)
= Ta (|D|, d1,…,dm) = Ta (N, P1,…,Pm)
3.1. Порядково - зависимые
Количество операций зависит от порядка расположения исходных объектов.
Пусть множество D состоит из элементов (d1,…,dn), и |D|=N. Определим Dp = {(d1,…,dn)}-множество всех упорядоченных N-ок из d1,…,dn, отметим, что |Dp|=n!.
Если Ta (iDp) Ta (jDp), где iDp, jDp Dp, то алгоритм будем называть порядково-зависимым по трудоемкости.
Слайд 30
Асимптотический анализ алгоритмов
Часто работать непосредственно с функцией трудоемкости сложно, т.
к. они обладают такими свойствами:
являются слишком волнистыми, когда сильно влияние
исходных данных на функцию трудоемкости;
требуют слишком много информации для точного определения количества инструкций RAM-машины, а потому реально их определить только для простых алгоритмов;
при изменении хотя бы одной операции, необходимо по новой пересчитывать коэффициенты;
при достаточно больших n коэффициенты перестают играть существенную роль.
Цель асимптотического анализа – сравнение затрат ресурсов системы различными алгоритмами, предназначенными для решения одной и той же задачи при больших объемах входных данных(n→∞).
Слайд 31Основные оценки сложности
Оценка (g(n)) (тетта) - функции, растущие с той
же скоростью, что и g.
Пусть T(n) и g(n) – положительные
функции положительного аргумента, n ≥ 1.
Говорят, что время работы алгоритма T(n) имеет порядок роста g(n), если существуют натуральное число n0 и положительные константы c1 и c2 (0 < c1 ≤ c2), такие, что для любого натурального n начиная с n0 выполняется неравенство :
c1 ∙ g(n) ≤ T(n) ≤ c2 ∙g(n).
Обозначение: T(n) = Θ(g(n)).
Читается как «Тэта большое от g от n».
T(n) = (g(n)), если с1 >0, с2 >0, n0 >0 такие, что: с1 g(n) T(n) c2 g(n), для n > n0.
Обычно говорят, что функция g(n) является асимптотически точной оценкой функции T(n), т.к. по определению функция T(n) не отличается от функции g(n) с точностью до постоянного множителя.
Отношение симметрично:
T(n) = (g(n)) следует, что
g(n) = (T(n)), но из T1(n)= (g(n)) и T2(n)= (g(n)) не следует, что T1(n)= T2(n).
Слайд 322. Оценка О(g(n)) (О большое) - функции, растущие медленнее чем
g.
В отличие от оценки , оценка О требует только, что
бы функция T(n) не превышала g(n) начиная с некоторого n > n0, с точностью до постоянного множителя: c > 0, n0 > 0 : 0 T(n) cg(n), n n0
Вообще, запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию T(n).
Например, для всех функций: t(n)=1/n, t(n)= 12, t(n)=3*n+17, t(n)=n*ln(n), t(n)=6*n2 +24*n+77 будет справедлива оценка О(n2 ). Однако, указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию.
Слайд 33Отыскивая асимптотическую оценку для суммы, можно отбрасывать члены меньшего порядка,
которые при больших n становятся малыми по сравнению с основным
слагаемым. Коэффициент при старшем члене роли не играет так как он может повлиять только на выбор констант c.
Слайд 343. Оценка (Омега) - функции, растущие быстрее чем g.
В
отличие от оценки О, оценка является оценкой снизу –
т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:
c > 0, n0 >0 : 0 c g(n) t(n) n n0
Пример:
запись (n*Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n*Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.
Слайд 36Сравнение скорости роста.
Сравнение скорости роста
Чем меньше степень
роста функции трудоемкости, тем больше размер задачи, которую можно решить
на компьютере.
Предположим, что имеются 4 программы, временная сложность которых и два компьютера: на первом можно использовать 1000 единиц машинного времени для решения задачи, на втором в 10 раз больше.
Слайд 40Задачи со сложностью O(1):
- вставка и удаление элемента в односвязном
и двусвязном списке;
- добавление вершины или ребра в графе.
Задачи со
сложностью O(log N):
двоичный поиск в линейном упорядоченном массиве;
Задачи с полиномиальной сложностью:
- задача сортировки;
- задача поиска эйлерова цикла на графе;
- поиск некоторого слова в тексте длиной n символов;
- поиск кратчайшего пути на графе;
-линейное программирование.
Задачи экспоненциальной сложности:
- задача коммивояжёра, задача выполнимости булевых формул;
- построение всех подмножеств данного множества;
- задачи распознавания правильных выражений в несложных языках;
- составление расписаний и раскрасок.
Слайд 41Класс NP
Задачи, которые нельзя отнести ни к классу P, ни
к классу E.
Задачи, которые недетерминированная машина Тьюринга может решить за полиномиальное время,
тогда как для детерминированной машины Тьюринга полиномиальный алгоритм неизвестен.
Для этих задач до сих пор не разработан эффективный (т.е. полиномиальный) алгоритм, но и не доказано, что таких алгоритмов не существует.
К классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Оракул предлагает решения, которые после проверки верификатором за полиномиальное время приобретают «юридическую» силу.
Слайд 42Пример.
Дано n чисел a1,…an и число V.
Задача: Найти вектор (массив)
X=(x1,…,xn), xi{0,1}, такой, что aixi = V.
Т.е. может ли быть
представлено число V в виде суммы каких- либо элементов массива А.
Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка aixi = V требует не более (N) операций.
Слайд 43Проблема равенства классов P и NP.
Поскольку детерминированная машина Тьюринга может
рассматриваться как специальный случай недетерминированной машины Тьюринга, в которой отсутствует
стадия угадывания, а стадия проверки совпадает с ДМТ, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов).
Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики.
Слайд 44На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP),
так и их несовпадения.
Предположение состоит в том, что класс
P является собственным подмножеством класса NP, т.е. NP \ P не пусто.
Класс NPC (NP – полные задачи)
Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP, и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP
Слайд 45 Для класса NPC доказана следующая теорема: если существует задача, принадлежащая
классу NPC, для которой существует полиномиальный алгоритм решения, то класс
P совпадает с классом NP, т.е. P=NP
В настоящее время доказано существование сотен NP– полных задач, но ни для одной из них пока не удалось найти полиномиального алгоритма решения. В настоящее время исследователи предполагают следующее соотношение классов:
Слайд 47Пути решения NP-полных задач.
1. Поиск приближенного решения (например, использование жадных алгоритмов
для решения задач о коммивояжёре, о рюкзаке);
2. Организация “разумной” стратегии перебора
(например, метод ветвей и границ);
3. Сведение NP-полных задач друг к другу (например, сведение задачи коммивояжёра к задаче линейного программирования);
4. Выделение из общей NP-полной задачи эффективно разрешимых частных случаев.
Слайд 48Когда временными оценками можно пренебречь.
Если создаваемая программа будет использована только
несколько раз, тогда стоимость написания и отладки программы будет доминировать
в общей стоимости программы.
Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения.
Эффективные, но сложные алгоритмы могут быть нежелательны, если готовые программы будут поддерживать лица, не имеющие достаточной квалификации для того, чтобы в них разобраться.
Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти, что этот фактор сводит на нет их преимущество.
В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.
Слайд 49Вычисление времени выполнения не рекурсивных алгритмов
I. Нахождение функции трудоемкости
по фактическому количеству элементарных операций.
В качестве «элементарных» операций алгоритма, представленного
в формальной системе RAM будем использовать следующие:
1) простое присваивание: а b;
2) одномерная индексация a[i];
3) арифметические операции: (*, /, -, +);
4) операции сравнения;
5) логические операции.
Слайд 50Анализ трудоемкости основных алгоритмических конструкций
Слайд 52
Примеры анализа простых алгоритмов
Пример 1. Задача суммирования элементов квадратной матрицы
Алгоритм
выполняет одинаковое количество операций при фиксированном значении n, и следовательно
является количественно-зависимым.
Sum 0
For i 0 to n-1
For j 0 to n-1
Sum Sum + A[i][j]
end for
TA(n)=1+1+3n + n (1+3n+4n)=7 n 2+4*n +2 = (n 2) , заметим, что под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n 2 значений.
Слайд 53
Пример 2. Задача поиска максимума в массиве
Данный алгоритм является количественно-параметрическим,
поэтому для фиксированной размерности исходных данных необходимо проводить анализ для
худшего, лучшего и среднего случая.
Max S[0]
For i 1 to n-1
if Max < S[i]
then Max S[i]
end for
Слайд 54Худший случай
Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет
в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость
алгоритма в этом случае равна:
TA^(n)=2+1+3 (n-1)+(n-1) (2+2)=7 n - 4 = (n).
Лучший случай
Минимальное количество переприсваивания максимума будет в том случае, если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна:
Ta(n) =2+1+3 (n-1) +2(n-1)=5 n - 2 = (n).
Слайд 55Средний случай
Элементарное усреднение
Tcр(n) =(Ta(n) + TA^(n))/2= 6n-3= Θ(n).
Вероятностный подход
Переприсваивание
максимума при просмотре к-го элемента происходит, если в подмассиве из
первых к элементов максимальным элементом является последний. В случае равномерного распределения вероятность этого равна 1/к. Тогда в массиве из n элементов математическое ожидание среднего количества операций присваивания определяется как:
Величина Hn называется n-ым гармоническим числом.
Ta(n) =2+1 +3 (n-1) + 2(n-1)+2 (Ln(n) + ))=5 n-2 +2Ln(n) +2 = (n).
Слайд 56
Некоторые математические формулы, необходимые для анализа алгоритмов.
Логарифмы Формулы суммирования
Слайд 58Математическое ожидание дискретной случайной величины.
Если известен закон распределения случайной величины x,
то есть известно, что случайная величина x может принимать значения x1, x2, ..., xk с вероятностями p1, p2, ..., pk, тогда
математическое ожидание Mx случайной величины x равно
Если случайная величина x имеет дискретное равномерное распределение:
, то её математическое ожидание равно
Свойства математического ожидания:
Математическое ожидание постоянной равно этой постоянной Mc=C
Математическое ожидание суммы случайных величин равно сумме их математических ожиданий: Mx+y =Mx+My
Математическое ожидание произведения независимых случайных величин равно произведению математических ожиданий этих величин: Mx*y =Mx*My
Слайд 59II. Нахождение вида функции трудоемкости без подсчета фактической стоимости команд.
Слайд 60Анализ наилучшего случая.
На вход подается уже отсортированный массив. При этом
все внутренние циклы состоят всего из одной итерации, то есть ti =1
для всех i. Тогда время работы алгоритма составит:
Слайд 61Анализ наихудшего случая.
Входной массив, отсортирован в обратном порядке. При этом
каждый a[i] элемент сравнивается со всеми уже отсортированными элементами a[0]…a[i-1].
Это означает, что все внутренние циклы состоят из i итераций, то есть ti =i для всех i. Тогда время работы алгоритма составит:
Слайд 62Анализ среднего случая.
Характер поведения "усредненного" времени работы часто ничем не
лучше поведения времени работы для наихудшего случая. Предположим, что последовательность,
к которой применяется сортировка методом вставок, сформирована случайным образом. Сколько времени понадобится, чтобы определить, в какое место подмассива a[l..i-1] следует поместить элемент a[i]? Предположим, что в среднем половина элементов этого подмассива меньше, чем a[i], а половина — больше его. Таким образом, в среднем нужно проверить половину элементов подмассива a[l..i-1], поэтому ti приблизительно равно i/2.
Слайд 64III. Оценивание порядков роста времени работы.
Следствие. Из правила сумм также
следует, что если f(n) < g(n) для всех n, превышающих
n0, то выражение O(f(n) + g(n)) эквивалентно O(g(n)). Например, О(n2 + n) то же самое, что О(n2).
![Анализ наихудшего случая.Входной массив, отсортирован в обратном порядке. При этом каждый a[i] элемент сравнивается со всеми уже](/img/thumbs/1c4cef97943ddda5faa8a65531aa4348-800x.jpg "Алгоритмически неразрешимые задачи Анализ наихудшего случая.Входной массив, отсортирован в обратном порядке. При этом каждый")
