一份很短的计算机科学介绍

本文针对少年班学院 19 级本科生，概括描述了科大计算机的课程设置，培养目标和一些关于计算机科学的认识。

前言

（这节本来想自己写，但是跑到知乎上发现源神把我想说的、会的不会的都说了，所以在下面的小节直接引用了…）

一些个人理解，仅供参考：

  • 作为计算机系来说，学「数理方程和热力学」等本身，对除了科学计算和「写物理引擎」之外的方向帮助不是很明显
    • 举例：
      • 用于高性能计算评分的 HPCG Benchmark，数值方法解 3D 热传导方程
      • 写/优化物理引擎，搞流体模拟啥的（
    • 当然你会发现，数理方程也不讲数值方法，还是要看点数值计算的课程和教材（躺
  • 作为计算机系同学，应该在课程学习中逐渐掌握一套自己的「问题解决方法」
    • 对计算机系统有整体的认识
      • 计算机是怎么从逻辑门开始，一步一步打造出你看到的东西的？
        • 相关课程：「计算机系统概论(H)」，「模拟与数字电路」，「计算机组成原理」，「操作系统」
      • 出现问题可以定位出现在哪一层，自己应该补充何种知识
      • 可以从整体上分析设计计算机系统
    • 熟练掌握对应领域的几门程序设计语言
      • 或者说，能控制对应层次系统的行为
    • 认识到各种解决方案的缺陷
      • Eg.1. C 的优点？缺点？
        • 为什么会有这样的优点和缺点？
        • 什么最适合成为大学通修的程序设计语言？
      • Eg.2. Unix / Linux vs Windows？
      • Eg.3. 计算机应该自顶向下学习还是自底向上学习？
        • 他们的代表课程（链）？
    • 熟练寻找并且阅读文档
      • 课上很少提出但是十分有用的一点：
        提出问题时遵循《提问的智慧》，努力提供完整的复现环境和自己的尝试。
  • 辩证的看待观点和技术

「计算机和其它学科的不同」

下面的文字引用自源神在知乎的答案。

劝退部分请辩证看待：

  • 一方面，学校的有些课程在积极作出改变（Eg. 运筹学/体系结构/数电实验），变得更加面向UCB面向实践
  • 另一方面，在 CS 的工科思维方面，（我个人认为）仍然缺乏更有力的引导

计算机科学和物理这些学科是不同的。

学习物理化学时大家应该感受到，越新越前沿的理论难度一般越大，比如历史上的一些理论层次是：重力原理（重力和质量成正比），杠杆原理，标准牛顿力学，电磁学，理论力学，电动力学，狭义相对论&量子力学，广义相对论&量子电动力学，电弱统一理论，标准模型，量子色动力学，超弦理论，M理论等等，层次不断提高，难度不断增加，确实不应该让学生从最先进的入手。

但是计算机领域有所不同。计算机先驱们的能力超乎想象——靠在纸带上打孔写程序，这在当今都是很难的事情。然而后来随着计算能力的增强，有了各种高级语言，以至于C语言编程变成了全校通修的课程。最近出来的Python语言用于这次引力波探测数据分析，但是科大学生基本上几周就能学个大概，可见难度并不大。另外最著名的几个例子是CISC和RISC指令集架构。Intel的指令集体系是CISC的，非常复杂。但是后来发现在统计学上简单的RISC更有利于性能调优，于是有了ARM等架构，并且逼得Intel在内部实现了RISC微码来提升自己的性能。现在计算机教学上也是从RISC入手。

计算机学科之所以能够这么做，是因为计算机是少有的人造的但是非常成功的东西。由于人造特性，人们可以随时根据计算力和需求变革思想－－计算机领域几乎能够抽象和虚拟任何东西，制定任何规则（除了request和girlfriend），而自然科学由于受到定律和实验条件的限制不能这么灵活，这也是为什么计算机相关领域几乎天天创新，基本上一个产品发布会就有一个创新，并且这些创新很快改变了所有人的生活，不到10年而已。可见计算机学院学生接触前沿是应该的，也是可行的，并且有助于创新。可惜我们大多数课程依然是大纲形式或者教条形式——自出现就很少变过。

「极端还原论」

上面的一些部分有不严密之处，这里补充论证一下。针对的问题是交叉学科。目前学校交叉学科的意思大约是和物理交叉。这个我曾经质疑过，也问过某人，得到的回答大意是“物理是自然科学的基础，所以应该从物理着手，这样基础强了后面都不是问题。” 我不否认数学基础强了可以增强能力－－因为数学直接作用于学科；但是物理基础强了就一定使得上层建筑比别人好这点我是反对的。这个是典型的（极端）还原论思想。

举个例子，比如大家做过PPT对吧？但是PPT是什么原理呢？它是一个程序，程序响应用户的操作，调用操作系统功能完成任务，操作系统在硬件体系之上，硬件体系又受数字电路支持，数字电路又受工艺支持，工艺又有它的物理原理，可能最终要扯到量子力学。按照（相对极端的）还原论思想，你不懂操作系统，不懂硬件体系结构，不懂数字电路，不懂固件工艺，不懂量子力学，PPT技术是不能有大的突破的。所以说要做PPT前要先学CS的整套课程，然后再学化学工艺，然后再学整套物理，这样制作PPT才后劲足。然而我大多都学过，为什么PPT却做不过一个都不知道自己用的是 Windows7 还是 Windows 8 的美工师啊？

「学习计算机的目标」

计算机学院学习多少门课程倒不是最重要的，像交大 ACM 班那位没学过数字逻辑的同学，经过两个月的适应，就在我们的 FPGA 研究项目里做出了重要贡献。重要的是养成一种计算机的思维方式，也就是如何用计算机解决一个实际问题。包括如何用搜索引擎，掌握一门称手的编程语言，出了 bug 之后如何有条不紊的找出 root cause。

现在科大的课程对“计算机思维”的培养还很欠缺，有计算机思维的同学们多数是在大学之前就已经有不错的基础了，也就是大学本身没有教会更多的人。比如说有一些数据要处理，有计算机思维的人会自然想到先去搜一下有没有现成的工具，不行的话就自己写个脚本。没有计算机思维的人，宁可一个个手工处理。他们也知道脚本更快，但是他们对写程序解决这个问题没有信心，写的过程中出了问题也没有信心解决，所以就会逃避写程序。

计算机专业毕业的一个标志，应该是能用而且愿意用计算机来解决重复性、程序性的问题。计算机的各种专业课，在讲解计算机基础理论的时候应当紧密结合生活实际，让学生真正用上这些知识，比如处理实验数据，识别验证码，破解软件，刷课，建个人主页。具体的技术倒是次要的，主要是要建立起查资料、写程序、调 bug 的习惯，对这个流程不感到恐惧。

和其它院/系的不同

首先，计算机学院只有一个系，（011）「计算机科学与技术系」。

计院 vs 信院

下面关于信院的专业解读是我看着课表瞎写的，仅供参考

信院一共有「电子信息工程」、「自动化」、「信息安全」、「电子科学与技术」几个系。

  • 电子信息工程：通信，etc
  • 电子科学与技术：电路设计（比如 VLSI）
  • 自动化：数字控制/机器人/系统工程
  • 信息安全：
    • 多学一点密码学，软件安全设计和评估测试的内容
    • 少学一点体系结构、组成原理的内容
      • 和计院各种方向课的东西（见下文）

计院 vs 其它院

不会有人搞不清楚计院和其它院的区别吧

如果有，请问 cwk

科大的计算机课程设置

请参见从教务系统导出的 2017 级培养方案的 PDF。

2019 级的培养计划可能与 2017 级略有不同（比如，我们没有上过「计算机导论」）

所以，以下信息仅供参考，具体情况请以教学秘书和教务处的说法为准。

计院都学什么 - Overview

没上过的基本上是按我个人理解写的，233

  • （大一）编程语言：C 的基本语法，用 C 设计控制台程序
  • （大二上、下）图论 & 数理逻辑：各种图的性质和定义证明，一阶逻辑和谓词演算
  • （大二上）数据结构：在计算机中常用的数据组织方法（链表、队列、栈、树、图）、简单算法（排序、图/树/表遍历、Huffman 树、查找树，etc）
  • （大二上）模拟与数字电路：帮你了解计算机系统的数字电路基础（与或非门，组合和时序逻辑电路、状态机、RAM & ROM；模电的 OpAmp 和 BJT 放大电路）
  • （大二下）计算机组成原理：与或非门是怎么组成加法器、（时序）乘/除法器的；CPU 是如何从基本的门构建的（状态机=>CPU Cycle、ALU，RegFile，etc.）
  • （大二上、下）数字电路 & 组成原理实验：利用 FPGA（在线可编程逻辑门阵列）实现 状态机/乘法器/CPU 等
  • （大二下）运筹学：线性规划、排队论、0-1 规划、指派问题，etc
  • （大二下）操作系统：操作系统的原理、意义，设计中要考虑的部分；Unix System Call，etc
  • （大三上）计算机网络：计算机网络的构成，常见协议的实现，etc
  • （大三上）编译原理：如何实现编译器（词法、语法分析、中间代码生成和优化、指令和寄存器分配、一些语言特性的实现）
  • （大三上）算法基础：计算机常用算法（复杂度、排序、查找树、二叉堆、贪心算法、DP、字符串匹配，etc）
  • （大三上）计算机体系结构：流水线、Cache & Cache 一致性、分支预测，etc
  • （大三下）数据库：SQL & 范式 & 架构（？）（我猜还会有数据库的优化吧）
  • （大三上）微机原理：听说「科普+汇编语言+简单数字电路」，大概会涉及比如 x86 GDT 啥的
  • （大三下）人工智能基础：听说「比较经典传统的人工智能内容（搜索，逻辑，概率论，还有贝叶斯方法，决策树，回归，SVM等一些明显能找到数学上解释的方法）」

方向课（大三/大四），以下为听说的，详情请参阅评课社区：

  • Web 信息处理与应用：聚类/分词/…
  • 嵌入式系统设计方法：ARM 架构 & 汇编
  • 并行计算：MPI/OpenMP/… & 常用的并行计算算法
  • 信息安全导论：听着就像文科课程可能讲一点密码学/网络安全协议啥的？
  • 网络算法学：DPDK & extra stuff
  • 程序设计语言基础
  • 系统建模与仿真
  • 计算机图形与图像
  • 网络系统实验
  • 高性能处理器体系结构

Extra（H 课）：

第一年的不同

在大一上和大一下，计院培养计划和少院的不同之处如下所示：

  • 单变量 & 多变量 vs 数分 B1 & B2
    • 这个不要紧
  • 力学与热学 & 电磁学C vs 力学 热学 电磁学A
    • 这个也不要紧（高级替代）
  • 程序设计 I vs 计算机程序设计
    • 程序设计 I 可以被 计算机程序设计 高级替代
    • 事实上，程序设计 I 较 计算机程序设计 少讲授了链表相关内容，而是将其放到 程序设计 II 中
      • （2017 级情况）
  • 程序设计 II（大一下）
    • 讲一些递归、DP、表达式求值（NPL）、实数加减法的内容
      • 吐槽：实数加减法我们竟然是用字符串做的…浪费了多少硬件资源
    • 在有些暑假（暑期小学期）开，但是有些小学期就不开（比如这个暑期）
  • 代数结构（大一下）
    • 讲一些基本的群、环、域的知识
    • 做密码之类的比较有用，其它的时候不是很直接相关
    • 据说：「（超）简化版近世代数」

据同学说，教秘说过「只要第一年完整按少院课程修读，程序设计 II 和代数结构就不用修了」。

但是，请同学们开学自己验证此事的真伪，以及政策有无变化。（我发邮件教秘没理我）

计院英才班？

就是都学 H 课而已啦。一共有三门 H 课：

  • 计算机系统概论(H)（评课社区链接：点我）
  • 操作系统原理与设计(H)（评课社区链接：点我）
  • 编译原理和技术(H)（评课社区链接：点我）

然后诸如拿钱之类的福利应该都差不多吧…（不是英才班的菜鸡路过）

除了上课，还能搞点啥

  • 去实验室找课题做
  • Be indie developer / join open source community
  • 比赛（iGEM / ACM / Robogame…）
  • 实习
  • … （想干啥干啥233）
  • 学物理（？）

Extra / Q&A

计院本科之后都干什么

  • 去工作
    • 这个抱歉没有太多经历和经验分享，可能直接去知乎找更合适一些
  • 读研（出国/国内）

计算机读研的方向（包括但不限于）：

  • 机器学习
  • 计算机图形学
  • 体系结构
  • 高性能计算
  • 网络
  • 算法
  • 人机交互/机器人
  • ……

建议有相应打算的早进实验室（比如大二），自学一点然后去找对应的实验室老师聊聊，去组里体验一下研究生们都在干啥。

CS 应届生平均工资

我并不比知乎多知道多少…

可以直接知乎「计算机 平均工资」就好了。

科大 CS 国外申请情况

请参考 https://adrain.ustclug.org/ 中关于 CS 的部分。

同时，CS 的飞跃手册也可以在上面下载。

需要注意的是，这个页面可能要求用科大的统一用户认证系统登录。

如果还没有统一用户认证的帐号的话，各位亲稍安毋躁，到开学就可以登录啦。

什么编程语言最好？

出门左转知乎不谢～

我知道，大家可能会问在大学阶段熟练掌握什么比较重要——这个因人而异。

在计院的最低要求：

  • C
  • Verilog

（要不然完不成课程实验的）

在这个基础上，我建议学一门 OOP 语言和 FP 语言。

（做开发的话，肯定是要针对性的学语言和框架）

  • 虽然此条还处于 TODO 态（

其它建议？

  • 都应该学一下 Linux 的基本使用，如何配置 toolchain 等
    • 至少操作系统课要用
    • 之后如果做网络和系统也是跑不了用 Linux 的
    • Also: 有问题可以去 USTC Linux User Group 求助
  • 没了，想到再添加…

Compiler Princlple Study Node

编译原理预习

为了暑假好好学习选昱姐的课不会挂的太惨，提前过一遍昱姐的 ppt，和《编译器设计》（第二版）的书籍。内容会交叉进行。

词法分析

FA

为了形式化识别器，引入有限自动机（FA）。有限自动机是一个五元组 $ (S, \Sigma, \delta, s_0, S_A) $：

  • $ S $ 是识别器有限状态集，以及一个错误状态 $s_e$。
  • $ \Sigma $ 是识别器用的有限字母表。
  • $ \delta(s,c) $ 是识别器的转移函数，对每个 $ s \in S , c \in \Sigma $ 对应一个状态。一般也这么表示：$ s_i \xrightarrow{c}{\delta (s_i, c)} $。
  • $ s_0 $ 是指定的起始状态。
  • $ S_A \in S $ 是接受状态的集合，表示为双层圆圈。

复杂性：

  • 注意到 FA 的运行开销只与输入长度成正比（因为就是简单的状态机嘛），而与生成 FA 的 RE 长度或者复杂性没有关系。

正则表达式

RE 描述了一个定义在某个字母表 $ \Sigma $ 上的字符串集合。一个 RE 由三个基本操作构成：

  • 选择：$ R | S $
  • 连接：$ RS $
  • 闭包（Kleene closure）： $ R^* $ ，R 出现零或无穷次
    • 相当于 $ \epsilon | R | RR | RRR | RRRR $ ….（当然，这种写法显然不是 RE）
    • ($ \epsilon $ 表示仅包含空串的集合)
    • 为了方便：
      • 有限闭包 $ R_i $ 为 R 出现一次到 i 次形成的闭包：
        • 例如 $ R^4 $ 也可以表示为 $ R | RR | RRR | RRRR $
      • 正闭包：$ R_+ $ 为 R 出现一次到无穷次形成的闭包
  • 优先级：括号>闭包>连接>选择

用上面定义和数理逻辑的东西，可以定义全体 RE 在给定字母表 $ \Sigma $ 上构成的集合。

任何可以利用 RE 定义的语言（即，对于给定语言，可以找出一个 RE 使得语言的所有可能字串都恰好是 RE 可表示的字串）组成的语言集合称为正则语言。

RE 的闭包性质：$ RE op RE $ 的结果仍然是 RE（这里 op 指的是前面那些操作）

  • 这样就可以很方便的证明（&寻找算法使得）对于任意 RE 都有 FA 与之对应了

JauntyLiu 想出的简单算法：

（这里需要 RE 的分层性质，仿照数理逻辑即可给出）

  • 对于任意 $ p \in RE $，它必为下面几种情况之一：
    1. 存在 $ q,r \in RE $，使得 $ p = qr $
    2. 存在 $ q,r \in RE $，使得 $ p = q | r $
    3. 存在 $ q \in RE $，使得 $ p = q* $
      • 正闭包可以写成 $ qq* $，所以不需要单独讨论
      • 有限闭包更显然
    4. p 为一个字母的字母串

4 的构造显然。

下面讨论 1,2,3 的构造。假设 q,r 均有了对应的 FA。

对于 1，FA 构造如下（比较显然）：

  • 取 q 的所有 accept state （$ S_A $），分别「接上」r 的 i nitial state （$ S_0 $）就好了
    • 严谨证明的话，可以写成 FA 的语言

对于 2，FA 构造有些难度。我们需要知道「匹配到什么程度才能把 q 和 r 分开」。比如 $ abc $ 和 $ abd $，就要匹配到第三个才知道到底选 q 还是选 r。

  • 如果没有闭包，那这个取交集的操作肯定是有限的；那就非常好办。
  • 如果有闭包，则不能保证？看书吧

书上的做法：RE ==(Thompson)==> NFA ==(子集构造伐)==> DFA ==(Hopcraft)==> 最小 DFA

子集构造法：用 $ \epsilon -closure $ 找状态的等价集合（「配置」），然后遍历。因为总配置数是有限的，所以一定可以停止。

Hopcraft 算法：先分类，然后迭代，找出类中不等价的元素，切分。重复，知道遍历所有类均找不出不等价的元素，这样就构造了一组等价类（状态）。

语法分析

Modern C++ Note

被弃用的特性

  1. char *str = "Hello World"; // use "const char *" instead
  2. bool a; a++;
  3. auto_ptr => unique_ptr
  4. C++98 异常说明 (?)
  5. 如果一个类有析构函数，为其生成拷贝构造函数和拷贝赋值运算符的特性被弃用了
  6. C 语言风格的类型转换

语言可用性强化

常量

  • nullptr: 为了解决 NULL 的模糊性。

    NULL 如果实现为 ((void *)0)，因为 C++ 编译器不支持 (void *) 隐式转换为其它指针类型，在 char *s = NULL 这种地方会出问题。

    所以只好在 C++ 中定义 NULL 为 0。但在重载调用时会有反直觉的情况发生：

    1
    2
    3
    void foo (int a) { /* do something */ }
    void foo (char *a) { /* do something */ }
    foo(NULL); // will call `foo(int)` instead of `foo(char)`

    引入 nullptr，其类型为 nullptr_t，能够隐式转换为任何指针和成员指针类型，也可以进行相等和不等比较。

  • constexpr：常量表达式（C++11、C++14）

    constexpr 修饰可以作用在函数和变量上，用来让编译器「明确验证」它是一个常量表达式。

    常量表达式之间可以传递（C++11）

    constexpr 函数可以在内部使用局部变量、循环和分支等简单语句（C++14）

    • 为了和 C++11 兼容，可以都用 a : b ? c 来作判断，不过就不能有循环了(?)…

变量及其初始化

  • if 和 switch 的括号中可以定义临时变量（C++17）

    1
    2
    3
    4
    5
    // 将临时变量放到 if 语句内
    if (const std::vector<int>::iterator itr = std::find(vec.begin(), vec.end(), 3);
        itr != vec.end()) {
        *itr = 4;
    }

  • 初始化列表和 std::initializer_list<>（C++11）