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

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

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

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

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

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

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

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

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

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

Приближенные значения функций, важных для анализа алгоритмов ©Павловская Т.А. (СПб НИУ ИТМО) 11 nlog 2 nnn·log 2 nn2n2 n3n3 2n2n n! , ,3· ,6· , ,6· ,3· ,3· · · · ·

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

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

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

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

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

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

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

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

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

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

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

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