Об этом курсе
4.7
Оценки: 121
Рецензии: 34
100% онлайн

100% онлайн

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

Гибкие сроки

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

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

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

Английский

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

100% онлайн

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

Гибкие сроки

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

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

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

Английский

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

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

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

Vertex cover and Linear Programming

We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques....
Reading
8 videos (Total 54 min), 13 материалов для самостоятельного изучения, 8 тестов
Video8 видео
Lecture: Definition4мин
Lecture: Integer program6мин
Lecture: A linear programming relaxation6мин
Lecture: Approximation algorithm6мин
Lecture: Analysis6мин
Lecture: General facts5мин
Half integrality (7:35 bug, fixed in pdf slides)10мин
Reading13 материала для самостоятельного изучения
Slides10мин
All slides for all chapters of Approx Algs part 110мин
Attempt to upload slides in Keynote format10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Practice Exercises10мин
PDF version of the peer-graded assignment10мин
Half-integrality slides10мин
All slides together in one file10мин
Quiz7 практического упражнения
Quiz 1: P vs. NP review6мин
Quiz 28мин
Quiz 34мин
Quiz 46мин
Quiz 54мин
Quiz 64мин
Quiz 74мин
Неделя
2
Часов на завершение
5 ч. на завершение

Knapsack and Rounding

This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem....
Reading
7 videos (Total 52 min), 9 материалов для самостоятельного изучения, 8 тестов
Video7 видео
Lecture: Greedy algorithm5мин
Lecture: Special dynamic program8мин
Lecture: General dynamic program8мин
Lecture: algorithm6мин
Lecture: analysis7мин
Lecture: approximation scheme4мин
Reading9 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Practise Exercises10мин
All slides together in one file10мин
Quiz7 практического упражнения
Quiz 12мин
Quiz 22мин
Quiz 34мин
Quiz 42мин
Quiz 52мин
Quiz 62мин
Quiz 72мин
Неделя
3
Часов на завершение
5 ч. на завершение

Bin Packing, Linear Programming and Rounding

This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)...
Reading
8 videos (Total 74 min), 10 материалов для самостоятельного изучения, 8 тестов
Video8 видео
Lecture: a linear program12мин
Lecture: small items6мин
Lecture: large items, few sizes11мин
Large items, many sizes8мин
Lecture: large items analysis8мин
Lecture: general algorithm7мин
Lecture: conclusion6мин
Reading10 материала для самостоятельного изучения
Slides (with typo corrected)10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Practice Exercises10мин
All slides together in one file10мин
Quiz7 практического упражнения
Quiz 14мин
Quiz 26мин
Quiz 32мин
Quiz 46мин
Quiz 54мин
Quiz 66мин
Quiz 76мин
Неделя
4
Часов на завершение
5 ч. на завершение

Set Cover and Randomized Rounding

This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem....
Reading
8 videos (Total 58 min), 11 материалов для самостоятельного изучения, 9 тестов
Video8 видео
Lecture: randomized rounding4мин
Lecture: cost analysis5мин
Lecture: coverage analysis8мин
Lecture: iterated algorithm4мин
Lecture: stopping time algorithm4мин
Lecture: stopping time analysis10мин
Lecture:final remarks6мин
Reading11 материала для самостоятельного изучения
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
Slides10мин
A reference on this stopping time analysis10мин
Practise Exercise10мин
All slides together in one file10мин
Quiz8 практического упражнения
Quiz 12мин
Quiz 22мин
Quiz 32мин
Quiz 44мин
Quiz 52мин
Quiz 62мин
Quiz 72мин
Quiz 84мин

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

О É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....

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

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

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