About this Course
5,736

100% 온라인

지금 바로 시작해 나만의 일정에 따라 학습을 진행하세요.

탄력적인 마감일

일정에 따라 마감일을 재설정합니다.

완료하는 데 약 21시간 필요

권장: 4 hours/week...

영어

자막: 영어

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....
8 videos (Total 54 min), 13 readings, 8 quizzes
8개의 동영상
Lecture: Definition4m
Lecture: Integer program6m
Lecture: A linear programming relaxation6m
Lecture: Approximation algorithm6m
Lecture: Analysis6m
Lecture: General facts5m
Half integrality (7:35 bug, fixed in pdf slides)10m
13개의 읽기 자료
Slides10m
All slides for all chapters of Approx Algs part 110m
Attempt to upload slides in Keynote format10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
PDF version of the peer-graded assignment10m
Half-integrality slides10m
All slides together in one file10m
7개 연습문제
Quiz 1: P vs. NP review6m
Quiz 28m
Quiz 34m
Quiz 46m
Quiz 54m
Quiz 64m
Quiz 74m
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....
7 videos (Total 52 min), 9 readings, 8 quizzes
7개의 동영상
Lecture: Greedy algorithm5m
Lecture: Special dynamic program8m
Lecture: General dynamic program8m
Lecture: algorithm6m
Lecture: analysis7m
Lecture: approximation scheme4m
9개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practise Exercises10m
All slides together in one file10m
7개 연습문제
Quiz 12m
Quiz 22m
Quiz 34m
Quiz 42m
Quiz 52m
Quiz 62m
Quiz 72m
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.)...
8 videos (Total 74 min), 10 readings, 8 quizzes
8개의 동영상
Lecture: a linear program12m
Lecture: small items6m
Lecture: large items, few sizes11m
Large items, many sizes8m
Lecture: large items analysis8m
Lecture: general algorithm7m
Lecture: conclusion6m
10개의 읽기 자료
Slides (with typo corrected)10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
All slides together in one file10m
7개 연습문제
Quiz 14m
Quiz 26m
Quiz 32m
Quiz 46m
Quiz 54m
Quiz 66m
Quiz 76m
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....
8 videos (Total 58 min), 11 readings, 9 quizzes
8개의 동영상
Lecture: randomized rounding4m
Lecture: cost analysis5m
Lecture: coverage analysis8m
Lecture: iterated algorithm4m
Lecture: stopping time algorithm4m
Lecture: stopping time analysis10m
Lecture:final remarks6m
11개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
A reference on this stopping time analysis10m
Practise Exercise10m
All slides together in one file10m
8개 연습문제
Quiz 12m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 84m
5
완료하는 데 5시간 필요

Multiway Cut and Randomized Rounding

This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)...
5 videos (Total 71 min), 8 readings, 6 quizzes
5개의 동영상
Lecture: linear programming relaxation20m
Lecture: randomized rounding14m
Lecture: analysis14m
Lecture: conclusion6m
8개의 읽기 자료
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice exercise10m
All Chapter Slides together in one file10m
Slides for all chapters of Approx Algs Part 1 together in one file10m
5개 연습문제
Quiz 1 : Some context on cuts4m
Quiz 26m
Quiz 34m
Quiz 44m
Quiz 54m
4.7
34개의 리뷰Chevron Right

최상위 리뷰

대학: DAJan 27th 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

대학: ZWSep 17th 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

에콜노르말쉬페리외르 정보

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

자주 묻는 질문

  • 강좌에 등록하면 바로 모든 비디오, 테스트 및 프로그래밍 과제(해당하는 경우)에 접근할 수 있습니다. 상호 첨삭 과제는 이 세션이 시작된 경우에만 제출하고 검토할 수 있습니다. 강좌를 구매하지 않고 살펴보기만 하면 특정 과제에 접근하지 못할 수 있습니다.

궁금한 점이 더 있으신가요? 학습자 도움말 센터를 방문해 보세요.