Презентация Аналіз алгоритмів онлайн

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

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

Содержание слайда: Чарльз Беббідж «Як тільки Аналітична Машина буде створена, вона буде спрямовувати майбутній розвиток науки. Кожний раз коли буде потрібно отримати результат за її допомоги буде ставати питання який напрямок обрахунків, що проводяться машиною приведуть нас якомога швидше до результату» – Чарльз Беббідж 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

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

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

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

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

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

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

Содержание слайда: Спостереження Почнемо з спостереження. 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

Содержание слайда: Вимірювання часу роботи Як виміряти час роботи програми? Вручну.

Содержание слайда: Вимірювання часу роботи Як виміряти час роботи програми? Автоматично. Ми можемо скористатися класом Stopwatch() int[] a = In.readInts(testFile); Stopwatch stopwatch = new Stopwatch(); System.out.println(count(a)); double time = stopwatch.elapsedTime(); System.out.println(time);

Содержание слайда: Емпіричний аналіз Ми можемо запустити програму на різних об’ємах даних і оцінити витрачений час. Давайте спробуємо запустити з більшими об’ємами і подивимося на результат. 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

Содержание слайда: Емпіричний аналіз

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

Содержание слайда: Аналіз даних Намалюємо 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

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

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

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

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

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

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

Содержание слайда: Математична модель Скільки інструкцій буде виконано в залежності від 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)

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

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

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

Содержание слайда: Математична модель Скільки операцій доступу до масиву в наступному коді? 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++; Відповідь:

Содержание слайда: Математична модель Скільки операцій доступу до масиву в наступному коді? 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++; Відповідь: Як ви бачите ми не обраховуємо всі операції, ми беремо найдорожчі.

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

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

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

Содержание слайда: Класифікація за порядком зростання

Содержание слайда: Класифікація за порядком зростання

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

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

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

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

Содержание слайда: Порівняння

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

Содержание слайда: Аналіз

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

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

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

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

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

Содержание слайда: Типові показники використання пам’яті

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

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

Содержание слайда: Приклад. Запитання: Скільки пам’яті займає об’єкт 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; } … }

Содержание слайда: Приклад. 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 байтів.

Содержание слайда: Дякую за увагу.