Doraemonzzz

这一部分是第二单元的作业详解，作业可以在下面的网站下载。 http://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/105S109/9 Problem 1(a)分别验证3个性质即可 (i) 因为f(\Omega) = \overline {\mathbb R}，所以 f^{-1}(\overline {\mathbb R}) = \Omega，从而\overline {\mathbb R} \in f_{\sharp} \sum(ii) 如果A \in f_{\sharp} \sum，那么 f^{-1} (A)\in \sum，即存在B\in \sum ，使得f^{-1} (A) = B\\ 因此 f^{-1} (A^C) = (f^{-1} (A) )^C= B^C \in \sum，从而A^C\in f_{\sharp} \sum(iii) 任取 f_{\sharp} \sum中序列\{A_n\}_{n=1}^{\infty},所以存在\sum中序列\{B_n\}_{n=1}^{\infty}，使得f^{-1} (A_n) = B_n\\ ...

这一部分是第一单元的作业详解，作业可以在下面的网站下载。 http://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/105S109/9 Problem 1先证明一个引理： 引理 1 A为不可数集,C_\alpha >0 (\alpha \in A) \\ 那么\sum_{\alpha \in A} C_\alpha = \infty证明： 利用反证法，假设$\sum_{\alpha \in A} C_\alpha <\infty$，令 E_n =\{x|x>\frac 1 n, x\in A\}如果$\sum_{\alpha \in A} C_\alpha = \infty$，那么由调和级数的性质可知 对于任意n>0, A\bigcap E_n的元素个数最多有有限个这是因为，如果存在$n_0$使得$A\bigcap E_{n_0}$的元素个数有无限个，则$A\bigcap E_{n},n\ge n_0$的元素个数都有无限个，从而 C_\alpha >\sum_{n=n_0}^{\infty}\frac{1}{n} =\infty这与我们的假设矛盾 ...

这一周的内容主要介绍了Hash表以及bloom-filters。 Course 2 Week 4Hash TableHash表是一种存放键值对的数据结构，时间复杂度几乎为$O(1)$，支持的操作如下： High-Level IdeaHash表的原理是构造一个映射$h$，将元素映射到$h(x) \in \{0,1,2,…,n-1\}$，然后访问$A[h(x)]$，其中$A$是一个数组，$A$中每个元素可以是链表或者元素本身，这两者的区别如下： 如果$A$中每个元素是链表，那么一个格子中可以装很多元素。 hash表的运行时间为： Resolving Collisions如果存在$x,y$使得$h(x)=h(y)$，那么称其为冲突，这是我们不想看到的，解决方法如下： 如果$A$中元素是链表，那么可以在$A[h(x)]$尾部直接添加元素（这种方法称为Chaining)；否则可以根据某个规则让$x$找到下一个空位置，例如linear probing (这种方法称为Open addressing) The Load of a Hash Table为了后续讨论，这里定义一个变量： \a ...

这一部分将带来Course2 week3的习题解析。 选择题选择题 1假设您使用排好序的数组（例如，从最大到最小）实现优先级队列的功能。 Insert和Extract-Min的最差运行时间分别是多少？（假设您有足够大的数组来容纳您所面临的插入。） $\Theta(1)$和$\Theta(\log n)$ $\Theta(n)$和$\Theta(1)$ $\Theta(n)$和$\Theta( n)$ $\Theta(1)$和$\Theta(n)$ Insert需要移动后续的元素，最坏时间复杂度为$\Theta(n)$，Extract-Min直接弹出最后一个元素即可，最坏时间复杂度为$\Theta(1)$ 选择题 2假设您使用未排序的数组实现优先级队列的功能。 Insert和Extract-Min的最差运行时间分别是多少？（假设您有足够大的数组来容纳您所面临的插入。） $\Theta(1)$和$\Theta(\log n)$ $\Theta(n)$和$\Theta(1)$ $\Theta(n)$和$\Theta( n)$ $\Theta(1)$和$\Theta(n)$ 因为没有 ...

这一周的内容主要介绍了一些常用的数据结构。 Course 2 Week 3HeapHeap是一种特殊的数据结构，其特点为父节点的值或者都不小于子节点，或者都不大于子节点，所以根节点或者为最小值（此时称为最小堆），或者根节点为最大值（此时称为最大堆），来看下堆的具体特点： 以最小堆为例，堆支持如下操作： 下面介绍堆的实现方法（以最小堆为例）： Implementation我们这里使用数组表示Heap，注意此时用完全二叉树表示堆，特点为第$i$个元素的父节点为第$[i/2]$个元素，子节点为$2i,2i+1$（注意下标从1开始），来看个图示： 有了这种表示之后，下面介绍Insert以及Extract-Min Insert将元素插入队尾（记下标为$i$），如果该元素小于其父节点元素（第$[i/2]$个元素)，那么插入成功；否则交换其父节点和该元素的位置，重复此操作直至满足条件或者无法交换为止。可以看到，因为堆是用完全二叉树表示，所以树的高度为$O(\log n)$，所以最多交换$O(\log n)$次。 下面从一个图示中看下具体过程： Extract-Min删除位置为$1$的元素， ...

这一周主要介绍聚类，分别介绍了Hierarchical以及K-means的使用。 课程地址： https://www.edx.org/course/the-analytics-edge setwd("E:\\The Analytics Edge\\Unit 6 Clustering") 这次的数据不是csv格式，要使用read.table函数来读取。 movies = read.table("movieLens.txt", header=FALSE, sep="|",quote="\"") str(movies) 'data.frame': 1682 obs. of 24 variables: $ V1 : int 1 2 3 4 5 6 7 8 9 10 ... $ V2 : Factor w/ 1664 levels "'Til There Was You (1997)",..: 1524 6 ...

这一部分将带来Course2 week2的习题解析。 选择题选择题1考虑边长非负且不同，源点为$s$的有向图。固定目标顶点$t$，并假设该图包含至少一个$s-t$路径。 以下哪项陈述属实？ $s-t$的最短路径必须排除最长边$G$ $s-t$的最短路径必须有最短边$G$ $s-t$的最短路径可能有$n-1$条边，$n$是顶点总数 $s-t$的最短路径没有重复顶点 最短路径和单个边长无关，前两个选项错误。考虑一条直线上$n$个点，从起点到终点有$n-1$条边，第三项正确。假设最短路径有重复顶点，所以包含环，把这个环去掉依旧是$s-t$路径，由边长非负可得，长度更短，第四项正确。 选择题2考虑边长不同，源点为$s$的有向图，目标顶点$t$的有向图，在什么条件下$s-t$最短路径唯一。 当所有边长都是不同的正整数时，并且图$G$不包含有向循环 当所有边长都是2的不同幂 没有其他选项是正确的 当所有边长都是不同的正整数时 选项1,4可以考虑一个四边形，两条边长为1,4另外两条为2,3，那么最短路径不唯一。当边长为2的不同幂时，可以把最短路径理解为一个二进制数，由二进制数表示的 ...

这一部分介绍了度量空间的基本概念。 我们之前考虑的都是测度空间$(\Omega,\Sigma, \mu)$，接下来我们要考虑定义在其上的度量空间$L^p(\Omega,\Sigma, \mu),1\le p \le \infty$，我们先介绍度量空间的预备知识。 度量的定义令$M$是一个非空集合，考虑$\rho :M\times M \to \mathbb R$，如果$\rho$满足以下三个性质，$\rho$被称为度量： \begin{aligned} (i) & \rho(x,y) = \rho(y,x) 对所有(x,y) \in M\times M \\ (ii) & \rho(x,y) \ge 0 , \rho(x,y) =0 \Leftrightarrow x = y \\ (iii)& \rho(x,y) \le \rho(x,z) +\rho(z,y) (三角不等式) \end{aligned}来看几个具体例子 例1 M = \mathbb R^n = \{x =(x_1,...,x_n): x_j \in \mathbb R ,j =1,...,n\}\\ 定义\ ...

这一讲介绍了Fatou引理以及勒贝格控制收敛定理。 首先给定一个测度空间$(\Omega,\Sigma, \mu)$，其次回顾上次介绍的单调收敛定理： Theorem 2 单调收敛定理 \{f_n\}可测函数序列， f_n \ge 0 (a.e.), f_n\uparrow(a.e.)\\ 那么\int_{\Omega} \lim_{n\to \infty} f_n d\mu = \lim_{n\to \infty} \int_{\Omega}f_n d\mu这里简单说明下这个定理，假设当$x\in N_n$时，$f_n<0$，其中$\mu(N_n)=0$，所以 \mu(\bigcup_{n=1}^{\infty} N_n) \le \sum_{n=1}^{\infty} \mu(N_n) = 0这说明$\{f_n\}$除去一个零测集上都大于等于$0$。此外，由于$f_n\uparrow(a.e.)$，说明存在一个$N$，使得当$x\in \Omega \setminus N$时，$f_n \uparrow $，那么 \mu((\bigcup_{n=1}^{\infty ...

这一周主要介绍了要介绍了文本分析。 课程地址： https://www.edx.org/course/the-analytics-edge 首先读取数据。 setwd("E:\\The Analytics Edge\\Unit 5 Text Analytics") emails = read.csv("energy_bids.csv", stringsAsFactors=FALSE) emails$email = iconv(emails$email, "WINDOWS-1252", "UTF-8") str(emails) 'data.frame': 855 obs. of 2 variables: $ email : chr "North America's integrated electricity market requires cooperation on environmental policies Comm ...

这周主要介绍SLT的内容。 课程地址： coursera：C++程序设计 https://www.coursera.org/learn/cpp-chengxu-sheji 中国大学MOOC：程序设计与算法（三）C++面向对象程序设计 程序设计与算法（三）C++面向对象程序设计 string类基本使用 string 类是模板类：typedef basic_string char string; 使用string类要包含头文件string string对象的初始化： string s1(“Hello”); string month = “March”; string s2(8,’x’); 错误的初始化方法： string error1 = ‘c’; // 错 string error2(‘u’); // 错 string error3 = 22; // 错 string error4(8); // 错 可以将字符赋值给string对象 string s; s = ‘n’; 来看一个具体例子： #include <iostream> #include < ...

这一周的内容主要介绍了Dijkstra算法。 Course 2 Week 1Dijkstra’s AlgorithmDijkstra算法是解决单源最短路径问题，来看下算法的输入输出： Input：有向图$G=(V, E). (m=|E|, n=|V| ) $，每条边有非负边长$l_e$，一个源点$s$ Output: 对于每个节点$v$，计算$L(v)$，其中$L(v)$为$s$到$v$的最短路径长度 这里最重要的假设为$l_e \ge 0$。 来看下算法描述： 解释下算法，这里将节点分为$X$和$V-X$，前者为已经计算完结果的节点，后者为还未计算的节点，$A[s]$表示到$s$的最短距离，$B[s]$记录了最短路径。 Why It Works这部分证明为什么Dijkstra算法计算出了正确的结果，即如下事实成立： L(v) =A[v],\forall v\in V利用数学归纳法证明。 证明： 对于出发点$s$，由于边长非负，所以显然有$L(s) = A[s] = 0$，基本情形得证。 假设对于任意$v\in X$（$X$为之前描述的已经计算的节点），$L(v) = ...