CS61A计算机程序的构造与解释课程介绍及课程学习总结这是⼀门UCB开设的 CS 专业核⼼基础课程。
其前⾝是针对课程及课本：SICP: Structures and Interpretation of Computer Programs 的⼀门课程。能够学习到基本的编程概念，软件⼯程概念，程序设计概念。主要练习了 Python 编程，函数式编程，⾯向对象编程，LISP Scheme 语⾔。适合⼤⼀学习。我是在⼤⼆上学期才学的。。。历时3个⽉业余时间 (懒 + 过年…，⼤概百来个⼩时差不多)。有很多具备反馈的 lab 和交互式的 homework，有⼏个好玩的 project，最后⼀个 project 是⽤ python 实现⼀个  scheme 解释器很有意思，为后续各种学习都能做⼀个导论，⽐学校⼤⼀开的谭浩强c 语⾔指针都讲不到的PPT reading计导课不知道⾼到哪⾥去了，后悔没有早点跟这个学习。
课程具体的开发环境是 linux 下，hw、lab 都具备 ok 程序可以⽤来评判代码，使⽤时加 --local 禁⽌打开⽹页输⼊邮箱即可。
把总结学到的内容的概要放上来⽅便⾃⼰回顾。也能分享这门课能学到什么给有需要的⼈，可以观看下⾯的⼤纲初步了解这门课的⼀些内容。
学习课程链接：
HOF
1. 函数第⼀公民, dependency injection, 依赖注⼊(指函数作为参数)
2. 熟悉lambda函数
3. 柯⾥化的原理
4. 装饰器(包装⼀个函数), 重点学习trace包装器和后⾯学到的尾递归优化包装器
5. 变量的immutability
6. scope与environment的概念
7. 掌握GCD的递归解法 (辗转相除/减)
8. 掌握⽜顿法逼近零点(以及数值的求导)
递归和迭代的熟悉
1. 掌握两种递归: 尾递归和先递归
2. 编写递归的⼼情: 只关⼼什么关系(不⽤想太多)
3. 掌握递归的immutable var 和 迭代的mutable var 区别
4. helper 的作⽤
5. Mutual recursion, 关注轮流的情况, 经典例⼦是fgh函数序列
6. Tree recursion, Tree recursion ⽆法优化, 经典是DP的递归基练习, 钱问题
7. 迭代可以把不变量转为参数从⽽转为递归
设计准则
1. 能抽象, 有必要抽象(封装等⼿段)请抽象, 本课程关注函数抽象
2. 名词和动词的使⽤
3. TDD
抽象
1. 构造器和数据选择器
2. 理解selectors 和properties 的区别(应当提供抽象和接⼝⽽不是内置实现)
3. ⾏为和实现的隔离
4. 理解函数也可以表⽰数据
⾮线性结构
1. ⼴义列表就是树, 理解层次结构, ⼴义表是FP术语
2. 理解数据的闭包属性(递归定义), 对⽐函数式的闭包(即通过变量⽣成函数内常量的⽅法)
3. 熟悉了树形递归的base case编写
4. 了解剪枝是什么(prune)
5. 掌握permutation, 全排列的树状递归和剪枝
打字游戏编写
1. 理解函数抽象对思考解决⼤问题的帮助
2. 理解权值打分机制对程序⾃动决策的作⽤
3. 掌握MED, 最⼩编辑距离的递归写法, 熟悉Leetcode的同题⽬的迭代/DP写法, 后⾯学习尾递归优化后, 练习尾递归写法CS导论杂项
1.  阅读了编码,
2.  理解晶体管是什么, 掌握继电器版本的计算机构造法(略),
3. 了解ASCII是有规律的0x3x是数字.
可变操作和可变数据和可变函数
1. 理解副作⽤和引⽤透明
2. 理解函数式编程的lazy computaion
3. 了解了区间计算中的两个数据有依赖的难题(interval computation)
4. 理解了为什么要有environment 和non-local 等区分.
通过迭代器理解迭代抽象
1. 理解⼀次性导致的迭代器不应该在递归出现
OOP, OOD 以及通⽤的
1. HAS-A, IS-A, LIKE-A 应该使⽤的OOP实现⽅法
1. 学习了EMAIL服务器和客户端的⼗分粗糙的OOP模型
2. 蚂蚁打蜜蜂项⽬: 深⼊理解抽象, 不能打破抽象,
1. 理解什么应该抽象, 怎么抽象(复习⼤⼀JAVA课程)
2. 基类⽅法对继承类来说很重要, 即使使⽤空的基类⽅法
3. 掌握现代OOP语⾔中的迭代器的删除问题(⼗年前的⾯试题?)
1. 练习分解问题的思维(decomposition)
2. 吃⼀堑: while/if/else中出现的提前结束⼀定要return/break!
学习了链表和树结构的⼀些处理, 包括遍历等等.
1. 链表继续熟悉 (都是⽼⽣常谈，对常规的问题再研究⼀些follow up 问题)
2. 树要掌握⼀些树的遍历操作(复习⼀下⼆叉树表⽰的普通树的操作⽅法, 怎么通过操作访问⼆叉树去操作访问树)
3. 复习了⼀遍has_cycle,  现在应该能写has_cycle和entry的follow up了
数学思维与抽象, 代价评估
1. 理解同构是什么
2. 学习了算法和问题也有同构的思想⽅法(神奇的卡特兰数)
3. 掌握使⽤⼆分法求指数的⽅法
LISP 语⾔语法学习
1. LISP (list processing) 的精髓是所有东西都是⼀个 list, procedure 和 data 都是 list.
2. Symbolic Programing, 理解⽤程序编写程序的思想⽅法, 程序⽣成程序也就是 meta programing
3. 所有的 while 都可以转换成⼀个带参数递归函数来编写
4. 再次复习引⽤透明的含义以及Cherch-rosser theorem, ⽆论是 call by value (参数先计算) 还是 call by name (procedure 名 先计
算), 都有参数先计算再计算 procedure 值的顺序 (参数在被传⼊ procedure 计算时先求得参数的值).
控制流的概念
1. 对于连续的控制流, 没有中断和跳转
2. 错误的种类 等
1. runtime
2. syntax
3. value
4. type
程序解释
1. 元语⾔抽象 metalinguistic abstraction 是化解复杂度的⽅法, 通过创建⼀个DSL或者 tailored script 来继续简化表达.
2. 区分语法syntax和语义semantics, ⼀个是建⽴语法树的结构形式, 没有内容, 语义是拥有含义的语法, 语义错误可能是执⾏错误或者类
型错误.
3. ⼀门语⾔必须有⼀个canonical implementation 作为标准, 就是⼀个标准解释器.
4. 解释过程经过lexical ⽂法分析分离关键字, syntactic 语法分析tokens得到表达式(描述语句的结构).
5. token 解析的时候使⽤ buffer 抽象⼀个从输⼊中获取⾏和过滤的⽅法, 避免直接操作字符输⼊缓冲区.
6. 了解递归语法分析和递归下降语法分析, 这要求语⾔是LL(1)⽂法, 具备⼀个递归结构.
7. Homoiconic 同像的概念, Lisp 就是同像的把数据和程序共⽤⼀种列表表述.
8. 语法上可以把表达式分为 primitive expression  和 call expression, 符合递归的分类.
9. ⽤语法树来表达分析结果符合递归的表达式.
10. 递归下降法解释程序, 使⽤ eval 和 apply 实现, 两个函数相互调⽤, 这是因为 eval 的表达式中可能需要 apply, apply 要实现⼜必须
eval 所有的参数以及 proceudre 名字.
11. 栈的实现, 怎么继承命名空间, 最简单的是通过⼀个字典副本.
基本 SQL
课程中练习到的⼀些编程经验归纳⽅便回顾
算法解题
1. GCD 计算⽅法, ⼤数减/模⼩数, ⼩数和结果迭代
2. ⽜顿迭代求零点, ⽤于开⽅可证明. xn+1 = xn - f(xn) - f'(xn)
3. Count-partition 分区递归基础及DP转换, 学习状态转移⽅程, 不关⼼怎么做. 递归解题中 helper 的作⽤.
4. MED, 最⼩编辑距离, 递归解法和 DP 解法, 不遗漏的分类以及等价类简化.
5. Permutaion 学习回溯法中的 state restore
6. Catalan Number 与同构问题分析法.
7. ⼆分法求指数以及memo fib, 学习时空复杂度的优化.
8. 链表判断 has cycle 的双指针法
mutable是什么意思编程要点
1. dependency injection 实现模块分离.
2. decorator 思想来添加功能, 继承的思想, 中间层思想, 兼容思想.
3. 轮流递归 Mutual recursion 的⽤法, 可以实现分类的递归.
4. Data/Function Abstraction 通过抽象减少程序编写的复杂度, 有必要抽象就抽象.
5. 命名⽅法, noun & verb
6. TDD 减少 Debug 烦躁
7. Selectors & properties 辨析, properties 不应该直接访问, 违反了 barrier. 隔离 isolation 的实现
8. 权值评估机制, 如打字游戏 accuracy 定义和 wpm 定义, autocorrect 中 grade system 以及 MED 最⼩编辑距离. 评分机制能⽤来
实现决策.
9. 决策上限 limit , 对于涉及复杂计算的决策过程, 或者是最优化过程, 可以限制最优化程度, 达到⼀个平衡, 平衡最优和性价⽐.
10. Tree 结构的⼦树 pruning 剪枝算法, 以及剪枝对于算法优化, 问题解决的过程中的⼀个尽早抛弃思想.
11. Email server 的 CS 模式, 以及 OOP 编写⼀个 CS 系统的 toy.
12. 模块化设计 modular design 的思想, 减少编写的复杂度, 降低耦合. (模块内⾼内聚)
13. OOP 类设计的⼀些⽅法:
1. 类抽象, 需要⽤什么样的类来表达什么概念, 各种类各⾃要解决什么样的问题, 进⾏什么样的动作.
2. Attributes 的选择, 哪些 atributes 是可变的, 哪些是固有的, 决定是类的变量还是实例的变量. 属性是类内的数据形式, 对外应该
展现为选择器.
3. 基类应该尽可能地提供通⽤的⽅法, 甚⾄是提供空的⽅法, 让⼦类 inherit 或者 override.
BUG FREE 要点
1. TDD
2. while ⾥⾯提前 break 或者 continue (原来我不论在哪都犯这个错误)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。