Лекція 11. Властивості відрізків. Опукла комбінація. Векторний добуток. Обмежуючий прямокутник. Обчислення опуклої оболонки. Задача комівояжера. Задача про рюкзак. Задача про призначення
Дізнаємось
Які властивості мають відрізки та як визначити їх перетин.
Що таке опукла комбінація точок і чому це важливо для геометричних алгоритмів.
Як обчислюється векторний добуток і як він використовується для визначення напрямку повороту.
Як побудувати обмежуючий прямокутник множини точок.
Як працює алгоритм побудови опуклої оболонки (метод Грехема, Джарвіса тощо).
Які є постановки задач комівояжера та рюкзака, і які алгоритмічні методи їх розв’язують.
Навчимось
Використовувати векторні обчислення для аналізу геометричних задач.
Використовувати векторний добуток для визначення орієнтації точок.
Розуміти зв’язок між геометричними задачами та задачами комбінаторної оптимізації.
Реалізовувати базові алгоритми для задач комівояжера та рюкзака.
Матеріали
Доступно тільки для зареєстрованих користувачів
Проблемні питання
Доступно тільки для зареєстрованих користувачів
Д.з.
Доступно тільки для зареєстрованих користувачів
| № | Тема |
|---|---|
| 3 лекції | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 |
Лекція 11. Властивості відрізків. Опукла комбінація. Векторний добуток. Обмежуючий прямокутник. Обчислення опуклої оболонки. Задача комівояжера. Задача про рюкзак. Задача про призначення
|
| 12 | |
| 13 | |
| 14 | |
| 15 | |
| 16 | |
| 3 практичні заняття | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | |
| 14 | |
| 15 | |
| 16 | |
| 17 |