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各种脑内搏斗中,而且这东西还不一定能搞出什么有用的结果,所以现在心理上有点压力……不过还是加油吧~~~

MSRA实习简记

话说我们ENS的DI有一个很特别的制度:M1的学生要在学校上半年课,然后到外边随便什么实验室实习大概半年,这才能拿到足够的学分。半年的课上得半死也最多只有30分,实习则又占了30分。而且对于法国学生还有个规定就是必须不在法国实习,当然了这个对我没啥影响。但是当教导主任问我们想去什么地方实习的时候,我还是说不在法国就在中国,因为实在不想办签证。所以各种机缘巧合之下,我就去了北京的MSRA做实习。

于是,十几小时的飞机之后,回到了广东,稍微收拾了一下行李,就又出发到北京了。

我不是第一次到北京,小的时候去过一次,前几年又去了一次,不过都是旅游的形式,只逗留了几天。这次在北京生活了5个月,我深深地感受到,北京真的不是一个适合像我这样的普通人生活的地方。它的空气极其浑浊,平均的能见度低到了可怕的地步,晚上的街灯可以验证丁达尔效应。物价达到了一个相当高的水平,难以想象我能找到的最便宜的饭菜价格也需要大约15块一顿,相比收入来说,这也算是相当高了。一下雨就有海景这个就不说了,本来这个城市也没多少雨。不能登录各种东西这个是早就预料到了。

但是,除开这些由于城市本身带来的麻烦问题的话,我这几个月的实习还是挺惬意的。很多东西MSRA那边都包了,减轻了不少经济上的负担,这对于一个穷学生来说还是相当重要的。也因为很多东西都是那边包了,有些比如说宿舍的网速问题我想就不能要求太高了。

关于在MSRA实习的情况,因为我实在不知道什么能说什么不能说,所以我只挑那些从MSRA外部也能知道的东西说。

MSRA的工作环境还是不错的,免费饮料什么的,工作时间也比较自由,然后研究员和实习生都挺厉害,气氛还是挺不错的。但是这个实习最厉害的还是各种合约合同,我签之前都细细看过好多遍,确认什么能做什么不能做,以免MSRA到时找我麻烦。我刚去的时候还是在希格玛大厦(一个莫名其妙的名字),后来才搬到微软的新楼。教授什么的人很好,我一开始本来是打算跟其中一位研究员做比较理论化的研究的,但是去了才发现水太深,五个月做不了,所以就跟另一位研究员做一点比较简单的东西。

然后本来我想讲讲实习做了什么,但是我不知道那属不属于那二十二条军规式的东西的管辖范围内,所以我只能大概说说,是有关社交网络的,我做的基本上就是图论和概率的研究,然后更多的我就不知道能不能说了,等我做完报告然后确认没人找我麻烦之后再说吧,要不就直接把摘要贴出来。大家也知道,我平时也有研究一些奇怪的东西,优美树之类的,但是因为合同之类的限制,如果我在工作时间做这个的话,可能会导致我非常不喜欢的结果,所以一直就只在空余时间做。

然后说一下MSRA的饭堂。这个饭堂的菜式是挺多的,基本上啥都有,不过有一个问题就是,很多菜都很喜欢无谓地放巨多的辣椒,这是北方饭馆的一个我非常讨厌的特点。除了这个以外,其实饭菜还是挺好的,不过我反正就是随便吃吃,所以也无所谓。

然后我难得到北京那么长时间,松鼠会那边的活动也参加了不少,去了一趟天津,算是意外收获。然后另外也参加了一个关于BOINC的活动,看见了David Anderson,还有分布式计算论坛的一帮人,还是挺不错的。

大概就是这样了,我发现真的我要是不学术的话没啥可以说的……

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了学生平均水平下降了然后混日子的人多了,所以造成分数上调的错觉……

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

迁移到WordPress

没想到啊没想到,早上刚看到微软撑不住Live Space的消息,中午登录Live Space的时候就已经有提示要迁移到WordPress了……

然后花了大概半个小时注册、迁移文章和评论,有个工具很好用,大家搜索“wordpress live space 导入”就好了,是个python脚本~~~

不过迁移到WordPress之后,有一个很大的问题就是以后墙内的人很可能不能看了……可能又要去弄个墙内的博客更新啥的,还要再想想办法……

新地址是https://fwjmath.wordpress.com/,大家用RSS订阅的话,可以改为订阅那边的RSS了~~~以后这边就不更新了~~~

实习小记

这个暑假基本上都花在我们DI的L3必修实习上了,只回家了两个星期多一点的时间,不过这个实习还是比较有趣而且有用的~~~

我是去南特做的实习,是关于SAT和WalkSAT的。SAT就是那个著名的NPC的可满足性问题,而WalkSAT是一个专门解SAT的Solver,用的是局部搜索的方法。我之前用过不少局部搜索的东西(比如说做优美树的时候),所以还是对这个题目比较感兴趣的。这次实习主要就是研究WalkSAT的各种参数对程序的性能有什么影响,这个也是局部搜索的老问题了,总是会遇到local minima出不来,所以就要各种各样的机制来逃出去,这样少不免就要牵涉到很多很多的参数之类的东西,而且这些参数对性能的影响非常大,每次写局部搜索的时候不仅要选取适当的heuristique,还要慢慢给参数调优,其实是相当麻烦的。我选这个实习也就是为了学学别人是怎么样解决参数调优的这个问题的,虽然不能直接应用,但是稍微借鉴一下经验估计也是没问题的~~~

这个实习的encardant有两个,一个女的一个男的。女encardant(以下简称CT)是在南特的,见得比较多,也基本上是她指导各种东西的;男的encardrant(以下简称FS)是在昂热的,所以见得比较少,对我这个实习的指导工作也比较少而且抽象。他们人都很好,很热情,在实习中也给了我很多很有用的建议和意见。

我是6月1号就去南特的。一开始情况相当困难,中午到的时候,住的地方没有人办公,都出去吃饭了,我却拉着一大堆行李没饭吃。然后等啊等,终于有人办公了,但是又遇上各种问题,于是就只能先去找CT报到,看看能不能说有些手续可以帮忙搞一下。然后经过各种非常复杂的手续之后,终于住进了CiteU。大学里边实习生的手续倒是很简单,或者说就是已经搞定了,拿了个badge就好了。实习工资不多,但是房租学校给,所以其实也还好,然后房间相当大,比ENS的大多了。

CT有一个博士生,叫Marie,也是女的,也是很好人,经常拉我去参加各种实验室的人一起去玩的活动,虽然显然我不一定很有兴趣,然后在实习里边也帮了不少各种事情,比如说revise报告之类的。

这个实习中我做的事情其实主要就是找WalkSAT的最好的参数组合。显然这些参数组合也是因实例而不同的,比如说随机的实例跟来自planning问题的实例,本来性质就不同,然后最优的参数组合也是不同的,我做的其实就是弄个算法,找到对不同的实例的最好的参数组合。基本上这些算法都需要解决实例,但是对比较小的实例得到的参数组合对比较大的实例也是有参考意义的,所以其实这样做还是reasonable的。

然后为了测量性能,我们就需要弄一个benchmark,但是因为有这么多种性质不同的实例,针对不同种类的实例,最优的参数组合也不同,所以如果要很好衡量一个参数组合的话,最好还是抽取一些有代表性的实例,然后用这些实例做benchmark。我的另一个工作就是想办法弄一个方法来将一堆实例好好分类,然后选出一些有代表性的实例。CT给的方法是选取一些statistic characteristic,然后算出来之后做一个k-means clustering,根据结果来分类然后选取有代表性的实例。

于是我就写了一个很简单的程序来算statistic characteristic,虽然很简单但是为了优化还是花了不少的功夫的。现在那东西就躺在我在ENS的网站上,其实估计也没啥用。这个东西的另一个功能就是自动做clustering,其实就是把别人某个开源的implementation稍稍改了一下然后而已,不是很复杂。

然后用这个工具我分析了SAT Competition 2007的所有实例,结果很悲剧,clustering做出来的结果跟实例的性质关系不是很大,所以那个有代表性的benchmark就浮云了。于是接下来找参数组合就只能随便做了。

找参数组合的算法,FS提议说用一个叫Revac的东西,但是那玩意儿要用matlab,然后我完全不懂……所以我就看了原始的论文,自己写了一个简化版本,基本上也是很简单的,几百行的样子。运行还是可以的,但是就是慢。

然后看着这个实习的主要内容做得差不多了,CT就给了我一篇Sermerjian和Monasson的文章,是用统计物理的方法来研究random SAT实例的。然后CT就让我去验证一下这个paper的一些结论。然后我做了一些,然后其实也有一两个发现。基本上做完这个就做完实习了。

然后就是写报告和弄presentation。报告花了我两个星期的时间。那个时间学校放假,然后我就躲在寝室里边有心情就写两段,断断续续的竟然也在两个星期内写完了。最后各种更改(我的法语还是一如既往地很多bug……)之后最终是36页。那个时间真是非常累啊……

其实南特风景很好,但是我因为实习很忙,其实基本上就没啥时间出去透气,当然我很宅这也是一个非常重要的因素。平时做饭因为只有一个人做,所以做的东西也很简单,天天不是煮意粉就是煮面,大部分时间外加煎猪排或者碎肉牛排,蔬菜大部分时间都是番茄,因为做起来容易。有时候也会去买点好吃的,不过不多,而且集中在实习最后很有空的时间。在实习的时间里边也没有做很多比较有建设性的东西,一方面是因为忙,另一方面是因为在松鼠会的工作遇到了一些很令人沮丧和状况。唯一有点创造性的东西就是那个水滴游戏的解程序,而且直到现在因为情况没怎么改变,所以暂时也没什么热情去写文章。

那个优美树的东西,我也去问了CT,从Constraint Programming的角度CT也给了不少的建议,虽然我觉得都是比较靠近于通用问题的思路,对于这种特殊性比较强的问题这种方法可能不是太好,不过还是可以考虑一下的。

然后前几天刚刚弄完presentation。本来我一开始做presentation的时候不知道需要多少时间,然后就随便做了做,看看要多少时间去讲,结果计时是差不多半个小时。但是CT给ENS这边的负责人发了信来问,结果发现一个人只有20分钟的时间,于是我就杯具了……最后做的时候只好一味地省略很多东西,然后才勉强在20分钟里边讲完。

其实这次实习收获还是很大的,虽然这个的性质基本上也就是implementation – observation,不是什么很有创造性的工作,不过起码也是有用的,而且也是很锻炼的。要说一开始的目的,其实也没有达到,因为本质上我现在用的方法也是差不多的,如果假定参数之间的相关性不高的话。不过也学了不少关于SAT的东西,还是很有趣的~~~

又一个学期结束了~~~

今天终于所有课的分数都出来了,又是时候做总结了~~~

这个学期上的课比上个学期要少一门,就是少一门语言的课,因为实在没有时间适合而我又感兴趣的英语课……尽管其实这个学期课程表很松……

好了,报一下这个学期学了些啥:

Pratical Scientific Informatics:其实这门课我也不知道到底是要来干啥的,好像一点东西都没学到一样就混过去了……学了一个8位芯片的指令集,然后用它实现了几个高精度取模的算法。以前碰过x86和x64的指令集的一小部分,所以写起来问题还是不大的。不过这门课的Project倒是很有意思。老师给了几个题目,然后大家自己组队挑一个题目研究研究,看能弄出些啥东西来,然后写个论文。我一个人挑了一个比较简单的题目,就是n*n棋盘n着色,使同色方格距离最小值最大。然后弄了一个还算漂亮的算法可以给近似解。因为题目比较简单,所以很早就交了。别的组的题目其实比这个复杂得多,比如说自动寻找关于zeta函数的恒等式之类的。

Initiative of Cryptography:这门课分三部分由三位老师上,第一部分是对称密码,对称密码的攻击方法其实说来说去就是利用加密算法会泄露出的信息,这些信息大部分是以统计的形式存在的,也就是说攻击就是尝试寻找一个加密算法与一个随机置换在统计上的不同之处,然后攻击这个弱点;第二部分是不对称密码,这个主要就是单向陷门和多项式规约证明安全性,攻击的话也是很数论的方法;第三部分是实际应用上的攻击,给人一种胜之不武的感觉,比如说拿个电压表去测人家芯片加密时候的电压啊,根据别人padding的形式凑出一个签名forgery啊之类的……其实还是挺有趣的,虽然我很难说我学到了多少东西……我总是觉得攻击的技巧很难捉摸……

Informatic Logic:这个课分三部分,首先讲了lambda演算,它的confluence的证明之类;然后是Curry-Howard对应性的一些实例,其实就是讲了很多类型系统和它们对应的逻辑系统,比如说CAML用的(部分)F类型系统其实和只用全称量词的二阶直觉逻辑是对应的;最后是几个和lambda演算等价的模型,当然是更接近lambda演算而不是图灵机的,比如说Combinatoric Logic之类的。其实这个课还不错,老师讲得也很有趣,但是continuation我死活就是不怎么明白……倒是后面那些等价的模型好明白些……

Geometry Bases for Informatics:这个课,不得不说我是纯粹去混学分的……两部分由两位老师上,老师讲课都很无聊……第一部分是组合几何,开头还好,最后听得头都大了都完全不明白在讲什么,果然一下子弄那么深入是不行的……第二部分是计算机视觉,这回的基本原理倒是好懂,但是很快就迷失在各种矩阵中了……如果考试的话是绝对会挂科的,不过好在考试形式是做两个presentation,两位老师分别选一堆论文,大家就分别一位老师选一篇然后做个幻灯片讲一下。然后这样混居然混过去了……我讲的第一篇是关于k-set的一个上界估计,貌似是目前为止最好的上界,然后第二篇是讲怎么在有摩擦力的情况下,用四只机械手指夹住任意的多面体……

Algorithmic Number Theory:这个课也是两个部分两位老师。第一部分是相对比较初等的各种数论和算法,这个其实非常简单,基本上看了就会。第二部分就突然地困难了起来了……是代数数域,然后研究它的各种性质,最后的目的是为了讲数域筛法(NFS)。我倒是很想知道NFS怎么弄的,但是差点就迷失在途中的荆棘丛中了……然后讲到最后,我发现其实途中不用那么多荆棘也是可以大概明白NFS的思路的……好在上过上学期的代数课,要不然这门课怎么死的都不知道……

System and Network:这个纯粹就是教Linux操作系统结构和使用的课,各位计算机人士表示毫无压力……起码基本使用是够的……

Software Engineering and Cloud Computing:其实我本来是冲着云计算去的,毕竟是分布式计算的亲戚,不过去到那里发现竟然是软件工程为主,我对软件工程毫无感觉……然后就混啊混啊就混过去了,这门课也是最低分的一门……

其实貌似物理系那边也有几门小课,听说挺有趣的,而且我也有时间,因为课程表来看的话星期五是没有课的,不过因为懒,所以还是没有去……

好了,汇报完毕!我现在正在做实习,主要是做SAT的各种统计还有WalkSAT的各种Benchmark的,实习完了再来汇报~~~

学期终于结束了……

汇报一下这个学期学了些啥~~~

作为一个计算机系学生,选的课当然以计算机系的课为主。(这不废话么……)

Digital System:主要说的是很简单的电路方面的东西,顺便讲了讲一点点信息论和一些多媒体的压缩技术。这个课有个project是设计一个同步电路的模拟器,然后写一个微处理器的电路,再在上面写一个电子表的程序。感觉还好。

Algorithm and Programming:算法课,分两部分,第一部分是传统的数据结构-算法,第二部分是一些比较新奇的偏向数值的算法,比如说数论算法、多项式分解的算法之类的。有一个写程序的Project。感觉也都还好。

Formal Language, Computability and Complexity:这个就偏向于理论计算机,分三部分。第一部分讨论形式语言,讨论了正则语言和上下文无关语言;第二部分讨论了可计算性,也就是图灵机啦;第三部分是复杂度,有时间的有空间的,也在图灵机上,说了复杂度层次的几个定理。有一个读文章之后重新写出来的Project,用LaTeX。这个课比较对我的胃口。

Programming Languages and Compilation:编译原理,这个估计不用多说。基础语言是CAML,整个课经常用CAML举例子。然后有一个Project,是写一个CAML的编译器,编译成MIPS汇编。这个也都还好。个人感觉CAML在这方面相当好用,尤其是构造语法分析树的时候。

Random Structures and Algorithms:这个课分两部分,第一部分是随机数学初步和随机算法,第二部分是马尔可夫链。第一部分那个老师讲得太烂,内容不错,但是讲得烂。第二部分还好。第一部分的考试杯具了……不过第二部分还好……

然后作为一个伪装成数学系学生的计算机系学生,修一点数学课是明智的,也是合适的,对于伪装来说……

Algebra I:这个就是近世代数,群讲了一点群表示论的初步,环讲到诺特环,域讲到分裂域。其实还好,代数对我来说还是有点用的。

Logic:这个课的名字太具有欺骗性了……其实它分为5个部分。首先是朴素集合论下的序数和基数,然后是模型论初步,然后是递归函数与图灵机,然后是哥德尔不完备性定理的证明(暴汗……),最后是策梅洛-弗兰克集合论初步。模型论暴抽象,后面的还好。期中考杯具了,期末考神奇般拿到了不错的分数。平心而论,课是不错,但是老师讲得不算很好……

最后还选了门英语学学,不过这个没什么好说的,比较空虚……

 

好,汇报完毕。