墨干

简体中文

English

简体中文

English

Appearance

《零基础SICP》公开课 ​

《零基础SICP》面向任何无编程基础、对Scheme和编程的本质感兴趣的小伙伴。

我们期望读者：

  • 具有高中水平的数学基础和英文基础
  • 对操作系统（Windows/macOS/Linux三者之一）有一定了解，能够学会如何打开终端，并使用cd命令切换当前目录

如果您已经学会编程了，《零基础SICP》公开课仍旧值得您花时间观看和学习，您可以通过练习题来判断是否可以直接跳过其中的一些课程。

课件和软件 ​

在墨干中点击帮助->墨客星球，可以找到《零基础SICP》的讲义、课件、练习、勘误等信息。

本课程提供的资料：

相关资料：

有基础SICP第二课 ​

  1. 迭代求和
  2. 线性递归求和
  3. 尾递归
  4. 斐波那契数列
  5. 树形递归和哈希表
  6. 副作用
  7. 函数库
  8. 算法复杂度
  9. 求b的n次幂
  10. 矩阵快速幂
  11. 欧几里得算法

有基础SICP第一课 ​

  1. 编程的基本原理
  2. 表达式的求值
  3. 命名与函数
  4. 代换模型
  5. 条件表达式和谓词
  6. 牛顿法求平方根
  7. 利用函数做抽象

第12课：集合、列表和二叉树 ​

番外：创业中…(｡･ω･｡)ﾉ 菜鸟的第一台Linux笔记本 ​

第11课：符号数据和符号求导 ​

  • B站回放：https://www.bilibili.com/video/BV1r7421Z7p9/?spm_id_from=333.999.0.0&vd_source=316078287b560136fdb78e5901a17e4f

  • 00:31 回顾：通过定义一组逻辑自洽的选择函数和构造函数，定义数据（以有理数为例）。

  • 01:47 辨析：列表 & 单向链表 LISP = list processing

  • 11:15 回顾：语法糖衣

  • 16:04 定义符号数据——构造函数 quote

  • 17:59 自面量在（单次）引用之后，还是自面量。符号在引用之后，则变成了符号数据。

  • 24:02 定义符号数据——选择函数 unquote

  • 27:09 定义符号数据——参数为列表的构造函数

  • 31:34 定义符号数据——在列表中理解选择函数（quote、unquote、quasiquote 综合实例）

  • 36:16 比喻：quote是失重，unquote是加重器，quasiquote是允许里面放加重器的失重器；quasiquote 可译为准引用

  • 39:29 eval 对符号数据求值

  • 40:22 实例：分子分母计算

  • 49:08 用符号数据可以延迟计算

  • 42:46 应用符号数据（实例：符号求导；符号数据可用于构造符号计算系统）

  • 50:08 预告：打造硅基e老师

第10课：函数式编程三板斧-map, filter, fold ​

本期主要内容 ​

  • 01:15 围绕链表（list）结构讨论函数式编程三板斧（映射、过滤、折叠）和衍生算子描述数据处理逻辑，0基础学习软件工程师的底层逻辑

（复习）定义数据：list ​

  • 02:17 list 的构造器：cons、空链表
  • 03:52 list 的选择器：car、cdr、cadr
  • 05:26 list 访问链表的第n个元素（list-ref）
  • 09:43 list 的性质：length、list?、eq?、null?
  • 勘误：list? 无法自己实现，是scheme解释器提供的，和 interger? 类似

三板斧之映射：map ​

  • 17:12 map 是可以接受函数作为参数的高阶函数

三板斧之过滤：filter ​

  • 19:58 filter 在 S7 是没有的，但在 SRFI 中有定义
  • 21:00 filter 的应用
  • 24:32 filter 的实现
  • 25:37 教学代码的漏洞

三板斧之折叠：fold 和 fold-right ​

  • 29:21 fold 的应用，fold 与 fold-right 的区别
  • 31:01 fold 与 fold-right 的实现
  • 34:10 可视化理解 fold 与 fold-right

衍生算子：flatmap ​

  • 43:06 flatmap 的应用，与 map 对比
  • 46:44 在 Scheme 实现类似 Scala 的 flatten

衍生算子：map / filter / flatmap ​

  • 48:21 三板斧应用实例：全排列

总结 ​

  • 54:13 本课总结
  • 55:39 SRFI

第9课：创办一家一周工作四天的公司 ​

沈浪熊猫儿（人类）总结的视频内容：

一、学习小众编程语言，可以找到躺平的机会 ​

  • 00:26 创办一家一周工作四天的公司
  • 01:23 一些使用小众编程语言的公司和场景

二、三鲤的使命、愿景、价值观和四天工作制 ​

  • 04:53 使命是服务科技创新与教育发展
  • 06:28 愿景是定义人类传承、挖掘、创造知识的接口
  • 08:45 团队第一、知行合一、自我成长、传递快乐、独立个体

三、做什么和怎么做 ​

  • 23:21 小e老师主导的项目是计算机代数系统，比如Mathematica（全程录制、全部开源、全靠大家）
  • 30:06 四天工作制的具体规则，周一到周四是工作日，周六和周日是非工作日

第8课：有理数的数据抽象 ​

MathAgape（人类）总结的视频内容

  • 00:11 从本视频开始，进入 SICP 的第二章——构造数据抽象（第一章是构造函数抽象）。本视频对应的是 SICP 2.1.1～2.1.3的内容。

有理数的抽象 ​

  • 01:22 有理数与分式：构造函数、选择函数、显示函数
  • 03:54 有理数的算数运算：分式的加、减、乘、除
  • 06:55 定义分式加：用到 let*、选择函数、构造函数，并用 gcd 处理约分

抽象层级 ​

  • 12:15 接口与实现的分离
  • 16:18 比喻：做蛋挞不必关心先有鸡还是先有蛋
  • 13:43 答疑：浮点数？
  • 18:22 答疑：如何让用户自然语言做计算？（NLP，Torch）

有序对的抽象 ​

  • 22:58 有序对构造器、选择器

链表的抽象 ​

  • 26:24 链表的构造器：()，cons；链表的选择器：car，cdr
  • 27:55 一个特殊的构造器：list

定义数据 ​

  • 35:45 定义数据的一般性步骤：确定逻辑自洽的选择函数和构造函数
  • 37:50 例子：基于皮亚诺公理，定义自然数这种数据

总结 ​

  • 42:14 为什么需要抽象层级？
  • 44:15 Scheme 原语（R7RS small）

答疑、补充 ​

  • 46:14 答疑：关于书上 2.1.3 的代码
  • 51:26 补充：链表本质是递归的嵌套的 pair，即使显示出来看起来是平铺的形式

代码清单 ​

  • 54:01 中文编程与分数的排版显示是如何实现的
  • 58:04 在构造时就化简分数
  • 59:02 架构师与抽象层级

第7课：用高阶函数做抽象-lambda,let ​

MathAgape（人类）总结的视频内容

预热 ​

  • 00:19 用 let 循环一个函数运行多次（这是针对习题1.22-1.24的答疑；有些程序运行一次时间极短，难以统计时间，可用循环很多次的方式解决）
  • 03:55 比较 Python

正课 ​

  • 07:14 本课会替换掉书本上较为复杂的数学例子，让编程教程更易懂
  • 08:43 回顾第一课的观念：编程的基本原理是对数据和计算的组合和抽象（总结，非书上原话）；本课重点：用函数去做计算的组合和抽象
  • 09:18 以求和公式为例，讲解在参数中传递函数值（函数也可作为参数）
  • 12:42 用 lambda 构造匿名函数的好处
  • 14:46 以斐波那契数对，讲解用 let 创建局部变量的好处（避免重复计算，方便修改）
  • 17:36 实例：区间折半法，搜索算法，二分查找法
  • 29:08 实例：寻找不动点（在函数的有限次迭代之后回到相同值的点叫做周期点；不动点是周期等于 1 的周期点）
  • 34:32 总结

答疑 ​

  • 38:32 Scheme 的 let 相当于 Python 的？；宏：let*；let 与 define

第6.2课：时空复杂度习题1.14~1.20讨论 ​

MathAgape（人类）总结的视频内容：

  • 00:22 习题1.14
  • 08:07 习题1.15
    • 08:46 法1:用调试控制台查看计算次数
    • 09:37 法2:用全集变量输出计算次数
    • 13:22 法3:用参数变量模拟全局变量，更符合函数式编程的本意
  • 14:28 习题1.16
    • 14:34 用分段函数表示
  • 19:41 习题1.17
    • 20:22 位运算
    • 31:28 逻辑与
  • 38:12 习题1.18
    • 39:45 矩阵乘法
    • 42:23 用 Octave 插件计算矩阵
    • 45:33 下载 Octave
  • 47:08 习题1.20
    • 51:00 打印应用序求值计算过程次数

第6.1课：时空复杂度随堂练习答疑 ​

MathAgape（人类）总结的视频内容：

  • 00:24 优化 list-min
  • 03:28 实现 append
  • 04:49 比较不同斐波那契算法的时空复杂度，并通过实验比较真实消耗时间（详细讲解了数形递归的时空复杂度如何估算）
  • 15:52 墨干图形编程

第5课：时空复杂度 ​

MathAgape（人类）总结的视频内容：

  • 00:12 介绍我们的官方主页，这里汇总零基础SICP公开课的所有信息：https://mogan.app/zh/guide/SICP.html
  • 02:48 源起杂谈：南京大学的SICP课程（冯新宇）
  • 10:46 本课开始
  • 11:54 什么是正则？
  • 15:42 Θ记法、增长阶
    • 18:00 算法导论对 Θ、O、Ω 的形式化定义
  • 20:22 链表（list）的底层原理
    • 27:30 求链表长度/链表中最小值的时间复杂度
    • 31:46 【练习1:优化 list-min】
  • 34:38 range（n）
    • 37:58 【练习2:用 cons 实现 append】
  • 43:32 求幂算法
    • 44:14 应用序展开，递归，延迟计算，栈，空间复杂度
  • 1:02:04 求幂算法优化方案
  • 1:14:34 最大公约数
    • 1:16:30 【练习3:证明欧几里得算法的复杂度为Θ(log n) 】
  • 1:18:14 总结
    • 1:24:30 【练习4:找到最优化的斐波那契数列，实验看看它在3s内能算到的最大值】
  • 1:30:04 排序算法
    • 1:30:26 不可变结构（immutable）
    • 1:32:42 冒泡排序

第4.2课：递归与迭代 习题1.11~1.13 ​

MathAgape（人类）总结的视频内容：

  • 00:23 习题 1.9 复习
    • 辨析过程（procedure）与计算过程（process）
  • 03:57 习题 1.10 复习
    • 考虑n为非自然数的情况
  • 08:13 习题1.12 杨辉三角
  • 11:48 怎样下载、使用解释器（这次是Windows系统的教程，MacOS 见上期）
  • 22:26 副作用
  • 30:53 在cmd里打印杨辉三角
  • 36:08 练习：写出和书上格式一样居中对齐的杨辉三角】
  • 43:42 在墨干的调试控制台里打印杨辉三角（用for）
  • 55:48 for 循环的定义（宏）
  • 37:42 习题1.13 证明Fib(n)以指数增长
  • 59:53 答疑：习题1.2

注意：这一期中讲到quasiquote，实际上是墨干V1.2.5的一个错误，这个错误我们将在下周一（2024/03/18）之前发布的墨干V1.2.5.1中解决，目前不会影响大家学习SICP第一章的。

第4.1课：递归与迭代 习题1.9~1.10 ​

MathAgape（人类）总结的视频内容：

  • 01:31 复习：代码清单

  • 04:44 技巧：用scheme生成墨干里的树

    scheme
    (stree->tree '
       (tree "a"
          (tree "b")
          (tree "c")))

  • 06:28 习题1.9

    • 用 inc、dec实现加法的两种方式
    • 递归/迭代的计算过程（可参考书上p.21-23）

  • 11:41 习题1.10

    • Ackermann 函数
    • 墨干的可折叠结构（13:04）
      • 插入->可运行->Scheme
      • 通过回车操控折叠

  • 16:09 习题1.13 提示

  • 20:21 怎样下载、使用解释器

  • 20:51 下载地址
  • 20:59 macOS 演示教程
    bash
    ; 首先打开“终端”
cd ; 进入家目录
ls ; 查看家目录

mkdir bin ; 新建文件夹
; 把下载的文件放到 bin 文件夹，可改短文件名为 s7
cd bin
chmod +x s7 ; 添加可执行权限
./s7 ; 运行
ctrl+c ; 退出
touch add.scm ; 创建 scm 文件

; 编辑 scm 文件，例如：
(display (+ 1 1))
(display "\n")

time ./s7 add.scm ; 运行并查看时间

第3课：递归与迭代 ​

MathAgape（人类）总结的视频内容：

  • 00:45 答疑 关于REPL
    • 以文心一言类比REPL
    • 没有REPL的语言？ c语言
    • 编译器与解释器的区别
  • 12:01 复习：条件表达式
    • 应用序求值
    • 短路运算
    • 以围棋类比scheme语言
  • 31:15 循环：求和（书上是阶乘）
    • 伪代码与常规写法（for、set!）
    • 线性递归
    • 线性递归的应用序展开
  • 01:03:00 递归&迭代：斐波那契数列
    • 树形递归
    • 两种迭代法实现
    • 比较三种算法的效率（焦点工具栏->输出选项->显示花费时间）

第2.2课：编程的基本原理 习题1.7~1.9 ​

MathAgape（人类）总结的视频内容：

  • 00:35 习题1.7
    • 关键1：把 good-enough? 的算法从“绝对误差”改成“相对误差”，即可避免被开方数过小或过大导致的问题；
    • 关键2：由于 sqrt 已经在标准库中，做练习时建议起一个新名字如 sqrt-new，以免混淆
  • 06:40 开发技巧：如何一次性执行全部代码，而不是一个个回车
    • 方法1：转成 .scm 文件，再使用“调试控制台”或“终端”查看
    • 方法2：焦点工具栏：求值->全部求值
  • 16:48 如何交作业
    • 文件->导出->可编辑PDF（方便我们在邮箱预览）
  • 24:47 习题1.9
    • 预热讨论：什么是inc、dec；什么是寄存器

第2.1课：编程的基本原理 习题1.1~1.8 ​

  • B站回放: https://www.bilibili.com/video/BV1kU421d7jz/
  • 操作系统: macOS 13 (M1芯片)
  • 墨干版本：v1.2.4
  • 内容：第一章第一节的练习题
  • 勘误：习题1.7的讲解有误，正确思路是：把绝对误差的算法改成相对误差。

第1课：编程的基本原理 ​

  • B站回放：https://www.bilibili.com/video/BV1cp421f7xP/
  • 操作系统：macOS 13 (M1芯片)
  • 墨干版本：v1.2.4
  • 内容
    • 表达式
    • 命名与环境
    • 组合式的求值
    • 复合函数
    • 函数应用的代换模型
    • 条件表达式和谓词

第0课：准备Scheme编程的环境 ​

  • B站回放：https://www.bilibili.com/video/BV1CK421y77g/
  • 操作系统：UOS 1050 (龙芯3A5000)
  • 墨干版本：v1.2.4
  • 内容：
    • 如何下载安装墨干
    • 如何在墨干中插入Scheme会话
    • 如何通过帮助->墨客星球找到《零基础SICP》的交互式讲义、课件、练习、代码清单

享受探索科学与技术的乐趣！

版权所有 © 2022-2024 墨干贡献者