Prometheus. Масовий онлайн курс "Основи програмування". Лекція 8
Download as PPT, PDF1 like19,735 views
1. Проблема вибору алгориму 2. Асимптотична складність алгоритму 3. Класи складності 4. Деякі підходи до розв'язку задач: 4.1. Перебір та його оптимізація 4.2. Перебір із поверненням 4.3. Евристичні розв'язки Повний курс доступний на першому українському проекті масових відкритих онлайн курсів Prometheus: http://edx.prometheus.org.ua/courses/KPI/Programming101/2015_T1/about
More Related Content
What's hot (19)
Similar to Prometheus. Масовий онлайн курс "Основи програмування". Лекція 8 (9)
Recently uploaded (20)
Prometheus. Масовий онлайн курс "Основи програмування". Лекція 8
- 1. Хороший, поганий, повільний Види алгоритмів. Поняття складності алгоритму Основи програмування мовою Python, лекція 8 Київ, 2015
- 2. Будь-яка задача має як мінімум 2 розв'язки x = a a = b b = x a = a+b b = a-b a = a-b простіше швидше менше зміннихбільше змінних повільніше
- 3. Простибоженко Солоха Ореївна 14 350 12312312312312 1965 Квітка Ганна Казимирівна 7 500 23423423423423 1978 Всі прізвища є вигаданими, будь-яке співпадіння з реальними особами є випадковим :-) Лютий Краснояр Даромирович 8 900 34343434343434 1985 Мамай Милорада Любомирівна 8 600 53454756342109 1982 Безіменко Любомир Добромудрович 6 800 78328943905402 1976 Розбийніс Златозар Радиборович 8 600 74836732902100 1970 Яховайко Дарислава Гудимирівна 10 200 11567567567211 1971
- 4. Варіант №1 1 1 1 1 x Nx M 1 ~ 4*N*M + M операцій
- 5. Варіант №2 ~ 4*N*log2N M ~ 4*N*log2N + M операцій
- 6. 4*N*M + M 4*N*log2N + M 4*N*M + M 4*N*log2N + M 4*N*M 4*N*log2N M log2N при M=6 ~ однакова кількість операцій при M>6 2й варіант ефективніший при M<6 1й варіант ефективніший нехай N=64, тоді:
- 7. M так як робиться 1 раз, швидкість несуттєва 1 <N 1 Варіант №3
- 8. Обчислювальна складність — поняття теорії алгоритмів, що позначає функцію залежності обсягу роботи алгоритму від об'єму вхідних даних f(n), де n – об'єм вхідних даних
- 9. 3 прочитати дані поточного об'єкту прочитати дані "найкращого" об'єкту порівняти 1 0 або M в середньому М/2 порівнянь, для кожного необхідно ще прочитати поле, тобто 2*М/2 (якщо 1-ша умова хибна, сюди не потрапимо) ~4 0 або 1 (якщо умови хибні, сюди не потрапимо) N повторів f(n) = (4 + M)*N + 5 графік y = (4+M)*N+5
- 10. 3 прочитати дані поточного об'єкту прочитати дані "найкращого" об'єкту порівняти 1 0 або M в середньому М/2 порівнянь, для кожного необхідно ще прочитати поле, тобто 2*М/2 (якщо 1-ша умова хибна, сюди не потрапимо) ~4 0 або 1 (якщо умови хибні, сюди не потрапимо) N повторів f(n) = (4 + M)*N + 5f(n) = 3*N + 5 + M графік y = 3*N+5+M
- 11. y = f(n) = (4+M)*N+5 значить: функція, що залежить від n f(n) O(n)ϵ Асимптотична складність – поняття, що позначає рівень зростання обсягу роботи алгоритму з ростом об'єму вхідних даних – лінійна
- 12. значить: функція, що залежить від n y = f(n) = 5 f(n) O(k)ϵ – константна
- 13. f(n) O(log n)ϵ – логарифмічна y = f(n) = log N
- 14. Бінарний пошук 20 21 23 30 38 44 55 64 66 77 79 82 90 97 55<64 знайти 64: < < < < < < < < < < < < < 64 66 77 79 82 90 97 79>64 64 66 77 66>64 64SUCCESS!!! f(n) = log2n
- 15. бінарний пошук на python генерація випадкової відсортованої послідовності сам пошук
- 16. y = f(n) = n 2 y=f(n)=n3 y=f(n)=n4 поліноміальні: f(n) O(nϵ 2 ) f(n) ϵ O(n3 ) f(n) ϵ O(n4 ) ... 2x4 + 5x3 + 3x2 + 4x
- 17. бульбашкове сортування (bubble sort) найпростіший код, але найменш ефективне для сортування послідовності вимагає порядку n2 операцій
- 18. "швидке" сортування (quicksort) для сортування послідовності вимагає порядку n*log2n операцій реалізоване як вбудована функція в більшості мов програмування
- 19. y=f(n)=2n y=f(n)=3n y=f(n)=4n експоненціальні: f(n) O(2ϵ n ) f(n) ϵ O(3n ) f(n) ϵ O(4n ) ...
- 20. Підбор паролю abcdefghijklmnopqrstuvwxyz 26n комбінацій ?????? (n=6) 266 = 308 915 776 = 308 916 секунд = 5 148.6 хвилин = 85.8 годин = 3.6 днів 2610 = 141 167 095 653 376 = 141 167 095 653 секунд = 2 352 784 927.5 хвилин = 39 213 082 годин = 1 633 878 днів = 4 000 років ?????????? (n=10)
- 21. Підбор паролю abcdefghijklmnopqrstuvwxyz 26n комбінацій ?????? (n=6) 266 = 308 915 776 = 308 916 секунд = 5 148.6 хвилин = 85.8 годин = 3.6 днів 2610 = 141 167 095 653 376 = 141 167 095 653 секунд = 2 352 784 927.5 хвилин = 39 213 082 годин = 1 633 878 днів = 4 000 років ?????????? (n=10) • перебір з використанням словників • імітація форми входу • використання особистих даних для відновлення паролю та ін.
- 22. Задача про 8 ферзів 8х8 = 64 поля 4 426 165 368 комбінацій розстановки ферзів
- 23. Не намагайтеся повторити це вдома Як мінімум, з перебору слід виключити зовсім безглузді варіанти див. example8_1.py
- 24. Перша оптимізація оскільки кожний ферзь "пробиває" до кінця вертикалі та горизонталі, їх можна одразу розподілити по 1 на лінії і перебирати лише 1 координату див. example8_3.py
- 25. Перебір з поверненням (backtracking) якщо на будь-якому етапі перебору хоч 1 фігура займає погану позицію, всі наступні варіанти, які її включають, також будуть завідомо погані тому ефективніше повернутися на крок назад і переставити цю фігуру, одразу відкинувши ціле сімейство поганих варіантів див. example8_4.py
- 26. Ще одна оптимізація початкову позицію перших 4 фігур взагалі легко розрахувати вручну (0, 1) або (0, 0) (1, 3) (1, 2) (2, 5) (2, 4) (3, 7) (3, 6) див. example8_5.py
- 27. Евристичний алгоритм (евристика) — це алгоритм розв'язку задачі, який не має точного обґрунтування, але в більшості практичних випадків забезпечує прийнятну відповідь (за якістю та часом роботи).
- 28. Евристичний розв'язок 2 2 2 2 1 2 1 1 обрати фігуру, яка "погано" стоїть, знайти для неї найменш потенційно небезпечне поле та переставити повторювати, поки не знайдено розв'язок див. example8_6.py
- 29. • чи є задача типовою? • чи існує для неї точний відомий розв'язок? • чи можна виявити закономірності і побудувати еврістичний алгоритм? • спробуйте розв'язати задачу вручну • невже її можна розв'язати лише перебором? • точно??? • ну хоча б перебором із поверненням • а розуміння, вироблене під час розв'язку вручну, допоможе зменшити кількість варіантів
- 30. • f(n) O(k)ϵ — константна складність • f(n) O(n)ϵ — лінійна складність • f(n) O(nϵ k ) — поліноміальна складність • f(n) O(nϵ 2 ) — квадратична складність (частковий випадок) • f(n) O(kϵ n ) — лінійна складність • f(n) O(logϵ kn) — логарифмічна складність Складність алгоритму можна приблизно оцінити за кількістю циклів Для вибору алгоритму порівнюють вищу межу або середню складність
- 31. Дякую за увагу! Над випуском працювали: • Павлюченко Нікіта Сергійович • Панібрат Марія Олексіївна НТУУ "КПІ", 2015