MPRI M2上学期总结

嗯,又到了一年一度的总结的时候了,自从分数都出来之后。还是按照惯例,稍微讲一下今年上了些啥课。

Randomness in complexity:主要分三个部分,分别是一些随机的complexity classes、Probabilistic Checkable Proof和纠错码在计算复杂度中的应用。第一部分相当容易,因为以前在Advanced Complexity的课上已经学过了;PCP学过一点,这次讲得深入一点,而且用expander了,但是因为非常复杂,所以其实技术细节不是非常明白;纠错码那个因为后边可能时间不够,讲得非常简略。不过整体感觉还是挺好的,老师是去年Quantum Computing的人马加上一位新的。因为复杂度之类的以前讲过,所以理解得还可以,18.6。

Arithmetic Algorithms for Cryptology:这个就是讲了一些用于密码学的数论算法,最大头还是质因数分解,不过后面也讲了很多椭圆曲线和有关的各种奇怪protocol。个人感觉还是很有收获的,但是要有老师讲课讲得非常粗略的心理准备,而且后面椭圆曲线的部分还是不太容易的。因为数论也算是学过一点,以前也上过这帮老师的课了解过一点,所以还好,16.8。

Polynomial systems, computer algebra and applications:这个课简单来说就是介绍了怎么用计算机解多元高次方程组,也就是求一个多项式理想的Grobner基,然后还有这种方法的应用。我倒是大体听明白了算法怎么运作的,而且他们的应用其实就是将各种密码系统用多项式表达出来,然后通过解一个方程组来破解这个密码,也就是说代数密码分析,这个也不是太难明白,虽然我不是非常感兴趣。问题是,考试跟这两个东西都没有太大的关系啊……期中考完全是理想的性质,然后期末是读论文做题,那个题不读论文也能做出来……课上得也不是非常有趣……最后是17.9。

Error-correcting code and applications in cryptology:我一直都想上一门编码理论的课,于是就选了这门课,之前的那门课其实是这门课的陪衬……但是这门课也讲得不是非常深入,而且也没有涉及组合设计,光讲code-based cryptology了……不过讲得非常清楚,基本上都很明白。原来给code人为加个噪音也可以达到公钥加密的效果,这点是学到了。考试也不难,所以harmonisation之后分不高,16.6。

Analysis of algorithms:这门课很好很强大,本来是Flajolet教的,但是去年停了所以我没上,据说那时候Flajolet身体就不太好了,后来的事情大家也就都知道了……所以要保重身体……这门课其实说白了就是Analytic combinatorics的伪装版,整门课可以浓缩为一句话:通过生成函数的解析性质,尤其是极点的位置和性质,能直接获得数列的渐近性质。在这个原则下,课上介绍了很多工具,老师们也讲得非常清楚。因为之前学了不少组合,所以上起来非常轻松,考试也不错,19.5。

Modelisation by finite automata:这个课相当高级,四个老师讲的四种关于有限自动机的进阶理论,有multiplicity automata,rational relations,automata group和B-automata,一个比一个难懂,而且都是一般的有限自动机的某种意义上的推广,非常复杂。不过感觉讲得还好,虽然也没有完完全全明白所有内容……结果运气好,最后拿了19.7。

Game theorectic techniques in computer science:本来我是很期待他们讲组合博弈的,结果没讲……先讲了Buchi game, parity game之类的,然后纳什均衡(这个我懂),然后有概率的博弈,然后game in extensive form,然后讲了一点点protocol design。内容还好,但是课讲得不行,到后边云里雾里的……我期中看错题各种杯具,期末好一点,结果18.7。

Mathematical fundations of automata theory:上这个课的人貌似是大牛,还正在写一本关于这个的书,顺便就给我们做讲义了。一言以蔽之,就是用代数(还有一点点拓扑)的方法来研究有限自动机。这东西到后面的演化非常奇怪,比如说在某个拓扑空间下既开且闭的子集的某种意义上的投影恰好是所有正则语言,还有关于方程(嗯,当然是在monoide上的)的一些很奇怪的东西。到后面我也有点晕了,其实考试发挥得不是非常好,后面有很多东西其实都不太会,不过harmonisation之后分数还好,17.1,可能是因为大家都不是很会的原因……

Efficient algorithms in computer algebra:简而言之就是maple内部是怎么运作的。算法这方面我还是比较拿手的,这门课教的算法也非常数学化,所以感觉不错,基本上都理解了。实际上那些奇怪的特殊函数是用它们满足的微分方程来表达的,而且是用算符的形式,也就是说annihilator,然后各种计算就变成了一个非交换代数上的Grobner基的计算了,这东西非常漂亮。因为学起来非常顺,所以考试不错,20。

Graph algorithms:这个是本学期最坑爹的课,没有之一。课的前半部分是坑爹的主体,讲的主要是各种奇怪的graph decomposition,这个主题其实很有趣,信息量非常大,但是讲得非常简略,根本不明白老师在讲的是啥……后半部分是良心,讲的是matroid,然后非常标准的展开方式,因为课时短所以其实也没讲多深入。两种风格直接反映在了考试上,期中所有人基本都杯具了,期末所有人基本都不错……这种奇怪的结果综合起来harmonisation之后,给出的也是同样奇怪的结果:17.8。

Constraint programming:这是我学得最差的课,主要是被它的标题骗了。原本以为是讲约束编程的各种技巧方法之类的,结果实际上一大部分都是在讲逻辑编程,真正约束编程的篇幅就只有一节课……然后逻辑编程我各种不熟,虽然prolog不难学,但是后面什么Concurrent constraint language啊还有它的Linear logic变种啊就一个头两个大了……我的形式逻辑看来还是不怎么样啊……考试的时候也是各种杯具,虽然有个project挺有趣,就是那个non-transitive dice,但是这也弥补不了什么,结果是14.5。

这个学期选的课有点多,因为这大概是能正经上课的最后一个学期了,而这场考试如无意外也是正经考的最后一场了。以后就要更侧重于做研究而不是学东西了,所以这个学期就打算多学点,作为以后的储备。现在从效果看来的话还是可以的,虽然有些课还是模模糊糊……顺带一提,法布雷斯依然强劲,和我一起上的课分数也是差不多,果然Math进来的人就是厉害啊~~~

好了,现在实习火热进行中,是组合方面的,现在天天就跟Young’s tableau各种脑内搏斗中,而且这东西还不一定能搞出什么有用的结果,所以现在心理上有点压力……不过还是加油吧~~~

Advertisements

One thought on “MPRI M2上学期总结

  1. 居然看到了这个课程总结……国内本科准备去MPRI的飘过……感觉好多基础知识都没有学过啊T.T
    看了觉得好多课都不敢选了……以及楼主分数好高orz

发表评论

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