Структуры и алгоритмы обработки данных 2 - презентация, доклад, проект скачать

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

Структуры и алгоритмы обработки данных 2, слайд №1

Структуры и алгоритмы обработки данных 2, слайд №2

Структуры и алгоритмы обработки данных 2, слайд №3

Структуры и алгоритмы обработки данных 2, слайд №4

Структуры и алгоритмы обработки данных 2, слайд №5

Структуры и алгоритмы обработки данных 2, слайд №6

Структуры и алгоритмы обработки данных 2, слайд №7

Структуры и алгоритмы обработки данных 2, слайд №8

Структуры и алгоритмы обработки данных 2, слайд №9

Структуры и алгоритмы обработки данных 2, слайд №10

Структуры и алгоритмы обработки данных 2, слайд №11

Структуры и алгоритмы обработки данных 2, слайд №12

Структуры и алгоритмы обработки данных 2, слайд №13

Структуры и алгоритмы обработки данных 2, слайд №14

Структуры и алгоритмы обработки данных 2, слайд №15

Структуры и алгоритмы обработки данных 2, слайд №16

Структуры и алгоритмы обработки данных 2, слайд №17

Структуры и алгоритмы обработки данных 2, слайд №18

Структуры и алгоритмы обработки данных 2, слайд №19

Структуры и алгоритмы обработки данных 2, слайд №20

Структуры и алгоритмы обработки данных 2, слайд №21

Структуры и алгоритмы обработки данных 2, слайд №22

Структуры и алгоритмы обработки данных 2, слайд №23

Структуры и алгоритмы обработки данных 2, слайд №24

Структуры и алгоритмы обработки данных 2, слайд №25

Структуры и алгоритмы обработки данных 2, слайд №26

Структуры и алгоритмы обработки данных 2, слайд №27

Структуры и алгоритмы обработки данных 2, слайд №28

Структуры и алгоритмы обработки данных 2, слайд №29

Структуры и алгоритмы обработки данных 2, слайд №30

Структуры и алгоритмы обработки данных 2, слайд №31

Структуры и алгоритмы обработки данных 2, слайд №32

Структуры и алгоритмы обработки данных 2, слайд №33

Структуры и алгоритмы обработки данных 2, слайд №34

Структуры и алгоритмы обработки данных 2, слайд №35

Структуры и алгоритмы обработки данных 2, слайд №36

Структуры и алгоритмы обработки данных 2, слайд №37

Структуры и алгоритмы обработки данных 2, слайд №38

Структуры и алгоритмы обработки данных 2, слайд №39

Структуры и алгоритмы обработки данных 2, слайд №40

Структуры и алгоритмы обработки данных 2, слайд №41

Структуры и алгоритмы обработки данных 2, слайд №42

Структуры и алгоритмы обработки данных 2, слайд №43

Структуры и алгоритмы обработки данных 2, слайд №44

Структуры и алгоритмы обработки данных 2, слайд №45

Содержание ▲

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

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

Слайд 1

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

Структуры и алгоритмы обработки данных, 2 Лекция 2 (+3) Сортировка (новый раздел) Постановка задачи Простые алгоритмы сортировки Сортировка выбором Сортировка обменами Сортировка вставками Быстрая сортировка Процедура разделения Алгоритм QuickSort Модификации Анализ алгоритма

Слайд 2

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

Сортировка 2 Дан массив a: array [1..n] of Ordinal Отрезок (сегмент) массива a[p..q] упорядочен: Sort (a, p, q)  ( i: p  i  q: a[i]  a[i+1]) Предусловие: a[1..n] = a0[1..n] Постусловие: Sort (a, 1, n) & & Перестановка(a[1..n], a0[1..n]), где Перестановка(a[1..n], a0[1..n])  ( i: 1  i  n: (N j: 1  j  n: a[ i ] = a0[ j ] ) = = (N j: 1  j  n: a[ i ] = a [ j ] ) )

Слайд 3

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

Сортировка 3 Простые алгоритмы сортировки Сортировка выбором Идея. Пример. Список (удаление и вставка)

Слайд 4

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

Сортировка 4

Слайд 5

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

Сортировка 5 Простые алгоритмы сортировки Сортировка выбором Инвариант внешнего цикла:

Слайд 6

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

Сортировка 6 Сортировка 6

Слайд 7

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

Сортировка 7 Анализ сортировки выбором Сi – число сравнений при выборе минимального элемента на i-ом шаге (в сегменте из (n – i + 1) элементов) Сi = n – i Суммарно по всем шагам:

Слайд 8

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

Сортировка 8 Анализ сортировки выбором Пусть Mi – число перестановок на i-ом шаге, включая обновления текущего минимума (в сегменте из (n – i + 1) элементов). В худшем случае (обратно упорядоченный массив): Mi =(n – i) + 3 Тогда суммарно по всем шагам (i1..n1): Mmax= (n2 – n)/2 + 3(n – 1)

Слайд 9

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

Сортировка 9 Анализ сортировки выбором В среднем: Вероятность того, что произойдет обновление текущего минимума на j-ом шаге внутреннего цикла = 1/j (любой, в том числе последний из j элементов - минимальный). Т.о. за i-й шаг среднее (М.О.) число перестановок = 1/2 + 1/3 + 1/4 +… + 1/(n-i+1) = Hn-i+1 -1, где частичная сумма гармонического ряда Hk= 1 + 1/2 + 1/3 + … + 1/k, Hk= ln k +  + 1/(2k) +... , где  - постоянная Эйлера. Итак, за i-й шаг внешнего цикла среднее число присваиваний Hn-i+1 -1+3= Hn-i+1 +2  ln (n-i+1) +  +2

Слайд 10

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

Слайд 11

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

Сортировка 11 Простые алгоритмы сортировки Сортировка обменами («пузырьковая»)

Слайд 12

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

Сортировка 12

Слайд 13

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

Сортировка 13

Слайд 14

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

Сортировка 14 Простые алгоритмы сортировки Сортировка обменами Инвариант внешнего цикла For i:=n downto 2 do

Слайд 15

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

Сортировка 15 Сортировка обменами (пузырьковая) for i:=n downto 2 do begin {просмотр a[1..i] с обменами соседних элементов} for j := 2 to i do if a[j1] > a[j] then a[j1]  a[j] ; {a[i] = max a[1..i] } end

Слайд 16

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

Анализ сортировки обменами (пузырьковой) Анализ сортировки обменами (пузырьковой)

Слайд 17

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

Сортировка 17 Простые алгоритмы сортировки Сортировка вставками (включением)

Слайд 18

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

Сортировка 18 Простые алгоритмы сортировки Сортировка ВСТАВКАМИ Инвариант внешнего цикла:

Слайд 19

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

Сортировка прямыми ВСТАВКАМИ Сортировка прямыми ВСТАВКАМИ

Слайд 20

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

Сортировка 20 Простые алгоритмы сортировки Сортировка ВСТАВКАМИ АЛГОРИТМ Прямые вставки (StraightInsertion) type index=0..nMax; index1=1..nMax; index2=0..nMax+1; mass=array [index] of Integer;

Слайд 21

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

Сортировка 21 procedure StraightInsertion ( var a: mass; n: index1; k: index1 ); { сортировка массива методом вставки } var i: index; j: index1; x: Integer; begin for i:=2 to n do begin { включить a[i] на соотв. место в a[1..i] } x := a[i]; a[0] := x; { a[0] - "барьер" } j := i; while x < a[j-1] do begin { 1

Слайд 22

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

Сортировка 22 Сортировка ПРЯМЫМИ ВСТАВКАМИ Анализ Число сравнений  число перемещений. Число сравнений на i –ом шаге Ci = i/2 в среднем. Тогда по всем шагам i2..n

Слайд 23

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

Сортировка БИНАРНЫМИ ВСТАВКАМИ Сортировка БИНАРНЫМИ ВСТАВКАМИ for i:=2 to n do begin { Найти место a[i] среди a[1..i-1] } x := a[i]; L:=1; R:=i; while LR do begin m:=(L+R) div 2; if a[m] < x then L:=m+1 else R:=m end; {(L1..i) & (a[L-1] < x  a[L])} {сдвинуть a[L..i-1] на позицию вправо на место a[L+1..i]} for j:=i downto L+1 do a[j] := a[j-1]; {вставить x на место a[L]} a[L]:=x end {for}

Слайд 24

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

Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма Число сравнений на i –ом шаге Ci  log2i. По всем шагам (i2..n)

Слайд 25

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

Сортировка 25 Быстрая сортировка (QuickSort)

Слайд 26

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

Сортировка 26 Быстрая сортировка (QuickSort)

Слайд 27

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

while q

Слайд 28

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

Быстрая сортировка: Быстрая сортировка: разделение и слияние

Слайд 29

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

Сортировка 29 procedure Sortp1 (var a: mass; m, n: index1; k: index1 ); var p, q: index2; begin Partition1 ( a, m, n, p ); if p-m>k then Sortp1 ( a, m, p-1, k ); q:=p+1; if n-q+1>k then Sortp1 ( a, q, n, k ) { подмассив длиной

Слайд 30

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

Сортировка 30 begin { QuickSort1 } Sortp1( a, 1, n, k ); if k>1 then { окончательная сортировка простым методом } StraightInsertion ( a, n ,1) end { QuickSort1 };

Слайд 31

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

Быстрая сортировка Быстрая сортировка Неполная сортировка. Выбор k

Слайд 32

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

Первый вызов Partition 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 у п О р я д о ч И в а н и е о п О р я д у ч И в а н и е о е О р я д у ч И в а н и п о е О р я д у ч И в а н и п о е О и я д у ч И в а н р п о е О и н д у ч И в а я р п о е О и н д у ч И в а я р п о е О и н д а ч И в у я р п о е О и н д а в И ч у я р п И е О и н д а в о ч у я р п

Слайд 33

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

Сортировка 33 1 2 3 4 5 6 7 8 9 10 11 12 13 14 И е О и н д а в о ч у я р п

Слайд 34

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

Сортировка 34 Анализ. Лучший случай

Слайд 35

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

Сортировка 35 Анализ. Худший случай

Слайд 36

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

Слайд 37

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

Анализ. В среднем Анализ. В среднем

Слайд 38

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

Анализ. В среднем (продолжение) Анализ. В среднем (продолжение)

Слайд 39

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

Анализ. В среднем (продолжение) Анализ. В среднем (продолжение)

Слайд 40

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

Приложение Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций, которые не более чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение О(f(n)). Запись g (n)  О(f(n)) означает, что cуществуют: вещественная константа C > 0 и натуральная константа n0 , для которых g (n)  C f (n) при всех n  n0

Слайд 41

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

Асимптотические оценки Обозначение О(f(n))

Слайд 42

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

Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций, которые не менее чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение (f(n)). Запись g (n)  (f(n)) означает, что существуют : вещественная константа C > 0 и натуральная константа n0 , для которых g (n)  C f (n) при всех n  n0.

Слайд 43

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

Асимптотические оценки Обозначение (f(n))

Слайд 44

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

Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций того же порядка, что и f (n) при достаточно большом n, используется обозначение (f(n)) Запись g (n)  (f(n)) означает, что существуют : вещественные константы C1 > 0 и C2 > 0 и натуральная константа n0 , для которых C1 f (n)  g (n)  C2 f (n) при всех n  n0