Doraemonzzz

这里回顾下第二门课的期末考试。 课程地址：https://www.coursera.org/specializations/algorithms 选择题 1考虑边长非负的有向图$G=(V,E)$ 和两个不同的顶点$s,t$。让$P$表示$G$中$s$到$t$的最短的路径。如果我们在图中的每条边的长度上加$10$，那么： 如果$P$只有一条边， $P$绝对是$s-t$最短路径 $P$可能会也可能不会保持最短$s-t$最短路径（取决于图） $P$绝对是$s-t$最短路径 $P$绝对不是$s-t$最短路径 因为每条边都增加$10$，所以总长度为原长度加上边的数量乘以$10$，不难看出前两项正确 选择题 2DFS的运行时间是多少，作为$n$和$m$的函数，如果是输入图$G=(V,E)$ ，图由邻接矩阵表示$n=|V|,m=|E|$? $\theta(n+m)$ $\theta(n^2 \log m)$ $\theta(n^2)$ $\theta(n*m)$ 每次要扫描和某个点相连的节点，判断是否有边存在，时间复杂度为$\theta(n^2)$，第三项正确 选择题 3对于有$n ...

这一部分将带来Course3 week1的习题解析。 选择题选择题 1我们作为输入给出了一组$n$请求（例如，使用礼堂），对于每个请求$i$有已知的开始时间$s_i$和完成时间$t_i$。假设所有开始和结束时间都是不同的。如果两个请求在时间上重叠，则会发生冲突 ——如果其中一个请求在另一个请求的开始和结束时间之间开始。我们的目标是选择不包含冲突的给定请求的最大子集。（例如，给定三个请求的时间区间为$[0，3]$， $[2，5]$，和$[4，7]$，我们想要返回第一个和第三个请求。）我们的目标是使用以下形式为此问题设计一个贪心算法：在每次迭代时，我们选择一个新请求$i$，将其加入到目前为止的解决方案，并在未来删除所有与之冲突的请求。 以下哪种贪婪规则可以保证始终能够计算出最佳解决方案？ 在每次迭代中，选择与剩余请求冲突最少的剩余请求（重复时任意选取）。 在每次迭代时，使用最早的开始时间选择剩余的请求。 在每次迭代中，选择需要最少时间的剩余请求（具有最小$t_i-s_i$的剩余请求）（重复时任意选取）。 在每次迭代时，选择最早完成时间的剩余请求。 答案为最后一项，每次选择完 ...

这一部分继续介绍了正则外测度的概念。 继续上次的内容，给出如下推论： Collary 1 给定一个测度空间(\Omega,\sum,\mu)，\\利用\text{method 1}从准测度\tau构建的外测度\mu^* 是在\Omega上满足\mu^*(A)=\mu(A)的唯一的\sum-正则测度,A\in \sum\\ 注意\sum\subset {\sum}^{\mu^*}证明： 因为$\sum$是$\sigma$代数($\sum_{\sigma\delta}= \sum$)，所以由Proposition 2，$\mu^*$是$\sum-正则$，结论第一部分证毕。 接下来证明唯一性： 令$\nu$是$\Omega$上一个$\sum-正则$测度，使得$\nu(A)=\mu(A)$对于$A\in\sum$。 现在任取$B\subset \Omega$，存在$\sum$中$A_1$和$A_2$，使得$B\subset A_1,B\subset A_2$，并且 \mu^*(A_1)= \mu^*(B),\nu(A_2)= \nu(B)取$A= A_1\bigcap A_2\in \su ...

这一部分介绍了正则外测度的概念。 回顾之前的记号表示： \Omega：全集\\ g：包含\varnothing的\Omega的子集类 \\ \tau：g上的准测度\\ \tau^*：利用\text{method 1}从准测度\tau构建的外测度接下来介绍正则（外）测度 正则（外）测度 假设\mu是\Omega上（外）测度，\mu被称为\Omega上正则（外）测度，\\ 如果对于任意B\subset \Omega，存在A \in {\sum}^{\mu}（\mu可测集），使得\\ B\subset A，并且\mu(A) = \mu(B)例 1$\lambda$是$\mathbb R$上正则外测度，$\lambda$是上一讲介绍的$\mathbb R$上勒贝格外测度，因为根据定义，存在开集序列$\{A_n\}$（由下确界的定义），使得$B\subset \bigcap A_n$，且$\mu(B) = \mu(\bigcap A_n)$ Theorem 3 如果A_1 \subset A_2 \subset ...\subset A_n \subset A_{n+1} \subset ...

这一周的内容主要介绍了贪心算法 Course 3 Week 1贪心算法的思路是总是选择“最优”的选择，“最优”可以人为定义，来看两个例子。 A Scheduling Application问题的背景是我们有一些共享的资源（例如处理器）以及很多工作去做，每个工作有权重$w_j$以及长度$l_j$，定义任务$j$的完成时间$C_j = \sum_{i\le j} l_i$，我们的目标是最小化$\sum_{j=1}^n w_j C_j$ 关于$C_j$来看一个Quiz Quiz 1$3$个工作，$l_1=1,l_2 =2 ,l_3=3$，按如下方式安排 $C_1, C_2,C_3$分别为多少？ 利用定义即可，$C_1= 1,C_2= 3, C_3=6$ 继续回到问题本身，考虑特殊情形：如果两个工作长度一样，那么权重大的显然要优先安排；如果两个工作权重一样，那么长度小的要优先安排。现在的问题是如果长度权重都不一样则如何处理，我们有如下贪心算法： 按照\frac {w_j}{l_j}从大到小排序，使得\\ \frac {w_1}{l_1} > \frac {w_2}{l_2}...>\fr ...

这两周主要介绍了线性规划以及整数规划。 课程地址： https://www.edx.org/course/the-analytics-edge 这两周的内容主要在Excel中操作，以后可能用的比较少，这里略过。 最后对整个课程进行总结，这门课程算是edx上的明星课程，确实也讲的通俗易懂，主要介绍了以R为主的工具来解决预测分类等问题，学习完后，可以运用R中的包解决基本的问题。当初想学这门课一是看介绍中有一个期中比赛，想通过这个比赛来熟悉R，有空的话也用Python完成这个比赛，比较可惜的是这次开课并没有比赛；第二个原因就是因为这个MIT以及edx上评价颇高的课程，想领略一番。

这一周主要介绍数据可视化。 课程地址： [https://www.edx.org/course/the-analytics-edge] setwd("E:\\The Analytics Edge\\Unit 7 Visualization") 读取数据 WHO = read.csv("WHO.csv") str(WHO) 'data.frame': 194 obs. of 13 variables: $ Country : Factor w/ 194 levels "Afghanistan",..: 1 2 3 4 5 6 7 8 9 10 ... $ Region : Factor w/ 6 levels "Africa","Americas",..: 3 4 1 4 1 2 2 4 6 4 ... $ Population ...

这一部分继续介绍外测度。 回顾上次内容： Theorem 2 令\mu是全集\Omega上的测度(外测度)，那么\Omega上全体\mu可测的子集构成的子集族{\Sigma}^{\mu}为\sigma代数, \mu在{\Sigma}^{\mu}上\sigma可加\\ i.e. \mu是{\Sigma}^{\mu}上的测度Remark因为每个零集都可测，所以 (\Omega,{\Sigma}^{\mu},\mu)是完备的测度空间继续回顾上次结论 记\lambda为\mathbb R上勒贝格(外)测度，那么每个有限开区间是\lambda可测的定理2可以推出，$\mathbb R$上开集可测(因为开集为开区间的可列并)，这也可以推出闭集可测，从而所有的Borel集合可测。 接下来介绍如何从准测度构造(外)测度 Constructing a measure from a premeasure 令\Omega为全集，g为包含\varnothing的\Omega的子集类，\\ \tau:g\to [0,\infty]，并且\tau(\varnothing) =0注意$\tau$为之前定义的准 ...

这一部分继续介绍外测度。 回顾外测度的定义： 映射$\mu:2^{\Omega} \to [0,\infty]$被称为外测度如果满足如下三个条件： \begin{aligned} (i)&\mu(\varnothing) = 0 \\ (ii)&\mu(A) \le \mu(B)，如果A\subset B \subset \Omega \\ (iii)&\mu(\bigcup_{n=1}^{\infty} A_n) \le \sum_{n=1}^{\infty} \mu(A_n) 对于\{A_n\} \subset 2^\Omega \end{aligned}回顾$\mu​$可测的概念： 给定\Omega上外测度\mu，定义\Omega的子集A为\mu可测，如果 \\ \mu(B) = \mu(B\bigcap A) +\mu(B\bigcap A^C)，对于任意B\subset \Omega \\ 或者\mu(C\bigcup D) = \mu(C) + \mu(D)对于任意C\subset A以及D\subset A^C注意到由外测度的定义可得： \mu(B) = \m ...

这一部分介绍了外测度的基本概念。 Unit 4 Outer measure考虑全集$\Omega$，定义在$\Omega$的全体子集上的非负集合函数$\mu$被称为外测度，如果满足如下三个条件： \begin{aligned} (i)&\mu(\varnothing) = 0 \\ (ii)&\mu(A) \le \mu(B)，如果A\subset B \subset \Omega \\ (iii)&\mu \left(\bigcup_{n=1}^{\infty} A_n \right) \le \sum_{n=1}^{\infty} \mu(A_n) 对于\{A_n\} \subset 2^\Omega \end{aligned}$\Omega$上外测度常常被被简称为测度（注意之前的测度是定义在$\sigma$代数上的，所以这样称呼不会引起歧义） 给定$\Omega$上外测度$\mu$，定义$\Omega$的子集$A$为$\mu​$可测，如果 \mu(B) = \mu(A\bigcap B) +\mu(B\bigcap A^C)，对于任意B\subset \Omega \\ ...

这一部分介绍了巴拿赫空间的概念。 给定一个度量$(M,\rho)$，按如下方式定义序列： M中一个序列是从\mathbb N到M的映射，通常用\{x_n\}_{n\in \mathbb N}表示，简写为\{x_n\}， 其中x_n是自然数n\in \mathbb N的象接着给出极限的定义： 令\{x_n\}是M中序列，那么\lim_{n\to \infty} x_n = x \Leftrightarrow \lim_{n\to \infty} \rho(x_n, x) =0\\ 其中x被称为\{x_n\}的极限仿照数学分析中定义柯西序列： 一个序列\{x_n\}被称为柯西序列，如果对于任意的\epsilon >0，存在N\in \mathbb N，\\ 使得对于任意的n,m\ge N， \rho(x_n,x_m)

这一部分将带来Course2 week4的习题解析。 选择题选择题 1以下哪一项不是您期望精心设计的hash函数具有的属性？ hash函数应该“展开”大多数（即“非病理”）数据集（跨散列表的桶/槽） hash函数应该易于计算（恒定时间或接近它） hash函数应该易于存储（恒定空间或接近它） hash函数应该“展开”每个数据集（跨散列表的桶/槽） 第四个选项的意思是希望hash函数将元素映射到每个bucket中，错误。 选择题 2假设我们使用哈希函数$H$将$n$个不同的键映射到长度为$m$的数组$T$中。假设简单的uniform hashing——也就是说，每个键独立且均匀地映射到随机桶中，那么映射到第一个桶的预期键数是多少？更准确地说，该集合元素数量$\{k:h(k)=1\}$ $m/(2n)$ $1/n$ $n/m$ $1/m$ $n/(2m)$ $m/n$ 每个元素映射到第一个桶的概率为$\frac 1 m$，因为有$n$个元素，所以答案为$n/m$，第三项正确 选择题 3假设我们使用哈希函数$H$将$n$个不同的键映射到长度为$m$的数组$T$中。如果$h(x ...