# 现代编程思想 接口 Hongbo Zhang ## 回顾 ## • 第六课：定义平衡二叉树 我们定义一个更一般的二叉搜索树，允许存放任意类型的数据 1. enum Tree[T] { 2. Empty 3. Node(T, Tree[T], Tree[T]) 4. } 5. 6. // 我们需要一个比较函数来比较值的大小以了解顺序 7. // 负数表示小于，0表示等于，正数表示大于

现代编程思想 案例：自动微分 Hongbo Zhang ## 微分 • 微分被应用于机器学习领域 ◦ 利用梯度下降求局部极值 牛顿迭代法求函数解： $ x^{3}-10x^{2}+x+1=0 $ • 我们今天研究简单的函数组合 ○ 例： $ f(x_{0},x_{1})=5x_{0}^{2}+x_{1} $ ■ $ f(10,100)=600 $ ■ $ \frac{\partial ■ 缺点：计算机无法精准表达小数，且绝对值越大，越不精准 符号微分：Mul(Const(2), Var(1)) -> Const(2) ■ 缺点：计算结果可能复杂；可能重复计算；难以直接利用语言原生控制流 1. // 需要额外定义原生算子以实现相同效果 2. fn max[N : Number](x : N, y : N) -> N { 3. if x.value() < ■ 缺点：计算机无法精准表达小数，且绝对值越大，越不精准 符号微分：Mul(Const(2), Var(1)) -> Const(2) ■ 缺点：计算结果可能复杂；可能重复计算；难以直接利用语言原生控制流 ◦ 自动微分：利用复合函数求导法则、由基本运算组合进行微分 ■ 分为前向微分和后向微分 ## 符号微分 ## • 我们以符号微分定义表达式构建的一种语义 1. enum Symbol

## 现代编程思想 ## 案例：基于梯度下降的神经网络 Hongbo Zhang ## 案例：鸢尾花 • 鸢尾花数据集是机器学习中的"Hello World" ☐ 1936年发布 包含对3种鸢尾花的测量，各有50个样本 ☐ 每个样本包含4项特征：花萼与花瓣的长度和宽度 目标 ☐ 通过特征，判断属于哪一类鸢尾花 ◦ 构建并训练神经网络，正确率95%以上 ## 神经网络

## 现代编程思想 案例：栈式虚拟机 Hongbo Zhang ## 编译与解释 ## • 编译 ☐ 源程序 x 编译器 -> 目标程序 ☐ 目标程序 x 输入数据 -> 输出数据 ## • 解释 ☐ 源程序 x 输入数据 x 解释器 -> 输出数据 ☐ CPU可以被视为广义上的解释器 • 拓展阅读：二村映射/部分计算 ◦ 部分计算：程序优化，根据已知信息，运算进行特化

现代编程思想 # 函数, 列表与递归 Hongbo Zhang 基本数据类型：函数 ## 函数 - 在数学上，描述对应关系的一种特殊集合。对于特定的输入，总是有特定的输出 - 在计算机中，对相同运算的抽象，避免大量重复定义 ○ 计算半径为1的圆的面积： $ 3.1415 \times 1 \times 1 $ ○ 计算半径为2的圆的面积： $ 3.1415 \times 2 \times

现代编程思想 命令式编程 Hongbo Zhang ## 函数式编程 - 到此为止，我们介绍的可以归类于函数式编程的范畴 - 对每一个输入，有着固定的输出 对于标识符，我们可以直接用它所对应的值进行替代——引用透明性 • 开发实用的程序，我们需要一些计算之外的“副作用” ☐ 进行输入输出 ☐ 修改内存中的数据等 ☐ 这些副作用可能导致多次执行的结果不一致 ## 引用透明性 let t = acc1 + acc2 5. acc1 = acc2; acc2 = t 6. } 7. acc1 8. } ## 总结 本章节初步接触了命令式编程，包括 • 如何使用命令 • 如何使用变量 • 如何使用循环等

现代编程思想 哈希表与闭包 Hongbo Zhang ## 回顾 ## · 表 键值对的集合，其中键不重复 简单实现：二元组列表 - 添加时向队首添加 - 查询时从队首遍历 树实现：二叉平衡树 - 基于第五节课介绍的二叉平衡树，每个节点的数据为键值对 - 对树操作时比较第一个参数 ## 哈希表 - 哈希函数/散列函数 Hash function ◦

现代编程思想 # 泛型与高阶函数 Hongbo Zhang ## 设计良好的抽象 - 软件工程中，我们要设计良好的抽象 - 当代码多次重复出现 ☐ 当抽出的逻辑具有合适的语义 - 编程语言为我们提供了各种抽象的手段 - 函数、泛型、高阶函数、接口..... ## 泛型函数与泛型数据 ## 堆栈 - 栈是一个由一系列对象组成的一个集合，这些对象的插入和删除遵循后进先出原则（Last

# 现代编程思想 多元组，结构体与枚举类型 Hongbo Zhang 基础数据类型：多元组与结构体 ## 回顾：多元组 • 多元组：固定长度的不同类型数据的集合 ☐ 定义： $ (\leq $ 表达式 $ \gt $ , $ \leq $ 表达式 $ \gt $ , $ \geq $ ) ☐ 类型：(<表达式类型>，<表达式类型>，...) ○ 例如： ■ 身份信息：("Bob"

## 现代编程思想 队列：可变数据结构实现 Hongbo Zhang ## 队列 - 我们曾经介绍过队列这个数据结构 - 先进先出 ☐ 利用两个堆栈进行实现 - 我们利用可变数据结构进行实现 - 基于数组的循环队列 ☐ 单向链表 ## 队列 • 我们实现以下函数（以整数队列为例） 1. struct Queue { ... } 2. 3. fn make() ->