读书: Problem Solving with Algorithms and Data Structures

What is CS?

Computer Science 就是一门专门研究 Problems 与 Problem-solving 的学科.

面对一个 问题, 一个 Computer Sciencist 的目标就是找出一个 算法 (即解决方案), 明确指示出如何一步步地解决该问题.

当然, 这里还会涉及到 可计算性 的问题(P与NP), 面对不可计算的问题, 设计什么 样的算法来满足解决问题的目标, 也是一个CS的研究内容.

一个计算机科学家在解决问题的过程中, 要多次进行抽象:

首先是对 待解决的问题 进行一次抽象 现实世界里的问题一般都会包含比较多的条件, 把现实世界里的问题明确表示的过程中, 不可避免地要进行一次抽象, 去掉无关的边缘条件, 保留该问题最核心的内容.

其实是对 解决方案 的抽象 我们开车的时候, 踩一脚油门车就动了, 我们不需要去了解车是怎么打火的, 发动机是 怎么运作的. 这种对解决方案的包装, 展示给最终用户的界面, CS里叫Interface, 现 在互联网圈叫用户体验.

What is Programming?

编程 就是把 算法 (问题的解决方案) 用某一种编程语言给表述出来的过程.

也就是说, 编程的第一步是 你已有某一问题的解决方案在手 , 没有 算法 就没有 程序.

CS不是研究如何编程的学科, 但编程, 却是一个Computer Scientist工作中的一个重要 组成. 毕竟, CS目标是 解决问题 , 编程是把这个 问题的解决方案 给最终实现的 基础操作, 重要性可想而知.

综合以上两部分, 总结一下计算机科学家的工作主要是:

把一个现实问题抽象, 用 Data 来表示 针对该问题, 设计出相应的解决方案 算法 把该 算法 用编程语言给表述出来 程序 计算机运行该 程序 , 从而解决现实问题

Programming Languages

编程语言提供了 Data Structure 和 Control Structure.

Data Structure

计算机只认识 0 和 1.

相信每个CS都听过上面这句, 所有Data对应到计算机执行指令的时候都是0和1, 但各个 编程语言会对这些01串进行「包装」, 这样我们在使用这些语言的时候, 就可以从包装 后的「砖块」层级来考虑如何把算法用该语言表述出来, 而不需要以01串的角度来思考.

各编程语言本身自带的这些对01串的「包装」叫做 Primitive Data Types. 可以理 解为天赋属性. 语言好坏, 很多时候从这里就可以做一个区分了.

对于复杂的现实世界问题, 所有编程语言都不可能出厂时都「包装」好「砖块」让你砌 墙. 所以后来才会有了 Abstract Data Type 的概念. 通过支持自定义类, 你可以自 己去「包装」现实世界, 抽象数据类型出来, 想怎么玩就怎么玩.

Control Structure

有了数据结构, 我们可以表示现实世界中的问题了. 但仍需要更重要的一个东西来把我 们的 算法 表述出来. 表述算法的语句就是 Control Structure.

语句控制可以大概分为三类:

  1. Sequential Processing (顺序执行)
  2. Selection (选择分支执行)
  3. Iteration (重复执行)

只要有了这三类语句控制, 我们就可以表述算法了. 剩下的工作就是把 算法 给翻译 成 这些语句的工作了, 也就是 编程.