1
holyzhou 2016-04-21 16:58:01 +08:00
看不懂 但我能说 ,作业正文的第一句话亮了嘛? 老外治学这么严谨啊
|
2
hzm0318hzm 2016-04-21 17:13:28 +08:00
看着头晕, mark 下看有没大神给你解决
|
3
seki 2016-04-21 17:31:27 +08:00
这是个大作业,但是已经是循序渐进地分好了每一步
你是从哪一步开始没有思路? |
4
stackpop 2016-04-21 17:36:44 +08:00
|
5
stackpop 2016-04-21 17:37:08 +08:00
|
6
NightVermouth OP @seki 我说一下我对题目的理解吧,首先我高数还没学到傅立叶变换,这可能对我理解题目会造成偏差,题中的对 y 的分解我就无法理解。我理解的内容是,为了缩减时间复杂度,需要对矩阵 S 进行降维,分成 N/2 维的 S ,以及 N/2 维的 T , T 可以再降维成 N/4 的 T ,及 N/4 的 U , U 还可以进行降维(这一步怎么做到我没理解)。降维过程递归进行,最后当 N/2^l 为基数时停止,然后把底层的小矩阵算出来,大矩阵根据小矩阵得出(动态规划的思想?),然后计算对应的 Xi 。
以上是我的理解。然后题目第一题我就一头雾水。。。 |
7
GtDzx 2016-04-21 18:11:25 +08:00 1
大概就是让你算 x=SN*y ,其中 x,y 是(N-1)维的向量, SN 是 N-1xN-1 的矩阵。暴力去乘就是 O(N^2)的。
让后他介绍了一种递归分治的 O(NlogN)算法。大概思路就是把 x 分成两组, x2,x4,x6,x8... 这一组可以直接用 S_{N/2}*a , x1,x3,x5,x7...这一组可以用 T_{N/2}*s 求出来(其中 T,a,s 都在文中有定义)。 这样我们就把 x=SN*y 分解为 2 个一半规模的小问题 x=S_{N/2}*y 和 x=T_{N/2}*y 。比较郁闷的是 x=TN*y 是一个新问题。幸好这个问题也有递归分治的解法。 x=TN*y 可以被分解为 x=T_{N/2}*y 和 x=U_{N/2}*y 两个规模一般的小问题。但是这里又引入了一个新问题 x=UN*y 。不过这个问题也是能分解的,可以分解为 x=T_{N/2}*y 和 x=T_{N/2}*y 两个子问题。到这里终于没有再引入新问题了。于是整个问题可以在 O(NlogN)解决。 |
8
seki 2016-04-21 20:49:30 +08:00 1
@NightVermouth
我就看了一下前言还有第一题, DST 就是将一个向量分解为多个带 sin 值的向量序列,你可以把它类比于泰勒展开…… 第一题是给定一个数字 n ,然后输出一列双精度向量,分别是各个 sin 值,用在后边的计算当中当作 sin 值表,避免重复求同一个 sin 值 剩下的我觉得楼上说得挺好的了,就是需要补一点矩阵的知识,比如向量与矩阵的乘法是如何计算的等等,这个可以看线性代数 |
9
seki 2016-04-21 21:12:22 +08:00
第 2 题是让你实现选出来的子向量与各个矩阵的乘法,矩阵的各个元素的值在 summary 中给出了。看样子在这里需要写分治递归,这两题中的 N =1 × 2^m
第 3 题是考虑 N = 3 × 2^m 的情况 第 4 题是算法分析 第 5 题和前面的作业有关,放弃了…… 第 6 题是扩展到 N=5 × 2^m 的情况 |
10
cpygui 2016-04-21 21:31:14 +08:00
这题占 40%的期末总成绩!这题要是挂了是不是就挂科了?
她不去 office hour 吗? |
11
NightVermouth OP @cpygui 我也不知道啊, 40%你是从哪里看到的?
|
12
cpygui 2016-04-21 22:00:10 +08:00
|
13
aprikyblue 2016-04-21 22:12:10 +08:00 via Android
一脸懵逼
|
15
NightVermouth OP @cpygui 我也不清楚,这题目只是交给我做一下,至于来龙去脉我并不知道。貌似是某个人拜托我老师解决,然后老师没空,就推到了我这里(这些是我猜的)。。。
|
16
rubytek 2016-04-22 00:24:05 +08:00
这是数字信号处理的课后题吧。。算法?
|
17
cpygui 2016-04-22 01:02:36 +08:00 via Android
@NightVermouth 伦敦帝国理工算是世界顶级名校啊,当初这人是怎么混进去的(๑><๑)
真要是做不来,问 TA 或者教授。不过按你说的,这特么还是层层转包给你的。。。。你和这人没瓜葛,帮别人做题有意思么? 要是有好事者把这个帖子举报给讲师就好玩了,哈哈哈 |
18
Andiry 2016-04-22 01:12:03 +08:00
在这里问算是作弊吧?
|
19
NightVermouth OP @cpygui 我做题是出于兴趣,不过听你这么一说,我还是推掉比较好。但这题拿来钻研,锻炼思维对我来说还是蛮不错的。
|
20
NightVermouth OP @Andiry 从我的角度讲,算请教或者探讨更为合适吧,毕竟这不是我的作业,谈不上作弊抄袭。
|
21
NightVermouth OP @rubytek 有算法的内容,比如需要用到分治策略
|
22
cpygui 2016-04-22 01:29:01 +08:00 via Android
@NightVermouth (ಡωಡ)hiahiahia 那我能不能出于兴趣把这人举报?
|
23
NightVermouth OP @cpygui 出于兴趣,你可以。。。 xD
|
26
paulagent 2016-04-22 05:15:37 +08:00 via Android
如果被人举报这孩子就完了,澳洲不是刚刚有个被人举报了,因为 wuwei 那事
|
27
cpygui 2016-04-22 06:13:14 +08:00 via Android
@shiji 嘻嘻嘻,你肯定不知道西方有些学校不收学费的吧,国际生也不收。不过要是能花钱进 mit ,我还是愿意的
|
28
tempdban 2016-04-22 06:38:51 +08:00 via Android
兄弟我时间有限只看了一眼,没猜错的话…骑士应该就是 FFT 吧
|
29
Tink 2016-04-22 08:22:33 +08:00 via iPhone
我的高数跟没学一样
|
30
NightVermouth OP @tempdban 维基百科上说是该算法类似于 FFT,然而我并不知道 FFT 是什么。。。我才大一,高数课还没到这部份内容。
|
31
proudzhu 2016-04-22 09:40:46 +08:00 via Android
@NightVermouth 然而 FFT 是 DSP 的内容,不是高数
|
32
NightVermouth OP @proudzhu 软件专业的表示不明觉厉。只是知道高数中有个傅立叶, DSP 又有跟傅立叶转换与关系,就想当然地联系在一起了 xD
|
33
tempdban 2016-04-22 18:57:07 +08:00 via Android
@NightVermouth 简单介绍一下,傅里叶变换可以把一个和时间有关的函数,转换成和频率有关的函数,但是要求函数是连续的,套用连续函数傅里叶变换的定义,还有个离散傅里叶变换(dft),可以对离散函数进行傅里叶变换,但是按照一般的算法太慢了,数学家们又研究出来可以进行快速傅里叶变换的方法,叫 fft
|
34
NightVermouth OP @tempdban soga 谢谢
|