Doraemonzzz

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://cs170.org/assets/pdf/hw09-sol.pdf 吴彧文（atyuwen）Algorithms.Exercises.solution 这次回顾HW10。 2. Existence of Perfect Matchings参考： https://cs170.org/assets/pdf/hw09-sol.pdf 证明： $\Rightarrow$： 如果$G$有一个完美匹配，那么对于任意$X\subseteq L$，存在$Y\subseteq R,|Y|=|X|$，使得$X$和$Y$相连（利用该完美匹配的一部分即可）。 $\Leftarrow$： 依然使用吴彧文（atyuwen）Algorithms.Exercises.solution 7.23的图： 按照之前的方式增加$S,T$，对于任意Cut $C$ ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 10。 1. NP Basics 无法判断$B$ $A$属于$\mathrm P$ $B$属于$\mathrm{NP-hard}$ 无法判断$A$ 2. Hitting Set下面证明顶点覆盖问题可以规约到此问题。 对于图$G(V,E)$以及顶点$v$，构造集合 S_{(u,v)}=\{u,v\}那么该集合族大小小于等于$b$的Hitting Set即为原问题大小小于等于$b$的顶点覆盖，这是因为Hitting Set为$S=\{v_1,\ldots,v_n\}$，该顶点集合和每个$S_{(u,v)}$（边）都有交点。 3. Reliable Network此题参考了习题解答。 下面证明Rudrata问题可以规约到Reliable Network问题。 取 $b=n$ 最多$n$条边 $d_{ij}=1,(i,j)\ ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾HW9。 2. A cohort of spies最大流问题： 顶点：起点$s$，间谍的出发城市$\cup \{s_i\}$，安全城市$T$，终点$t$ 边：分为三部分 起点：$(s ,s_i)$ 逃生路径：$(s_i,t_j)$ 终点：$(t_i,t), t_i \in T$ 容量： 起点：$c(s, s_i)=c$ 逃生路径：$c(s_i,t_j)=c$ 终点：$c(t_i,t)=c$（这样可以保证不会有超过$c$个人通过每个安全城市） 3. Max Flow, Min Cut, and Duality(a)对偶问题： \begin{aligned} \min\quad & 7x_1 + 5x_2+ 4x_3 + 4x_4 + 7x_5\\ & x_1+x_3 \ge 1\\ &x_1 +x_4+x_5\ge 1\\ &x ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： 吴彧文（atyuwen）Algorithms.Exercises.solution 这次回顾Section 9。 1. Maximal Matching假设maximal匹配的边集合为 E^1= \{(u_1^1,v_1^1),\ldots,(u_n^1,v_n^1)\}maximum匹配的边集合为 E^2= \{(u_1^2,v_1^2),\ldots,(u_m^2,v_m^2)\}任取$e=(u,v)\in E^1$，或者$e\in E^2$，或者$e\not \in E^2$，对于第二种情形，$E^2$中必然存在一条边包含$u$或$v$，这是因为如果该条件不满足，则$E^2$中可以添加$e$，这就与maximum匹配的定义矛盾。 因此$E^1$中的每一条边或者和$E^2$中一条边对应，或者和$E^2$中两条边对应，假设这两种情形 ...

这次回顾第四章第一部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest http://community.schemewiki.org/?SICP-Solutions http://community.schemewiki.org/?sicp 4.1(p255 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs 这次回顾HW8。 2. Jeweler(a)假设生成$x$个项链，$y$个戒指，那么线性规划问题为 \begin{aligned} \max\quad &60 x + 30y \\ & 4x +y\le 80\\ & 2x + 3y \le 90\\ & x \ge 0\\ &y \ge 0 \end{aligned}顶点以及对应的利润为（这里假设项链的利润为$C$） $x$ $y$ 利润 0 80 2400 0 3 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 8。 1. Taking a Dual对偶问题为 \begin{aligned} \min &&10y_1+14y_2 + 11y_3\\ && y_1 +3y_2+2y_3 &\ge 4\\ && 2y_1+ y_2+3y_3&\ge 7\\ && y_1,y_2,y_3\ge 0 \end{aligned}2. Weighted Rock-Paper-Scissors(a) r p s r 0 -5 3 p 5 0 -1 s -3 1 0 (b)假设策略为$(x_1,x_2,x_3)$，那么LP问题为 \begin{aligned} \max\ & z\\ &z\le 5x_2-3x_3\\ &z \le -5x_1+x_3\\ &z\le 3x_1-x_2\\ & x_1\ge 0\ ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾寄存器分配。 寄存器分配问题 中间代码使用无限的临时变量 简化代码生成和优化 但是复杂化翻译为汇编的步骤 典型的中间代码使用过多的临时变量 问题： 重写中间代码以使用不超过机器寄存器的临时变量 方法： 为每个寄存器分配多个临时对象 但不更改程序行为 例子 考虑程序 \begin{aligned} a &:= c + d\\ e &:= a + b\\ f &:= e - 1 \end{aligned} 可以将$a,e$和$f$全部分配给一个寄存器($r_1$)： \begin{aligned} r_1 &:= r_2 + r_3\\ r_1 &:= r_1 + r_4\\ r_1 &:= r_1 - 1 \end{aligned} 这里假设使用后$a,e$变成dead dead临时变量可以“重用” 历史 寄存器分 ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾全局优化。 数据流分析简介 回顾简单的基本块优化 常数传播 消除死亡代码 \begin{aligned} \begin{aligned} &\mathrm{X:=3} \\ &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=X +Y } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{X:=3} \\ &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=3 +Y } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=X +Y } \end{aligned} \end{aligned} 这些优化可以扩展到整个控制流图 ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾局部优化。 中间代码简介中间代码是 源代码和目标代码之间的语言 提供中间级别的抽象 比源语言更多的细节 比目标代码更少的细节 中间语言 = 高级汇编 使用寄存器名称，但数量不受限制 使用汇编语言之类的控制结构 使用操作码，但有些是更高级别的 例如，push转换为多个汇编指令 大多数操作码直接对应于汇编操作码 例子 每条指令的格式均为 \begin{array}{l} \text{x:=y op z} \\ \text{x:=op y} \end{array} $\mathrm y$和$\mathrm z$是寄存器或常量 这是中间代码的常见形式 表达式$\mathrm{x + y \star z}$被翻译为 \begin{array}{l} \mathrm{t_{1}:=y\star z} \\ \mat ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾操作语义。 语义概述 我们必须为每个Cool表达式指定在求值时会发生什么 这是表达的“含义”。 编程语言的定义： token对应词法分析； 语法对应句法分析； 类型规则对应语义分析； 评估规则对应代码生成与优化。 我们其实间接指定了评估规则： 将Cool编译为堆栈机； 然后利用堆栈机的评估规则。 该评估规则这是完整的描述 但是为什么不够好？ 实现语言的汇编语言描述有不相关的细节，例如 是否使用堆栈机？ 堆栈以哪种方式增长？ 如何表示整数？ 体系结构的特定指令集。 我们需要完整的描述 但不是过于严格的规范。 指定语义有许多方法 它们同样强大 适用的场景不同 操作语意 通过执行规则描述程序评估 在抽象机器上 对特定实现最有用 这就是我们用于Cool的语义描述 指定语意的方法 指称语义（Denotationa ...

这次回顾第三章第八部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest http://community.schemewiki.org/?SICP-Solutions http://community.schemewiki.org/?sicp 3.73(p23 ...