Tags:

细说红黑树(1)-核心定理

Written on October 7, 2016

我一直觉得那些著名的数据结构,都是工程设计和数学的完美结合。

所有的数据结构都是被精心设计出来的,此所谓工程设计。但是,既然叫精心设计,就意味着有一套准则,这个准则就是数学。

没有数学基础的数据结构都是耍流氓。

红黑树拥有精巧的结构设计和强大的数学基础,但我总觉得有点过于复杂,故写本文来回顾总结下。

Read More

立体角(Solid Angle)详解

Written on July 9, 2016

理解立体角之前要先理解圆心角。在二维平面上,一个圆的圆弧的微分记为ds(也叫弧微分),半径为r,则圆心角指的是弧微分与半径的比值:

\[ d\theta = \frac {ds}{r} \]

Read More

线性代数之主成分分析(PCA)算法

Written on May 30, 2016

PCA(Principal Component Analysis)的主要应用场景是:在大数据集中找出关键的信息并剔除冗余的信息。根据这个特性,PCA也可以用来做信息压缩(有损)、特征提取。不过在本文中,只会对PCA的数学原理进行阐述。

另外,PCA可以说是Machine Learning领域的自编码机(AutoEncoder,AE)的基础。主要区别在于,PCA是线性算法,而AE则不一定。所以在学习AutoEncoder之前,有必要先将PCA搞清楚。

Read More

线性代数之伪逆矩阵(pseudoinverse matrix)

Written on May 29, 2016

众所周知只有方阵才有逆矩阵,非方阵没有逆矩阵。这个不和谐的问题已在20世纪初被数学家E. H. Moore等人解决掉了,因为他们发明了一般化的逆矩阵(generalized inverse),也称为伪逆矩阵(Moore–Penrose pseudoinverse)

Read More

矩阵微分(一)

Written on May 8, 2016

基本认识

3种标准导数(梯度)公式

1) 自变量是一个数值量(Scalar)时:

\[ Df(x) = \lim _{t\to 0} \frac {f(x+t)-f(t)}{t} \]

2) 自变量是一个向量(Vector)时:

\[ D_{\textbf {w}}f(\textbf {x}) = \lim _{t\to 0} \frac {f(\textbf {x} + t\textbf {w}) - f(t)}{t} \]

Read More

最小二乘估计(Least Squares Estimator)的公式的推导

Written on May 6, 2016

最近在学习ML(Machine Learning),注意到了一个有趣的东西:Least Squares Estimator

先从简单说起吧。看下面的式子:

\[ y = ax + e \]

这是一个非常简单的直线方程。如果赋予y、a、x、b具体的意义,这个式子就有意思了:

  1. 假设x是一个统计变量(预先就知道的),譬如,x代表人的年龄。

  2. 假设y是关于x的一个label量(预先就知道的),譬如,y代表的是年龄为x时的人的智商。

Read More

线性代数之视角矩阵Lookat Matrix

Written on March 20, 2016

引言

我对视角矩阵的理解是这样子的,假设3维空间有一个观察者(摄像机),这个观察者必然有它的坐标位置、视角、焦点,根据这3个参数,可以建立一个正交化、规范化的坐标系(一个正交化、单位化的3x3矩阵),这个坐标系对应的矩阵就是Lookat矩阵。

Read More

《OpenGL编程指南(第8版)》阅读笔记01

Written on February 21, 2016

Example源码Bug备忘

第三章

ch03_drawcommands

    glUniformMatrix4fv(render_model_matrix_loc, 4, GL_FALSE, model_matrix);

应改为:

    glUniformMatrix4fv(render_model_matrix_loc, 1, GL_FALSE, model_matrix);

原因:

void glUniformMatrix4fv(GLint location, GLsizei count, GLboolean transpose, const GLfloat *value);

Parameters

location

Specifies the location of the uniform value to be modified.

count

Specifies the number of matrices that are to be modified. This should be 1 if the targeted uniform variable is > not an array of matrices, and 1 or more if it is an array of matrices.

transpose

Specifies whether to transpose the matrix as the values are loaded into the uniform variable. Must be GL_FALSE.

value

Specifies a pointer to an array of count values that will be used to update the specified uniform variable.

因为例子使用的是primitive_restart.vs.glsl顶点着色器,model_matrix不是数组,所以参数count应该为1。

还发现了一句注释: // "model_matrix" is actually an array of 4 matrices

不明白为什么model_matrix会是一个包含4个矩阵的数组。并且确实改成1后就能运行了。

(后面发现有一个shader里面的model_matrix确实是一个长度4的数组...估计是混淆了吧)

真是坑。

vmath

vmath::rotation 要改为 vmath::rotate vmath::translation 要改为 vmath::translate

绝对路径....

ch03_instancing的Initialize函数里:

    // Load the object
    object.LoadFromVBM("C:/Vermilion-Book/trunk/Code/media/armadillo_low.vbm", 0, 1, 2);

太坑了。

把vs和fs写在cpp文件里

如果是为了演示如何手动编译shader,也不用放在多个example里吧。

第四章

ch04_shadowmap的vbm.h和vbm.cpp是不对的,运行会出错

换成第三章的工程里的就OK了。

Read More

曲线数学之B样条曲线B-Spline

Written on December 29, 2015

上一篇文章已经介绍了贝塞尔曲线。本篇文章接着介绍B样条曲线。

B样条曲线,简单来说,它是对贝塞尔曲线的一个补充。为什么这样说呢?是因为贝塞尔曲线某些情况下不实用:曲线上每个点受所有控制点影响,这会给调整曲线工作带来麻烦。可以想到的第一个优化是,把整个贝塞尔曲线变成多段贝塞尔子曲线的拼接。然而,这个方案也不好用,因为拼接工作很难做好,因为要拼接曲线显得“光滑”前提是保证相邻曲线之间的连续性。

于是,老外发明了一个算法:De Boor's algorithm,基于这个算法的曲线也被称为贝塞尔曲线的变种:B-Spline(B样条)曲线。为什么叫Spline曲线呢?我猜是因为Spline曲线在4个控制点的情况下,有个典型的形状:

Read More

线性代数之Cholesky分解

Written on December 19, 2015

又到了矩阵分解时间。这次介绍的是Cholesky分解。这个方法只适用于符合厄米特矩阵、正定矩阵定义的矩阵。

算法原理

设A是一个n阶厄米特正定矩阵(Hermitian positive-definite matrix)。

Cholesky分解的目标是把A变成:

\[ A = LL^{T} \]

L是下三角矩阵。

Read More

线性代数之逆矩阵

Written on December 19, 2015

逆矩阵是一个很基本的概念,这里就不说定义了。本文只介绍求解方法。

初等变换求逆法——高斯消元法(Gauss-Jordan elimination)

先在要求解逆矩阵的A的右边增加一个临时的单位矩阵(阶数显然和A一致)。那么A就变成了一个n行、2n列的矩阵A'。 然后对A'进行高斯消元,也就是通过row operation不断对A'做变换,直到A'的左边的A变成单位矩阵时,A'的右边部分就是A的逆矩阵了。 要注意的是,A不一定有逆矩阵,当A没有逆矩阵时,这个高斯消元过程中肯定会出现A的某row全是0的情况。

Read More

《Effective Modern C++》读书笔记

Written on November 8, 2015

Note:为避免各种侵权问题,本文并没有复制原书任意文字(代码除外,作者已经声明代码可以被使用)。需要原书完整中文翻译的读者请等待官方译本的发布。

Read More

线性代数之奇异值(SVD)分解

Written on October 27, 2015

在线性代数中,SVD(Singular Value Decomposition)是对实数矩阵(甚至复数矩阵)的一种因式分解。在信号、统计、图像图形学中都有应用。

SVD非常强大且实用,因为数学界前辈已经证明任意的一个矩阵都可以做SVD分解。这一点特别重要,因为相比SVD分解,和SVD相近的特征值分解只能应用于方阵。

第二个重要的点是:SVD分解可用来解决非方阵不能计算逆矩阵的问题。

Read More

理解卷积 Convolution

Written on October 18, 2015

数学中的卷积

卷积的wiki:Convolution

卷积和(convolution sum)的公式是:

\[ y(t) = x(t)*h(t) = \sum _{\tau =-\infty }^{\infty }x(\tau )h(t-\tau )\]

写成积分形式是:

Read More

gcc-4.9.3 编译过程笔记

Written on October 15, 2015

官方的编译指南:https://gcc.gnu.org/install/

唠叨几句

之前升级了我的阿里云的gcc,记得是费了些功夫的,有些坑。可惜忘了记笔记。今天编译node.js时发现我编译的gcc有些问题,要重新编译下,悲催的是gcc的编译目录都删掉了。全部得重来过。

Read More

线性代数之TRS分解

Written on October 5, 2015

pbrt的TRS分解

设矩阵A,假设A可以分解成T、R、S,则有A=TRS,设A:

\[ A = \left[ \begin{matrix} A_{11}&A_{12}&A_{13}&A_{14}\\ A_{21}&A_{22}&A_{23}&A_{24}\\ A_{31}&A_{32}&A_{33}&A_{34}\\ A_{41}&A_{42}&A_{43}&A_{44}\\ \end{matrix} \right] \]

再设T、R、S分别为:

\[ T = \left[ \begin{matrix} 1&0&0&t_{x}\\ 0&1&0&t_{y}\\ 0&0&1&t_{z}\\ 0&0&0&1\\ \end{matrix} \right] \]

\[ R = \left[ \begin{matrix} r_{11}&r_{12}&r_{13}&0\\ r_{21}&r_{22}&r_{23}&0\\ r_{31}&r_{32}&r_{33}&0\\ 0&0&0&1\\ \end{matrix} \right] \]

\[ S = \left[ \begin{matrix} s_{x}&0&0&0\\ 0&s_{y}&0&0\\ 0&0&t_{y}&0\\ 0&0&0&1\\ \end{matrix} \right] \]

Read More

线性代数之各种各样的矩阵

Written on October 5, 2015

矩阵家族成员非常多,本文主要记录了我遇到过的矩阵(前面的文章所提到的矩阵,在这里就不重复列举了)。以后见识了新的矩阵时,会继续扩充本文。

(以下知识均查阅了wikipedia。单词的中文翻译查的是有道词典。)

Read More

Understanding Quaternions 中文翻译《理解四元数》

Written on September 30, 2015

原文地址:http://www.3dgep.com/understanding-quaternions/

正文

在这篇文章中我会尝试用简单的方式去解释四元数的概念,即用可视化的方式解释四元数以及几种对四元数的操作。我将把矩阵、欧拉角和四元数放在一起比较,并解释什么时候该用四元数、什么时候该用欧拉角或矩阵。

内容结构

  • 介绍
  • 复数
    • 复数的加减
    • 复数的系数缩放
    • 复数的积
    • 复数的平方
    • 共轭复数
    • 复数的绝对值
    • 两复数的商
  • i的幂
  • 复数平面
    • 旋转数(Rotors)
  • 四元数
    • 作为有序数的四元数
    • 四元数的加减
    • 四元数的积
    • 实四元数
    • 四元数的系数缩放
    • 纯四元数
    • 四元数的加法形式
    • 单位四元数
    • 四元数的二元形式
    • 共轭四元数
    • 四元数范数
    • 四元数规范化
    • 四元数的逆
    • 四元数的点乘
  • 旋转
  • 四元数的插值
    • SLERP
      • 四元数的差
      • 四元数的指数运算
      • 2个四元数的分数差
      • 注意事项
    • SQUARD
  • 结论
  • 下载Demo
  • 引用
Read More

矩阵的特征值、特征向量、特征矩阵、迹、特征值分解

Written on September 26, 2015

定义

设A是数域F上的n阶矩阵,如果存在数域F中的一个数\(\lambda \)与数域上F的非零向量\(\vec \alpha \),使得: \[ A\vec \alpha = \lambda \vec \alpha \] 则称\(\lambda \)为A的一个特征值(根)(eigenvalue),称\(\vec \alpha \)为A的属于特征值\(\lambda \)的特征向量(eigenvector)。

显然从上式可以看出,\( A\vec \alpha \)和\(\vec \alpha \)平行。

将上式做一下变换:

\[ A\vec \alpha = \lambda \vec \alpha \]

\[ A\vec \alpha - \lambda \vec \alpha = \vec 0 \]

\[ A\vec \alpha - \lambda E\vec \alpha = \vec 0 \]

\[ (A - \lambda E)\vec \alpha = \vec 0 \]

\[ (\lambda E - A)\vec \alpha = \vec 0 \]

称:

  • \(\lambda E - A\)为A的特征矩阵

  • 行列式\(f(\lambda ) = |\lambda E - A|\)为A的特征多项式

  • \(|\lambda E - A| = 0\)为A的特征方程

  • \((\lambda E - A)\vec x = \vec 0\)是A关于该\(\lambda \)的齐次线性方程组

A的主对角线上元素之和称为A的(trace),记为tr(A),即

\[ tr(A) = a_{11} + a_{11} + \cdots + a_{nn} \]

迹和特征值有很重要的联系:

\[ tr(A) = \lambda _{1} + \lambda _{2} + \cdots + \lambda _{n} \]

特征值还和A的行列式有关系:

\[ |A| = \lambda _{1}\lambda _{2}\cdots \lambda _{n} \]

Read More

<复习向>线性代数之正交矩阵

Written on September 26, 2015

基础知识

标准正交向量组(Orthonormal vectors)的点积(内积)性质:

\( q_{i}^{T}q_{j} = 0 \) if \( i\neq j \)

\( q_{i}^{T}q_{j} = 1 \) if \( i = j \)

其中每个正交向量的长度\(||q_{i}||=1\)。

标准正交向量组成的矩阵是:

Read More

<复习向>线性代数之投影矩阵

Written on September 26, 2015

投影矩阵是what?

先给出结论:投影矩阵P(projection),可以把一个向量b,投影到一个“空间”上,投影点称为p,从p到b的向量称为e,e = b - p,e的含义是误差向量(error)。

再举例子帮助读者理解:

上述的“空间”为一维时

一个向量b,投影到一个一维的空间,显然,这个空间是一条直线,设直线为单位向量a,那么这个投影其实就是找到这个直线上离b最近的点p,误差向量e就是b到p的距离。因为p在a上,所以有:

p = ax(p和a都是向量,x是一个值)【式子1】

然后,因为p是b在a上的投影,那么意味着,a与e成90度角,当2个向量互相垂直时,他们的点积(或 内积、 dot product)等于0,于是有:

Read More

More Effective C++ 笔记

Written on September 6, 2015

基础议题(basics)

条款1:仔细区别pointers和references

  • 使用引用,可以不做null判断
  • 当需要考虑“不指向任何对象”的可能性时,或是考虑“在不同时间指向不同对象”的能力时,你就应该采用pointer,前一种情况可以将pointer设为null,后一种情况可以改变pointer所指对象。
  • 当确定“总是会代表某个对象”,而且“一旦代表了该对象就不能够再改变”,那么应该选用reference。
  • 总是令operator[]返回一个reference。
Read More

<复习向>线性代数之PLU分解

Written on August 31, 2015

行列式的求解

从行列式的定义出发去求行列式,是一个简单但低效的方法。而实际上,解决数学问题的途径往往有多种。这里,我将介绍其中一种比较常见的快速解法:PLU分解

PLU的LU

要理解PLU,得先搞懂LU分解。(这里分享一个外教的讲解视频,简单好理解:https://www.youtube.com/watch?v=UlWcofkUDDU 能翻墙的同学就直接看吧。)

LU分别代表:Lower Triangular Matrix 和 Upper Triangular Matrix,即下三角矩阵和上三角矩阵。

下面手动演示下LU分解过程:

Read More

<复习向>线性代数之矩阵与行列式(2)

Written on August 29, 2015

行列式的意义

貌似一般的线性代数教科书并没有告诉读者行列式的实际意义,只是教会了读者行列式的定义和计算方法。(起码我所阅读的线性代数课本没有提及)

那么在这里我简单地介绍一下。

一阶行列式

要说行列式的意义,得先从行列式的"|"符号谈起。下面是一阶方阵的行列式:

\[ |x| = x \]

是不是想到什么?一阶方阵,其实就是一个数,且它的行列式等于这个数。且,一阶方列式的写法,恰好就是高中数学里的绝对值写法!

想一下绝对值的几何意义:指明了一个实数(这里不提虚数)距离数轴原点的大小。

Read More

<复习向>线性代数之矩阵与行列式(1)

Written on August 25, 2015

矩阵的基本性质

我对矩阵的定义:一个含有x个元素的数组(x>=1),以n个数为一段,将把这个数组按顺序分成m段,并按顺序排成m行,就构成了一个矩阵。数组分段是构成一个矩阵的充分必要条件。

这个定义是从程序实现角度考虑的。一个矩阵可以用二维数组Array[m][n]来存放,也可以用一维数组Array[m*n]来存放,在不考虑实现语言之前,我更倾向于使用一维数组。

矩阵的定义虽然不复杂,但是聪明的数学家对矩阵进行了各种研究,导致产生了非常多的概念、术语、定理、推论:

Read More

leetcode题解 problem87 Scramble String

Written on July 24, 2015

题解:

设s1,s2是两个长度都为len的字符串(把s1、s2当做字符数组理解)

设状态量res[n][i][j],(n < len, i <= n, j <= n), 元素是bool值

Read More

leetcode题解 problem213 House Robber II

Written on July 24, 2015

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题意:

"House Robber"的变种(尼玛又改需求了摔)。改动的地方是,房子分布从一条线变成了一个环,首尾相接了。依然是求最大值。

Read More

《数学之美》读后小结

Written on July 24, 2015

大学时候读过吴军博士的《浪潮之巅》,从中了解到了IT行业的近代史,形形色色的传奇人物和大事件,非常震撼,读完的同时也对作者的才华感到佩服,不仅是一名一流的计算机科学家,更是一位难得的历史研究者。

最近又拜读了吴博士的《数学之美》。入手前以为是一本和《编程之美》类似的书,无非讲讲算法、数学之类的。但等到开始读的时候才发现,这本书的特别之处,他将IT发展史和数学、算法一起介绍,却一点也不显乱,甚至是让枯燥的数学变得生动,读完的感觉就像读了一本小说。

大概记录下读书笔记吧。

Read More

leetcode题解 problem 45 Jump Game II

Written on July 20, 2015

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

题意:

Jump Game I 的升级版,问到达最后一个位置时,至少要跳跃多少步。

Read More

我是这样用jekyll搭建个人博客的

Written on July 18, 2015

好几年前就尝试用github pages服务来搭建github博客,当时也已经用了jekyll,不过由于那时候主要是在windows下工作学习(学图形学),手头也只有一台电脑,在win环境弄jekyll实在是不方便,要装ruby啊gem啊,都感觉没有linux环境顺手,最后还是转去了csdn博客。不过csdn博客在我毕业后也是荒废了。

Read More

leetcode题解 problem 134 Gas Station

Written on July 15, 2015

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

题意:

有N个加油站,连成环形,每个加油站有gas[i]的油,从第i个加油站到第i+1个加油站需要消耗cost[i]的油。现在有一辆车,它有无限大的油箱,但是是空的。求问这辆车应该从哪个加油站出发,才可以跑一遍所有的加油站,返回该加油站的序号,如果不存在这样的起点,返回-1。

Read More

leetcode题解 problem 142 Linked List Cycle II

Written on July 8, 2015

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:

Can you solve it without using extra space?

题意:

判断一个链表是否有环,有环的话返回环的起始节点,无环的话返回NULL。

Read More

leetcode题解 problem 152 Maximum Product Subarray

Written on July 6, 2015

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],

the contiguous subarray [2,3] has the largest product = 6.

题意:

求数组里最大的连续子序列的乘积。

Read More

leetcode题解 problem 221 Maximal Square

Written on July 5, 2015

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 4.

题意:

给定一个01矩阵,求矩阵里最大的1字正方形的面积

Read More

leetcode题解 problem 222 Count Complete Tree Nodes

Written on July 3, 2015

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

题意:

求一颗完全二叉树得节点的数量。

Read More

leetcode题解 problem 11 Container With Most Water

Written on June 30, 2015

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Read More

leetcode题解 problem 62 63 Unique Paths I & II

Written on June 27, 2015

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Read More

leetcode题解 problem53 Maximum Subarray

Written on June 26, 2015

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Read More

leetcode题解 problem120 Triangle

Written on June 25, 2015

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

  • [
  • ........[2],
  • .......[3,4],
  • .....[6,5,7],
  • ....[4,1,8,3]
  • ]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Read More

leetcode题解 problem198 House Robber

Written on June 24, 2015

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Read More