M1上学期总结

嘛,说是上学期,其实就是上半年在上课,下半年去实习……不过这个学期上的课貌似都比较有趣(废话,你自己选的……),所以说一下~~~

Advanced Complexity:其实就是计算复杂度,学了logspace,alternating machine,一些简单的circuit(真的很浅很浅……),概率的那些class,Arthur-Merlin Hierarchy,最后稍微讲了讲PCP。这些看来都是相当基本的东西,老师讲得也相当有趣,是去年讲lambda calculus的老师。考试碰巧拿了20分……

Category, Lambda Calculus:我选这个课其实是为了体验一下范畴论这个东西,而且将它跟lambda calculus扯在一起貌似还是相当有趣的。问题是,范畴论太难了……我还特地借书看了,还是晕乎,现在掌握的也就是monad啊CCC之类的东西,连Yoneda’s lemma都还没搞懂,范畴论真抽象啊……不过不用考试,做个presentation就行,我做了个关于将2-lambda calculus(就是把rewrite也弄成可以看的term)看成rewrite system然后用范畴论capture的文章的presentation,这个做了18分,还算可以吧,毕竟费了好大的力气把文章搞懂……

Abstract Interpretation:这个课是为了捧我们教导主任的场的,不过我对这种比较应用的课兴趣不太大……这个领域的目的是一个不可能完成的任务:验证某个程序是否符合某个特性。因为不可能完成,所以允许失败,但是为了效果起见不能失败太多。然后因为现在代码动辄数十万行,所以基本上只能允许接近线性时间的算法,东西很受限制。一开始教理论框架是把程序都弄到一个abstract domain(一个lattice)里边,然后在里边分析什么的。然后考试。后边就是让一大堆研究生给我们讲不同的应用啥的,最后做一个presentation。我的是关于一个根据程序推测输出数组的性质的论文的。结果还好,15.7分,是最低的一门。

Algorithmic Aspects of Combinatorics:说是这样说,其实就是个组合课……不过我就喜欢组合!分三部分,第一部分是简单的组合,具体请见Stanley的那本书的第一章。第二部分是random generation,讲了一些比较显然的,还有counting-generation的inter-reduction,然后还有个叫Boltzmann machine的东西。第三部分是algebraic series,就是讲生成函数和language (regular或者algebraic)的。对于搞过竞赛的人来说这些都不难。考试一次期中一次期末,一共19.4。

Advanced Algorithmics and Complexity:这门课跟复杂度丝毫没有关系。分两部分,一部分讲随机算法,我觉得讲得挺不错的;第二部分讲在线算法,各种paging和k-server什么的,那部分比较难理解。考试考了18.4,这个是我把随机算法的部分全做了(估计多半都对了)然后在线算法基本没怎么碰的情况下弄出来的……

Quantum Information and Applications:这门课主要是量子算法,量子信息只是随便碰了一下,讲了讲communication complexity。量子算法主要还是Shor和Grover,然后还加了一个被Grover启发出来(好吧也有Markov链和expander风潮的影响)的量子随机行走算法。不过这些东西貌似都是很新很新的。随便考了一下,18分,另外其实这门课真的不怎么需要学量子物理就能搞懂了……

Optimization:一句话概括就是两个老师讲线性规划。一个讲了一下unimodular矩阵可以做成简单的多项式算法,另一个讲了random rounding,primal-dual。其实这些不容易,但是考试很容易……期中期末各一次,期中只做出来一半,期末提早了半个小时交卷还20分(总长度2小时)……最后弄出来是17.2,一般一般……

Algorithmic and Complexity of CSP:这个分两部分,第一个老师讲了用polymorphism,还有别的,反正就是整个CSP理论界(不是实用界,我去年实习的那个是实用界)的一个宏观描述,比较偏向算法。第二个老师专门讲在Boolean上的CSP的P-NP seperation,用代数(Post’s Lattice)的那套。然后第一部分的考试20分,第二部分只有8分……第二部分杯具了,虽然我也不是完全不懂但是犯了一个非常SB的错误……然而最后算出来是18.2分,那可能是其他同学第二部分也杯具了……嘛,恶补一下还是能明白的……

Use of Randomness in Computer Science:这个课是比较烂的一个课,虽然内容不错……主要是老师讲得很烂,一看就觉得没怎么备课……不过内容的话,基本上把我新买的一本《随机算法》里边的内容讲得七七八八而且还有余了(虽然有些很有趣的没讲,具体忘了)。考试也不难,问题是考出来的分数,有3个20分,有我和法布雷斯,然后还有ENS Ulm M2的某人,接下来是17分,而我算过自己的分数(按照那个表),貌似被cut off了……虽然很多人混分数,但是你们也不至于这样子啊……太不给力了……

其实课不错,但是可能是我选得不太好,有很多内容重叠了,比如说随机算法,Optimization有讲random rounding,然后Advanced Algorithmics and Complexity的第一部分和Use of Randomness in Computer Science整门课都是随机算法,这样其实不太好……不过算是巩固了知识吧……而且这个学期考试分数不合理地偏高,估计是因为在MPRI了学生平均水平下降了然后混日子的人多了,所以造成分数上调的错觉……

好,就汇报这么多,现在实习火热进行中!

Advertisements

2 thoughts on “M1上学期总结

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s