Spring 2022 课程记录

与上个学期不同,这个学期的工作量可以说是相当的大:一共enroll了7门课(还有一门课旁听了前七周)。如果说上学期有一些重复修的课和一些已经接触过的课,那么这学期大多的课反而是全新的内容。虽然这7门课中随便把哪一门单拿出来都不会造成太大的困难,但积少成多,7门课加在一起,便对时间的管理和学习的效率提出了非常高的要求——整个学期,七门课一共有54个作业和14个考试,而整个一学期按照16周计算也就只有16*7=112天。也就是说,平摊下来不到2天就要完成一个作业/考试,而完成一个之后马上又要接着完成下一个。考虑到课业之上还要兼顾两个project和CS4780助教的工作,整个学期基本就是不断的连轴转,很难有真正松下来的时候。

 

本学期刚开学时候的课表 (由于随着学期演进会渐渐不去上课而躺在床上睡大觉,课表上的方块会逐渐减少直至完全没有)

到学期后半段的时候,自己学习的workflow已俨然成为了如下所示的状态:

本学期的Workflow

如果有A, B, C, D, E这五门课,那么自己关于所有这五门课的知识都存储在Memory里,而如果要开始做一门课的作业或者准备一门课的考试,那么必须要把关于这门课的记忆load到cache里。而由于能力所限,自己大脑的cache至多只能存储关于一门课的知识。如果完成了A课的作业要继续做B课的作业,必须要把关于B课的知识load到cache里。而由于cache里最多只能储存一门课的知识,load B就意味着必须把原来储存在cache里的关于A课的知识evict回memory中。而由于作业和考试是按照ABCDEABCDE这样的顺序循环出现的,每一次read都会产生一次cache miss (capacity miss),这样的cache miss则产生极大的overhead。

如果如上的解释太过冗长不能使人理解,那用一句话概括就是“学完一门忘一门”。

纵然这学期颇具挑战,进程中也有诸多困难,现在自己终究也还是熬下来了。事实上,这学期应该会成为自己本科学业最忙碌的一个学期,而大三基本就是水通识课的养老模式了。

扯了这么多,下面还是进入正题,记录一下这学期上过的每门课。

MATH 4140 Honors Intro to Analysis II

之所以把这门课放第一位,是因为MATH 4140是我这学期最喜欢的一门课——这门课相较于其他课内容上更有意思,理论上更加漂亮,难度上也更有挑战性。比较遗憾的是,由于这门课是早八起不来,我从第8周以后就不去上课,而是对着lecture notes自学了。万幸的是Reyer Sjamaar教授的lecture notes写得非常好,自学和上课学习效果上并无二致。从工作量上来讲,这门课就是常规的每周一张作业,每次七八道题,不过和MATH 4130不同的是,这门课期中期末都是当堂考试,因而会相对来说难一点。

从内容上来说,这门课就是接着MATH 4130往下讲,涵盖了The Way of Analysis的第9-14章(遗憾的是第15章重积分没有时间涉及),但由于内容更为深入,这门课在难度上较MATH 4130有了一个较大的提升。具体来说,第9章将之前R上的拓扑拓展到Rn空间甚至一般的度量空间上,让得到的性质更具一般性。第10章将之前一元函数中关于导数和微分的概念拓展到多元函数上,得到了多元函数微分学。第11章将分析工具,特别是压缩映照原理应用到对于ODE的理论分析中,证明了常微分方程解的存在性唯一性定理,展示了分析方法在微分方程领域中的强大应用。第12章将分析工具和线性空间理论应用到对于傅立叶级数的研究当中,将函数集合看成一个无穷维线性空间,将傅立叶级数的项看成无穷维线性空间的一组标准正交基,在这样的观点下研究函数傅里叶级数的收敛性问题,体现了线性空间这种抽象理论带来的实际意义。第13章证明反函数存在定理和隐函数存在定理,并由此将二维和三维空间中的曲线和曲面推广到一般的Rn空间,从而给出了Rn空间子流形的定义。第14章介绍基本的测度论并由此引入Lebesgue积分从而放宽了可积性的要求、拓宽了可积函数的范围,然后证明单调收敛定理、Fatou定理和Lebesgue控制收敛定理,大大放松了积分与极限交换次序的条件,最后根据Lebesgue可积定义了完备的L1和L2函数空间,并在傅立叶展开的意义下证明了L2函数空间和l2空间(平方和数列空间)之间的同构。

事实上,第11到14章的内容只是对几个大方向的略作介绍——第11章对应整个ODE和PDE领域,第12章对应调和分析,第13章对应微分流形,第14章对应实变函数,而限于时间MATH 4140都没有办法涉及得很深入,如要进一步深入学习则还需要修习后续的课程。

虽然这门课和这学期上的其他课相比算是比较难的,但和其他数学系的课程相比,无论从横向还是纵向上来比,这门课其实都不算太难。从横向上来说,国内一些本科的数学分析课程讲授卓里奇的教材,从广度和深度上来说都要高于这门课。从纵向上来说这只是一门浅尝辄止的基础课,后续更进一步还有许多高阶的课程,正所谓一入数学深似海。遗憾的是,笔者天资愚钝,不会选择在数学方向上进一步深造,因而这门课就算给我分析方向的学习画上了一个句号了(也许并不圆满)。大三将要转战代数,继续完成4330和4340这两门专业必修课的学习。

学完这门课程的另一个感想可能是自己得找时间接触点物理,毕竟很多数学问题的产生和数学理论的应用都来源于物理。

CS 4220/MATH 4260 Numerical Analysis: Linear and Non-linear Equations

我校本科的数值分析课一共有两节。一节讨论微分方程相关的问题(CS 4210/MATH 4250),由数学系上。另一节就是这节,由计算机系教授上,主要讨论的是数值线性代数、线性和非线性方程组求解、数值优化。数值分析的核心内容就是“既要算得准,又要算得快”,而作为一门应用数学/计算数学方向的学科,它的性质可以说是介于数学和计算机之间:一方面,数值分析中最为关键的问题便是对误差的估计(算得准)和对收敛速度的分析(算得快),而这种问题的研究严重依赖于分析学中的各种理论和方法(比如许多迭代方法的收敛性证明便依赖于压缩映照原理);另一方面,由于要利用计算机作为计算的工具,数值分析又需要有比较强的代码和工程能力,从而能够将算法真正在具体问题上实践。从这个角度来说,这门课既不像数学那么数学,因为除了理论以外还要考虑很多实际的问题,也不像CS那么CS,因为到处充斥了数学公式的推导。

具体到课程的内容上来说课程主要分为两大部分,前半学期主要是数值线性代数,包括矩阵分解、最小二乘法、特征值问题、迭代法解线性方程组;后半学期主要是非线性方程组求解和数值优化,包括梯度下降、牛顿法、各种牛顿法的变种、constrained optimization等等。这门课学习上的一大特点就是内容比较杂,不会像纯数那样严谨把公式一条一条推出来,很多时候会比较handwavy,这也造成了lecture泛泛而谈而比较难follow的问题。事实上,到后半学期我一般都直接看教授的lecture notes而不去上课了,因为就算上课很多东西其实也还是听得一知半解,不如直接看lecture notes。事实上,这门课的作业有些和lecture关联并不是太大,而有很多lecture讲的也没有在作业里体现,所以虽然lecuture听得一知半解后半学期也不去听课,作业基本做起来还是没什么很大问题。

本学期作业使用的编程语言是Julia,一门scientific computing领域用得比较多的语言。这学期一共是5份homework和3个project,全部都用Julia notebook的方式呈现。作业当中理论问题非常少,偶尔有一两道题会让证一下error bound,其他大多数问题还是coding为主。当然这门课的coding本质上就是把一条条数学公式转换成代码的形式,所以和一般的coding还是有些区别的。从workload上来讲,我对这门课的评价是“远超预期”。事实上5份homework都还比较正常,最多两三个小时就能完成,但那3个project量都非常大(project 1是利用bordered system处理Graph Laplacian的edge update,project 2是利用regularization处理图像的傅里叶变换,project 3是利用牛顿法优化函数拟合),至少要花上两个整天的时间去完成,而且因为有些东西描述得不是很清楚,必须得ed上提问或者office hour去问教授。从这个角度来说,这门课的workload基本可以比肩CS 3410,而这在我选这门课之前是没有预计到的。虽然工作量远超预期,但适应了之后通过合理安排时间还是基本能够handle。

如果说要问这门课学了有什么用处的话,我觉得这门课所学内容的应用比较多还是在自然科学和工程领域,和机器学习也有一定关联,和传统CS的联系反而不是太大,因为像解大量线性/非线性方程组的任务,更多的还是出现在物理、化学、工程这些处理连续对象的领域,事实上这门课上许多的例子也都是从这些学科中来的,比如解热传导方程或者化学热反应方程之类的。

总而言之这门课作为一门应用数学/计算数学的课程,和之前学习的纯数课程还是有着非常不同的taste,虽然自己对课程的内容相比纯数来说没有那么感兴趣,但接触一下总无坏处。而且这门课的教授David Bindel还是相当负责的,一学期上下来还是学到很多东西。

CS 4410 Operating Systems

中规中矩的OS课,和CS 3410比起来就没有那么惊艳了,workload几乎是core里面最小的。需要注意的是这门课完全就是理论知识的讲解(除了当中并发编程会涉及到一点点coding,代码量也不大),不涉及到具体的代码和操作系统的实现。如果想要了解这方面的内容,需要选修CS 4411 OS Practicum(内容听说就是实现一个小的操作系统,笔者下学期会上)。整个课程就是一般操作系统课会涉及到的东西,包括进程和线程的概念,CPU调度,并发编程,虚拟内存,硬盘和文件系统,安全。这学期因为讲得比较慢,所以本来计划两周介绍的网络也最后没有讲。教授是Robbert van Renesse,人很和蔼,节奏也很chill,一学期五张书面作业和三次编程作业,每份作业基本两个小时以内就能搞定。考试的话这门课一共是3个,两次prelim一次final,但是允许drop一个。我就只考了前面两次,final直接没有去考。教授讲课感觉比较一般,经常听得昏昏欲睡,到后面发现自己看课本的学习效果比听课要好,于是一般也就不去上课了。教材是Operating System: Three Easy Pieces,是一本评价非常高的操作系统教材,循序渐进浅显易懂,非常适合自学。

整个课最为重要和相对最困难的部分是concurrent programming,其他的内容都是以记忆为主,偏文科一点,而concurrent programming这边对思维的要求就比较高。事实上如果仅以完成作业和应付考试为目标的话,学会套模版和画DFA基本就能畅通无阻了。但是如果要真正深入理解concurrent programming,其实还会牵扯到很多理论的东西,比如证明程序正确性之类的,当然这门课也不会过多涉及。这门课concurrent programming使用的语言是教授自己开发的Harmony(语法类似python),使用Harmony的好处是它会穷举并发程序的每一种可能的执行顺序从而发现可能存在的bug,不会出现写了个有bug的程序但是运行好多次都发现不了的情况。

总之是很chill的一门操作系统课,如果想认真学习os的话建议同时选修practicum。

CS 4820 Introduction to Analysis of Algorithms

一门中规中矩的算法课,内容包括Stable Matching(1周),贪心(1周),DP(1周),分治(1周),网络流(2周),NP-Completeness(2周),图灵机和可计算理论(2周),近似算法(1周),随机算法(1周)。教授是Eshan Chattopadhyay,IIT毕业的印度人,第一次教这门课(之前春季一直是Bobby Kleinberg教,但是这学期他转去教CS 4850了,具体下面会说到),个人觉得讲得还是很好的。事实上,这个教授非常chill,他上课的philosophy就是宁愿讲得简单一点,也要让所有学生都能听懂。如果听他上课的话,基本课后就只要复习一下他的lecture notes,没有必要去看课本了。

作业方面其实也比较chill——一共是10次作业,一次2-3道题,有时候一次作业还只有1道题。作业题很多还是需要想一想(毕竟题那么少),但最花时间的其实还是想完了以后要把答案在latex上打出来。考试的话也比较chill,没有难题,基本随便复习一下就能考得还行。

最后要专门谈一下这门课的ta——感觉ta们有些时候批作业都不是太仔细,经常乱扣分,有时候还会犯一些非技术性的低级错误(比如对reduction的理解都有问题),这方面必须给个差评。当然考虑到这门课庞大的人数(300个学生),这也不难理解,因为批阅证明题这件事情还是需要一定的水平,像数学系在学生数量比较少的情况下,批作业这种任务都是由phd助教完成。而由于算法课学生那么多,必然不可能请phd来批作业,于是就必须要雇佣很多本科生来当ta,而招这么多本科生,当中就必然有良莠不齐和滥竽充数的情况发生。

 

CS 4850 Mathematical Foundations for the Information Age

选这门课主要是因为自己要满足CS的probability requirement又不想水MATH 4710。总的来说这是一门中规中矩偏chill的一门课。

先介绍一下这门课的历史:这不是一门传统的CS专业课,大概是10年前开出来的,是前系主任、我校唯二的图灵奖得主之一John Hopcroft亲自指挥、亲自部署的产物,且之前一直都是由他任教。这位John Hopcroft教授与中国颇有一番渊源:不知道是不是嫌弃康奈尔本科生水平太差的缘故,John Hopcroft先生非常热衷于往中国跑,帮助提升中国计算机的科研和教育水平。北大的图灵班就是在他的主持下开设的,交大也成立了以他名字命名的研究中心,属于是在建设社会主义的康庄大道上阔步前行了。

John Hopcroft教授于2020年终于从康奈尔退休,于是就由之前长年执教CS 4820的Bobby Kleinberg来接替这门课的教学任务。这位Bobby Kleinberg也绝非等闲之辈,在1992年代表美国国家队获得过IMO金牌,本科一开始学习数学,然后在phd时候转行到理论计算机。

最后回到正题,来聊一聊课程本身的内容。这门课一开始一个多月的时间基本都是在复习线性代数和概率论,如果这方面有一定背景的话应该不会有很多新东西。讲完Chernoff Bound以后剩下半个多学期的课基本就是分析各种Randomized Algorithm和证明各种Bound。基本的思路就是利用各种概率不等式,使得样本个数取足够多之后,误差比较大的概率能够被控制得足够小。说白了,这其实还是分析的内容和技巧,核心还是对于收敛性的研究,只不过这里研究的性质是依概率/依测度收敛,而非数学分析中研究的一般意义下的收敛性。

作业和考试方面的话,这门课一共有6次作业,每次作业和CS 4820风格差不多,都是两三道题,题干很长,然后每道题要稍微想一想。需要指出的是,Kleinberg的作业和之前Hopcroft的作业风格还是不大一样,Hopcroft的题目风格更像是数学课本的课后习题,每道题是那种很短的一两行,而Kleinberg的题风格看着更像是算法题,每道题都是好几段。然后考试的话这学期一共是4个quiz和一个Final,其中4个quiz中允许一个drop,final允许整个都drop,所以考试的压力相对来说还是不太大。quiz的话题目也不会很难,40分钟4道题,基本都能够写得出来。上课的话不记attendence,教授也会录视频,所以不想去的话可以直接不去。

总之,如果想要一门课来满足CS的probability的requirement又不想如MATH 4710这样完全水过去的话,推荐选择这门课,会是一个不错的选择。

CS 1998 Intro to Backend Development

因为以后很可能还是得滚去当码农,所以这学期上这个课熟悉一下后端开发的基本概念。感觉workload一般,然后该讲的都涉及到了:从基本的route,到基本的数据库和ORM,再到后面的containerization和deployment,让学生对后端开发的各个步骤能有一个基本的了解。感觉这门课是一个不错的介绍,如果想要深入的话在各个方向上可以进一步地学习。

CS 2043 Unix Tools and Scripting

这是一门7周的s/u的short course,基本就是教你熟悉基本的linux命令,然后写一些简单的脚本。一共是5个作业,每次就是写一个小脚本,workload几乎没有。不过课程的内容作为常识,知道一下还是有帮助的。

*CS 4810 Introduction to the Theory of Computing (旁听前7周)

这门课我是旁听的,而且只去了前7周,自从不去上MATH 4140之后这门课也跟着不去了。虽然旁听意味着这门课学得一点也不算扎实,但我觉得这门课的内容还是挺有意思的。课程前一半形式语言与自动机(DFA/Regular Language + Context Free Grammar/Pushdown Automata),后一半是图灵机和effective computatility之类的,最后两节课会讲哥德尔不完备性定理。需要注意的是,这门课其实很多内容其实和其他课是overlap的,比如前面DFA和Regular Language的东西CS 2800会讲一点,图灵机的部分和CS 4820又有重复。这门课虽然讲的主要是理论,但是这些理论在计算机科学中都有实际意义,比如DFA可以用来描述程序状态,CFG在编译原理中有重要的应用等等。这门课的教授是Dexter Kozen,教过包括CS 4820,CS 3110,CS 2112在内许多本科的课程,讲课也是讲的非常好。因为是旁听所以作业和考试都没有参加,在这方面无法做什么评价。

我觉得旁听了这个课给我最大的收获是发现原来代数在理论计算机领域的应用比我想象的要多得多。Kozen本科就是学数学出身的,而且上课经常会提到如幺半群、同态/同构、商空间、余代数之类的概念。虽然现在上课的具体内容已经忘得一干二净了,但这门课给了我很强的继续学习抽象代数的动机。

Leave a Reply