※ [本文轉錄自 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