Алгоритм
<<  Определение и свойства алгоритма Информатика «Понятие алгоритма»  >>
Алгоритмы: основные понятия
Алгоритмы: основные понятия
Алгоритмом называют точное предписание
Алгоритмом называют точное предписание
Свойства алгоритма
Свойства алгоритма
Основные способы записи алгоритмов
Основные способы записи алгоритмов
Этапы разработки и анализа алгоритмов
Этапы разработки и анализа алгоритмов
Базовые структуры данных
Базовые структуры данных
Важные типы задач
Важные типы задач
Основы анализа эффективности алгоритмов
Основы анализа эффективности алгоритмов
Измерение времени выполнения алгоритма
Измерение времени выполнения алгоритма
Порядок роста
Порядок роста
Приближенные значения функций, важных для анализа алгоритмов
Приближенные значения функций, важных для анализа алгоритмов
Эффективность алгоритма в разных случаях
Эффективность алгоритма в разных случаях
Асимптотические обозначения
Асимптотические обозначения
Строгое определение
Строгое определение
«Омега»
«Омега»
«Тэта»
«Тэта»
Свойства обозначений
Свойства обозначений
Использование пределов для сравнения порядка роста двух функций
Использование пределов для сравнения порядка роста двух функций
Примеры
Примеры
Основные классы эффективности
Основные классы эффективности
Эмпирический анализ алгоритмов
Эмпирический анализ алгоритмов
Различия между математическим и эмпирическим анализом алгоритмов
Различия между математическим и эмпирическим анализом алгоритмов
Визуализация алгоритмов
Визуализация алгоритмов
Презентация «Основы алгоритмов». Размер 271 КБ. Автор: Mux.

Загрузка...

Основы алгоритмов

содержание презентации «Основы алгоритмов.ppt»
СлайдТекст
1 Алгоритмы: основные понятия

Алгоритмы: основные понятия

Алгоритмы: основные понятия. Свойства алгоритмов Этапы разработки Основные типы задач Анализ эффективности алгоритмов Основные классы алгоритмов. 1. ©Павловская Т.А. (СПбГУ ИТМО).

2 Алгоритмом называют точное предписание

Алгоритмом называют точное предписание

Алгоритмом называют точное предписание, которое задает вычислительный процесс и представляет собой конечную последовательность обычных элементарных действий, четко определяющую процесс преобразования исходных данных в искомый результат. 2. ©Павловская Т.А. (СПб НИУ ИТМО).

3 Свойства алгоритма

Свойства алгоритма

Свойства алгоритма. Каждый алгоритм имеет дело с данными — входными, промежуточными и выходными. Конечность (1 — алгоритм состоит из отдельных элементарных действий, множество различных действий конечно; 2 — алгоритм должен заканчиваться за конечное число шагов.) Дискретность (конечная последовательность отдельных шагов; каждый шаг выполняется за конечное время) Детерминированность (определенность) Элементарность (понятность) Результативность Массовость Эффективность. 3. ©Павловская Т.А. (СПб НИУ ИТМО).

4 Основные способы записи алгоритмов

Основные способы записи алгоритмов

Основные способы записи алгоритмов. Вербальный символьный графический. 4. ©Павловская Т.А. (СПб НИУ ИТМО).

5 Этапы разработки и анализа алгоритмов

Этапы разработки и анализа алгоритмов

Этапы разработки и анализа алгоритмов. 5. ©Павловская Т.А. (СПб НИУ ИТМО).

6 Базовые структуры данных

Базовые структуры данных

Базовые структуры данных. Линейные: массив и список строки, битовые массивы одно- ни двунаправленные списки, стек, очередь, очередь с приоритетами Граф ориентированный и неориентированный; взвешенный дерево: связный ациклический граф дерево поиска (бинарное) Множество мультимножество. 6. ©Павловская Т.А. (СПб НИУ ИТМО).

7 Важные типы задач

Важные типы задач

Важные типы задач. Сортировка; поиск; обработка строк; задачи из теории графов; комбинаторные задачи; геометрические задачи; численные задачи. 7. ©Павловская Т.А. (СПб НИУ ИТМО).

8 Основы анализа эффективности алгоритмов

Основы анализа эффективности алгоритмов

Основы анализа эффективности алгоритмов. ВременнАя эффективность является индикатором скорости работы алгоритма оценивается по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n Важен порядок роста времени выполнения алгоритма в зависимости от n Пространственная эффективность показывает, сколько дополнительной оперативной памяти нужно для работы алгоритма Эффективность оценивают в наихудшем, наилучшем и среднем случаях Виды анализа: математический и эмпирический. Когда вы можете измерить и выразить в цифрах то, о чем говорите, вы что-то знаете об изучаемом предмете. Лорд Кельвин (1824-1907). 8. ©Павловская Т.А. (СПб НИУ ИТМО).

9 Измерение времени выполнения алгоритма

Измерение времени выполнения алгоритма

Измерение времени выполнения алгоритма. Непосредственное (эмпирический анализ) Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ) T(n) ? сор * С(n) пусть, например, С(n) = n(n — 1)/2 Насколько дольше будет выполняться программа, если удвоить размер входных данных? 9. ©Павловская Т.А. (СПб НИУ ИТМО).

10 Порядок роста

Порядок роста

Порядок роста. При малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для больших значений n вычисляют порядок роста функции. 10. ©Павловская Т.А. (СПб НИУ ИТМО).

11 Приближенные значения функций, важных для анализа алгоритмов

Приближенные значения функций, важных для анализа алгоритмов

Приближенные значения функций, важных для анализа алгоритмов. n. log2n. n. n·log2n. n2. n3. 2n. n! 101. 3,3. 101. 3,3·101. 102. 103. 103. 3,6·106. 102. 6,6. 102. 6,6·102. 104. 106. 1,3·1030. 9,3·10157. 103. 10. 103. 10·103. 106. 109. 104. 13. 104. 13·104. 108. 1012. 105. 17. 105. 17·105. 1010. 1015. 106. 20. 106. 20·106. 1012. 1018. 11. ©Павловская Т.А. (СПб НИУ ИТМО).

12 Эффективность алгоритма в разных случаях

Эффективность алгоритма в разных случаях

Эффективность алгоритма в разных случаях. Cуществует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск). Эффективность измеряют для: наихудшего случая наилучшего случая среднего случая Пример: среднее количество операций сравнения при поиске: 12. ©Павловская Т.А. (СПб НИУ ИТМО).

13 Асимптотические обозначения

Асимптотические обозначения

Асимптотические обозначения. Нестрогие определения «О большое» О (g(n)) —множество всех функций, порядок роста которых при достаточно больших n не превышает некоторую константу, умноженную на значение функции g(n). 13. ©Павловская Т.А. (СПб НИУ ИТМО).

14 Строгое определение

Строгое определение

Строгое определение. Говорят, что функция t(n) принадлежит множеству O(g(n)), что записывается как t(n) ? O(g(n)) если для всех больших значений n функция t (n) ограничена сверху некоторой константой, умноженной на значение функции g(n), т.е. если существует положительная константа с и неотрицательное целое число nо такое, что t (n) ? сg(n) для всех n ? nо. 14. ©Павловская Т.А. (СПб НИУ ИТМО).

15 «Омега»

«Омега»

«Омега». ? (g(n)) — множество всех функций, порядок роста которых при достаточно больших n не меньше некоторой константы, умноженной на значение функции g(n). 15. ©Павловская Т.А. (СПб НИУ ИТМО).

16 «Тэта»

«Тэта»

«Тэта». ?(g(n)) — множество всех функций, порядок роста которых при достаточно больших n равен некоторой константе, умноженной на значение функции g(n). 16. ©Павловская Т.А. (СПб НИУ ИТМО).

17 Свойства обозначений

Свойства обозначений

Свойства обозначений. Если t1(n) ? O(g1(n)) и t2(n) ? O(g2(n)) , то t1(n) + t2(n) ? O(max { (g1(n)), (g2(n)) }) Аналогично для остальных обозначений. Это свойство с точки зрения анализа эффективности означает, что общая эффективность алгоритма, состоящего из двух исполняемых частей, зависит от той части, которая имеет наибольший порядок роста, т.е. от его наименее эффективной части. 17. ©Павловская Т.А. (СПб НИУ ИТМО).

18 Использование пределов для сравнения порядка роста двух функций

Использование пределов для сравнения порядка роста двух функций

Использование пределов для сравнения порядка роста двух функций. 18. ©Павловская Т.А. (СПб НИУ ИТМО).

19 Примеры

Примеры

Примеры. 19. ©Павловская Т.А. (СПб НИУ ИТМО).

20 Основные классы эффективности

Основные классы эффективности

Основные классы эффективности. Константа Логарифмическая Линейная n-log-n Квадратичная Кубическая Экспоненциальная Факториальная. 20. ©Павловская Т.А. (СПб НИУ ИТМО).

21 Эмпирический анализ алгоритмов

Эмпирический анализ алгоритмов

Эмпирический анализ алгоритмов. 1. Уяснение цели предстоящего эксперимента. 2. Определение измеряемой метрики М и единиц измерения (количество операций или время работы). 3. Определение характеристик входных данных (их диапазон, размер и т.д.). 4. Создание программы, реализующей алгоритм (или алгоритмы), для проведения эксперимента. 5. Генерация образца входных данных. 6. Выполнение алгоритма (или алгоритмов) над образцом входных данных и запись наблюдаемых данных. 7. Анализ полученных данных. 21. ©Павловская Т.А. (СПб НИУ ИТМО).

22 Различия между математическим и эмпирическим анализом алгоритмов

Различия между математическим и эмпирическим анализом алгоритмов

Различия между математическим и эмпирическим анализом алгоритмов. Преимущество математического анализа — независимость от конкретных входных данных недостаток — ограниченная применимость, в особенности для исследования эффективности в среднем случае. Эмпирический анализ применим к любому алгоритму, но его результаты могут зависеть от конкретных входных данных и использованного для проведения эксперимента компьютера. 22. ©Павловская Т.А. (СПб НИУ ИТМО).

23 Визуализация алгоритмов

Визуализация алгоритмов

Визуализация алгоритмов. Визуализация алгоритмов - еще один путь изучения алгоритмов, помимо математического и эмпирического анализа: статическая динамическая (анимация) «Десять заповедей анимации алгоритмов»: 1. Последовательность. 2. Интерактивность. 3. Ясность и краткость. 4. Снисходительность к пользователю и прощение его ошибок. 5. Адаптация к уровню знаний пользователя. 6. Упор на визуальную часть. 7. Удержание интереса пользователя. 8. Символьное и пиктограммное представление. 9. Наличие анализа алгоритма (статистики выполнения) и сравнение с другими алгоритмами для решения той же задачи. 10. Наличие истории выполнения. 23. ©Павловская Т.А. (СПб НИУ ИТМО).

«Основы алгоритмов»
Сайт

5informatika.net

115 тем
5informatika.net > Алгоритм > Основы алгоритмов.ppt