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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

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

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

Слайд 1

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

Структуры и алгоритмы обработки данных, 2 Лекция 5 Сортировка (продолжение) Нижняя граница задачи сортировки Оптимальная сортировка Поразрядная сортировка

Слайд 2

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

Сортировка 4 2 Нижняя граница задачи сортировки Вопрос: существует ли алгоритм сортировки, основанный на сравнениях и решающий задачу за меньшее число операций, чем O (n log n) при любых входных данных? Сортировка с минимальным числом сравнений (избыточные сравнения не выполняются) Деревья решений (сравнений) Для простоты – все ключи различны. Основная операция сравнения: ki < kj

Слайд 3

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

Сортировка 4 3 Сортировка с минимальным числом сравнений Деревья решений (сравнений)

Слайд 4

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

Сортировка 4 4 Сортировка с минимальным числом сравнений Деревья решений (сравнений)

Слайд 5

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

Сортировка 4 5 Деревья решений (сравнений)

Слайд 6

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

Сортировка 4 6 Деревья решений (сравнений) Пусть m высота дерева (максимальное число сравнений). 2m  число листьев  n! (число листьев должно быть не менее числа исходов) m  log2 n! Итак, утверждение: Для любого алгоритма сортировки, основанного на сравнениях, всегда можно подобрать такие исходные данные, что применение алгоритма потребует не менее log2 n! шагов.

Слайд 7

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

Сортировка 4 7 Формула Стирлинга

Слайд 8

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

Сортировка 4 8 Оптимальная сортировка

Слайд 9

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

Сортировка 4 9 Оптимальная сортировка

Слайд 10

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

Сортировка 4 10 Оптимальная сортировка

Слайд 11

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

Сортировка 4 11 Поразрядная сортировка (Распределяющая сортировка) Пример 1 (с картами). Карта = (масть, достоинство) Масть:  ‑ трефа,  ‑ бубна,  ‑ черва,  ‑ пика Достоинство: 2, 3, 4, 5, 6, 7, 8, 9, 10, В, Д, К, Т Порядок по масти:  <  <  < . Порядок по достоинству: 2

Слайд 12

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

Сортировка 4 12 Поразрядная сортировка Сортировка колоды карт в лексикографическом порядке: 1 шаг – распределяем по достоинству (раскладываем) на кучки («лицом» вверх)

Слайд 13

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

Сортировка 4 13 Поразрядная сортировка

Слайд 14

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

Сортировка 4 14 Поразрядная сортировка Пример 2 (с числами). Рассмотрим целые (положительные) трехразрядные числа в позиционной шестиричной системе счисления, т.е. каждый разряд содержит цифры 0, 1, 2, 3, 4, 5 Например, пусть дана последовательность из 9 чисел 203, 045, 141, 405, 321, 522, 130, 054, 513 1 шаг – распределяем числа последовательности сначала по младшей цифре по ящикам с «именами»: «0», «1», «2», «3», «4», «5». Ящики заполняются снизу вверх.

Слайд 15

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

Сортировка 4 15 Поразрядная сортировка 203, 045, 141, 405, 321, 522, 130, 054, 513

Слайд 16

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

Сортировка 4 16 Поразрядная сортировка 130, 141, 321, 522, 203, 513, 054, 045, 405 2 шаг – аналогичным образом распределяем по ящикам числа полученной последовательности по средней цифре.

Слайд 17

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

Сортировка 4 17 Поразрядная сортировка 203, 405, 513, 321, 522, 130, 141, 045, 054 3 шаг – аналогичным образом распределяем по ящикам числа полученной последовательности по старшей цифре.

Слайд 18

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

Сортировка 4 18 Алгоритм поразрядной сортировки В общем случае даны числа (ключи): x1, x2, x3,…, xn. Каждый ключ состоит из p разрядов: (  i 1..n: xi  (xi(p), xi(p1),…, xi(1)) ), а каждый q-й разряд представлен цифрой xi(q) 0..r1. Тогда (xi