Оценка сложности вычислительных алгоритмов. Лекция 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, слайд №31

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

Основные параметры вычислений и данных Как число необходимых команд и ячеек памяти зависит от размера входных данных? Обозначим Time(А, х) и Space(A, x) число команд и ячеек памяти, необходимых программе А для обработки входных данных х Обозначим |x| >= 0 размер входных данных x

Слайд 4

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

Примеры Умножение матриц MM |x| = порядок матрицы x Space(MM, x) = 3*|x|^2 Time(MM, x) = число умножений и сложений = 2 * |x|^3 Сортировка массива простыми вставками I |x| = длина массива х Space(I, x) = |x| |x| - 1

Слайд 5

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

Минимальные требования к |.| Число команд, необходимых программе для обработки входных данных, должно стремиться к ∞ когда размер входных данных стремится к ∞ Time(A, xk) -> ∞ при |xk| -> ∞

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

Связь между разными мерами сложности Сложность в среднем не превосходит сложность в худшем случае T(A, n)

Слайд 12

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

Пример вычисления сложности по времени в среднем 1/3 Возведение a в степень x методом повторных квадратов RS RS(a, x): q = a u = 1 for bit in запись х в двоичной с.с. : if bit == 1: u *= q q *= q return u

Слайд 13

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

Пример вычисления сложности по времени в среднем 2/3 Input(n) = { x | 2n – 1

Слайд 14

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

Пример вычисления сложности по времени в среднем 3/3 Как известно, k∙C(n, k) = n∙C(n – 1, k – 1) Σx ∈ Input(n)( число битов = 1 в х) = = Σ0

Слайд 15

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

Оценка сложности с практической точки зрения Точное число команд и ячеек памяти на практике не важно Зависит от набора команд Для входных данных большого размера слагаемые низших составляют исчезающий % от общего числа команд и ячеек памяти Обычно приближенно оценивают сверху самое быстро растущее слагаемое в зависимости от размера данных Существуют разные методы построения приближенных оценок сверху для сложности программ

Слайд 16

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

Как оценить сложность программы на языке Си? Обозначим T(A, n) оценку сверху для T(A, n) на основе записи А на языке Си T({ А1; А2; }, n) = T (A1, n) + T(A2, n) T({ if (C) A1; else A2; }, n) = T (C, n) + max(T(A1, n), T(A2, n)) T({ for (i = N(n); i > 0; --i) A(i); }, n) = T (N(n), n) + Σ0

Слайд 17

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

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

Слайд 18

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

Дерево трасс исполнения Трасса исполнения программы для входных данных х – это множество пар вида (номер шага при обработке х, исполненная на этом шаге команда) Дерево трасс исполнения для входных данных размера n Множество вершин = объединение трасс для всех входных данных размера n Вершина (q, c1) является родителем вершины (r, c2), если q + 1 = r «Дерево трасс исполнения получается склеиванием общих префиксов»

Слайд 19

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

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

Слайд 20

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

Построение оценки снизу для поиска min и max -- 2/4 Каждый шаг произвольной программы, решающей эту задачу, характеризуется 4 множествами элементов массива (A, B, C, D): A = не участвовали в сравнениях B = во всех сравнениях были больше C = во всех сравнениях были меньше D = в одних сравнениях были больше, а в других — меньше

Слайд 21

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

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

Слайд 22

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

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

Слайд 23

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

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

Слайд 24

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

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

Слайд 25

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

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

Слайд 26

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

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

Слайд 27

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

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

Слайд 28

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

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

Слайд 29

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

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

Слайд 30

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

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

Слайд 31

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

Пример 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)) – так как делить нужно в с раз более точно

Слайд 32

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

Пример 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 -- очевидно