0627Mini-homework1.ipynb.ipynb



 
 Problem 1. Fibonacci Sequence
在课程里，讨论过如果去找到第N个Fibonacci number。在这里，我们来试着求一下它的Closed-form解。 
Fibonacci数列为 1,1,2,3,5,8,13,21,.... 也就第一个数为1，第二个数为1，以此类推...
我们用f(n)来数列里的第n个数，比如n=3时 f(3)=2。
下面，来证明一下fibonacci数列的closed-form, 如下：
$f(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
 // your proof is here ....
可参考
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibformproof.html
具体证明如下：
首先根据fibonacci数列的定义，我们可以得到如下的公式：
$\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}=\begin{pmatrix}
1&1\\1&0 \end{pmatrix}^n \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}$
 $|\lambda E-A|=0$ $\lambda_1=\frac{1-\sqrt{5}}{2},\lambda_2=\frac{1+\sqrt{5}}{2}$
进一步得到特征向量为
$\alpha_1=\begin{pmatrix} 1\\ \frac{1+\sqrt{5}}{2} \end{pmatrix},
 \alpha_2=\begin{pmatrix} 1\\ \frac{-1+\sqrt{5}}{2} \end{pmatrix}$
 从而得到
$P=\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix},
P^{-1}=\begin{pmatrix} \frac{1-\sqrt{5}}{2} & 1 \\ \frac{1+\sqrt{5}}{2} & -1 \end{pmatrix} $
 $(PAP^{-1})^n=PA(P^{-1}P)A...(P^{-1}P)AP^{-1}=PA^nP^{-1}$  $f(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$ 
 证明如下:
$\begin{pmatrix} f_{n+1} \\ f_n \end{pmatrix}=\begin{pmatrix}
1&1\\1&0 \end{pmatrix}^n \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}$
 $|\lambda E-A|=0$ $\lambda_1=\frac{1-\sqrt{5}}{2},\lambda_2=\frac{1+\sqrt{5}}{2}$
进一步得到特征向量为
$\alpha_1=\begin{pmatrix} 1\\ \frac{1+\sqrt{5}}{2} \end{pmatrix},
 \alpha_2=\begin{pmatrix} 1\\ \frac{-1+\sqrt{5}}{2} \end{pmatrix}$
 从而得到
$P=\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix},
P^{-1}=\begin{pmatrix} \frac{1-\sqrt{5}}{2} & 1 \\ \frac{1+\sqrt{5}}{2} & -1 \end{pmatrix} $
 $(PAP^{-1})^n=PA(P^{-1}P)A...(P^{-1}P)AP^{-1}=PA^nP^{-1}$  $f(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$ 
 Problem2. Algorithmic Complexity
对于下面的复杂度，从小大排一下顺序：
$O(N),  O(N^2),  O(2^N),  O(N\log N),  O(N!),  O(1),  O(\log N),  O(3^N),  O(N^2\log N), O(N^{2.1})$
 // your answer....
$O(1) --> O(\log N)-->O(N)-->O(N\log N)-->O(N^2)-->O(N^2logN)-->O(N^{2.1})-->O(2^N)-->O(3^N)-->O(N!)$
 Problem 3  Dynamic Programming Problem
 Edit Distance (编辑距离）
编辑距离用来计算两个字符串之间的最短距离，这里涉及到三个不通过的操作，add, delete和replace. 每一个操作我们假定需要1各单位的cost. 
例子： "apple", "appl" 之间的编辑距离为1 （需要1个删除的操作）
"machine", "macaide" dist = 2
"mach", "aaach"  dist=2

    In [14]:
  
 # 基于动态规划的解法
def levenshtein_dp(s, t):
    m, n = len(s), len(t)
    table = [[0] * (n) for _ in range(m)]

    for i in range(n):
        if s[0] == t[i]:
            table[0][i] = i - 0
        elif i != 0:
            table[0][i] = table[0][i - 1] + 1
        else:
            table[0][i] = 1

    for i in range(m):
        if s[i] == t[0]:
            table[i][0] = i - 0
        elif i != 0:
            table[i][0] = table[i - 1][0] + 1
        else:
            table[i][0] = 1

    print(table)
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1], int(s[i] != t[j]) + table[i - 1][j - 1])

    print(table)
    return table[-1][-1]
 

    In [17]:
  
 str1 = input("输入字符串1：")
str2 = input("输入字符串2：")
print(levenshtein_dp(str1, str2))
 
    Out [17]:
  
 输入字符串1：appl
输入字符串2：apple
[[0, 1, 2, 3, 4], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [3, 0, 0, 0, 0]]
[[0, 1, 2, 3, 4], [1, 0, 1, 2, 3], [2, 1, 0, 1, 2], [3, 2, 1, 0, 1]]
1
 Problem 4 非技术问题
本题目的目的是想再深入了解背景，之后课程的内容也会根据感兴趣的点来做适当会调整。 
Q1: 之前或者现在，做过哪些AI项目/NLP项目？可以适当说一下采用的解决方案，如果目前还没有想出合适的解决方案，也可以说明一下大致的想法。 请列举几个点。
Q2: 未来想往哪个行业发展？ 或者想做哪方面的项目？ 请列举几个点。
Q3: 参加训练营，最想获得的是什么？可以列举几个点。