Skip to content

《零基础SICP》公开课

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

我们期望读者:

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

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

课件和软件

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

本课程提供的资料:

相关资料:

第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》的交互式讲义、课件、练习、代码清单

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