Doraemonzzz

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十六讲，这一讲介绍了常微分方程（ODE）。 Chapter 常微分方程基本理论ODE的基本形式如下： \begin{aligned} \text { Find } &f(t) : \mathbb{R} \rightarrow \mathbb{R}^{n} \\ \text { Satisfying }& F\left[t, f(t), f^{\prime}(t), f^{\prime \prime}(t), \ldots, f^{(k)}(t)\right]=0 \\ \text { Given } &f(0), f^{\prime}(0), f^{\prime \prime}(0), \ldots, f^{(k-1)}(0) \end{aligned}我们讨论的ODE主要是显式的，定义如下： 定义 13.1 (显式ODE)我们称ODE是显式的，如果能写成如下形式： f^{(k)}(t)=F\left[t, f(t), f^{ ...

这次回顾第三章的内容，这部分主要介绍了时序门，寄存器，内存以及计数器的概念。 课程官网： https://www.nand2tetris.org/ 视频地址： https://www.coursera.org/learn/build-a-computer Chapter 3 时序逻辑Part 1：课程回顾之前两章介绍的芯片都是组合芯片（combinational logic），这些芯片的特点是和时间无关。这一讲引入时序芯片（sequential logic），之所以引入时序芯片，是为了构建能够记忆“信息”的芯片，而记忆必然是之前的，所以我们首先需要开发一些表示时间的芯片。 触发器（Flip-Flop）计算机中最基本的时序单元是触发器（Flip-Flop），其实现的功能为 \text{out}(t)=\text{in}(t-1)本课程中我们使用名为数据触发器（data flip-flops）的变体，其架构和输入输出如下： DFF可以由与非门（NAND）实现，方法比较复杂，老师表示本课程略过这点，所以时序芯片的基本单元为DFF，其余常用的芯片都在Project中有详细介绍。 Part ...

最近碰到一个调和级数有关的问题，挺有意思的，这里记录一下，题目来自Mit公开课Session 23。 问题假设一个人在沙漠里探险，他随身最多携带$1$加仑水，行走一天需要消耗$1$加仑水（为方便讨论，假设一天行走的距离为$1$），但是可以在任意地点存储水，到达任意一个地点后需要返回，例如携带$1$加仑水最多到达距离出发点$\frac 12 $的位置，因为需要来回。假设最开始他在起始点$A$并且$A$处的水无限，现在问此人能否走到离$A$任意远的地方？ 考虑$A$处有$n$加仑水，其能够行走的距离，其中$n\in \mathbb N$。 当$n=1$时，由提示可知最远距离为$\frac 12 $；当$n\ge 2$时，考虑出发点为$n$加仑水和出发点为$n-1$加仑水的关系，思路如下： 首先想办法存储$n-1$加仑的水，假设存储点距离出发点为$a$，那么来回一次可以存储的加仑数为 1-2a假设来回$k$次，那么总共存储的加仑数为 k(1-2a)要使得上式为$n-1$，可取 k=n ,a=\frac 1 {2n}即缓存点距离出发点的距离为$\frac 1{2n}$。注意最后一次运水 ...

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十五讲，这一讲介绍了数值积分和微分。 Chapter 12 数值积分和微分积分首先讨论一元函数求积分的问题，即 f:\mathbb R\to \mathbb R我们的目标是求 I(f)=\int_a^b f(x)dx这里有两个假设： $a,b$固定。 可以计算$f(x)$任意一点的值。 插值求积因为定积分是由黎曼和定义的，即 \int_{a}^{b} f(x) dx=\lim _{\Delta x_{k} \rightarrow 0} \sum_{k} f\left(\tilde{x}_{k}\right)\left(x_{k+1}-x_{k}\right)其中 \begin{aligned} &1.a=x_{1}

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十三讲，这一讲介绍了插值。 Chapter 11 插值之前讨论了函数求根以及极值的问题，但是在实际中函数常常未知，所以就要根据已有的值估计未知的值，这就是这一讲插值所需要解决的问题。 单变量插值首先讨论单变量的插值问题，首先给出问题的形式： f:\mathbb R\to \mathbb R 是单变量函数，已知(x_i,y_i),i=1,\ldots ,k,y_i =f(x_i)\\ 计算f(x), x\neq x_i ,i=1,\ldots ,k这里假设 x_1

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十三讲，这一讲完整介绍了共轭梯度法。 首先回顾梯度下降的残差： \vec{r}_{k} = \vec{b}-A \vec{x}_{k}下面讨论$\vec r_{k+1}$和$\vec r_k$的关系。我们知道更新公式为 \vec{x}_{k+1}=\vec{x}_{k}+\alpha_{k+1} \vec{v}_{k+1}其中 \alpha_{k+1}=\frac{\vec{v}_{k+1}^{\top} \vec{r}_{k} }{\vec{v}_{k+1}^{\top} A \vec{v}_{k+1} }那么$\vec r_{k+1}$计算方式如下： \begin{aligned} \vec{r}_{k+1} &=\vec{b}-A \vec{x}_{k+1} \\ &=\vec{b}-A\left(\vec{x}_{k}+\alpha_{k+1} \vec{v}_{k+1}\right) \\ &=\left( ...

这次回顾第二章的内容，这部分主要介绍了布尔运算，讲解了如何实现二进制加法，负数的表示以及算数逻辑单元（ALU）。 课程官网： https://www.nand2tetris.org/ 视频地址： https://www.coursera.org/learn/build-a-computer Chapter 2 布尔运算Part 1：课程回顾这部分回顾一些重点内容。 二进制加法来看一个二进制加法的例子： 从上述例子不难看出，最后一位只要考虑两个数相加的问题，处理这部分使用HalfAdder，接口如下： 除最后一位以外，其余每一位还要考虑前一位的进位问题，所以要处理三个数相加的问题，处理这部分使用FullAdder，接口如下： 最后要注意计算机存储数字的位数是固定的，如果超过这个范围，就会产生溢出： 处理方法是直接不考虑溢出位。假设计算机存储的位数为$n$，那么$x+y$的结果为 (x+y)\mod 2^n负数一个比较关键的问题是如何在计算机中表示负数，一个直接的想法是用第一位表示符号，$0$表示正数，$1$表示负数，但是这样$0$会有两个表示： 0000,1000并且 x ...

这周开始学习From Nand to Tetris，中文名为“依据基本原理构建现代计算机：从与非门到俄罗斯方块”，课程介绍了计算机的工作原理，每周有一个项目，完成课程之后，可以真正构建出一个可以运行的计算机，课程也没有太多的先修课程，只要学过任何一门编程语言即可。 课程官网： https://www.nand2tetris.org/ 视频地址： https://www.coursera.org/learn/build-a-computer Chapter 1 布尔逻辑Part 1：课程回顾第一讲的内容比较基础，下面回顾几个重点部分： Bool逻辑与Bool函数课程首先介绍Bool逻辑的常用性质，这里假设我们只使用$\text{And,Not,Or}$操作。比较关键的一点是Bool表达式对应了真值表，例如 f(x, y, z) = (x\text{ And }y)\text{ Or }(\text{Not}(x)\text{ And }z)对应了 $x$ $y$ $z$ $f$ 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 ...

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾作业5。 Problem 1(a) \begin{aligned} \nabla_{\vec x} f(\vec x) &= A\vec x -\vec b\\ \nabla_{\vec x}^2 f(\vec x) &=\nabla(A\vec x -\vec b)\\ &= A^T\\ &=A \end{aligned}令第一个式子为$\vec 0$可得 \vec x' =A^{-1} \vec b因为$A$正定，所以$\vec x’ ​$是极小值点。 (b)首先考虑如何将两个向量变成$A-$共轭，假设两个向量为$\vec v_1, \vec v_2$，取$\vec w_1=\vec v_1$，设 \vec w_2 =\vec v_2 -\alpha \vec w_1要使得$\vec w_1, \vec w_2​$为$A-​$共轭，那么 \begin{aligned} \langle \vec w_2, \vec w_1 ...

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十二讲，这一讲介绍了迭代法求解线性系统的思路，引出了共轭梯度法的思想。 优化算法序列二次规划回顾之前介绍的优化问题： \begin{aligned} \text { minimize }& f(\vec{x}) & \\ \text { such that } & g(\vec{x})=\vec{0} \\ &h(\vec{x}) \geq \vec{0} \end{aligned}现在讨论如何使用迭代算法求解，首先对目标函数和条件使用泰勒展开： \begin{aligned} f(\vec x_{k+1})&\approx f(\vec x_k)+\frac{1}{2} \vec{d}^T H_{f}\left(\vec{x}_{k}\right) \vec{d}+\nabla f\left(\vec{x}_{k}\right) \cdot \vec{d}+f\left(\vec{x}_{k}\right) \\ g_{i ...

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾第十一讲，这一讲介绍了BFGS和KKT条件。 黄金分割搜索定义8.5 (Unimodular) 函数f:[a,b]\to \mathbb R是\text{unimodular}，如果存在x' \in [a,b]使得f在[a,x']递增，在x\in [x',b]递减下面讨论如何求满足unimodular性质的函数$f$的最小值$x’​$，首先不难想象这种函数的图像是U字型的，所以可以使用类似二分法的思路求解。 假设我们有两个点$a<x_0<x_1<b​$，接下来分两种情形讨论： 如果$f(x_0 )\ge f(x_1)$，那么对$x\in [a, x_0]$，我们有$f(x)\ge f(x_1)$，最小值点$x’ \in [x_0, b]$，所以删除区间$[a, x_0]$ 如果$f(x_1 )\ge f(x_0)$，那么对$x\in [x_1, b]$，我们有$f(x)\ge f(x_0)$，最小值点$x’\in ...

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html 这次回顾作业4。 Problem 1(a)假设 \begin{aligned} \Delta J&= J_k -J_{k-1}\\ \Delta \vec x&= \vec x_k -\vec x_{k-1}\\ \vec d &= f(\vec x_k) -f(\vec x_{k-1}) -J_{k-1}\Delta \vec x \end{aligned}那么原问题可以化为如下形式： \begin{aligned} \min_{\Delta J}&\ \Arrowvert \Delta J\Arrowvert^2_{\text{Fro}}\\ \text{such that}&\ \Delta J.\Delta \vec x =\vec d \end{aligned}构造拉格朗日乘子： \Lambda =\Arrowvert \Delta J\Arrowvert^2_{\text{Fro}} + \vec \lambda^T(\D ...