东京大学情报理工CS专攻备考策略

　　根据《东京大学大学院情报理工学系研究科computer科学专攻》，考察的科目（选择四道做）有：情报数学(information mathematics)数值计算(numerical algorithms)离散数学算法和计算量(algorithms and complexity)形式语言(formal languages)伦理学(logic)Programming languagesComputer ArchitectureOperation systemsDigital circuit机器学习

　　口试考试是两天后，八月下旬进行。不出意外的话，仍旧是不考察具体内容，也就是和考生聊聊天，了解考生的基本情况，二面的话就是询问考生是否愿意服从调剂。考生在笔试当天心情可以比较放松。

　　笔者翻看了17年的备考日记，专门科目分为两场进行。第一场是必答题，一共三道题，考试范围是前十个科目。综合历年的试题来看，3道必答题，数据结构与算法、自动机两道题几乎都是必考的，第三题很大概率是逻辑电路设计。第二场是六选2，也就是让你考完试上下厕所，稍微放松一下就马上考试了。考试内容是除了上面的科目，再加上机器学习、计算机图形学、自然语言处理、生物信息学。我们可以看出，第一场考试考试时间是90分钟，一共三道题，每道题答题时间是30分钟；第二场考试考试时间也是90分钟，一共两题，每道题的答题时间是45分钟。从这里也可以看出来，第二场考试的题目难度会比较大。原因应该是第一场考试的考试科目都是本科计算机专业必修的科目，都是本科毕业生比较熟悉内容，所以答题时间会比较短。第二场考试的考察内容基本都是研究生阶段的内容或研究方向，对于本科毕业生来说，可能答题的时候需要结合题目背景，需要有额外的阅读量，所以答题时间稍微给多一点。

　　相比笔者17年考试，少了计算机图形学、自然语言处理、生物信息学、计算机视觉等科目，专门科目的考察也由笔者当年的二场砍为一场。相对来说，备考的难度是大大下降了。笔者观察到，考试形式发生变化是发生在2020年夏季考试，也有可能是由于新冠疫情的影响，考察形式不再那么繁琐。

　　由于考试形式发生重大变化，所以前两年的考试题就具有极其重要的参考意义。笔者将2020年以及2021年两年份的考题的考查科目罗列如下。我们依旧可以看到，无论考试怎么变化，算法和计算量、形式语言两道题是雷打不动的，几乎就是告诉你了，这两道题是必考的，而且这两道题的考察范围也是比较固定的，所以考生想要报考CS的话，建议先从这两门备考开始。其余的两道题，波动会比较大，比较难以猜测。不过，我们看到，2020年考察的逻辑电路也是老常客了，机器学习几乎就是改革前专门科目二的必考。2021年考察了操作系统和计算机结构，这两门虽然说出现的频率没有逻辑电路那么频繁，但是出现的话一点也不意外，因为它们无可争议就是计算机专业的核心课程。年份第一题第二题第三题第四题2020算法和计算量形式语言逻辑电路机器学习2021操作系统算法和计算量形式语言计算机结构

　　接下来笔者就来分析考纲给出的十一门课程究竟是如何备考。情报数学(information mathematics)

　　日文名称叫做情報数学，日文版的参考书(榎本 彦衛: 情報数学入門, 新曜社, 1987)，官网给出的英文版的参考书籍(Rudolf Lidl, Gunter Pilz: Applied Abstract Algebra, Springer, 1998)

　　虽然这门课程听起来很陌生，笔者先附上这本书的目录，让读者感受一下：

　　我们可以看到，lattice、group、field等翻译成中文就是格、群、域，相信考生一看到这些名词就会感到很熟悉了，没错，这些其实就是我们本科阶段离散数学里面的代数系统模块里面的内容。相信了解真相后会减轻考生的胆怯心理。不过，这一部分的内容，笔者发现过去问里面涉及到的极少，建议放在最后复习。

　　2.数值计算(numerical algorithms)

　　其实就是工程数学，主要有微积分、线性代数、复变函数、数学物理方程以及概率论与数理统计等等。

　　日语教材的话，官网推荐(久保田 光一: 工学基礎 数値解析とその応用, 数理工学社, 2010)

　　英语教材的话，官网推荐(Erwin Kreyszig: Advanced Engineering mathematics (Part E: Numerical Methods), John Wiley & Sons, 2011),此外官网的日语教材还推荐了本书的翻译版(E. クライツィグ (田村 義保 訳): 数値解析 (技術者のための高等数学 5), 培風館, 2003)

　　

　　虽然整本书很厚，但是官网友好地给出了考试范围是Part E，因为内容就是数值分析(numeric analysis)

　　对应的中文是19.2迭代法求方程解19.3插值法19.4样条插值19.5数值积分和微分20.1高斯消元法20.2LU分解，矩阵求逆20.3迭代法求解线性系统20.4坏条件下的线性系统，范数20.5最小二乘法20.6矩阵特征值20.7矩阵特征值的包含20.8求解特征值的强有力方法20.9QR分解21.1一阶ODE21.2多步法21.3高阶ODE求法

　　相对来说，数值计算考的也不是很多，但是也出过，比如可以穿插在线性代数的考试里面，如LU分解、QR分解等，插值法也在往年的考试中出现过。这部分内容其实不算多，但是因为可能会穿插在数学里面考察，所以也应该引起足够的重视。

　　3.离散数学

　　这门课程不用太多介绍，计算机相关专业的同学绝对很熟悉，问题是离散数学在学术界从来就没有一个明确的概念说应该包括什么，相反，更多的是会排除不包括什么。在国内本科一般会涉及四个模块：数理逻辑（命题逻辑、谓词逻辑）、集合论（二元关系、特殊关系、函数）、图论（图、树、特殊图）、代数系统（群环域格等），有的书籍可能还会介绍组合数学、生成函数等等。但是国内本科一般介绍前三个模块比较多（如果是48学时的话），或者四个模块（对应64学时）。所以选用不同的离散数学书籍所学到的知识模块可能会有所差异。

　　英文版教材官网推荐：Jiri Matousek, Jaroslav Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2009

　　日语教材官网推荐的是对应的英文版翻译：J. マトウシェック, J. ネシェトリル (根上 生也, 中本 敦浩 訳): 離散数学への招待 (上, 下), 丸善出版， 2002

　　我们来看一下这本书的目录

　　我们可以看到，主要涉及到的内容有：组合数学、以及图论的内容（图、树、特殊图）、生成函数

　　4.算法和计算量

　　通常对应于国内的《数据结构》与《算法设计与分析》，国内有些院校将两门课程合并称为《数据结构与算法》，这可以说是计算机相关专业最重要的核心课没有之一了，也是国内考研必考的，重要性不言而喻。并且每年考试必考，笔者建议考生应该把本门课程最为最优先复习、花时间最多的科目。

　　参考书目，英语版的(Robert Wayne, Kevin Sedgewick: Algorithms, Addison-Wesley, 2011)

　　这本书是算法书里面评价最高的大作之一，笔者强烈建议考过之后请花时间去好好阅读本书，因为本书介绍的非常详细，样例代码也非常充足，不过不建议作为备考资料，因为本书非常厚。

　　个人还是比较建议遇到考查科目内容太多太杂的情况下优先选择日语教材，因为日语教材一般不会太厚，会比较简洁，复习起来比较有针对性。

　　所以本科目推荐日语教材(五十嵐 健夫: データ構造とアルゴリズム, 数理工学社, 2007)。此外提一下，作者五十岚是东大CS的教授，他本人一直担任本科数据结构的课程授课，所以毫无疑问，就是得选这本书。除此之外，大家也可以去五十岚教授的主页去寻找本门课程的一些资料，尤其是历年期末考题，参考价值非常高。

　　5.形式语言(formal language)

　　虽然本科目听起来也很陌生，但是它所涉及的自动机、正则语言、上下文无关文法等内容，其实在咱们国内本科的编译原理有涉及到，所以当初笔者备考这门课程的话，压力不是很大。虽然国内考研不考，很多互联网公司面试也几乎很少问及这一门科目，但是这是CS专门科目每年必考的题目，而且考点固定、范围比较稳定，所以笔者强烈建议考生，形式语言与算法和计算量两门放在最优先复习的地位。

　　参考书目，官网推荐(John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (Chapters 1–7), Pearson, 2013)

　　日语版的话就是这本书的翻译(J. ホップクロフト, R. モトワニ, J. ウルマン (野崎 昭弘, 高橋 正子, 町田 元, 山崎 秀記 訳): オートマトン 言語理論 計算論 I (第2版), サイエンス社， 2003)

　　同样我们看到只考察前七章的内容，所以压力真的不算大，笔者强烈建议这本书的章后每一道习题都要做一遍。

　　6.伦理学(logic)

　　同样的，笔者当初看到这门科目的时候也是很惧怕，不知所云，但当笔者翻开参考书目的时候，发现其实大致对应于离散数学的数理逻辑模块（命题逻辑、谓词逻辑）。

　　日语版的参考书目：萩谷 昌己, 西崎 真也: 論理と計算のしくみ (1, 2, 4章), 岩波書店, 2007

　　英语版的参考书目：Dirk van Dalen: Logic and Structure (Chapters 1–3, 7), Springer-Verlag, 2011

　　同样笔者放出该书目录给读者参考一下。

　　7.Programming languages

　　该门科目，笔者在备考的时候是放弃的。因为实在是太陌生。不过大体是有关编译原理的东西。官网推荐的日英参考书各有两本：

　　日文教材：W. Appel (神林 靖, 滝本 宗宏 訳): 最新コンパイラ構成技法, 翔泳社, 2009

　　B. C. Pierce (住井 英二郎 監訳): 型システム入門 —プログラミング言語と型の理論— (1–5, 8–9, 22章), オーム社, 2013

　　英文教材：

　　Andrew W. Appel: Modern Compiler Implementation in ML, Cambridge University Press, 2004

　　这本书也就是传言中的编译原理虎书，只不过是用ML语言实现的，要是读者觉得ML语言太过陌生也可以选取对应的C语言版本看看。

　　Benjamin C. Pierce: Types and Programming Languages (Chapters 1–5, 8–9 and 22), The MIT Press, 2002

　　8.计算机结构(Computer Architecture)

　　这门课程也是国内考研要考的，大致对应于国内的计算机组成原理。在专门科目里面出现频率也是不低。

　　参考书英日都是同一本，不过日文是翻译英文的。

　　David A. Patterson, John L. Hennessy: Computer Organization and Design MIPS Edition, Fifth Edition: The Hardware/Software Interface, Morgan Kaufmann, 2013

　　这本书也是计算机结构的公认杰出著作了，不过确实非常厚(英文版近八百页)。

　　如果没时间看的话，不妨参考此日语教材作为替代(只有134页)

　　9.Digital circuit

　　这个对于笔者来说也是不算陌生，毕竟笔者本科学过《电工学》，涉及过时序逻辑电路和组合逻辑电路，大致对应于这门科目，不过要求更高，还需要通过做题来完善知识。这门科目考察的频率也就是个别年份没有而已，不过因为难度波动比较大，笔者建议考生可以将比较常见的电路设计出来，如加法器减法器，各种计数器等，可能考试会遇到一些非常难的小问，笔者当年就最后一问完全放弃。

　　笔者当初在备考的时候，官网应该是没有给出该门科目的参考书。不过好在现在官网已经有了。

　　参考书目日英都是同本书：David Money Harris, Sarah L. Harris: Digital Design and Computer Architecture, Second Edition, Morgan Kaufmann, 2012

　　10.操作系统

　　操作系统也是考研必考，在专门科目的出现次数也不少，最近两年也考过，不过因为它不像数据结构和形式语言那样是摆明了就要考的那种，所以不排除出过之后未来几年不考的情况。

　　英文版参考书目：Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating System Concepts, 9th Edition, Wiley, 2013

　　这本书国内很多教材都是采用它的翻译版吧。所以笔者当年复习的时候压力也不大，因为教材一样，整本书当然没法全部看完，就参考本科阶段重点介绍或者考研的考察要点复习，发现也基本覆盖了过去问的考点。

　　说实话，操作系统和计算机结构两门课的备考方式很相似，虽然参考书很厚，但是有重点，基本上和国内考研重合，考生可放心采用在对应知识点采用参考书来复习。不过就是内容稍微有些杂，需要考生静下心来好好整理，这两门科目考试难度不大，但是拿满分的难度大于必考的那两门。

　　11.机器学习

　　说实话，机器学习爆火当年，笔者已经大三，所以只是在课余时间大概涉猎一些内容，不像国内现在有些专业低年级开始就已经上过机器学习了，不过总体从试题来看，基本上机器学习的考题就是在考数学，尤其是概率和线代。所以大家可以发现CS对数学的要求真的非常高，考察的几率相当高。好在不太要求考生有太深的机器学习背景的了解。所以机器学习复习的不全面的考生，该题仍然有机会答得很好。

　　参考书目的话，英文版Trevor Hastie, Robert Tibshirani, Jerome H. Friedman: The Elements of Statistical Learning, Springer, 2009

　　

　　笔者在此说一句，这本书真的不太适合机器学习的入门，真的难度很高，当初笔者复习的时候看这本书果断选择放弃。

　　不过官网同样也给出了日文版教材：杉山 将: 統計的機械学習 —生成モデルに基づくパターン認識, オーム社, 2009

　　这本书是由东大CS最著名的杉山教授写的，笔者在研究生阶段曾经拜读此书，写的确实很赞。内容偏概率论。

　　算法和计算量理论、离散数学：今井浩、河原林 健一并行数值计算：须田礼仁编程语言、软件验证：小林直树用户接口、计算机图形学：五十岚健夫机器学习：杉山将、佐藤一诚、石田隆自然语言处理：宮尾 祐介、谷中瞳、相澤 彰子计算科学、并行仿真软件（特别是第一原理电子状态计算）：吉本芳英操作系统：加藤真平计算机结构与系统：高前田伸也、中田登志之图像解析、空间情报学：横矢直人生物信息学：中井 謙太、井元 清哉、渋谷 哲朗、清水 謙多郎、朴 聖俊、片山 琴絵计算机视觉：佐藤 いまり

　　从以上这些教授的研究领域我们可以看出，东大CS教授的研究范围几乎覆盖了方方面面，从硬件到软件再到算法，都能找到相应的教授在从事相关研究，而不是清一色的机器学习。当然，要提到东大CS声望最高的教授，非杉山将莫属。杉山教授是日本人工智能和机器学习领域的领军人物，当年笔者也是第一志愿报了杉山将，很遗憾的是竞争过于激烈，而且不少人第一志愿就是杉山教授。除了担任CS的教授外，他还是新领域复杂理工的教授。听说有中国学生考进了竞争相对来说不那么激烈的新领域，成为了他的学生，也算是曲线救国了。