Об этом курсе
4.8
Оценки: 41
Рецензии: 9
100% онлайн

100% онлайн

Начните сейчас и учитесь по собственному графику.
Гибкие сроки

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.
Часов на завершение

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 8 hours/week...
Доступные языки

Английский

Субтитры: Английский
100% онлайн

100% онлайн

Начните сейчас и учитесь по собственному графику.
Гибкие сроки

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.
Часов на завершение

Прибл. 12 часа на выполнение

Предполагаемая нагрузка: 8 hours/week...
Доступные языки

Английский

Субтитры: Английский

Программа курса: что вы изучите

Неделя
1
Часов на завершение
6 ч. на завершение

Linear Programming Duality

This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality....
Reading
9 видео ((всего 87 мин.)), 11 материалов для самостоятельного изучения, 9 тестов
Video9 видео
Properties of LP duality6мин
Geometry of LP duality10мин
Proof of weak duality theorem6мин
Changing the form of the LP10мин
Complementary slackness5мин
Primal-dual algorithms5мин
Vertex cover by primal-dual23мин
Conclusion3мин
Reading11 материала для самостоятельного изучения
Slides10мин
Comment10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
Quiz8 практического упражнения
Quiz 16мин
Quiz 22мин
Quiz 32мин
Quiz 44мин
Quiz 54мин
Quiz 64мин
Quiz 72мин
Quiz 84мин
Неделя
2
Часов на завершение
5 ч. на завершение

Steiner Forest and Primal-Dual Approximation Algorithms

This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem....
Reading
8 видео ((всего 73 мин.)), 9 материалов для самостоятельного изучения, 9 тестов
Video8 видео
A special case: Steiner tree12мин
LP relaxation for Steiner forest6мин
... and its dual4мин
Primal-dual algorithm, Part110мин
Primal-dual algorithm,Part 212мин
Analysis13мин
Proof of the main lemma9мин
Reading9 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
Quiz8 практического упражнения
Quiz 16мин
Quiz 24мин
Quiz 34мин
Quiz 44мин
Quiz 54мин
Quiz 66мин
Quiz 74мин
Quiz 86мин
Неделя
3
Часов на завершение
5 ч. на завершение

Facility Location and Primal-Dual Approximation Algorithms

This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem....
Reading
9 видео ((всего 64 мин.)), 10 материалов для самостоятельного изучения, 9 тестов
Video9 видео
A linear programming relaxation4мин
...and its dual8мин
A primal-dual algorithm7мин
Analyzing the service cost7мин
Analyzing the facility opening cost7мин
A better algorithm11мин
Analysis7мин
Conclusion4мин
Reading10 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides-all10мин
Quiz8 практического упражнения
Quiz 12мин
Quiz 24мин
Quiz 34мин
Quiz 44мин
Quiz 52мин
Quiz 62мин
Quiz 72мин
Quiz 86мин
Неделя
4
Часов на завершение
6 ч. на завершение

Maximum Cut and Semi-Definite Programming

We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem....
Reading
11 видео ((всего 76 мин.)), 12 материалов для самостоятельного изучения, 10 тестов
Video11 видео
Definition5мин
A 2-approximation5мин
A linear programming relaxation...11мин
...with an integrality gap of almost 210мин
Proof of Lemma7мин
A quadratic programming relaxation4мин
General facts about semidefinite programming7мин
A rounding algorithm7мин
Analysis6мин
General facts about MaxCut6мин
The end!3мин
Reading12 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Sldies10мин
Slides10мин
Slides-all10мин
Comment10мин
Quiz9 практического упражнения
Quiz 14мин
Quiz 24мин
Quiz 32мин
Quiz 42мин
Quiz 54мин
Quiz 62мин
Quiz 72мин
Quiz 82мин
Quiz 92мин

Преподаватель

О École normale supérieure

L’École normale supérieure (ENS) est un établissement d'enseignement supérieur pour les études prédoctorales et doctorales (graduate school) et un haut lieu de la recherche française. L'ENS offre à 300 nouveaux étudiants et 200 doctorants chaque année une formation de haut niveau, largement pluridisciplinaire, des humanités et sciences sociales aux sciences dures. Régulièrement distinguée au niveau international, l'ENS a formé 10 médailles Fields et 13 prix Nobel....

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

Остались вопросы? Посетите Центр поддержки учащихся.