approximate一个人生最优解-tan90
課程：COMP5712
作者：ychencd [14级 COMP|MATH(CS)]
創建於：2017-06-02 22:15:49
更新於：2017-06-02 23:01:22
課程：COMP5712
作者：ychencd [14级 COMP|MATH(CS)]
創建於：2017-06-02 22:15:49
更新於：2017-06-02 23:01:22
課程時間：2017 Spring
授課教授：Sunil Arya
我覺得教授: 人很好教得还行
這門課的Grade：Grade神/較好
【感想】闲的没事来写一发cwiki, 顺便介绍这门课, 之前有某阿姨写过,毕竟大一就上的巨巨, 对于巨巨们来说有一定的参考性0-0....像我这个之后才学算法的人估计这时候有另外一种参考性
【介绍】这大概是PG要修的theory部分的一门核心课，讲的是approximation algorithm。 主要内容包括（让我loading一下）:...
1. (metric) Steiner Tree and Travelling sales man(TSP)
2. Linear Programming and Duality
3. Weighted Vertex Cover: Deterministic Rounding and Primal-Dual Algorithm
4. Algorithms for Set Cover
5. Max Flow, algorithms and liner
6. Algorithms in Bipartite Graphs
7. Steiner Forest
8. Multiway cut problem (哇这一章我是真没学懂那几个算法...复习到最后还是一脸懵逼
9. max cut
10. max-sat, max-2sat, well-characterized problems and vector programming...
大概的内容就是对于一些NP-Hard, NP-Complete的问题找不到exact的polynomial的解的时候，采取了“一般人”很难在一时想出来的“奇技淫巧”去得到approximate的算法，让大家可以在polynomial的时间内得到最优解。
大概的思想呢，大概就是告诉你 有很多的情况下我们是找不到最优解的 但是你要知道我们不要死磕 我们可以换个思路去近似一个最优解（...um...我是这么理解的
我觉得课程本身挺有意思的，对于我这种启蒙渣大概就是好像看上去我是学懂了qwq 对 大概就是这种思想qwq 利用这种技巧qwq 但是一个回头QAQ 他当时是怎么想出来的QAQ 想出来之后为什么这么证明QAQ 这种证明为什么是正确的...我是一脸懵逼的???? 当然 对于知识当然要抱以不求甚解的态度...但是我也是意识到 在一定时间内智力是有局限的...所以弄不懂也没办法 但是我们要产出不是...掌握了这种思想就好了不是( 强行自我安慰一波
【教授授课】
上过3711或者3711h的人应该或多或少上过sunil的课( 我没上过... sunil喜欢板书 然后我就在下面写写抄抄日后复习 当然我也见过大神不计笔记... 各有各的好没有优劣 自己看着办好了 他说的东西我抄完发现 哇 看不懂了 很伤 所以就去看reference【如下各课本】相对应的部分 看了之后发现 sunil是把对应notes的部分自己理解之后表达出来方便大家理解 所以 你如果不是对他的口音感觉有小小迷的话 那就看notes好了... 我midterm之后的每堂课都没听懂过.... 当时感觉是天书... 日后翻reference理解的吧 嗯大概就这样
reference: 1. Luca Trevisan, Lecture Notes, 2011 (stanford cs261 lecture notes
2. Vijay Vazirani, Approximation algorithms, Springer, 2001.
3. David P. Williamson and David B. Shmoys, The design of approximation algorithms, Cambridge University Press, 2011
【grade】
homework 20% (4次)， midterm (35%), final (45%)。
workload看上去其实不是很大,但考虑到我智商有限就很大了
我觉得作业难度挺大的...每次作业我得做好几个小时...做个一两天的样子qwq 虽然网上可能存在答案 但是不自己做的话...你真的不知道每道题到底是怎么一种思想和解法... 虽然做完了我也不知道 每次大概4道题 但只抽2道改 你也不知道要抽哪道 所以都得做（x sunil允许相互讨论 但不允许抄作业（第一次作业就钓鱼了
midterm和final 难度适中吧 因为可能会出一些作业做过的类似的题（这时候你就知道做作业的重要性了 ） 会让你陈述某些学过的theorem 会有一些题的变形之类的 考的迷 因为我也不知道自己做的对不对 就按照思路和approximation的思想瞎写 学着上课做作业的思路瞎写 对于我这种渣渣当然是不会做很多题而且是做不完的QAQ 这里也就不多说了 （final sunil有道题解释错了....延误了很多学生的做题时间...所以大家好好听...那道题我本来就不会做留下最后15分钟瞎写了..gg
midterm和final的mean 大概在65左右 sd大概是15-20左右吧
就像之前几个post说的 因为是PG课本身给grade就还比较好 hw几乎满分(犯了一些微小的错误 midterm 刚到mean final差不多1个sd 拿的grade还行
如果你对algorithm有一点点想法的话 建议你可以上一上这门课感受一下
如果你对好grade有想法的话 上完3711还不错的话可以发一下request 问下sunil给不给你上
如果你像我一样对好grade弃疗无所谓并且想多学一点algorithm的话 你就大胆地上吧 毕竟历史的进程不可预料 万一这门课对你的grade做出了微小的贡献呢
个人主观评价，大家当故事看吧...反正大家都懂cwiki的作用...别信全 就酱
Write a comment
請登錄後再評論
請登錄後再評論
