Аналіз алгоритмів

Содержание

Слайд 2

Вступ Сьогодні ми поговоримо про: спостереження математичні моделі класифікацію за порядком зростання теорію алгоритмів пам’ять

Вступ

Сьогодні ми поговоримо про:
спостереження
математичні моделі
класифікацію за порядком зростання
теорію алгоритмів
пам’ять

Слайд 3

Чарльз Беббідж «Як тільки Аналітична Машина буде створена, вона буде спрямовувати

Чарльз Беббідж

«Як тільки Аналітична Машина буде створена, вона буде спрямовувати майбутній

розвиток науки. Кожний раз коли буде потрібно отримати результат за її допомоги буде ставати питання який напрямок обрахунків, що проводяться машиною приведуть нас якомога швидше до результату» – Чарльз Беббідж 1864.
В 1834 році Ч. Беббідж почав роботу над створенням програмованої обчислювальної машини, яку він назвав аналітичною.
http://ru.wikipedia.org/wiki/%D0%91%D1%8D%D0%B1%D0%B1%D0%B8%D0%B4%D0%B6,_%D0%A7%D0%B0%D1%80%D0%BB%D1%8C%D0%B7
Слайд 4

Running time За Беббіджем, час роботи вашого алгоритму вимірювався в тому,

Running time

За Беббіджем, час роботи вашого алгоритму вимірювався в тому, скільки

разів ви маєте прокрутити ручку Аналітичної машини.
Що змінилося зараз?
Ми отримали електронну ручку, але все одно сильно залежимо від того, скільки разів ми маємо повторити дискретні операції
Слайд 5

Причини аналізувати алгоритми Ми аналізуємо алгоритми що б: Оцінити продуктивність Порівняти

Причини аналізувати алгоритми

Ми аналізуємо алгоритми що б:
Оцінити продуктивність
Порівняти алгоритми
Надати гарантії обчислюваності/виконуваності
Зрозуміти

теоретичні основи
З практичної точки зору:
ми хочемо усунути помилки продуктивності
Слайд 6

Дискретне перетворення Фур'є Дискретне перетворення Фур'є (ДПФ, Discrete Fourier Transform) -

Дискретне перетворення Фур'є

Дискретне перетворення Фур'є (ДПФ, Discrete Fourier Transform) - це

математична процедура, що використовується для визначення гармонічного, або частотного, складу дискретних сигналів.
ДПФ є однією з найбільш розповсюджених і потужних процедур цифрової обробки сигналів.
ДПФ дозволяє аналізувати, перетворювати і синтезувати сигнали такими способами, які неможливі при неперервній (аналоговій) обробці.
Самий простий алгоритм (brute force) потребує N2 кроків
Алгоритм швидкого перетворення Фур’є (FFT) використовує N logN кроків. (був винайдений Гаусом ще в 1805 році)
Слайд 7

Проблема Основне питання, що ставить собі програміст – чи зможе моя

Проблема

Основне питання, що ставить собі програміст – чи зможе моя програма

вирішити поставлену задачу на великих вхідних даних.
Чому моя програма така повільна?
Чому моїй програмі не вистачає оперативної пам’яті?
Кнут в 1970 році сказав, що ми можемо використовувати науковий підхід до розуміння продуктивності програми.
Слайд 8

Науковий підхід, що застосовується для аналізу алгоритмів Науковий підхід: спостереження, якихось

Науковий підхід, що застосовується для аналізу алгоритмів

Науковий підхід:
спостереження, якихось характеристик з

реального світу, зазвичай на основі точних вимірювань
пропозиція гіпотетичної моделі, що узгоджується з спостереженнями
пророкування подій на основі запропонованої моделі
перевірка передбачень за допомогою подальших спостережень
обгрунтування за допомогою повторення процесу, поки гіпотеза і спостереження не співпадуть
Слайд 9

Принципи наукового підходу Експерименти мають бути відтворюємими, що б інші могли

Принципи наукового підходу

Експерименти мають бути відтворюємими, що б інші могли впевнитися

в вірності моделі, самостійно перевіривши гіпотезу.
Гіпотези мають бути фальсифікуємими, що б можна було точно знати, коли гіпотеза не вірна.
Висловлювання, що приписується Ейнштейну:
Жоден об’єм експериментальних досліджень не може довести, що я правий, але всього один експеримент може довести, що я помиляюся.
Слайд 10

Спостереження Почнемо з спостереження. 3-Sum. Дано N різних цілих чисел, скільки

Спостереження

Почнемо з спостереження.
3-Sum.
Дано N різних цілих чисел, скільки трійок в сумі

дають 0?
На вхід ми отримали числа:
30, -40, -20, -10, 40, 0, 10, 5
Відповідь:
30, -40, 10
30, -20, -10
-40, 40, 0
-10, 0, 10
Ця проблема має зв’язок з обчислювальною геометрією
Розглянемо розв’язання цієї проблеми
Перша спроба - TreeSumBF
Слайд 11

Вимірювання часу роботи Як виміряти час роботи програми? Вручну. http://standart-m.com.ua/userfiles/image/stopwatch1.jpg

Вимірювання часу роботи

Як виміряти час роботи програми?
Вручну.

http://standart-m.com.ua/userfiles/image/stopwatch1.jpg

Слайд 12

Вимірювання часу роботи Як виміряти час роботи програми? Автоматично. Ми можемо

Вимірювання часу роботи

Як виміряти час роботи програми?
Автоматично.
Ми можемо скористатися класом Stopwatch()
int[]

a = In.readInts(testFile);
Stopwatch stopwatch = new Stopwatch();
System.out.println(count(a));
double time = stopwatch.elapsedTime();
System.out.println(time);
Слайд 13

Емпіричний аналіз Ми можемо запустити програму на різних об’ємах даних і

Емпіричний аналіз

Ми можемо запустити програму на різних об’ємах даних і оцінити

витрачений час.
Давайте спробуємо запустити з більшими об’ємами і подивимося на результат.
8ints.txt
4
Витрачений час 0.0
1Kints.txt
70
Витрачений час 0.654
2Kints.txt
528
Витрачений час 5.133
4Kints.txt
4039
Витрачений час 41.941
8Kints.txt
32074
Витрачений час 330.783
Слайд 14

Емпіричний аналіз

Емпіричний аналіз

Слайд 15

Аналіз даних Зобразимо графічно залежність T(N) від N

Аналіз даних

Зобразимо графічно залежність T(N) від N

Слайд 16

Аналіз даних

Аналіз даних

 

Слайд 17

Аналіз даних Тепер ми отримали гіпотезу на основі гіпотези ми можемо

Аналіз даних

Тепер ми отримали гіпотезу
на основі гіпотези ми можемо спрогнозувати дані
після

чого провести серію експериментів і визначити чи співпадають реальні дані і дані за гіпотезою
Слайд 18

Аналіз даних Незалежні чинники Алгоритм Вхідні дані визначають значення b в

Аналіз даних

Незалежні чинники
Алгоритм
Вхідні дані
визначають значення b в степені.
Чинники залежні від системи
апаратне

забезпечення
програмне забезпечення
система
разом з незалежними чинниками впливають на значення константи a
Погані новини. Важко отримати точні вимірювання.
Хороші новини. Набагато простіше і дешевше, ніж в інших підходах.
Слайд 19

Математична модель Д. Кнут – «незважаючи на складність, в принципі можливо

Математична модель

Д. Кнут – «незважаючи на складність, в принципі можливо побудувати

математичну модель, що описує час виконання будь якої програми»
Загальний час виконання програми залежить від:
вартості виконання кожного оператора
властивість комп’ютера, компілятора і операційної системи
частота виконання кожного оператора
властивість програми і вхідних даних
Слайд 20

Математична модель Вартість базових операцій

Математична модель Вартість базових операцій

Слайд 21

Математична модель Вартість базових операцій

Математична модель Вартість базових операцій

Слайд 22

Математична модель Скільки інструкцій буде виконано в залежності від N? int

Математична модель

Скільки інструкцій буде виконано в залежності від N?
int count =

0;
for (int i =0; iif (a[i] == 0)
count++;
Відповідь:
оголошення змінних – 2
привласнення значень -2
оператор порівняння – N
порівняння рівності N
доступ до елементів масиву N
збільшення на одиницю – від N до 2N
Слайд 23

Математична модель Скільки інструкцій буде виконано в залежності від N? int

Математична модель

Скільки інструкцій буде виконано в залежності від N?
int count =

0;
for (int i =0; ifor (int j =i+1; jif (a[i]+ a[j] == 0)
count++;
Відповідь
оголошення змінних – N+2
привласнення значень – N+2
оператор порівняння – ½(N+1)(N+2)
перевірка рівності – ½N(N-1)
доступ до елементів масиву - N(N-1)
збільшення на одиницю – від 1/2N(N-1) до N(N-1)
Слайд 24

Математична модель «Дуже зручно мати міру об’єму робіт, навіть якщо вона

Математична модель

«Дуже зручно мати міру об’єму робіт, навіть якщо вона буде

дуже сира. Ми можемо підрахувати, скільки разів різні елементарні операції застосовуються в усьому процесі, а потім дати їм різної ваги.» - Алан Тюринг (1947).
Слайд 25

Математична модель Замість того, що б обраховувати прискіпливо всі операції ми

Математична модель

Замість того, що б обраховувати прискіпливо всі операції ми можемо

ігнорувати відносно малі операції і таким чином спрощувати математичні формули.
Це дозволяє нам працювати з апроксимацією.
Слайд 26

Математична модель Приклади апроксимації

Математична модель Приклади апроксимації

 

Слайд 27

Математична модель

Математична модель

 

Слайд 28

Математична модель

Математична модель

 

Слайд 29

Математична модель

Математична модель

 

Слайд 30

Математична модель В принципі, математична модель можлива. На практиці: формули можуть

Математична модель

В принципі, математична модель можлива.
На практиці:
формули можуть бути дуже складними
дуже

складні обрахування потрібні
дуже точні моделі мало коли потрібні
Ми будемо використовувати приблизні моделі.
Слайд 31

Класифікація за порядком зростання

Класифікація за порядком зростання

 

Слайд 32

Класифікація за порядком зростання

Класифікація за порядком зростання

Слайд 33

Класифікація за порядком зростання

Класифікація за порядком зростання

Слайд 34

Бінарний пошук Дано відсортований масив і ключ, потрібно знайти індекс ключа

Бінарний пошук

Дано відсортований масив і ключ, потрібно знайти індекс ключа в

масиві.
Бінарний пошук:
порівнюємо ключ з центральним елементом
якщо центральний елемент більше ключа, йдемо наліво
якщо менше, йдемо направо
рівний – знайшли відповідь.
Як знайти 34?
Слайд 35

Бінарний пошук Перший алгоритм бінарного пошуку опублікований в 1964 році Перший

Бінарний пошук

Перший алгоритм бінарного пошуку опублікований в 1964 році
Перший алгоритм без

помилок – в 1992 році
Помилки в Arrays.binarySearch() знайдені в 2006 році.
Подивимося на реалізацію BinarySearch
Твердження.
Бінарний пошук використовує 1+lgN порівнянь ключа і елементів масиву розміру N
Слайд 36

Бінарний пошук: математичний аналіз

Бінарний пошук: математичний аналіз

 

Слайд 37

N2logN алгоритм для 3-суми Алгоритм базований на сортуванні для 3-суми Відсортувати

N2logN алгоритм для 3-суми

Алгоритм базований на сортуванні для 3-суми
Відсортувати N чисел
Для

кожної пари чисел a[i] і a[j] ми робимо бінарний пошук елемента –(a[i]+a[j])
Порядок зростання N2logN
Слайд 38

Порівняння brute-force sorting-based

Порівняння

brute-force

sorting-based

Слайд 39

Аналіз В реальності наші приклади набагато складніші ніж ті, що ми

Аналіз

В реальності наші приклади набагато складніші ніж ті, що ми розглядали.
І

складність нашого алгоритму залежить від вхідних даних.
Тому ми можемо оцінити найкращий випадок,
самий простий випадок вхідних даних
та оцінити найгірший випадок (верхня межа вартості),
самий складний варіант вхідних даних
отримаємо гарантію того, що гірше вже не буде
Після цього ми можемо отримати середню складність. Очікувані витрати для випадкових вхідних даних.
Слайд 40

Аналіз

Аналіз

Слайд 41

Теорія алгоритмів Основними цілями теорії алгоритмів є: визначити «складність» проблеми запропонувати

Теорія алгоритмів

Основними цілями теорії алгоритмів є:
визначити «складність» проблеми
запропонувати «оптимальний» алгоритм
Оптимальний алгоритм:
Має

гарантовану продуктивність для будь яких вхідних даних
Не існує алгоритму, що може гарантувати кращу продуктивність
Слайд 42

Загально прийняті позначення в теорії алгоритмів

Загально прийняті позначення в теорії алгоритмів

Слайд 43

Теорія алгоритмів. Приклад 1.

Теорія алгоритмів. Приклад 1.

 

Слайд 44

Теорія алгоритмів. Приклад 2.

Теорія алгоритмів. Приклад 2.

 

Слайд 45

Пам’ять

Пам’ять

 

Слайд 46

Типові показники використання пам’яті

Типові показники використання пам’яті

Слайд 47

Типові показники використання пам’яті об’єктами в Java Заголовок об’єкта. 16 байт

Типові показники використання пам’яті об’єктами в Java

Заголовок об’єкта. 16 байт
Вказівник. 8

байт
Доповнення. Кожний об’єкт використовує розмір кратний 8 байтам, а тому інколи потрібно доповнення, що б зайняти цілий блок.
Приклад. Об’єкт Date використовує 32 байти пам’яті.
public class Date{
private int day;
private int month;
private int year;
}
Слайд 48

Приклад 2

Приклад 2

 

Слайд 49

Приклад.

Приклад.

 

Слайд 50

Приклад.

Приклад.

 

- Предыдущая
Графические изображения статистических данных
Следующая -
Урок-игра обобщающего повторения и контроля знаний по теме «Тепловые явления» (8 класс)

Похожие презентации

Устойчивость узла нагрузки
Понятие логарифма. Свойства логарифма. Десятичные и натуральные логарифмы
Презентация на тему 2 класс Математический диктант
Делители и кратные
Многокритериальные задачи. Метод идеальной точки
Урок математики в 4 классе: «Единицы массы. Тонна. Центнер.» Михайлова Н.А. Учитель высшей категории МОАУ СОШ №15 г. Орска, Оре
Итоговое повторение. Математика 5 класс
Учёные - математики Копылова Ольга 6 класс
Расстояние между скрещивающимися прямыми
Инварианты и их применение при решении задач
Последовательности
Курс лекций по подготовке к ЕГЭ по математике
Дифференцируемость функции
Координаты и векторы
Мультимедийные технологии в обучении математике
Изображение фигур в пространстве
Противоположные числа. 6 класс 2 урок
Прямоугольный параллелепипед
מדדי פיזור לשילוב
Учебно-исследовательский проект «Логарифмы в ЕГЭ и не только…» ВЫПОЛНИЛА Николаева Анна УЧЕНИЦА 11А КЛАССА МАОУ СОШ П. ДЕМЯНСК, НОВГОРОДСКАЯ ОБЛ. УЧИТЕЛЬ МАТЕМАТИКИ
Решение задач на применение признаков равенства треугольников
Старинные единицы измерения
Числа от 11 до 20
Упрощение выражений
Тема: Таблица единиц времени. Цель: Систематизировать знания учащихся об единицах времени, развивать умение преобразовывать к
Логарифмическая линия в ЕГЭ - 2011
Игра-тренажер 1 класс. Состав чисел 14 – 18
Математика. Закрепление. Внетабличное умножение и деление
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть