※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 ID）
（是／否／其他條件）：是
哪一學年度修課：
ψ 授課教師 (若為多人合授請寫開課教師，以方便收錄)
呂育道
δ 課程大概內容
涵蓋了基本的Complexity理論
期中考範圍
從最基本的single tape Turing Maching怎麼運作
演進到multi-tape TM，引入non-deterministic的概念
這裡因為一些存在性問題，所以介紹了cardinality
從這之中帶出來Halting problem
再來是基礎的complexity class，還有一些TIME和SPACE的關係
最後是complete及reduce的定義及方法
期末考範圍
一開始切入NP和coNP，用PRIME問題的方式
介紹一下機率的材料(Monte Carlo TM)
因為後面會用到，所以引入一些數論的東西
(Fermat, Chinese remainder thm, quadratic residue)
帶到一些蠻基本的密碼學，看看如何加密、解密
尾端帶到一個怎麼讀也讀不懂的interaction system, zero-knowledge
另一個大主題是approximation，這裡只強調理論性
學期末的兩次上課帶出兩個新興議題
一個是對於P!=NP的嘗試證明
另一個是引出#P的complexity class
(上面是憑印象打的，順序或內容有錯請指正)
Ω 私心推薦指數(以五分計) ★★★★★
★★★★
η 上課用書(影印講義或是指定教科書)
C. H. Papadimitriou, Computational Complexity
μ 上課方式(投影片、團體討論、老師教學風格)
首先，上課的媒介是非常厚實的投影片 (實是見仁見智，厚應該是客觀的厚)
這是大部分的人無法接受的一點
( 怎麼念了幾個小時，還沒念的投影片還是一樣高啊 )
( 第一次有一門課，投影片的數量要用公分計算的 )
但是我覺得不算非常誇張的多
比起三學期制的一些學校，這樣的進度算是適中
當然用想混過這門必修的想法渡過這門課會十分痛苦
畢竟這不是讀幾成就有幾分的科目 ( 但這兩年開始是了 )
因為國際學生的關係，這門課是用英文授課
老師一開始上課會講的字彙數量不少，所以要很專心聽才聽得懂
但是後期老師用的字就愈來愈少了，比較ok
就上課內容而言，整體的大架構老師不會特別交待
所以自己要抓好老師現在在教什麼，才會比較知道老師想講什麼
老師很愛穿插一些細節的大定理，所以會讓同學不知所措
( 最著名的應該是一開始證明在single type時，PALINDROM is in o(n^2) )
再來就是，老師會不斷的更新投影片
他鼓勵上課能夠有討論，所以只要有一些投影片上沒有的東西被討論出來
就會在課後時更新投影片，並且備註
"Thanks to a lively discussion on ??/??/??."
"Contributed by R9XXXXXXX on ??/??/??"
之類的流傳下去
但是也因為這樣，一份投影片除了愈來愈厚以外，還會有很多支微末節
這當然有好有壞，好處是如果一個地方不懂，可以有多一些參照
壞處是你要抓住一個大架構的話就更困難了
除了上面寫的那些
和直接讀課本來比，投影片已經做的十分完善了
因為有把課本的精華都提取出來
( 課本上其實有比較多例子，所以概念不懂的話應當回去看課本 )
( 不過課本上在講重要的概念時，用字和投影片一樣精簡 )
但在數學推導上面，其實鮮少把intuition講出來
( 當然要把數學的intuition講出來是一件十分困難的事情，
尤其是在投影片上面，這種東西通常都是口頭講的 )
( 我上課沒有很用心，不知道老師上課時有沒有講，應該沒有吧 XD )
我上數學課比較喜歡用黑板
在這堂課中其實有大半部分是在講數學
用投影片有一個壞處是，你就只有一個頁面的大小可以塞字了
而且要更改其實並不容易，這對於數學學習是一大障礙
此外，數學應該是要某種程度的「算給你看」
( 否則中小學就都用投影片上數學就好啦，一頁課本一張silde )
投影片直接show過去會引導學生某種程度上的不求甚解
當然投影片有太多好處，這裡就不細講
我只是覺得可以有某種程度上的黑板課 ( 當然在兩百人教室是不可能做到的 )
因為是一門大概需要兩百人修課的大型課程
只能在資工103上課，這裡有個缺點是冷氣非常冷，得蓋個外套
加上資工系人人一台筆電，搭配上老師溫和成熟的英文
很容易就睡著或是專注於自己眼前的筆電上
最後，老師其實很忙，不僅是系主任
而且還兼任了財工和資工兩邊的教授，要帶兩邊的研究生和專題生
能有這樣的教學熱誠真的很不容易了
我是很珍惜這樣的學習機會，雖然如果老師用中文講課我會比較聽得懂 XD
σ 評分方式(給分甜嗎？是紮實分？)
以往大概兩百人修課，幾乎不當人
有聽說期中乘期末不是零分就不會當
今年分數我還不知道，所以甜不甜不甚清楚
ρ 考題型式、作業方式
考試就是期中、期末考
這兩年一掃以前的只考那種想不出來的考古題無限段只好背起來的期中期末考
( 就是說以前都考蠻不容易的題目，不過都是考古題 )
全部由強大的助教自己命題再和老師討論
今年回歸基本，考的都是照理講「基本概念」有讀懂就一定會寫的題目
( 這又要牽扯到另一個問題，就是投影片太多了，大多人都讀不完 )
題目數量非常少，時間都是三小時，根本不用擔心時間會用完的問題
( 這是我喜歡的型式，可是題目太少了有點無趣 )
老實說我覺得今年考的有點過於容易了，沒什麼挑戰性
我比較喜歡的方式是hil式考法，再加一些由簡入深的基礎題目
這樣就兼備了鑑別力，和讓有讀書但沒讀熟的學生不至於拿不到分數
不過對於多數追求完美，近乎苛求的考生可能就不是這麼喜歡了
作業五次，每次都是兩題
也是助教出的，都蠻有趣 ( 當然大多不是太容易 )
ω 其它(是否注重出席率？如果為外系選修，需先有什麼基礎較好嗎？老師個性？
加簽習慣？嚴禁遲到等…)
出席完全不管(我最喜歡這種課了)
需要一些離散和機率的基礎
(離散部分：代數、組合學完全不需要，只要知道一些圖論的基礎就可以
機率部分：印象中只有Chernoff bound有用到random variable的概念
其他甚至連Marcov inequility也納入教本中了)
Ψ 總結
這太困難了，我不會寫 囧rz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.162.144
※ 編輯: abcde1234 來自: 61.217.162.144 (01/25 10:17)
※ 編輯: abcde1234 來自: 59.112.197.109 (02/07 01:28)