V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
NightVermouth
V2EX  ›  程序员

算法题(不是我的作业),老师没时间,然后希望我帮她做一下,然而我看了两节课依旧一头雾水,只能麻烦各位 v 友懂的给点提示,只要思路就行。

  •  
  •   NightVermouth · 2016-04-21 16:46:58 +08:00 · 5169 次点击
    这是一个创建于 3128 天前的主题,其中的信息可能已经有所发展或是发生改变。
    34 条回复    2016-04-22 20:17:27 +08:00
    holyzhou
        1
    holyzhou  
       2016-04-21 16:58:01 +08:00
    看不懂 但我能说 ,作业正文的第一句话亮了嘛? 老外治学这么严谨啊
    hzm0318hzm
        2
    hzm0318hzm  
       2016-04-21 17:13:28 +08:00
    看着头晕, mark 下看有没大神给你解决
    seki
        3
    seki  
       2016-04-21 17:31:27 +08:00
    这是个大作业,但是已经是循序渐进地分好了每一步
    你是从哪一步开始没有思路?
    NightVermouth
        6
    NightVermouth  
    OP
       2016-04-21 18:10:53 +08:00
    @seki 我说一下我对题目的理解吧,首先我高数还没学到傅立叶变换,这可能对我理解题目会造成偏差,题中的对 y 的分解我就无法理解。我理解的内容是,为了缩减时间复杂度,需要对矩阵 S 进行降维,分成 N/2 维的 S ,以及 N/2 维的 T , T 可以再降维成 N/4 的 T ,及 N/4 的 U , U 还可以进行降维(这一步怎么做到我没理解)。降维过程递归进行,最后当 N/2^l 为基数时停止,然后把底层的小矩阵算出来,大矩阵根据小矩阵得出(动态规划的思想?),然后计算对应的 Xi 。
    以上是我的理解。然后题目第一题我就一头雾水。。。
    GtDzx
        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)解决。
    seki
        8
    seki  
       2016-04-21 20:49:30 +08:00   ❤️ 1
    @NightVermouth
    我就看了一下前言还有第一题, DST 就是将一个向量分解为多个带 sin 值的向量序列,你可以把它类比于泰勒展开……
    第一题是给定一个数字 n ,然后输出一列双精度向量,分别是各个 sin 值,用在后边的计算当中当作 sin 值表,避免重复求同一个 sin 值
    剩下的我觉得楼上说得挺好的了,就是需要补一点矩阵的知识,比如向量与矩阵的乘法是如何计算的等等,这个可以看线性代数
    seki
        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 的情况
    cpygui
        10
    cpygui  
       2016-04-21 21:31:14 +08:00
    这题占 40%的期末总成绩!这题要是挂了是不是就挂科了?
    她不去 office hour 吗?
    NightVermouth
        11
    NightVermouth  
    OP
       2016-04-21 21:49:41 +08:00
    @cpygui 我也不知道啊, 40%你是从哪里看到的?
    cpygui
        12
    cpygui  
       2016-04-21 22:00:10 +08:00
    @NightVermouth http://wwwf.imperial.ac.uk/~drmii/M3SC_2016/
    好像还有一场 seminar 讨论之后,她从来不参加讨论的吗?
    aprikyblue
        13
    aprikyblue  
       2016-04-21 22:12:10 +08:00 via Android
    一脸懵逼
    msg7086
        14
    msg7086  
       2016-04-21 22:15:50 +08:00
    @holyzhou 抄袭作业但不署名是重罪。
    NightVermouth
        15
    NightVermouth  
    OP
       2016-04-21 23:35:43 +08:00
    @cpygui 我也不清楚,这题目只是交给我做一下,至于来龙去脉我并不知道。貌似是某个人拜托我老师解决,然后老师没空,就推到了我这里(这些是我猜的)。。。
    rubytek
        16
    rubytek  
       2016-04-22 00:24:05 +08:00
    这是数字信号处理的课后题吧。。算法?
    cpygui
        17
    cpygui  
       2016-04-22 01:02:36 +08:00 via Android
    @NightVermouth 伦敦帝国理工算是世界顶级名校啊,当初这人是怎么混进去的(๑>؂<๑)

    真要是做不来,问 TA 或者教授。不过按你说的,这特么还是层层转包给你的。。。。你和这人没瓜葛,帮别人做题有意思么?

    要是有好事者把这个帖子举报给讲师就好玩了,哈哈哈
    Andiry
        18
    Andiry  
       2016-04-22 01:12:03 +08:00
    在这里问算是作弊吧?
    NightVermouth
        19
    NightVermouth  
    OP
       2016-04-22 01:18:47 +08:00 via iPhone
    @cpygui 我做题是出于兴趣,不过听你这么一说,我还是推掉比较好。但这题拿来钻研,锻炼思维对我来说还是蛮不错的。
    NightVermouth
        20
    NightVermouth  
    OP
       2016-04-22 01:20:20 +08:00 via iPhone
    @Andiry 从我的角度讲,算请教或者探讨更为合适吧,毕竟这不是我的作业,谈不上作弊抄袭。
    NightVermouth
        21
    NightVermouth  
    OP
       2016-04-22 01:23:02 +08:00 via iPhone
    @rubytek 有算法的内容,比如需要用到分治策略
    cpygui
        22
    cpygui  
       2016-04-22 01:29:01 +08:00 via Android
    @NightVermouth (ಡωಡ)hiahiahia 那我能不能出于兴趣把这人举报?
    NightVermouth
        23
    NightVermouth  
    OP
       2016-04-22 01:44:08 +08:00 via iPhone
    @cpygui 出于兴趣,你可以。。。 xD
    shiji
        24
    shiji  
       2016-04-22 03:52:45 +08:00
    @cpygui 现在西方的学校都是赚钱为主了,进去的难度一年比一年低,想混进去真的没那么难。
    ShiHou
        25
    ShiHou  
       2016-04-22 04:53:48 +08:00
    @cpygui 兴趣使然的举报者 ? (ಡωಡ)hiahiahia
    paulagent
        26
    paulagent  
       2016-04-22 05:15:37 +08:00 via Android
    如果被人举报这孩子就完了,澳洲不是刚刚有个被人举报了,因为 wuwei 那事
    cpygui
        27
    cpygui  
       2016-04-22 06:13:14 +08:00 via Android
    @shiji 嘻嘻嘻,你肯定不知道西方有些学校不收学费的吧,国际生也不收。不过要是能花钱进 mit ,我还是愿意的
    tempdban
        28
    tempdban  
       2016-04-22 06:38:51 +08:00 via Android
    兄弟我时间有限只看了一眼,没猜错的话…骑士应该就是 FFT 吧
    Tink
        29
    Tink  
       2016-04-22 08:22:33 +08:00 via iPhone
    我的高数跟没学一样
    NightVermouth
        30
    NightVermouth  
    OP
       2016-04-22 08:52:17 +08:00 via iPhone
    @tempdban 维基百科上说是该算法类似于 FFT,然而我并不知道 FFT 是什么。。。我才大一,高数课还没到这部份内容。
    proudzhu
        31
    proudzhu  
       2016-04-22 09:40:46 +08:00 via Android
    @NightVermouth 然而 FFT 是 DSP 的内容,不是高数
    NightVermouth
        32
    NightVermouth  
    OP
       2016-04-22 10:18:17 +08:00
    @proudzhu 软件专业的表示不明觉厉。只是知道高数中有个傅立叶, DSP 又有跟傅立叶转换与关系,就想当然地联系在一起了 xD
    tempdban
        33
    tempdban  
       2016-04-22 18:57:07 +08:00 via Android
    @NightVermouth 简单介绍一下,傅里叶变换可以把一个和时间有关的函数,转换成和频率有关的函数,但是要求函数是连续的,套用连续函数傅里叶变换的定义,还有个离散傅里叶变换(dft),可以对离散函数进行傅里叶变换,但是按照一般的算法太慢了,数学家们又研究出来可以进行快速傅里叶变换的方法,叫 fft
    NightVermouth
        34
    NightVermouth  
    OP
       2016-04-22 20:17:27 +08:00
    @tempdban soga 谢谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5573 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 06:35 · PVG 14:35 · LAX 22:35 · JFK 01:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.