Оценка сложности вычислительных алгоритмов. Лекция 22 - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №1

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №2

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №3

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №4

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №5

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №6

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №7

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №8

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №9

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №10

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №11

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №12

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №13

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №14

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №15

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №16

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №17

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №18

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №19

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №20

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №21

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №22

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №23

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №24

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №25

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №26

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №27

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №28

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №29

Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №30

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Оценка сложности вычислительных алгоритмов. Лекция 22. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Оценка сложности вычислительных программ лекция 22

Слайд 2

Описание слайда:

План лекции ВременнАя и ёмкостная сложность программы Программа с точки зрения сложности Размер входных данных Сложность в худшем, в среднем Понятие оптимальной программы Классы вычислительной сложности программ Эквивалентность по сложности Примеры классов вычислительной сложности

Слайд 3

Описание слайда:

Программа, размер входных данных Обозначим Сt(А, х) и Сs(A, x) «затраты» по времени и по памяти на вычисление результата для данного х с помощью программы A Обозначим |x| «размер» входных данных программы |x| >= 0 Конкретный выбор |.| зависит от программы

Слайд 4

Описание слайда:

Примеры Умножение матриц MM |x| = порядок матрицы x Cs(MM, x) = 3*|x|^2 Ct(MM, x) = число умножений = |x|^3 Проверка на простоту пробными делениями TD |x| = x Cs(TD, x) = |x| 1

Слайд 5

Описание слайда:

Временная сложность ВременнОй сложностью (сложностью по времени в худшем случае) программы А называется функция от размера входных данных Т(А, n) = max{ Ct(A, x) | |x|=n }

Слайд 6

Описание слайда:

Пространственная сложность Пространственной сложностью (сложностью по памяти в худшем случае) программы А называется функция от размера входных данных S(А, n) = max{ Cs(A, x) | |x|=n }

Слайд 7

Описание слайда:

Пример – временная сложость TD Пусть |x| = число битов в x Пусть |x| = x

Слайд 8

Описание слайда:

Пример – возведение в степень Возведение в степень методом повторных квадратов RS Пусть в 2 c.c. x = β[k]β[k-1] ... β[1]β[0], β[i]∈{0,1} RS q := a; u := 1; for i = 0 to k do if β[i] = 1 then u := u * q fi; if i < k then q := q^2 fi; od Чему равна временная сложность RS для |x| = x и для |x| = число битов в записи х?

Слайд 9

Описание слайда:

Сложность в среднем 1/3 Обозначим In = { x||x| = n } множество входных данных размера n Обозначим Pn(x) вероятность входных данных x ∈ In Можно считать Pn(x) = 1/(число элементов в In) Иногда считают, что вероятность разных входных данных разная По определению вероятности Σx ∈ In Pn(x) = 1

Слайд 10

Описание слайда:

Сложность в среднем 2/3 Величина T(A, n) = Σx ∈ In Ct(A,x)Pn(x) называется временной сложностью программы А в среднем

Слайд 11

Описание слайда:

Сложность в среднем 2/3 Величина S(A, n) = Σx ∈ In Cs(A,x)Pn(x) называется пространственной сложностью программы А в среднем

Слайд 12

Описание слайда:

Связь сложности в худшем случае и в среднем Сложность в среднем не превосходит сложность в худшем случае T(A, n) = Σx ∈ In Ct(A,x)Pn(x)

Слайд 13

$Пример* – сложность в среднем RS In = { x | 2^(n-1)$

Описание слайда:

Пример* – сложность в среднем RS In = { x | 2^(n-1)

Слайд 14

Описание слайда:

Пример* – сложность в среднем RS kC(n,k) = nC(n-1,k-1) Σx ∈ In(число битов=1 в х) = = Σ0

Слайд 15

Описание слайда:

Полиномиальные программы Программа называется программой с полиномиально ограниченной сложностью, если ее сложность O(|x|^d) Программа называется полиномиальной, если ее сложность полиномиально ограничена

Слайд 16

Описание слайда:

Оптимальные алгоритмы Пусть АА – класс программ Программа А* называется оптимальной в классе АА, если для любой программы А из АА и любого размера n входных данных T(A*, n)

Слайд 17

Описание слайда:

Пример* min max -- 1/4 Пусть АА – все программы для одновременного нахождения минимума и максимума в массиве Покажем, что сложность по числу сравнений оптимальной программы 3n/2-2 и приведем оптимальную программу

Слайд 18

Описание слайда:

Пример * min max -- 2/4 Каждый этап произвольной программы V, решающей эту задачу, характеризуется 4 множествами элементов массива (A,B,C,D) A — множество элементов, не участвовавших в сравнениях B — множество элементов, которые во всех сравнениях оказывались большими C — множество элементов, которые во всех сравнениях оказывались меньшими D — множество элементов, которые в некоторых сравнениях были больше, а в других — меньше Начальная ситуация (n, 0, 0, 0) , конечная — (0, 1, 1, n − 2) Пусть λ (a,b,c) = 3a/2 + b + c − 2, где a, b и c -- число элементов в A, B и C

Слайд 19

Описание слайда:

Пример * min max -- 3/4 Начинаем с λ = 3n/2-2, Заканчиваем λ = 0 За шаг уменьшаем не более, чем на 1 Почему?? Всего шагов не менее 3n/2-2

Слайд 20

Описание слайда:

Пример * min max -- 4/4 Построим оптимальную программу Дан массив из n элементов x1 ,... , xn Образуем пары x1, x2 ; x3, x4 ; … В каждой паре найдём минимум и максимум за одно сравнение Пусть m1, m2, … – массив минимальных элементов пар размера n/2 Пусть M1, M2, ... – массив максимальных элементов пар размера n/2 Минимальный элемент исходного массива среди mi Максимальный элемент исходного массива среди Mi Если на первом шаге был непарный элемент (n — нечётное), то на него потребуется ещё два сравнения с найденными минимумом и максимумом В итоге на каждую пару тратится 3 сравнения

Слайд 21

Описание слайда:

Функции f и g называются функциями одного порядка, если найдутся такие c1 и c2, что для любого набора n значений аргументов f и g c1|g(n)| < |f(n)| < c2|g(n)| Обозначается f ~ g Функция f -- омега функции g, если найдется такая константа c, что |f (n)| > c | g(n) | для всех n Обозначается f (n) = Ω(g(n))

Слайд 22

Описание слайда:

Асимптотически оптимальная программа Программа А* называется асимптотически оптимальной (оптимальной по порядку сложности) в классе АА, если T(А*, n) = Ω(Т(А, n)) для любой другой программы A из АА

Слайд 23

Описание слайда:

Асимптотически оптимальная программа Если A* и B* -- оптимальные программы в классе АА, то T(А*, n) = Ω(Т(B*, n)) и T(В*, n) = Ω(Т(А*, n)) и T(А*, n) ~ Т(B*, n) Оптимальная асимптотическая сложность определена однозначно

Слайд 24

Описание слайда:

Классы сложности задач Под «задачей» будем понимать набор из трех объектов: функция P(.), которую требуется вычислить функция измерения входных данных |.| функция измерения числа операций T(.,.) в алгоритме вычисления функции P(.)

Слайд 25

Описание слайда:

Классы сложности задач Задача P не сложнее Q, если для любой программы QA, решающей задачу Q, найдётся программа PA, решающая задачу P, такая что T(PA, n) = O(T(QA, n)) Обозначение P ≤ Q Задачи P и Q, для которых одновременно верно P ≤ Q и Q ≤ P , называются эквивалентными (по сложности) Обозначение P >< Q

Слайд 26

Описание слайда:

Пример Рассмотрим следующие задачи: M: умножение 2-х целых чисел a и b D: деление целого a битовой длины ≤ 2m на целое b битовой длины m S: возведение в квадрат целого a R: обращение целого a Покажем, что M >< D >< S >< R

Слайд 27

Описание слайда:

Пример Можно доказать, что для |x| = число битов в x cложность f(.) любого из этих алгоритмов не убывает f(m) >= m af(m)

Слайд 28

Описание слайда:

Пример M < S ab = ((a+b)^2-a^2-b^2)/2 T(MA, m) = T(SA, m+1)+2T(SA,m)+O(m) = O(T(SA,m)) S < R a^2 = 1/(1/a-1/(a+1))-a T(SA, m) = O(T(RA, с*m)) – так как делить нужно в с раз более точно

Слайд 29

Описание слайда:

Пример R < M x[i]=2*x[i-1]-a*x[i-1]^2 Cходится к 1/а и x[i-1]=1/a*(1- ε) ==> x[i]=1/a*(1- ε^2) Почему? T(RA, m) = O(T(MA,m)) M >< S >< R D < M a/b = a*(1/b) R < D -- очевидно

Слайд 30

Описание слайда:

Заключение Задача, размер задачи как характеристика объема входных данных ВременнАя и ёмкостная сложность программы как функции размера задачи Верхняя, нижняя и средняя оценки Классы вычислительной сложности алгоритмов Эквивалентность по сложности Примеры классов вычислительной сложности Примеры определения класса вычислительной сложности задач