🗊Презентация Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №1Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №2Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №3Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №4Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №5Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №6Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №7Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №8Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №9Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №10Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №11Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №12Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №13Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №14Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №15Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №16Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №17Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №18Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №19Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №20Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №21Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №22Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №23Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №24Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №25Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №26Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №27Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №28Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №29Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №30Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №31Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №32Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №33Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №34Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №35
Скачать

Содержание ▲

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

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

Слайд 1


Математические модели
Описание слайда:
Математические модели

Слайд 2


Математические модели для времени выполнения Общее время выполнения. Сумма: стоимость каждой операции * частоту, для всех операций Анализ программ нужно производить на определенном наборе операций Стоимость зависит от компьютера и компилятора Частота зависит от алгоритма и входных данных
Описание слайда:
Математические модели для времени выполнения Общее время выполнения. Сумма: стоимость каждой операции * частоту, для всех операций Анализ программ нужно производить на определенном наборе операций Стоимость зависит от компьютера и компилятора Частота зависит от алгоритма и входных данных

Слайд 3


Стоимость основных операций
Описание слайда:
Стоимость основных операций

Слайд 4


Стоимость основных операций Ошибка новичков: неправильная оценка конкатенации строк
Описание слайда:
Стоимость основных операций Ошибка новичков: неправильная оценка конкатенации строк

Слайд 5


Пример: 1-Sum Подсчет количества инструкций, как функции от N.
Описание слайда:
Пример: 1-Sum Подсчет количества инструкций, как функции от N.

Слайд 6


Пример: 2-Sum Подсчет количества инструкций, как функции от N.
Описание слайда:
Пример: 2-Sum Подсчет количества инструкций, как функции от N.

Слайд 7


Упрощение вычислений
Описание слайда:
Упрощение вычислений

Слайд 8


Упрощение 1: модель стоимости Модель стоимости. Использовать некоторые основные операции для приближенного расчета времени выполнения.
Описание слайда:
Упрощение 1: модель стоимости Модель стоимости. Использовать некоторые основные операции для приближенного расчета времени выполнения.

Слайд 9


Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от входных данных N Игнорировать младшие члены Когда N велико, младшие члены незначительны Когда N мало, мы не о чем не заботимся
Описание слайда:
Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от входных данных N Игнорировать младшие члены Когда N велико, младшие члены незначительны Когда N мало, мы не о чем не заботимся

Слайд 10


Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от входных данных N Игнорировать младшие члены Когда N велико, младшие члены незначительны Когда N мало, мы не о чем не заботимся
Описание слайда:
Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от входных данных N Игнорировать младшие члены Когда N велико, младшие члены незначительны Когда N мало, мы не о чем не заботимся

Слайд 11


Пример: 2-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений
Описание слайда:
Пример: 2-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений

Слайд 12


Пример: 3-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений
Описание слайда:
Пример: 3-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений

Слайд 13


Оценка дискретной суммы Как оценить дискретную сумму? Средствами дискретной математики. Заменить сумму на определенный интеграл и посчитать
Описание слайда:
Оценка дискретной суммы Как оценить дискретную сумму? Средствами дискретной математики. Заменить сумму на определенный интеграл и посчитать

Слайд 14


Математическая модель для времени выполнения В принципе, всегда возможно построить точную математическую модель. На практике Формула может быть сложной Могут понадобиться дополнительные математические знания Точные модели лучше оставить экспертам
Описание слайда:
Математическая модель для времени выполнения В принципе, всегда возможно построить точную математическую модель. На практике Формула может быть сложной Могут понадобиться дополнительные математические знания Точные модели лучше оставить экспертам

Слайд 15


Классификация порядков роста
Описание слайда:
Классификация порядков роста

Слайд 16


Общая классификация порядков роста Малое число функций описывающих порядок роста основных алгоритмов 1, log N, N, Nlog N, N2, N3 и 2N
Описание слайда:
Общая классификация порядков роста Малое число функций описывающих порядок роста основных алгоритмов 1, log N, N, Nlog N, N2, N3 и 2N

Слайд 17


Общая классификация порядков роста
Описание слайда:
Общая классификация порядков роста

Слайд 18


Практическое применение порядков роста Нижняя оценка. Нужны линейные или линейно-логарифмические алгоритмы, чтобы идти в ногу с законом Мура.
Описание слайда:
Практическое применение порядков роста Нижняя оценка. Нужны линейные или линейно-логарифмические алгоритмы, чтобы идти в ногу с законом Мура.

Слайд 19


Бинарный поиск Цель. Найти индекс ключа в отсортированном массиве Бинарный поиск Ключ меньше — идем влево Ключ больше — идем вправо Равен — возвращаем результат
Описание слайда:
Бинарный поиск Цель. Найти индекс ключа в отсортированном массиве Бинарный поиск Ключ меньше — идем влево Ключ больше — идем вправо Равен — возвращаем результат

Слайд 20


Бинарный поиск: реализация Впервые бинарный поиск был опубликован в 1946; первая безошибочная реализация в 1962 Ошибка в Java.binarySearch() найдена в 2006
Описание слайда:
Бинарный поиск: реализация Впервые бинарный поиск был опубликован в 1946; первая безошибочная реализация в 1962 Ошибка в Java.binarySearch() найдена в 2006

Слайд 21


Бинарный поиск: математический анализ Предположение. Бинарный поиск использует 1 + lg N сравнений ключа в отсортированном массиве N T(N) количество сравнений ключа в отсортированном массиве размером <= N T(N) <= T(N / 2) + 1, для N > 1, с T(1) = 1
Описание слайда:
Бинарный поиск: математический анализ Предположение. Бинарный поиск использует 1 + lg N сравнений ключа в отсортированном массиве N T(N) количество сравнений ключа в отсортированном массиве размером <= N T(N) <= T(N / 2) + 1, для N > 1, с T(1) = 1

Слайд 22


N2log N алгоритм для 3-Sum Алгоритм основанный на сортировке Шаг 1: Сортировка N чисел Шаг 2: Для каждой пары чисел a[i] и a[j] сделать бинарный поиск для -(a[i] + a[j]) Анализ. Порядок роста N2log N Шаг 1: N2 сортировка вставками Шаг 2: N2log N бинарный поиск
Описание слайда:
N2log N алгоритм для 3-Sum Алгоритм основанный на сортировке Шаг 1: Сортировка N чисел Шаг 2: Для каждой пары чисел a[i] и a[j] сделать бинарный поиск для -(a[i] + a[j]) Анализ. Порядок роста N2log N Шаг 1: N2 сортировка вставками Шаг 2: N2log N бинарный поиск

Слайд 23


Сравнение программ Гипотеза. Основанный на сортировке 3-Sum алгоритм N2log N однозначно быстрее метода грубой силы N3
Описание слайда:
Сравнение программ Гипотеза. Основанный на сортировке 3-Sum алгоритм N2log N однозначно быстрее метода грубой силы N3

Слайд 24


Теория алгоритмов
Описание слайда:
Теория алгоритмов

Слайд 25


Типы анализа Лучший случай. Нижняя граница по стоимости Определяется самыми «простыми» входными данными Цель для любых входных данных Худший случай. Верхняя граница Определяется «самыми сложными» входными данными Предоставляет гарантии для всех возможных входных данных Средний случай. Ожидаемая стоимость для случайных входных данных Нужна модель для случайных входных данных Предоставляет возможность предсказывать производительность.
Описание слайда:
Типы анализа Лучший случай. Нижняя граница по стоимости Определяется самыми «простыми» входными данными Цель для любых входных данных Худший случай. Верхняя граница Определяется «самыми сложными» входными данными Предоставляет гарантии для всех возможных входных данных Средний случай. Ожидаемая стоимость для случайных входных данных Нужна модель для случайных входных данных Предоставляет возможность предсказывать производительность.

Слайд 26


Типы анализа Лучший случай. Нижняя граница по стоимости Худший случай. Верхняя граница Средний случай. Ожидаемая стоимость для случайных входных данных Реальные входные данные могут не соответствовать модели Нужно понимать, что может быть на входе, чтобы эффективно обрабатывать данные Подход 1: строить модель для худшего случая Подход 2: строить модель для случайных данных, в зависимости от вероятностных характеристик (если они даны)
Описание слайда:
Типы анализа Лучший случай. Нижняя граница по стоимости Худший случай. Верхняя граница Средний случай. Ожидаемая стоимость для случайных входных данных Реальные входные данные могут не соответствовать модели Нужно понимать, что может быть на входе, чтобы эффективно обрабатывать данные Подход 1: строить модель для худшего случая Подход 2: строить модель для случайных данных, в зависимости от вероятностных характеристик (если они даны)

Слайд 27


Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №27
Описание слайда:

Слайд 28


Пример: два алгоритма сортировки Быстрая сортировка Количество сравнений в худшем случае: N2 O(N2) Сортировка слиянием Количество сравнений в худшем случае: N logN O(N logN) Известно, что на практике быстрая сортировка в два раза быстрее и использует в два раза меньше памяти, чем сортировка слиянием. Не используйте O для предсказания производительности и сравнения алгоритмов
Описание слайда:
Пример: два алгоритма сортировки Быстрая сортировка Количество сравнений в худшем случае: N2 O(N2) Сортировка слиянием Количество сравнений в худшем случае: N logN O(N logN) Известно, что на практике быстрая сортировка в два раза быстрее и использует в два раза меньше памяти, чем сортировка слиянием. Не используйте O для предсказания производительности и сравнения алгоритмов

Слайд 29


Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором, слайд №29
Описание слайда:

Слайд 30


Сортировка выбором
Описание слайда:
Сортировка выбором

Слайд 31


Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом min Поменять местами a[i] и a[min] Видео 1
Описание слайда:
Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом min Поменять местами a[i] и a[min] Видео 1

Слайд 32


Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы и не меняются Нет элемента справа от стрелки, который был бы меньше элемента слева от стрелки
Описание слайда:
Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы и не меняются Нет элемента справа от стрелки, который был бы меньше элемента слева от стрелки

Слайд 33


Сортировка выбором: внутренний цикл
Описание слайда:
Сортировка выбором: внутренний цикл

Слайд 34


Сортировка выбором: реализация на Java
Описание слайда:
Сортировка выбором: реализация на Java

Слайд 35


Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N перестановок
Описание слайда:
Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N перестановок

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию