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

看不懂《算法》第四版中的命题和证明怎么办?

  •  
  •   hanxiaomeng · 2017-05-29 20:50:28 +08:00 via Android · 6882 次点击
    这是一个创建于 2720 天前的主题,其中的信息可能已经有所发展或是发生改变。
    大家好,我是一名运维工程师,想通过好好学习成为一名程序员。

    我看大家都推荐《算法》第四版,于是买了这本书,但是我根本看不懂这里面的命题和证明,请问我是不是要补充一下数学知识?该从哪里开始呢?

    我数学就是初二水平吧,后来就没好好学习过……

    另外,我在知乎也提问了,不过可能那个描述写的有点幽默,所以没人答……不过在这里的问题比较正常。
    17 条回复    2017-06-02 20:10:54 +08:00
    wannafly
        1
    wannafly  
       2017-05-29 22:22:19 +08:00
    先离散, 概率, 微积分这些看看差不多了吧
    swcsend
        2
    swcsend  
       2017-05-29 22:59:01 +08:00
    能看懂文字描述就可以了 可以先把数学部分忽略掉
    liuyu00
        3
    liuyu00  
       2017-05-30 08:54:11 +08:00   ❤️ 2
    离散数学,图论,概率论,Google 和 MIT 共同写了本 Mathematics for Computer Science,你可以看一下。
    dreamapple
        4
    dreamapple  
       2017-05-30 09:18:24 +08:00 via Android
    数学补一下证明的部分就行了吧,逆否什么的,有一本书是程序员的数学,不知道适不适合
    joxjo
        5
    joxjo  
       2017-05-30 10:16:18 +08:00   ❤️ 2
    《算法》第四版的证明比较简略,有些细节没说清楚。它比较强调算法实现,算法正确性证明和复杂度分析这方面比较简略,这部分还是需要看《算法导论》。

    数学不好,喜欢直觉化的解释,可以参考看下 :
    1. Sanjoy Dasgupta,Christos Papadimitriou,Umesh Vazirani 的《算法概论》。
    2. Jon Kleinberg 和 Eva Tardos 的《算法设计》。

    如果喜欢形式化的解释,推荐先看 @liuyu00 推荐的 Mathematics for Computer Science, 然后再看《算法导论》。
    《算法导论》其实非常适合初学者,但是在 MIT 上算法课前有门先修课 6.042 需要先学,Mathematics for Computer Science 是它的课本,关于证明,数论,图论和概率论等。
    《算法导论》的证明比较形式化,偏数学,但是解释的非常清晰。看懂它的数学证明,至少需要把 Mathematics for Computer Science 的第一部分看完,打下数学证明这部分的基础。看完后再看《算法导论》的证明,应该没有问题。
    hanxiaomeng
        6
    hanxiaomeng  
    OP
       2017-05-30 13:56:24 +08:00 via Android   ❤️ 1
    感谢楼上各位的回答,我打算看一下 Mathematics for Computer Science,不知道看这个初中数学基础是否能够看懂?@liuyu00 @joxjo
    f1r1ng
        7
    f1r1ng  
       2017-05-30 15:41:28 +08:00
    我觉得这本书的起点挺高的,适合的那种数学比较好刚学编程的初学者,不适合真正的初学者
    hanxiaomeng
        8
    hanxiaomeng  
    OP
       2017-05-30 16:30:03 +08:00 via Android
    @f1r1ng 我扫了几眼,由于是英文没太仔细看,不过貌似里面提到的不太懂,这个是不是更适合高中生数学比较好的去读?
    joxjo
        9
    joxjo  
       2017-05-30 20:15:23 +08:00
    @hanxiaomeng 我觉得初中数学基础应该可以看,因为我感觉它在知识上没有过多的依赖高中数学。Mathematics for Computer Science 的例子比较精简,刚开始看可能感觉有点难。可以参考看 Rosen 的 Discrete Mathematics and Its Applications,这本例子讲得比较多,但又有点琐碎,可以把它看作 MCS 的啰嗦版,两本对照的看,MCS 看概念,DM 看例子。

    其实有人带着学,可能会比较好。如果没时间看 MCS 的话,又想学算法,可以看下 Stanford 的 Tim Roughgarden 在 lagunita.stanford.edu 上开的 Algorithms: Design and Analysis 课,教的深入浅出,非常好。你可以试下,看能不能看明白他的算法讲解。如果 Tim 的课也觉得有点难,那还是需要先看 MCS,打好数学基础。
    这门课在 Coursera 上有开,可是现在的版本做习题需要交费,lagunita 上的是免费的:)
    《算法》的作者也在 Coursera 上开了课,也可以看下,但这门课比较强调算法的运用,想看算法证明还是 Tim 的这门课比较好。
    joxjo
        10
    joxjo  
       2017-05-30 20:26:32 +08:00
    在 MIT OCW 上 6.042 这门课有视频可以看,可以边看视频边学 MCS。还有 6.006(2011,6.046(2015),这两门是 MIT 的算法课,一门是低阶课,一门是高阶课,都有视频,就是讲得没 Tim 那么深入浅出。6.046 ( 2005 )这个版本的课讲得还不错,CLRS 的 L 有讲一部分课。
    joxjo
        11
    joxjo  
       2017-05-30 20:32:43 +08:00
    所有课都有英文字幕,课本也要看英文版的,这些的中文翻译版比原文还难看懂。
    zhengxiaowai
        12
    zhengxiaowai  
       2017-05-31 10:53:34 +08:00
    别听前面回答瞎说,先去看什么数学,至少对你目前的情况是没什么用的。

    《算法》这本书,偏重于实现,我认为的学习方法应该是:
    1. 先熟悉 JAVA,不用太深入看得懂就行,如果有 OO 语言基础,配合第一章的内容没压力。
    2. 看原理,实现过程、和结论。证明可以看,看不懂就拉倒。
    3. 所有的代码必须最少执行过。最好的是看完一遍,自己写,不懂得参考书中代码,自己 DEBUG 过。
    4. 可以配合 Coursera 上的课,是配套的。英文字幕慢点看,问题也不是很大。
    5. 有精力可以刷课后题,当然难度不小。

    所以总结来看你只需要会:
    1. 中文或者英文
    2. 写过程序,最好熟悉 OO 语言
    3. (重点)坚持
    hanxiaomeng
        13
    hanxiaomeng  
    OP
       2017-05-31 11:47:44 +08:00 via Android
    @zhengxiaowai 嗯,把算法的基本原理搞懂去面试工作就没问题了吧?

    我不是想成为算法大牛,就是想当一个靠谱点的程序员。

    因为我看到书里总是提到命题证明,里面有~f(n),还有 nlgn 啥的,所以不知道是不是不看这个就看不懂算法。
    hanxiaomeng
        14
    hanxiaomeng  
    OP
       2017-05-31 11:52:14 +08:00 via Android
    @joxjo 这些书层次都比较高了吧,我还是留着工作了,如果想往更高层面走再看吧。

    现在就先 MCS 和算法搭配着看试试吧,先以换工作为目标。
    hanxiaomeng
        15
    hanxiaomeng  
    OP
       2017-05-31 12:24:29 +08:00 via Android
    @dreamapple 这本书我看了一下,好像挺适合配合算法看的,不管了,先拿起一本看吧,问来问去越问越晕。
    liuyu00
        16
    liuyu00  
       2017-06-02 18:23:54 +08:00
    我觉得要是以找工作为目的,又没有接触过基本算法, coursera 上北大有门算法基础,还是挺好的,完全不会有看不懂证明的问题,因为根本就没讲。一边看一边刷刷 oj 上的题,提升还是很快的。
    hanxiaomeng
        17
    hanxiaomeng  
    OP
       2017-06-02 20:10:54 +08:00
    @liuyu00 好的,我看一下。现在在看《程序员的数学》,不知道看完能不能看懂《算法 4 》,看完再说吧。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2962 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 02:48 · PVG 10:48 · LAX 18:48 · JFK 21:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.