Аналіз алгоритмів - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Лекція 2. Аналіз алгоритмів Глибовець А.М.

Слайд 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 За Беббіджем, час роботи вашого алгоритму вимірювався в тому, скільки разів ви маєте прокрутити ручку Аналітичної машини. Що змінилося зараз? Ми отримали електронну ручку, але все одно сильно залежимо від того, скільки разів ми маємо повторити дискретні операції

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

Спостереження Почнемо з спостереження. 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

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

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

Слайд 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

Слайд 16

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

Аналіз даних Намалюємо log-log графік T(N) від N ми отримали лінію з нахилом 3 рівняння такої прямої має вигляд: lg(T(N))=3lgN+lga, де а константа а це еквівалентно T(N) = aNb = aN3 Таким чином ми отримали вираз часу виконання у вигляді функції від об'єму вхідних даних. Можна взяти одну точку наших даних для визначення а Наприклад: T(8000) = 51,1 = a*80003, звідки а=9,98*10-11 Тепер ми можемо використовувати формулу для пророкування часу виконання для великих N

Слайд 17

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

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

Слайд 18

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

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

Слайд 19

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

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

Слайд 20

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

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

Слайд 21

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

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

Слайд 22

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

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

Слайд 23

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

Математична модель Скільки інструкцій буде виконано в залежності від N? int count = 0; for (int i =0; i<N; i++) for (int j =i+1; j<N; j++) if (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

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

Математична модель Скільки операцій доступу до масиву в наступному коді? int count = 0; for (int i =0; i<N; i++) for (int j =i+1; j<N; j++) if (a[i]+ a[j] == 0) count++; Відповідь:

Слайд 28

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

Математична модель Скільки операцій доступу до масиву в наступному коді? int count = 0; for (int i =0; i<N; i++) for (int j =i+1; j<N; j++) for (int k =j+1; k<N; k++) if (a[i]+ a[j] +a[k]== 0) count++; Відповідь: Як ви бачите ми не обраховуємо всі операції, ми беремо найдорожчі.

Слайд 29

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

Математична модель Як оцінити дискретну суму? Замінити суму інтегралом і провести обрахунки. Приклад 1: 1+2+…+N 1+ ½ + 1/3 +… +1/N

Слайд 30

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

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

Слайд 31

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

Класифікація за порядком зростання Гарні новини – існує досить мало функцій, що описують порядок зростання.

Слайд 32

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

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

Слайд 33

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

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

Слайд 34

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

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

Слайд 35

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

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

Слайд 36

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

Бінарний пошук: математичний аналіз T(N) = кількість операцій порівняння в відсортованій підмножині розміру <=N ми ділимо проблему навпіл і можемо реалізувати порівняння з однією операцією …

Слайд 37

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

N2logN алгоритм для 3-суми Алгоритм базований на сортуванні для 3-суми Відсортувати N чисел Для кожної пари чисел a[i] і a[j] ми робимо бінарний пошук елемента –(a[i]+a[j]) Порядок зростання N2logN

Слайд 38

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

Порівняння

Слайд 39

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

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

Слайд 40

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

Аналіз

Слайд 41

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

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

Слайд 42

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

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

Слайд 43

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

Теорія алгоритмів. Приклад 1. Ціль: визначити складність проблеми розробити «оптимальний» алгоритм Приклад: 1-Сума = «Чи є в масиві 0»? Верхня межа: Brute-force алгоритм для 1-Суми: перебрати всі елементи масиву. Час виконання O(N) Нижня межа: Необхідно довести, що немає алгоритму, що робить краще В будь якому разі має перевірити всі N елементів (бо будь-який не перевірений елемент може бути 0) Час виконання Оптимальний алгоритм: Верхня межа = нижній межі Brute-force алгоритм для 1-Суми є оптимальним і його час виконання

Слайд 44

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

Теорія алгоритмів. Приклад 2. Ціль: визначити складність проблеми розробити «оптимальний» алгоритм Приклад: 3-Сума Верхня межа: Brute-force алгоритм для 3-Суми. Час виконання O() Але ми знайшли кращий алгоритм з складністю Нижня межа: В будь якому разі має перевірити всі N елементів Час виконання Відкрита проблема: Необхідно знайти оптимальний алгоритм

Слайд 45

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

Пам’ять Біт: 0 або 1 Байт: 8 біт Мегабайт: байт Гігайбайт: байт Старі машини - 32-бітові машини з 4 байтовими вказівниками Сучасні машини - 64-бітні машини, використовують 8 байтові вказівники. можуть адресувати більше пам’яті вказівники займають більше пам’яті

Слайд 46

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

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

Слайд 47

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

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

Слайд 48

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

Приклад 2 Приклад. Об’єкт String використовує байт пам’яті. public class String{ private char[] value; private int offset; private int count; private int hash; } 2N+64 байт

Слайд 49

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

Приклад. Запитання: Скільки пам’яті займає об’єкт WeightedQuickUnionUF як функція від N (використати нотацію для відповіді) public class WeightedQuickUnionUF { private int[] id; private int[] sz; private int count; public WeightedQuickUnionUF(int n){ count = n; id = new int[n]; sz = new int[n]; for (int i = 0; i<n; i++) id[i]=i; for (int i = 0; i<n; i++) sz[i] = 1; } … }

Слайд 50

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

Приклад. public class WeightedQuickUnionUF { private int[] id; private int[] sz; private int count; public WeightedQuickUnionUF(int n){ count = n; id = new int[n]; sz = new int[n]; for (int i = 0; i<n; i++) id[i]=i; for (int i = 0; i<n; i++) sz[i] = 1; } … } Відповідь: Заголовок 16 байт. id: 8(вказівник) +4N+24 sz: 8+4N+24 count: 4 Можливе доповнення 4 8N+88 8N байтів.