※ [本文转录自 neoneon 信箱] 作者: [email protected] ("爱宕有机奈米负离子猫") 标题: [心得] 蔡锡钧 - 演算法概论 时间: Sun Jul 10 09:28:52 2016 作者: shaform (回不去的旅程) 看板: NCTU-Teacher 标题: [心得] 蔡锡钧 - 演算法概论 时间: 2011/07/14 Thu 21:27:30 网志好读版： http://wp.me/pJ4X-ha ----------------------------------------------- ⊕课名⊕ 演算法概论 ▲教授▲ 蔡锡钧 ★修课年度★（请加注开课单位 如:大三通识、XX系选修、XX所） 99下 资工大二下必修 ￡教了什麽￡（课程大概内容。或是额外学会了什麽东西。） 这门课所使用的教科书是： Introduction to Algorithms, 3rd Ed, 2009, Cormen, Leiserson, Rivest and Stein MIT Press. http://mitpress.mit.edu/algorithms/ 教到的主题大约为 Growth of Functions Recurrence More on Divide and Conquer Heapsort Quicksort Sorting in linear time Median Selection Hash Tables --期中考-- Bloom Filter Dynamic Programming Greedy Algorithms Amortized Analysis B-trees Fibonacci Heaps Disjoint Set Operations Elementary Graph algorithms Minimum Spanning Tree Single Source Shortest Path All Pairs Shortest Paths Maximum flow ◆上课方式◆（投影片、团体讨论、老师教学风格） 使用投影片上课， 作业通常得在上课前交，不接受迟交。 所有的作业都会公布在网页上（在课堂公布前就贴上课程网站了） 投影片上有很多注解，有别班的同学说他自己觉得比他们班的投影片好理解， 不妨参考： http://www.cs.nctu.edu.tw/~sctsai/algo/notes/ ▼考试作业▼ 虽然老师一直强调注重实做的能力，认为修这班的学生一定要写 code， 不过觉得程式作业其实没有想像中繁杂。 (至少跟先前修吴育松老师的资料结构比起来，感觉 coding 时间少了很多) 大部分的题目可以在这里找到：http://goo.gl/9iwZI 或者点选 Inactive 应该可以找到所有的题目。 是属於 online judge 题目，现在也仍可以自行上传练习。 第一个程式作业是实做 merge sort 和 heap sort http://en.wikipedia.org/wiki/Merge_sort http://en.wikipedia.org/wiki/Heapsort 第二个是实做 Exercise 9.3-8 在 O(lg n) 时间找出两个 sorted array 的中位数 第三个作业是修改老师写到一半的程式码 实做 chained hash table (事实上只要改不到十行) http://en.wikipedia.org/wiki/Hash_table 第四个是 DP 有关的三个题目 http://www.cs.nctu.edu.tw/~sctsai/algo/hws/hw5.html 第五个是实做 Huffman codes 并且作成一个可以压缩和解压缩档案的程式 (需要 demo) 第六个是实做跟 Maximum-flow 有关的题目以及跟 A* search algorithm 有关的题目 http://en.wikipedia.org/wiki/A*_search_algorithm 大体上除了第五个作业外，都是纯粹演算法的题目，而没有很多实做的细节。 所以通常在一百行内就结束，最长也差不多两百多行。 只是有些题目到底要怎麽套用演算法可能需要深切的思考 跟那种没有复杂演算法但实做起来要花很多时间的 project 大不相同。 而手写的题目大多是证明题，助教对证明严谨度十分要求。 由於课本後面的解答大多忽略很多细节，所以直接照着写一定是会被扣分的。 （就算用老师公布的解答写在期中考上也会被扣分，笔者亲身经历） 笔者觉得写手写作业的时间比 coding 长很多。 ( 题外话， 在这堂课的训练之下，写到後来慢慢自己对严谨度的要求也愈来愈高。 像是这题 16.3-7 Generalize Huffman's algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes. 笔者为了达到十足的严谨度，足足写了 A4 纸两面半才证完。 (虽然我觉得应该不可能要写到这种地步才能拿满分，并且 数学好的人说不定可以用短一点又严谨的方法证明它吧) ) 考试方面有期中考和期末考 几乎都是考考古题，主要仍以证明为主，少部份是操作演算法 还有一两题是手写短程式 还有一个期中上机考 几乎都是考作业题 如果上机考不好，最後还有个上机补考。 ￥其他￥（是否注重出席率or严禁迟到？需要的基础？） 不点名 作业会抓抄袭， 小道消息指出，程式作业会搜寻一下网路看你是否直接下载别人的程式 可以多去实验室找助教问问题 期中考分数分布 00～09分-- 0 人 10～19分-- 1 人 20～29分-- 6 人 30～39分-- 6 人 40～49分-- 10 人 50～59分-- 11 人 60～69分-- 4 人 70～79分-- 5 人 80～89分-- 2 人 90~ 99分-- 1 人 ￠最後想说的话￠ 演算法是资工最核心的学科之一，没事可以多读读 Introduction to Algorithms。 如果对 online judge 形式的作业不熟悉可以参考：基础程式设计 http://wp.me/p1t0PL-c 学校的网站上有很多题目可供练习，未来应该会有很多课都采用此一介面来交作业及考试。 想看一下演算法的介绍可参考：演算法笔记 http://www.csie.ntnu.edu.tw/~u91029/ ＆谁适合修这门课＆ 想学演算法的人 -- ▄▄▄▄▄▄▄ ▄▄▄▄ ▄▄▄▄▄▄ ＜telnet://bbs.cs.nctu.edu.tw＞ █▄▄▄▄█ █ ▄▄▄▄▄█ Player: shaform ▄█▄▄▄▄█ ▄▄▄█ █▄▄▄▄▄ From: linux1.cs.nctu.edu.tw ☆ 次世代ＢＳ２ ☆ 可申请个人板 150MB 相簿 http://pic.bs2.to 交大资讯人 250MB 汪 PkmX：推荐这篇文章 07/14 21:32 推 gxlkhhc：推荐这篇文章 07/14 21:39 推 PSP：推荐这篇文章 07/14 21:50 推 philo165：推荐这篇文章 07/14 21:53 推 peanut：推荐这篇文章 07/14 22:22 推 crazyleaf：推荐这篇文章 07/14 22:34 推 b6683421：推荐这篇文章 07/15 00:30 推 dseser：推荐这篇文章 07/15 00:49 推 nathan：推荐这篇文章 07/15 01:52 推 always112358：推荐这篇文章 07/15 09:10 推 snz：推荐这篇文章 07/15 10:29 推 jk4837：推荐这篇文章 07/15 11:01 推 brightben：推荐这篇文章 07/15 15:51 推 lornwind：推荐这篇文章 01/05 08:57 作者从 linux1.cs.nctu.edu.tw 修改文章於 2013/01/01 Tue 14:20:28

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: neoneon (106.105.175.48), 07/12/2016 00:50:18