Видеокурс по расширенным алгоритмам от Гарвардского университета.
Часть 2
#fundamental@proglib #algorithms@proglib
Ссылка на первую часть курса:
https://vk.com/proglib?w=wall-54530371_170780
Видеокурс по расширенным алгоритмам от Гарвардского университета.
11. Алгоритм аппроксимации с помощью двойного подбора (обертывания), интервалов интегральности LP, определения PTAS/FPTAS/FPRAS, PTAS для задачи о рюкзаке.
12. FPTAS (рюкзак), FPRAS (подсчет DNF), полуопределенное программирование, алгоритм Goemans-Williamson MAXCUT.
13. Тематическая модель обучения
14. Линейное программирование: стандартная форма, вершины, симплекс.
15. Симплексное обертывание, сильная двойственность, дополнительная слабость, эллипсоид, введение в метод Interior point.
16. Метод path-following interior point, метод первого порядка (градиентный спуск).
17. Метод второго порядка (метод Ньютона), сквозное внутреннее обертывание.
18. Обучение у экспертов, мультипликативные веса.
19. Линейное программирование через мультипликативные веса, потоки, пути расширения.
20. Масштабирование максимального потока, блокировка потока.